Since the docstring of for is very concise, I cannot fathom one thing—as the title suggests.
for i = iter
# body
end
I have learned that i is local and different among passes.
For example, iter = 1:3, then we have 3 passes: i = 1, i = 2, i = 3. The three i here are all local, but they are mutually different objects despite they are all named i from the programmer’s view. This is good.
I think the iter part is decided once before the first pass starts. For example, this code has clear intention:
for i = shuffle(1:7)
println(i)
end
Clearly we want to shuffle 1:7 once and print the result—we certainly do not intend to shuffle 1:7every timei is updated (we do not intend to shuffle seven times)
Therefore I think the spirit of the for is:
do not re-evaluate iter every time i is updated to the next pass
Now the question is: am I sane to write this code?
function steal!(v)
for _ = 1:5
sleep(1)
popfirst!(v)
popfirst!(v)
popfirst!(v)
end
end;
function test()
v = collect(1:30)
Threads.@spawn steal!(v)
for i = v
println(i)
sleep(0.6)
end
end;
Threads.nthreads() # 7
test() # does this make some sense?
Is this defined behavior? Will it be useful in practice?
It’s undefined since none of the built in data structures (like Vector, Dict, Set) are thread-safe. You’ll need to synchronize the use of the v with a lock. This can’t be done with the iterator in a for loop, so you would need to write an equivalent while loop, and take out a lock whenever you access v. Then it would be defined behaviour, though it might be non-deterministic, depending on the timing.
for loops are used in a lot of performance critical code, a deepcopy of the iterator would incur overhead, both allocations and some cpu-use. And it might be that you actually want to update the elements of the iterator.
buffers = [fill(0, 100) for _ in 1:10]
for b in buffers
b .+= 1
end
all(vcat(buffers...) .== 1) # true
vs
buffers = [fill(0, 100) for _ in 1:10]
for b in deepcopy(buffers)
b .+= 1
end
all(vcat(buffers...) .== 1) # false
The docstring is somewhat unfortunate. for loops are not a fundamental language builtin, they are syntactic sugar for while loops and the iterate function:
julia> function foo(fun, iterable)
for item in iter
fun(item)
end
nothing
end
julia> function bar(fun, iterable)
next = iterate(iterable)
while next !== nothing
item, state = next
fun(item)
next = iterate(iterable, state)
end
nothing
end
For all remaining questions, you simply need to look up the implementations of the respective iterate functions.
As written, no: You have a data race.
The following works, though:
Most of the time, one should not modify iterables while an iteration is ongoing; and if one needs to do this, one should add lots of blinking warning signs / comments and unit tests.
Oh, I’ve learned that, thanks.
I though locks are needed only if 2 threads write to the same object. (I’ve made a pull request to modify JuMP’s doc about this point).
I also thought of this point☺️, really. I should use while in this case.
FWIW, it is theoretically perfectly fine code to modify an iterable while an iteration is ongoing.
However:
Such code is nontrivial to reason about
Most users of iterables don’t think about this possibility, hence there may be bugs
Most authors of iterate functions don’t think about this possibility either!
If the author of the iterate function didn’t think about it, and it happens to work as you wanted… doesn’t mean it will still work in the next point release.
So only do this with iterables that are explicitly designed for this purpose.
Oh me oh my, we just read uninitialized memory. If bar was in the business of writing to its argument, then we would have a nice heap memory corruption, and plausibly a security bug.
This is bad but doesn’t require iteration to expose.
julia> v = collect(1:7);
julia> w = view(v, :);
julia> popfirst!(v);
julia> w[7]
128975025987520
Addendum: It’s documented in the view docstring:
The behavior is undefined if the shape of the parent array is changed after view is called because there is no bound check for the parent array; e.g., it may cause a segmentation fault.
You can do that, but I think this is something where you need specific unit tests in order to ensure that Base doesn’t pull out the rug under you – it certainly doesn’t look very supported to me.
Just look at
function view(A::AbstractArray, I::Vararg{Any,M}) where {M}
@inline
J = map(i->unalias(A,i), to_indices(A, I))
@boundscheck checkbounds(A, J...)
J′ = rm_singleton_indices(ntuple(Returns(true), Val(ndims(A))), J...)
unsafe_view(_maybe_reshape_parent(A, index_ndims(J′...)), J′...)
end
If Base is today happy to change the semantics of your program by maybe pulling a copy of the indices if it thinks you cannot possibly have wanted aliasing… then it will be happy to make further similar changes to your program’s behavior.
Looking in old code, I see that after some deliberation I didn’t dare to modify the indices directly. I recreated the view with the modified indices, with neglible performance penalty.
Reading concurrently is generally ok, but if there’s one writer all access must use the lock. More advanced locking systems have separate locks for read and write, so many readers can hold the read lock, but only one writer can hold the write lock (together with no readers). I think there used to be a package which implemented such locks, but I can’t find it. It’s a pity it’s not in Base or an stdlib.
I somewhat doubt (hence temporarily reopen this topic).
I don’t think it’s necessary for a reader to use a @lock decoration. Because each a reader has a separate function, therefore a respective local name. So for a reader, it either reads the “older” information or reads the “younger” information. It has no chance to read an incomplete information.
Consider this
function reader(j, v)
for _ = 1:50
sleep(1)
println("reader $j reads: $v")
end
end
function writer_1_do!(v)
for _ = 1:50
sleep(1)
@lock mylock circshift!(v, 1)
end
end
function writer_2_do!(v)
for _ = 1:50
sleep(2)
@lock mylock circshift!(v, 2)
end
end
function coordinator()
v = collect(1:9)
for j = 1:10 Threads.@spawn reader(j, v) end
Threads.@spawn writer_1_do!(v)
Threads.@spawn writer_2_do!(v)
end
const mylock = ReentrantLock()
coordinator()
A data race happens when two threads access the same thingy, at least one of which is a writer.
So 10 readers can access concurrently no locks required. If you want 10 readers and one writer, then each reader needs to take some kind of lock, in order to not collide with the writer.
This is of course a world of suck, because now the readers conflict with each other. There are reader-writer locks that reduce the lock conflict on the software level (i.e. multiple readers can take the lock at the same time).
However, this will still have pretty bad scaling if your critical sections are short, because on the hardware level, the readers still need exclusive access to the cache line containing the num_readers counter.
For short critical sections, the appropriate datastructure are seqlocks, i.e. readers simply retry if a writer modified the data.
Theoretically, julia should play well with seqlocks, because data races are not immediate “bats out of nose” UB like C/C++, but instead pretty tame undef. Alas. I am not aware of a julia implementation of seqlocks.
However, this is something that probably should be in Base, in order to get the real experts to review it (like: Which exact fences are required where? Are there subtle differences between llvm and jvm memory models? What plays well with union tags, GC write barriers, shadow stack? What are appropriate patterns? Does GC need to be disabled during seqlock reader crit sections because we might write undef to the shadow stack? If so, then we need a new API that doesn’t produce the cache-line contention we wanted to avoid in the first place, cf julia/src/gc-common.c at f0ece4ad9ad07d766f9d3461771571f2f5a97a3c · JuliaLang/julia · GitHub).
This depends on what kind of update is being done. The circshift! looks like this:
function circshift!(a::AbstractVector, shift::Integer)
n = length(a)
n == 0 && return a
shift = mod(shift, n)
shift == 0 && return a
l = lastindex(a)
reverse!(a, firstindex(a), l-shift)
reverse!(a, l-shift+1, lastindex(a))
reverse!(a)
return a
end
If your reader happens to read between between two of the reverse! calls, it will read incomplete data.
Because in that case I have two writer, which is indeed a synthetic case.
In practice I will only use one writer. And I’ll not use in place update, but use the label v to associate some updated object. Just like the snap here
function masterˈs_loop(snap, timestamp, inbox)
v, i = fill(0, J), 0
while true
if isempty(inbox) # no event happens
yield()
continue
end # ∀ j, we have j ∈ buffer ∪ inbox ∪ js_at_large
up = false
while true
lens = @lock inbox_lock pop!(inbox)
local j, (cut_off_by_j, ø), con = lens(snap)
ismissing(con) && error("Subproblem $j terminates with $ø")
if cut_off_by_j
up = true
JuMP.add_constraint(model, con)
println("▶ ub = $(snap.ub) | t = $(snap.t), j = $j | vio = $ø")
end
v[i+=1] = j # write the buffer
isempty(inbox) && break
if up && i == LOGIS # LOGICAL PROCESSORS
break # early break to update master model, i.e. snap
end
end
if up
timestamp, snap = shot!(timestamp)
for j = view(v, 1:i) Threads.@spawn subproblemˈs_duty(j, snap, inbox) end
i = 0
elseif i == J
println("▶▶▶ No more progress can be made, quit!")
return
end
end
end
I don’t think this is necessarily true (depending on how you define difference). For example, if you want to produce collect(1:k) for all k <= n for a given n, you could use
struct S
n::Int
end
Base.iterate(s::S) = iterate(s, Int[])
function Base.iterate(s::S, state)
length(state) >= s.n && return nothing
push!(state, length(state) + 1)
return state, state
end
Base.length(s::S) = s.n
Then indeed
julia> s = S(3)
S(3)
julia> for i in s
println(i)
end
[1]
[1, 2]
[1, 2, 3]
Of course, this is a silly example, but I can imagine that in certain situations you might want to mutate the returned item/state in-place for performance reasons. In this case this should definitely be clearly documented. To be fully safe