slow subtyping of complex Union

[projekter]

I just ran into an example where precompilation of my package suddenly took forever (usually ~5s, now I terminate it after a minute). I managed to boil it down to the following:

module precompilationhang

const XorM{X} = Union{<:X,Missing}

struct Type1{P,V<:AbstractVector{P},Vr<:XorM{V},Vc<:XorM{V}}
end

struct Type2{P,
    E1<:(AbstractVector{M} where M<:Type1{P}),
    E2<:(AbstractVector{M} where M<:Type1{P}),
    E3<:(AbstractVector{M} where M<:Type1{P}),
    E4<:(AbstractVector{M} where M<:Type1{P})}
    f1::Vector{E1}
    f2::Vector{E2}
    f3::Vector{Vector{E3}}
    f4::Vector{Vector{E4}}
end

end

Precompilation of this tiny package takes about 4:40 minutes.
Trying to simplify it further first looked as if it still has the same issue, but this was merely impatience. For example (all of the examples have just the one thing changed that I mention, the changes don't accumulate):

• XorM = Union{X,Missing} takes 13 seconds
• removing just the field f1 takes 10 seconds
• removing E1 and f1 takes 5 seconds
• removing just the Vc type parameter from Type1 takes 2 seconds

Julia Version 1.10.1
Commit 7790d6f064 (2024-02-13 20:41 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 16 × 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, tigerlake)
Threads: 1 default, 0 interactive, 1 GC (on 16 virtual cores)

[KristofferC]

suddenly took forever

Compared to what? 1.9, 1.10.0?

[projekter]

Compared to a small change in the code where all the E1, ... were of the same type.

[JuergenWiemers]

Compared to what? 1.9, 1.10.0?

The example above runs instantaneously on 1.9.4 and takes several minutes on 1.10.0 (tested on Windows and Linux). The slowdown also occurs on master.

Bisected to c1d1bde (@N5N3).

[N5N3]

Subtype MWE

julia> struct Type1{A, B, C, D} end

julia> struct Type2{A, B, C, D, E} end

julia> S = Type{Type2{P, E1, E2, E3, E4}} where E4<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E3<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E2<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E1<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where P
Type{Type2{P, E1, E2, E3, E4}} where {P, E1<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s1"} where var"#s1"<:V), Vc<:(Union{Int64, var"#s13"} where var"#s13"<:V)})), E2<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s14"} where var"#s14"<:V), Vc<:(Union{Int64, var"#s15"} where var"#s15"<:V)})), E3<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s16"} where var"#s16"<:V), Vc<:(Union{Int64, var"#s17"} where var"#s17"<:V)})), E4<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s18"} where var"#s18"<:V), Vc<:(Union{Int64, var"#s19"} where var"#s19"<:V)}))}

julia> T = Type{Type2{P, E1, E2, E3, E4} where E4<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E3<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E2<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where E1<:(Array{M, 1} where M<:(Type1{P, V, Vr, Vc} where Vc<:(Union{Int, <:V}) where Vr<:(Union{Int, <:V}) where V<:Array{P, 1})) where P}
Type{Type2{P, E1, E2, E3, E4} where {P, E1<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s19"} where var"#s19"<:V), Vc<:(Union{Int64, var"#s18"} where var"#s18"<:V)})), E2<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s17"} where var"#s17"<:V), Vc<:(Union{Int64, var"#s16"} where var"#s16"<:V)})), E3<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s15"} where var"#s15"<:V), Vc<:(Union{Int64, var"#s14"} where var"#s14"<:V)})), E4<:(Vector{M} where M<:(Type1{P, V, Vr, Vc} where {V<:Vector{P}, Vr<:(Union{Int64, var"#s13"} where var"#s13"<:V), Vc<:(Union{Int64, var"#s1"} where var"#s1"<:V)}))}}

julia> @time S <: T
  0.000021 seconds (8 allocations: 2.547 KiB) # 1.9
  182.825040 seconds (196.29 M allocations: 64.375 GiB, 0.16% gc time) #1.10
false