How does Julia implement multimethods?

Question

I've been reading a bit from http://c2.com/cgi/wiki?ImplementingMultipleDispatch

I've been having some trouble finding reference on how Julia implements multimethods. What's the runtime complexity of dispatch, and how does it achieve it?

Answer 1

Dr. Bezanson's thesis is certainly the best source for descriptions of Julia's internals right now:

4.3 Dispatch system

Julia’s dispatch system strongly resembles the multimethod systems found in some object-oriented languages [17, 40, 110, 31, 32, 33]. However we prefer the term type-based dispatch, since our system actually works by dispatching a single tuple type of arguments. The difference is subtle and in many cases not noticeable, but has important conceptual implications. It means that methods are not necessarily restricted to specifying a type for each argument “slot”. For example a method signature could be Union{Tuple{Any,Int}, Tuple{Int,Any}}, which matches calls where either, but not necessarily both, of two arguments is an Int.²

The section continues to describe the type and method caches, sorting by specificity, parametric dispatch, and ambiguities. Note that tuple types are covariant (unlike all other Julian types) to match the covariant behavior of method dispatch.

The biggest key here is that the method definitions are sorted by specificity, so it's just a linear search to check if the type of the argument tuple is a subtype of the signature. So that's just O(n), right? The trouble is that checking subtypes with full generality (including Unions and TypeVars, etc) is hard. Very hard, in fact. Worse than NP-complete, it's estimated to be Π^P₂ (see the polynomial hierarchy) — that is, even if P=NP, this problem would still take non-polynomial time! It might even be PSPACE or worse.

---

Of course, the best source for how it actually works is the implementation in JuliaLang/julia/src/gf.c (gf = generic function). There's a rather useful comment there:

Method caches are divided into three parts: one for signatures where the first argument is a singleton kind (Type{Foo}), one indexed by the UID of the first argument's type in normal cases, and a fallback table of everything else.

So the answer to your question about the complexity of method lookup is: "it depends." The first time a method is called with a new set of argument types, it must go through that linear search, looking for a subtype match. If it finds one, it specializes that method for the particular arguments and places it into one of those caches. This means that before embarking upon the hard subtype search, Julia can perform a quick equality check against the already-seen methods… and the number of methods it needs to check are further reduced since the caches are stored as hashtables based upon the first argument.

But, really, your question was about the runtime complexity of dispatch. In that case, the answer is quite often "what dispatch?" — because it has been entirely eliminated! Julia uses LLVM as a just-barely-ahead-of-time compiler, wherein methods are compiled on-demand as they're needed. In performant Julia code, the types should be concretely inferred at compile time, and so dispatch can also be performed at compile time. This completely eliminates the runtime dispatch overhead, and potentially even inlines the found method directly into the caller's body (if it's small) to remove all function call overhead and allow for further optimizations downstream. If the types aren't concretely inferred, there are other performance pitfalls, and I've not profiled to see how much time is typically spent in dispatch. There are ways to optimize this case further, but there's likely bigger fish to fry first… and for now it's typically easiest to just make the hot loops type-stable in the first place.