Race condition caused by variable scope getting lifted from a multithreaded context

[jrevels]

I ran into this very strange bug while exploring the new multithreading stuff. The smallest reproducible case I can come up with:

using Base.Threads

function right(v)
    ws = ntuple(w->Vector{Int}(length(v)), nthreads())
    @threads for t in 1:nthreads()
        w = ws[t]
        for i in 1:length(v)
            w[i] = v[i]
        end
    end
    w2 = 1 # unused binding to an unused variable name
    return ws
end

function wrong(v)
    ws = ntuple(w->Vector{Int}(length(v)), nthreads())
    @threads for t in 1:nthreads()
        w = ws[t]
        for i in 1:length(v)
            w[i] = v[i]
        end
    end
    w = 1 # unused binding to the name of the previously used loop variable
    return ws
end

Note that the only difference between the above two functions is w2 = 1 and w = 1, and that neither variable is actually used after being assigned.

Running the above in the REPL:

julia> v = collect(1:3)

julia> right(v) # gives the correct output every time
([1,2,3],[1,2,3],[1,2,3],[1,2,3])

julia> wrong(v)
([4624170704,4658607408,4624170720],[4563189968,4574717712,4563189968],[1,2,3],[1,2,3])

julia> wrong(v)
([1,2,3],[1,2,3],[1,2,3],[4624170800,4658607472,4624170816])

julia> wrong(v)
([1,2,3],[1,2,3],[1,2,3],[1,2,3])

julia> wrong(v)
([1,4658458992,4624197552],[1,2,3],[4624197648,4624197664,4624197680],[1,2,3])

It appears that some iterations of the multithreaded loop in wrong(v) aren't always being executed, or possibly that the binding of the loop variable w to ws[t] is broken. Either way, one can induce the correct behavior by making sure the post-loop binding to 1 doesn't match the loop variable name.

I thought maybe that this was a escaping/scoping bug in _threadsfor, but I didn't see anything that jumped out at me.

julia> versioninfo()
Julia Version 0.5.0-dev+2502
Commit baf336f (2016-02-04 18:01 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin13.4.0)
  CPU: Intel(R) Core(TM) i5-4288U CPU @ 2.60GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.7.1

@mlubin

[yuyichao]

Hmm, without looking into the detail, my guess is that the assignment to w lift the scope of the variable and effectively introduces a race condition between threads (since all of them are modifying and reading the variable) Does it help if you protect the access of w with a lock?

[yuyichao]

i.e. something like

function wrong1(v)
    ws = ntuple(w->Vector{Int}(length(v)), nthreads())
    @threads for t in 1:nthreads()
        for i in 1:length(v)
            w = ws[t]
            w2 = w
            w2[i] = v[i]
        end
    end
    w = 1 # unused binding to the name of the previously used loop variable
    return ws
end

vs

function wrong2(v)
    ws = ntuple(w->Vector{Int}(length(v)), nthreads())
    lock = SpinLock()
    @threads for t in 1:nthreads()
        for i in 1:length(v)
            lock!(lock)
            w = ws[t]
            w2 = w
            unlock!(lock)
            w2[i] = v[i]
        end
    end
    w = 1 # unused binding to the name of the previously used loop variable
    return ws
end

[jrevels]

The lock fixes it, I think you're right about the scope lifting of w. Thus, another way to fix this - without introducing the lock - is by declaring w as local inside the loop. I guess this is semantically consistent with Julia's current scoping behavior, but it means that the current scoping behavior is scary in a multithreaded context.

[yuyichao]

If we want the behavior to be as close as possible to a non-threading version, we could make all assignments in a @thread local instead (no matter threading is enabled or not). Hopefully if a loop is declared as @thread it usually shouldn't be to assign to any local variable. However, in case it is actually what the user want (find a unique match in a threaded loop maybe?) I think there should be a way to do that (like python's nonlocal).

This doesn't help if the user is calling another closure that assigning to another local variable in the outer scope but I don't think we can fix that without completely break the scoping rule.

[JeffBezanson]

This is actually what the hacky localize_vars thing was introduced for --- to copy bindings so that assignments can't leak outside of a certain block. Originally for the distributed case, where you don't want binding relationships to depend on which machine the code runs on.

[kpamnany]

You do want to be able to access shared variables in an outer scope from inside a parallel loop; it's a simple and useful pattern. I don't think we can force local-only assignments.

I think the right answer is to generate a warning when a variable's scope is lifted after there has been an assignment to it. Practical?

[JeffBezanson]

What do you mean by "local-only assignments"? For example, I'm not sure what this code is meant to do:

x = 1
@threads for i = 1:n
    x = i
    f(x)
end

In this case, why is it useful to share x among the threads?

[yuyichao]

And I think this can be done with sth like,

x = Ref(0)
@threads for i in 1:n
    f(i) && x[] = 1
end

even if we "localize" all the variables in a @threads block.

[kpamnany]

By "local-only assignments", I was referring to @yuyichao's suggestion to make all assignments in an @threads block local. I don't think this is the right answer because it is useful to share outer-scope variables among threads. It doesn't seem useful to share x among the threads for the case you mention, but:

x = Atomic()
@threads for i = 1:n
    atomic_add!(x, foo(i))
end
bar(x[])

Or:

x = ConcurrentMap()
@threads for i = 1:n
    if foo(i)
        append!(x, (bar(i), baz(i))) # or something like this
    end
end
# iterate through x doing something

[yuyichao]

Both of the code you have does not have assignment in the loop. There's mutations of mutable object but no assignment so they won't be affected at all.

[kpamnany]

Given foo(x) returns true for only one element of some collection C, then:

p = false
@threads for i = 1:length(C)
    if foo(C[i])
        p = true
    end
end
if p
# do something

The principle is the same.

[yuyichao]

This pattern can be covered with Ref I mentioned above.

[kpamnany]

Sure. There are all sorts of ways to get those semantics, but are they clear semantics? My feeling is not.