tmerge return value types containing unions larger than three is Any

[bkamins]

Currently we have the following behavior:

julia> Core.Compiler.tmerge(Nothing, Tuple{Union{Int, Float64, Bool, Char},Int})
Any

julia> Core.Compiler.tmerge(Nothing, Tuple{Union{Int, Float64, Bool},Int})
Union{Nothing, Tuple{Union{Bool, Float64, Int64},Int64}}

The consequence is that current iteration protocol on collections that are union of more than three types starts boxing with a significant performance hit. I am reporting because I am not sure that this tmerge behavior is indented or not so I am reporting (I can see the possibility that there are cases when switching to Any and relying later on dynamic dispatch could be actually better so 😕).

The reason for this behavior is that MAX_TYPEUNION_COMPLEXITY = 3 and that when we calculate unioncomplexity we take into account unions hidden inside a Tuple (and this is exactly the case when we use iteration protocol which makes a union of Nothing and a tuple).

Here is an example. Running those definitions:

x = Union{Int, Float64, Char, Bool}[1 for i in 1:10^6]
y = Union{Int, Float64, Char}[1 for i in 1:10^6]

f1(x, v) = all(==(v), x)

function f2(x, v)
    for i in eachindex(x)
        x[i] == v || return false
    end
    true
end

yields the following results:

julia> using BenchmarkTools

julia> @btime f1(x, 1)
  385.869 ms (3998980 allocations: 76.28 MiB)
true

julia> @btime f2(x, 1)
  1.064 ms (0 allocations: 0 bytes)
true

julia> @btime f1(y, 1)
  7.276 ms (0 allocations: 0 bytes)
true

julia> @btime f2(y, 1)
  1.069 ms (0 allocations: 0 bytes)
true

[bkamins]

What I would do, if we do not to move MAX_TYPEUNION_COMPLEXITY (and I guess we do not want to) is to change to Any only if the resulting Union in tmerge is larger than 4 (this is exactly what happens now). In other cases I would change not the outermost Union but unions that are contained in Tuple that are actually causing the overflow.

E.g. now we have:

julia> Core.Compiler.tmerge(Nothing, Tuple{Union{Bool, Int, Float64, Char},Int})
Any

and after the proposed change we would have:

julia> Core.Compiler.tmerge(Nothing, Tuple{Union{Bool, Int, Float64, Char},Int})
Union{Nothing, Tuple{Any, Int}}

In this way we would be sure that iteration protocol is not broken badly as its outer Union would be always OK.

Does it sound reasonable?

[vtjnash]

This has been changed since then (most recently, #30833).