What about type instability hurts peformance so much?

Question

I'm curious, if you have a type instability in your code, what exactly is it that hurts performance so much?

• Is it literally the type checking that needs to be performed at runtime, which I imagine in my head to be a bunch of if/else statements (if Float64 ... elseif Int64 elseif Float32 ... etc)
• And/or does the type checking prevent the CPU from pipelining in for loops?
• Or is the main problem the heap allocations that occur for all operations with the type unstable variables?
• Or something else?
• Any insights or links to further resources would be appreciated.

_{This question was originally posed by Oscar on JuliaLang Slack Channel}

Answer 1

A major factor is that type instabilities cause dynamic dispatch where the language needs to workout what method (for some function taking the type unstable variable) needs to be called at runtime. In the static case, this compiles to a direct function call (basically a goto statement in machine code). With instable, code, however, it has to have code that reads the list of all methods for that function and find the one that matches. Dynamic dispatch also means it can't inline, which significantly limits what the optimizer can possibly do.

A particular problem is that a type instability is poisonous, e.g. not limited to the location it occurs. So you might turn a tight loop into a loop that does dynamic dispatch at each operation.

However, in Julia 1.x the compiler can do "small union optimization", which means that if the compiler determines that a value must be one a small number of concrete types (currently ≤ 4) then it can, instead of doing a dynamic dispatch, check if the actual type is any of those four possibilities and generate a branch in which the concrete type of the value is known and dynamic dispatch can be avoided entirely. For example, if a value could be an Int or nothing then the compiler can check if it's nothing and handle that case and otherwise it knows the value must be an Int and it can generate efficient code for that case as well.