Iterator bug?

General Usage
1

I just tested @Dan’s (?) answer on SO ( Julia - the way of kings (generator performance) - Stack Overflow )

There is function allSAWs(neigh, pathlen) which return iterator. His algorithm has problem that it return wrong “elements” which include 0… It is not what I like to present here! But when I checked it I found strange behavior which seems to be like Julia’s (0.6.1 and 0.7.0-DEV.0) bug.

If I create array with comprehension then every element include 0:

julia> a=[i for i in allSAWs(neigh, 2)]
84-element Array{Array{Int64,1},1}:
 [1, 0] 
 [1, 0] 
 [1, 0] 
 [2, 0] 
 [2, 0] 
 [2, 0] 
 [2, 0] 
 [2, 0] 
...

julia> a=[i for i in allSAWs(neigh, 2)];length([i for i in a if 0 in i])==84
true

But if I iterate elements in for loop (or add if statement to comprehension) there are “nonzero” elements too:

julia> for i in allSAWs(neigh, 2) println(i);end
[1, 5]
[1, 6]
[1, 0]
[2, 3]
[2, 5]
[2, 6]
[2, 7]
[2, 0]
...

julia> length([i for i in allSAWs(neigh, 2) if 0 in i])==16
true
2

To get more speed out of the iterator, it returns the paths in the same memory. So, to get an array of all the paths copy needs to be used:

[copy(i) for i in allSAWs(neigh,2)]

Regarding the zero elements, this is probably a bug, and will post an update soon.

3

This is not a bug. You always return the same mutable element when iterating over the object.

julia> a[1] === a[2]
true

If you don’t want this, you should change the return value of next to be copy(s[1]).

4

The zero elements are generated because of a nasty interaction between Flatten and an optimization in SAWs. In order to know if the iterator is done in a non-mutating way, the next function of flatten peeks ahead to another element in the iterator (and leaves the state so done() can know if the iterator is done). The same problem is present in SAWs and therefore, it also peeks ahead. But for optimization, SAWs uses a single vector for the path, and thus has to peek ahead mutatingly inside done(). This causes a slip by 1 of the iterator results, which drops the first path and adds the zero terminated path at the end.

This is the explanation.

One workaround is not to use Flatten and loop over the starting positions with explicitly. Something like:

julia> a=vcat([[copy(i) for i in SAWs(neigh, 2, j)] for j in eachindex(neigh)]...)
84-element Array{Array{Int64,1},1}:
 [1, 2]  
 [1, 5]  
 ⋮

Maybe there is a cleaner workaround, but it still escapes me.

5

Another, perhaps more general workaround is to redefine Flatten to peek into the future in a different way (perhaps slightly less performant). The following code does it:

julia> using Base: @propagate_inbounds

julia> import Base: Flatten

julia> @propagate_inbounds function next(f::Flatten, state)
           s, inner, s2 = state
           while done(inner, s2) && !done(f.it, s)
               inner, s = next(f.it, s)
               s2 = start(inner)
           end
           val, s2 = next(inner, s2)
           return val, (s, inner, s2)
       end
next (generic function with 77 methods)

julia> @inline function done(f::Flatten, state)
           s, inner, s2 = state
           done(inner, s2) || return false
           tmps = copy(s)
           while !done(f.it, tmps)
               tmps2, tmps = next(f.it, tmps)
               done(tmps2, start(tmps2)) || return false
           end
           return true
       end
done (generic function with 64 methods)

With these definitions:

for i in allSAWs(neigh, 2) println(i) ; end

works fine.

6

Thanks! :slight_smile: I am glad it is not a bug!

1 Like