Open topolarity opened 1 year ago
Turns out it's not the tuple combinatorics in this case:
This comes from the double-intersection we evaluate in intersect_unionall
: https://github.com/JuliaLang/julia/blob/a23b29cb1a6013277e381092147fc527a44d924a/src/subtype.c#L2913-L2932
This becomes O(2^N)
for nested UnionAll types.
My first stab at this was to statically adjust our types to reduce type-var nesting, while preserving type-equality.
Unfortunately, our current intersection algorithm will widen when you do this:
julia> T1 = Tuple{Pair{B, C}, C} where {B, C}
julia> T2 = Tuple{Pair{B, C} where B, C} where C
julia> U = Tuple{Pair{B, C}, Union{Real, B}} where {B, C}
julia> (@ccall jl_intersect_types(T1::Any, U::Any)::Any) == Tuple{Pair{B, C}, C} where {B, C<:Union{Real, B}}
true
julia> (@ccall jl_intersect_types(T2::Any, U::Any)::Any) == Tuple{Pair{B, C}, C} where {B, C}
true
Subtyping even becomes incorrect under this transformation (which should preserve type-equality):
julia> T = Tuple{Pair{A, B}, Union{A, Ref{T}}} where {A, B, T}
julia> S1 = Tuple{Pair{A, B}, Union{A, Ref{T}} where T} where {A, B}
julia> S2 = Tuple{Pair{A, B}, Union{A, Ref{T} where T}} where {A, B}
julia> T == S1
false
julia> T == S2
true
The widening is expected.
IIRC we had some attempt to pull these covariant UnionAll
s out and make result more accurate.
Edit: see #23700 and the added broken test there.
Thanks for the info! That's helpful historical information.
It's a shame that in this case it ends up opting into an exponential algorithm even when it's often not necessary, but I suppose the whole problem here is that the intersection algorithm is not good at dynamically expanding/shrinking UnionAll dependencies (based on the chains of type-vars considered)
I'm going to take a stab at solving this dynamically (by narrowing dependencies during intersection computation), rather than statically (with a type transformation)
Seems to happen when intersecting extremely large tuples.
50+s example from BlochSim.jl:
20+s example from StochasticDiffEq.jl:
Version:
I expect that we're going down a combinatorial path among all the tuple components, despite the fact that they don't actually share any typevars.
Fix is in the works 🙂