Understand why type stability depends on number of methods

I am reading the of Julia book of Kwong (@tk3369) and Karpinski 2020 and like to use the singleton type dispatch pattern.

However, when I check type stability (on Julia 1.7.3), I find that it suddenly fails when more methods are added. This cause was hard to track down.
How is this behavior explained? And what can I do to make this type-stable?

using Test
# convert :Symbol to Singleton type for dispatch
@inline foo(sym::Symbol, args...; kwargs...) = foo(Val(sym), args...; kwargs...)

foo(::Val{:m1}) = :m1
foo(::Val{:m2}) = :m2
foo(::Val{:m2}) = :m2
foo(::Val{:m4}) = :m4
@inferred foo(:m1) # is type stable

foo(::Val{:m5}) = :m5
@inferred foo(:m1) # suddenly becomes type-unstable

Alternatives to Symbols:

The alternatives, I used formerly, is to require the caller to use Value-types (anti-pattern?), or define many singleton types, but I am not satisfied with the resulting large number of identifiers/types in my Bigleaf package.

Defining own parametric singleton types leads to fewer identifiers, which however, tend to become disturbingly long, e.g. StabilityCorrectionMethod{:NoStabilityCorrection}().

It doesn’t fail, but the compiler stops optimizing because re-compiling methods for new methods also takes time. See for example the discussion at Add support for per-module max_methods. by chriselrod · Pull Request #43370 · JuliaLang/julia · GitHub.

1 Like

It’s the first inlined method that is type-unstable, the other methods are type stable:

julia> @which foo(:m1)
foo(sym::Symbol, args...; kwargs...) in Main at REPL[1]:4

julia> @which foo(Val(:m1))
foo(::Val{:m1}) in Main at REPL[1]:6

julia> @inferred foo(Val(:m1))

In a completely straightforward implementation, the first method could not be type-stable. The input argument sym has the type Symbol. In the body, you construct a Val(sym) which will have the type Val{sym}, which can be many different types depending on the value of sym. Because the value of sym is only known at runtime, the type Val{sym} is only known at runtime: this is type instability.

But Julia’s compiler isn’t that straightforward, it has optimization tricks. When you tried to infer foo(:m1) the first time, the compiler knew that there were only 4 Val-methods that all returned Symbol, and by assuming there will be no more methods, it could compile a method with a stable output type. Unfortunately, trying for a 5th one made the compiler give up on this optimization. The cutoff makes sense: just one new method that doesn’t return Symbol will force you to recompile all these methods, and you do not want to build a tower of assumptions just for it to collapse. The issue linked by @rikh talks about reducing that max_methods cutoff because it decreases compilation latency sometimes, see the first bullet point in issue 33326.

PS1. Something weird though is that I see the default max_methods is 3 in some code on Github and in another discourse post, but the number of methods seems to be 4. I don’t know if there’s a method I could use to check what max_methods is in an active session, and I could be misunderstanding max_methods’s exact meeting (it could mean 3 additional methods?).

PS2. The fact that the other methods are type-stable is a good thing, though, it means that in situations where you need to deal with some type instability, you can split your algorithm into many methods and isolate the instability to one dispatching method. If you only need to compile for a fixed few sym values, then most of your algorithm can be type-stable and more performant. Incidentally, you can write those type-stable methods more concisely as foo(::Val{T}) where T = T, though it will immediately make the max_methods optimization impossible (there doesn’t seem to be a way to write where T isa Symbol).

PS3. (foo(::Val{T})::Symbol) where T = T preserves the stability optimization, actually. Not as clean as declaring T must be a Symbol instance from the get-go…