Caching multimethod default value dispatch
I have seen this problem in my own code in the past (before I was working on Clojure itself) so I immediately saw the chance to find and kill a problem that has affected me. Anton did a phenomenal job feeding me everything I needed to quickly reproduce and detect the problem.
Backing up slightly, multimethods are functions that can dispatch to many possible method implementations based on the result of an initial dispatch function. For example:
Invoking a multimethod involves evaluating two functions: the dispatch function (class in the example above) and then using the return value to select the matching method implementation to actually invoke. The backing MultiFn class maintains a methodTable map from dispatch value to IFn (the method). However, finding a match is not exactly a simple lookup. There are several other features of multimethods:
- Inheritance hierarchy matching - using either custom hierarchies or Java class hierarchies
- Preferences - in the case of multiple possible matches, a preference may be stated for resolution
- Default dispatch - a method to use if no match is found (marked with :default by default)
Due to the possibilities of multiple matches resolved by preferences and falling through to a default, there is some complicated logic that implements this decision. For performance, the decision reached is cached at the end. Because multimethods are open (new methods or preferences may be added at any time), this logic must deal with the concurrency issues and possibility of a change happening during invocation.
I’ve annotated the key method here outlining what happens (note this is prior to the fix):
In the gist above you can see where I’ve noted the bug - if no matching method is found we do not alter the cache. That means that in the fallthrough case, the matching logic is done every time, which requires walking through every entry in the method table.
One situation where I see this come up as a frequent performance issue is when using clojure.walk with an update function, where there is often a default fall-through case.
Now here is the same method after the patch (now included in Clojure 1.7):
We now look up and alter the cache when the default branch is taken. This can make a dramatic difference in performance when you are using the :default case. Here is a simple test using a mixture of default and non-default values:
The JIT warms up in both cases but you can see that there is a dramatic performance boost here. This change was added in Clojure 1.7.0-alpha2.