# Nondeterministic results for subset sum using @threads

**URL:** <https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808>\
**Category:** General Usage\
**Tags:** multithreading\
**Created:** [May 5, 2020, 1:30pm UTC](https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808 "2020-05-05T13:30:01Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![eaubanel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eaubanel/32/13327_2.png) [@eaubanel](https://discourse.julialang.org/u/eaubanel)\
**Post date:** [May 5, 2020, 1:30pm UTC](https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808/1 "2020-05-05T13:30:01Z")

</div>

I’ve encountered nondeterministic results for a naive subset sum implementation using `@threads`. This algorithm fills the dynamic programming table column by column from left to right. There’s one column for each integer in set `s`, and the length of each column is given by the value of the target sum S, plus one. Computation of elements of each column are independent, since they depend only on values of the previous column to the left. Therefore there should be no race conditions when I parallelize the inner loop:

```julia
import Base.Threads.@threads
function subsetSumThreads(s, S)
    n = length(s)
    F = falses(S+1,n)
    for i in 1:n
        F[1,i] = true
    end
    s[1]≤ S && (F[s[1]+1,1] = true)
    @inbounds for j in 2:n
        @threads for i in 2:S+1
            F[i,j] = F[i,j-1]
            i > s[j] && (F[i,j] = F[i,j] || F[i-s[j],j-1])
        end
    end
    return F
end

```

However, when I test this function, it often doesn’t work. For instance, for the set `s = [6, 5, 3, 1, 8, 10]` and the target sum `S=43`, I sometimes get wrong values in the `F` matrix:

```julia
1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 1 1 1 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 0 0 1 1 1 1 
0 0 0 1 1 1 0 0 0 0 0 0 
0 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 1 1 1 0 0 0 1 1 1 
0 0 1 1 1 1 0 0 1 1 1 1 
0 0 1 1 1 1 0 0 1 0 1 1 
0 0 0 1 1 1 0 0 0 1 1 1 
0 1 1 1 1 1 0 1 1 1 1 1 
0 0 0 1 1 1 0 0 0 1 1 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 1 1 1 1 0 0 1 1 1 1 
0 0 0 1 1 1 0 0 0 0 1 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 0 0 1 1 0 0 0 0 0 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 1 1 0 0 0 0 1 1 
0 0 0 0 1 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 

```

On the left is the `F` matrix from the sequential computation (code above with `@threads` removed), and on the right is the `F` matrix from the multithreaded computation with two threads.

> **versioninfo()**
>
> Julia Version 1.4.0  
> Commit b8e9a9ecc6 (2020-03-21 16:36 UTC)  
> Platform Info:  
> OS: macOS (x86\_64-apple-darwin18.6.0)  
> CPU: Intel(R) Core™ i5-7360U CPU @ 2.30GHz  
> WORD\_SIZE: 64  
> LIBM: libopenlibm  
> LLVM: libLLVM-8.0.1 (ORCJIT, skylake)  
> Environment:  
> JULIA\_EDITOR = atom -a  
> JULIA\_NUM\_THREADS = 2

I’m assuming sequential consistency for data-race-free programs, so I can’t make sense of this behaviour.

---

<div class="post-metadata">

**Author:** ![fredrikekre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikekre/32/1688_2.png) [@fredrikekre](https://discourse.julialang.org/u/fredrikekre)\
**Post date:** [May 5, 2020, 1:31pm UTC](https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808/2 "2020-05-05T13:31:52Z")

</div>

`BitArray`s are not threadsafe (e.g. `falses(...)`).

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [May 5, 2020, 1:33pm UTC](https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808/3 "2020-05-05T13:33:51Z")

</div>

As it happens, this was recently merged: [document some of the thread safety issues with BitArray by KristofferC · Pull Request #33754 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/33754/files).

---

<div class="post-metadata">

**Author:** ![eaubanel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eaubanel/32/13327_2.png) [@eaubanel](https://discourse.julialang.org/u/eaubanel)\
**Post date:** [May 5, 2020, 1:37pm UTC](https://discourse.julialang.org/t/nondeterministic-results-for-subset-sum-using-threads/38808/4 "2020-05-05T13:37:40Z")

</div>

Of couse! Thanks!