# Parallelization gives wrong result

**URL:** <https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409>\
**Category:** General Usage\
**Tags:** bug, parallel, multithreading\
**Created:** [May 25, 2023, 9:14pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409 "2023-05-25T21:14:51Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [May 25, 2023, 9:14pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/1 "2023-05-25T21:14:51Z")

</div>

I have a simple function which, given a vector of floats `x`, returns a `BitVector` that has 1’s in places where the entry is nonzero. In other words, `f(x) = (x .!=0.0)`. When I parallelize it, I get incorrect results:

```julia
using Random
x = rand([1.0,2.0,3.0],10)

function f(x, prl)
    n = length(x)
    y = falses(n)
    if prl==0 for i=1:n y[i] = (x[i] !=0.0) end end
    if prl==1 Threads.@threads for i=1:n y[i] = (x[i] !=0.0) end end
    return y end

y0 = trues(length(x))
for k=1:100 if y0!=f(x,0) print("!") end end
# 
for k=1:100 if y0!=f(x,1) print("!") end end
# !!!!!!!!

```

Why does this happen? What am I doing wrong? Each thread writes in a different place in y.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 25, 2023, 9:23pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/2 "2023-05-25T21:23:03Z")

</div>

Maybe this:

```julia
help?> ?BitArray
search: BitArray

  BitArray{N} <: AbstractArray{Bool, N}

  Space-efficient N-dimensional boolean array, using just one bit for each
  boolean value.

  BitArrays pack up to 64 values into every 8 bytes, resulting in an 8x space
  efficiency over Array{Bool, N} and allowing some operations to work on 64
  values at once.

  By default, Julia returns BitArrays from broadcasting operations that
  generate boolean elements (including dotted-comparisons like .==) as well
  as from the functions trues and falses.

  │ Note
  │
  │ Due to its packed storage format, concurrent access to the
  │ elements of a BitArray where at least one of them is a write is
  │ not thread-safe.

```

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [May 25, 2023, 9:31pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/3 "2023-05-25T21:31:41Z")

</div>

Ouch, was not aware of that, thank you. So in this case, what does actually happen? One thread, when editing y[i], also locks some nearby y[j]?

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [May 25, 2023, 10:20pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/4 "2023-05-25T22:20:29Z")

</div>

The issue is that a `BitVector` is storing multiple values per byte. More specifically, it stores 64 values per `UInt64` (8 bytes). In order to write a single entry, it reads the entire `UInt64`, sets one of the bits to the value it wants, and then writes the entire `UInt64` back to memory.

This opens up the potential for a data race. The reason this is not thread-safe is that multiple threads can read the same `UInt64`, modify it by changing a single bit, and then write it back. This process takes time. If more than one reads it before the changes can get written back, then whichever writes it last will overwrite the work of everyone else. A lock would avoid this, but also would cause significant slowdowns.

A `Vector{Bool}` uses 1 byte per entry (rather than 1/8-byte like `BitVector`) and the bytes are addressed individually (rather than in blocks of 8 via `UInt64`), so it should be safe from data races in your example. I will recommend you use that instead.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 25, 2023, 10:24pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/5 "2023-05-25T22:24:41Z")

</div>

if you want to make this faster, you have to pack the bools into Ints yourself unfortunately.

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [May 26, 2023, 11:53am UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/6 "2023-05-26T11:53:41Z")

</div>

Thank you @GunnarFarneback for the solution and @Oscar_Smith for a clear explanation.

One last thing: are there any other basic datastructures (from base) that are not thread-safe? Dict? Set?

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 26, 2023, 12:06pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/7 "2023-05-26T12:06:30Z")

</div>

I wouldn’t expect any data structures to be thread-safe apart from `Array{T, N}` and specifically task-oriented ones like `Channel`.

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [May 26, 2023, 12:23pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/8 "2023-05-26T12:23:05Z")

</div>

`DataFrame`s probably are? I presume a column of a df cannot be a `BitVector`?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 26, 2023, 12:43pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/9 "2023-05-26T12:43:39Z")

</div>

`Vector{T}` also isn’t threadsafe in the sense that you can have races on resizing.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 26, 2023, 12:56pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/10 "2023-05-26T12:56:38Z")

</div>

Right, that was much too broad. I should have constrained that to `getindex` and `setindex!` without data races for the same index.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [May 26, 2023, 1:51pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/11 "2023-05-26T13:51:23Z")

</div>

```julia
julia> df = DataFrame(x = trues(5))
5×1 DataFrame
 Row │ x
     │ Bool
─────┼──────
   1 │ true
   2 │ true
   3 │ true
   4 │ true
   5 │ true

julia> typeof(df.x)
BitVector (alias for BitArray{1})

```

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [May 26, 2023, 1:52pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/12 "2023-05-26T13:52:14Z")

</div>

Ouch. Ok, I’ll have to be careful what data structure I parallelize on. Tnx!

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 26, 2023, 1:56pm UTC](https://discourse.julialang.org/t/parallelization-gives-wrong-result/99409/13 "2023-05-26T13:56:35Z")

</div>

In general, locking data structures have mostly fallen out of favor in CS since they impose a substantial overhead of users that aren’t using multithreading, and they still they often aren’t great for performance compared to custom locking solutions.