Eliminating weird interactions with Julia's compiler

[timholy]

https://github.com/JuliaGraphics/Colors.jl/issues/496 highlighted some bizarre behavior whose underlying cause is not understood. A partial investigation by several contributors to both these packages and Julia itself has revealed links to some fairly deep issues in Julia, with possibly more than one independent cause (https://github.com/JuliaLang/julia/issues/35800 and https://github.com/JuliaLang/julia/issues/35972). While it's very desirable to fix these things in Julia itself (and likely to be a focus of my own future efforts), it's also reasonable to ask whether ColorTypes & Colors can do things to work around the problem.

ColorTypes is unquestionably quite hard on Julia's type system. One direct way of seeing that is

julia> using Colors, SnoopCompile
[ Info: Precompiling SnoopCompile [aa65fe97-06da-5843-b5b1-d5d13cad87d2]

julia> tinf = @snoopi_deep include("runtests.jl")
⋮
InferenceTimingNode: 47.538766/73.885073 on Core.Compiler.Timings.ROOT() with 6085 direct children

from within the Colors test/ folder, followed by

julia> itrigs = inference_triggers(tinf);

julia> length(itrigs)
1096

julia> itree = trigger_tree(itrigs);

julia> using AbstractTrees

julia> print_tree(itree)
root
├─ Base.visit(::Base.var"#18#19"{Vector{Method}}, ::Core.TypeMapEntry)
│  └─ (::Base.var"#18#19"{Vector{Method}})(::Method)
├─ Base.visit(::Function, ::Core.TypeMapLevel)
├─ (::Base.var"#inner#37"{Bool, Method, Method})(::Type)
│  ├─ Base.has_bottom_parameter(::DataType)
│  │  ├─ Base.has_bottom_parameter(::Core.TypeofBottom)
│  │  └─ Base.has_bottom_parameter(::Symbol)
│  └─ Base.has_bottom_parameter(::UnionAll)
│     └─ Base.has_bottom_parameter(::TypeVar)
│        ├─ Base.has_bottom_parameter(::Union)
│        └─ Base.has_bottom_parameter(::Int64)
├─ (NamedTuple{()})(::Tuple{})
├─ (::Test.var"#19#24")(::Any)
├─ Base.print_to_string(::Type, ::Vararg{Any})
├─ string(::Type, ::String, ::Vararg{Any})
├─ ColorTypes._convert(::Type{Luv{Float64}}, ::Type{Luv}, ::Type{HSV}, ::HSV{Float64})
│  ├─ ColorTypes._convert(::Type{XYZ{Float64}}, ::Type{XYZ}, ::Type{HSV}, ::HSV{Float64})
│  │  └─ Colors.cnvt(::Type{XYZ{Float64}}, ::RGB{Float64})
│  └─ Colors.cnvt(::Type{Luv{Float64}}, ::XYZ{Float64})
├─ Colors.cnvt(::Type{Lab{Float64}}, ::XYZ{Float64})
├─ ColorTypes._convert(::Type{Lab{Float64}}, ::Type{Lab}, ::Type{HSV}, ::HSV{Float64})
├─ Base.indexed_iterate(::Pair{Symbol, Float64}, ::Int64)
├─ (NamedTuple{(:atol,)})(::Tuple{Float64})
├─ merge(::NamedTuple{(), Tuple{}}, ::NamedTuple{(:atol,), Tuple{Float64}})
├─ Base.var"#printstyled#873"(::Bool, ::Bool, ::Bool, ::Bool, ::Bool, ::Symbol, ::typeof(printstyled), ::Base.TTY, ::String, ::Vararg{Any})
│  └─ (::Base.var"#with_output_color##kw")(::NamedTuple{(:bold, :underline, :blink, :reverse, :hidden), NTuple{5, Bool}}, ::typeof(Base.with_output_color), ::Function, ::Symbol, ::Base.TTY, ::String, ::Vararg{Any})
├─ Base.var"#printstyled#874"(::Bool, ::Bool, ::Bool, ::Bool, ::Bool, ::Symbol, ::typeof(printstyled), ::String)
├─ sprint(::Function, ::Symbol)
├─ Base.indexed_iterate(::Pair{Symbol, Float32}, ::Int64)
├─ (NamedTuple{(:atol,)})(::Tuple{Float32})
├─ merge(::NamedTuple{(), Tuple{}}, ::NamedTuple{(:atol,), Tuple{Float32}})
├─ ColorTypes._convert(::Type{DIN99{Float32}}, ::Type{DIN99}, ::Type{RGB24}, ::RGB24)
│  └─ ColorTypes._convert(::Type{Lab{Float32}}, ::Type{Lab}, ::Type{RGB24}, ::RGB24)
├─ ColorTypes._convert(::Type{DIN99{Float64}}, ::Type{DIN99}, ::Type{RGB24}, ::RGB24)
│  └─ ColorTypes._convert(::Type{Lab{Float64}}, ::Type{Lab}, ::Type{RGB24}, ::RGB24)
├─ ColorTypes.cconvert(::Type{DIN99d{Float32}}, ::RGB24)
│  └─ ColorTypes._convert(::Type{DIN99d{Float32}}, ::Type{DIN99d}, ::Type{RGB24}, ::RGB24)
├─ ColorTypes._convert(::Type{LCHuv{Float32}}, ::Type{LCHuv}, ::Type{RGB24}, ::RGB24)
├─ ColorTypes._convert(::Type{LCHuv{Float64}}, ::Type{LCHuv}, ::Type{RGB24}, ::RGB24)
├─ Colors.cnvt(::Type{LMS{Float32}}, ::XYZ{Float32})
├─ ColorTypes._convert(::Type{DIN99{Float32}}, ::Type{DIN99}, ::Type{BGR}, ::BGR{Float32})
│  └─ ColorTypes._convert(::Type{Lab{Float32}}, ::Type{Lab}, ::Type{BGR}, ::BGR{Float32})
├─ ColorTypes._convert(::Type{LCHuv{Float32}}, ::Type{LCHuv}, ::Type{BGR}, ::BGR{Float32})
├─ ColorTypes._convert(::Type{DIN99{Float64}}, ::Type{DIN99}, ::Type{BGR}, ::BGR{Float32})
│  └─ ColorTypes._convert(::Type{Lab{Float64}}, ::Type{Lab}, ::Type{BGR}, ::BGR{Float32})
├─ ColorTypes._convert(::Type{LCHuv{Float64}}, ::Type{LCHuv}, ::Type{BGR}, ::BGR{Float32})
├─ ColorTypes._convert(::Type{DIN99{Float64}}, ::Type{DIN99}, ::Type{BGR}, ::BGR{Float64})
│  └─ ColorTypes._convert(::Type{Lab{Float64}}, ::Type{Lab}, ::Type{BGR}, ::BGR{Float64})
├─ ColorTypes._convert(::Type{LCHuv{Float64}}, ::Type{LCHuv}, ::Type{BGR}, ::BGR{Float64})
├─ ColorTypes._convert(::Type{DIN99{Float32}}, ::Type{DIN99}, ::Type{BGR}, ::BGR{Float64})
│  └─ ColorTypes._convert(::Type{Lab{Float32}}, ::Type{Lab}, ::Type{BGR}, ::BGR{Float64})
├─ ColorTypes._convert(::Type{LCHuv{Float32}}, ::Type{LCHuv}, ::Type{BGR}, ::BGR{Float64})
├─ ColorTypes._convert(::Type{DIN99{Float32}}, ::Type{DIN99}, ::Type{RGB}, ::RGB{Float64})
│  └─ ColorTypes._convert(::Type{Lab{Float32}}, ::Type{Lab}, ::Type{RGB}, ::RGB{Float64})
⋮

While that number of triggers is far from unprecedented, it's not trivial either. You expect inference triggers from the test suite itself (methods are not inferred until they are called, other than for precompilation), and some are internal in Julia (e.g., the first several branches have to do with detect_ambiguities). But the fact that there are internal inference failures in conversion, even though the end result is inferrable, is probably undesirable. The fact that caching in *,ji files is partly dependent on backedges, and runtime dispatch breaks those edges, might be one of the indirect contributors to some of the weird issues we're seeing. Consequently it might be worth considering how to make this package easier on inference.

One likely proximal cause is https://github.com/JuliaLang/julia/issues/36454. While I haven't run any tests, I see at least two potential workarounds:

1. define a Zero <: AbstractFloat type and do more of this package's type-logic in the value-domain rather than the type domain.
2. instead of passing RGB (a non-concrete type) as an argument to functions, pass something like RGB{Union{}} (a concrete type)

1 is fairly likely to introduce invalidations in other packages, so in general I'd favor 2. I don't plan on working on this immediately, but it may be relevant for efforts towards #261 and related topics, so I thought I'd throw this out there.

[kimikage]

I agree with you about the importance of this issue. However, the Colors tests use a lot of methods that are rarely used in practice. Also, the inference cost of the individual methods doesn't seem to be so critical.

[timholy]

I am confused about the combination of your first sentence and the second two, can you clarify? You do realize that fixing the inference problems of this package are likely to resolve all of the slowdowns in https://github.com/JuliaGraphics/Colors.jl/issues/496, right?

[kimikage]

I simply don't understand the relationship between what you have tried to show with itrigs and this issue. I'm more interested in solving specific practical problems than in general improvements (as workarounds on the package side).

I currently doubt that JuliaLang/julia#36454 is a "proximal" cause. If the approach 2. solves all the problems, then I have no reason to disagree with it.

Edit: For example, a workaround which bypasses the ColorTypes.jl implementation as shown below is effective, but not a panacea. https://github.com/JuliaGraphics/Colors.jl/blob/9b57362f5143ac5a53433b6ed0f30ed39db189da/src/conversions.jl#L62-L64

[timholy]

Think of inference_triggers as @code_warntype*1000. It detects every inference failure in everything you ran under @snoopi_deep, and lets you browse stacktraces for each via Cthulhu. The stats above indicate that there were >6000 separate calls to type inference (the number of children under tinf), but most of those came from runtests.jl and the files it loads. itrigs is SnoopCompile's best guess at "internal" inference failures, and there were more than 1000 of those. Every new combination of types counts, but the number of affected methods may be much smaller (try accumulate_by_source(Method, itrigs)).

[kimikage]

For example, runtests.jl of Colors.jl triggers many inferences on DIN99 and its variations. The color conversions of DIN99 and its variants have the Base functions with (potential) problem of precompilation (e.g. exp). Perhaps that's a separate issue from ColorTypes.jl, and I think it's better discussed with a more practical benchmark.