Efficiency of abstract types vs `Any`

I’ll start by saying this is one of the areas where I think Julia will change and improve in some nearby versions. So both answering how things are and how things may be changing towards.

Yes, the compiler will get this as a static constraint. And if you look at type-unstable code, it will in the typed code printout say things like _A <: MyType, so abstract type inference will know the smallest dispatch it’s allowed to assume, carry that work, and check for constraint violations.

This one is clear.

The answer is, kind of. There is a compiler optimization commonly referred to here as world splitting optimization, which is that, based in the current world age of the function, if some optimization can happen on the set of allowed types and the number of types is sufficiently small (IIRC <4), then do the optimization. A common case for this for example is (a::Any == b::Any)::Bool in Base for every dispatch, so therefore just assume what comes out of == will be a Bool until a dispatch is added (in which case, that dispatch will invalidate any uninferred a or b cases, requiring the dispatch to be recompiled in the world age that adds the “offending” == dispatch).

Because of this world age splitting, you can end up in cases where for example you have 2 concrete types which are subtypes of an abstract type, both might hardcode a field b::Bool, so therefore a::MyType.b::Bool will infer that the b should be a Bool. In that sense, you can get better type inference in the cases where you have such restrictions that world age can hit, but

This is where it can get a bit funky. If you know f(a::Any, b::Any) basically the question is “should I world split or give up?” World split is easy: if there’s more than 3 return types that can happen from any dispatch of f, then just give up. What I mean by that is f(a,b) = a+b, well FloatX + FloatX :: FloatX so that’s too many, you can’t world split. Done, validate that you can’t do that, make f(a::Any, b::Any)::Any. So pushing forward Anys is actually pretty easy in the compiler.

Pushing forward abstract types in the compiler can be much more difficult, since you need to validate if every concrete instantiation does something. f(a::AbstractFloat, b::AbstractFloat), inferring the output is ::AbstractFloat is a statement about all possible subtypes. If one subtype hits ::Any, cool short circuit give up you don’t need to check the others. But if one says ::AbstractFloat, then you need to check the next, and the next, and see they all do this. Because of that, simply giving up and going to ::Any can be nicer on the compiler, meaning that using an abstract type can slow down type inference.

Potential Changes in the Future: Interfaces

Now my personal statement from all of this is that this will be helped a lot when interfaces are added to the language. Being able to state that for every dispatch of f, you must have f(a::T,b::T)::T would be able to guarantee such relations, and you would then be able to short circuit many difficult inference problems. Additionally, I think if such interfaces exist then the language could drop world splitting as the way to get these optimizations in some cases (something that I think has been discussed quite a bit), since right now world splitting does a lot of heavy lifting on uninferred code while being a bit fragile (and one of the main reasons for invalidations and long compile times). So, I don’t think the story here is complete by any means. Right now just using ::Any can decrease compile times, but in the future by placing interfaces ::MyType could be much better because if it can impose strong guarantees, then you could make type inference do a lot less work.

So for now, ::Any is likely going to have much shorter compile times, ::MyType will sometimes get a runtime improvement if you only have a few cases and it can prove in the current world-age that it is safe, and ::MyType is great for static checks and self-documenting code so it should be preferred when we can use it it’s just certain compiler behaviors that inhibit it in its current form.

16 Likes