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?
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?
Copyright © 2021 Jogjafile Inc.
Dr. Bezanson's thesis is certainly the best source for descriptions of Julia's internals right now:
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 ΠP2 (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:
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.