Union splitting vs C++

General Usage Performance
17

I am not sure how easy is to understand everything that is going on. The easiest part is that if one initializes the vector with

p = Picture([line_types[rand(1:5)](rand()) for i in 1:1000]);

the container is of completely abstract line types, of course:

julia> typeof(p.lines)
Vector{Main.Lines.LineAbstract} (alias for Array{Main.Lines.LineAbstract, 1})

and then yes, to that vector we can push! a new type of line:

julia> push!(p.lines,NewLine(1.0))
1001-element Vector{Main.Lines.LineAbstract}:
 Line5(0.46793882745951554)
⋮
 NewLine(1.0)

this is more flexible than doing

julia> p = Picture2(Union{Line1,Line2,Line3,Line4,Line5}[line_types[rand(1:5)](rand()) for i in 1:1000]);

julia> typeof(p.lines)
Vector{LineUnion} (alias for Array{Union{Line1, Line2, Line3, Line4, Line5}, 1})

julia> push!(p.lines,NewLine(1.0))
ERROR: MethodError: Cannot `convert` an object of type 
  NewLine to an object of type 
  LineUnion

Yet, that difference in flexibility is only associated to the manipulation of the array, not with the function paint. That will work either way, but will specialize differently for each type of array. One could expect (I did) that with the Union type the compiler could do some sort of automatic splitting and be reasonably fast.

Yet that is more complicated:

julia> p = Picture([line_types[rand(1:5)](rand()) for i in 1:1000]);

julia> @btime Lines.paint1($p)
  55.803 μs (2000 allocations: 31.25 KiB)
504.7398735079236

julia> p = Picture2(Union{Line1,Line2,Line3,Line4,Line5}[line_types[rand(1:5)](rand()) for i in 1:1000]);

julia> @btime Lines.paint1($p)
  179.357 μs (5980 allocations: 109.06 KiB)
509.5267566245098

I would not expect the result above, on the contrary. paint1 there iterates with for l in p.lines, and I hoped that with the Union type it would be faster.

That changes completely if one iterates with for i in eachindex(p) (the paint3 function suggested by Elrod):

julia> @btime Lines.paint3($p)
  57.717 μs (2000 allocations: 31.25 KiB)
500.16546958495144

julia> p = Picture2(Union{Line1,Line2,Line3,Line4,Line5}[line_types[rand(1:5)](rand()) for i in 1:1000]);

julia> @btime Lines.paint3($p)
  984.929 ns (0 allocations: 0 bytes)
493.92273981135605

The performance with the Union type is not only faster, as expected. Is much faster than expected (it much faster than the C++ alternative as well).

So there is something related to the implementation of these iterators and how they correlate with the type of array that is being input that is important for the result here. That escapes me, but I think that suggests that some iterators could be improved (in particular the non-indexed one).

I will call attention for this fact: if one iterates with pairs, like this:

function paint4(p)
  s = 0.
  for (i,l) in pairs(p.lines)
    s += paint(l)
  end
  s
end

we get:

julia> @btime Lines.paint4($p)
  994.917 ns (0 allocations: 0 bytes)
493.92273981135605

while with

function paint1(p)
  s = 0.
  for l in p.lines
    s += paint(l)
  end
  s
end

we get:

julia> @btime Lines.paint1($p)
  176.550 μs (5980 allocations: 109.06 KiB)
493.92273981135605

I would, at this point, probably call this a bug on the iterators of the form for x in v, I cannot see how it can behave so much worse than for (i,x) in pairs(v), which is more general than the former.

Edit: I reported this as an issue: very bad performance of iterator on array of union types · Issue #40950 · JuliaLang/julia · GitHub

4 Likes