There was a question recently on the Clojure mailing list about when to use multimethods vs protocols vs case vs cond:

There are situations where I want to dispatch functions using based on their certain properties. I can also use case statements instead but it looks more coupled and more change is required if I want to add new types.

What I want to ask is if I need to avoid using multi-methods for performance reasons? I read somewhere that they are not really fast but the posts were old and the performance might have been improved in between. Should I favor case and cond branches instead of defmulti when I need performance?

I responded there with some guidance but wanted to flesh that out a bit more and add some numbers. There are a couple of axes of interest here:

• Open vs closed - are you ok with code that specifies a concrete set of choices and requires modification to add new cases? Or do you want an open system that can be extended without modifying the existing code. Multimethods and protocols are open, case and cond are closed.
• Type vs value - do you want to dispatch based on type of a single argument or based on values or types of multiple arguments? Are the values you are choosing between constants or expressions that require evaluation?

General guidelines:

• open extension and type-based dispatch => protocols
• open extension and value-based dispatch => multimethods
• closed constant choices => case
• closed expressions => cond

I created a repo with some perf tests in it for comparison purposes - run them with lein run if you like. The numbers recorded here were created on a Macbook Pro with Java 1.8 and either Clojure 1.6 or 1.7.0-beta2 as specified.

Value-based dispatch performance

If we look first at value-based dispatch, I compared using case vs cond vs multimethods for this. The implementation of case is actually more complicated than you might expect, going to great lengths to leverage a table-based constant-time lookup. This constant-time is only available if the values to compare are compile-time constants, so you cannot use arbitrary expressions. The example being tested:

(defn value-case [n]
  (case n
    1 "1"
    2 "2"
    3 "3"
    4 "4"
    5 "5"))

This is being compared with cond, which evaluates a series of conditions until a match is found (on average, linear time not constant time):

(defn value-cond [n]
  (cond
    (= n 1) "1"
    (= n 2) "2"
    (= n 3) "3"
    (= n 4) "4"
    (= n 5) "5"))

And we can do something similar with multimethods:

(defmulti value-multi identity)
(defmethod value-multi 1 [n] "1")
(defmethod value-multi 2 [n] "2")
(defmethod value-multi 3 [n] "3")
(defmethod value-multi 4 [n] "4")
(defmethod value-multi 5 [n] "5")

Multimethods first evaluate the dispatch function (here, identity), then perform a linear search for a value match, and finally invoke the actual implementation method. The linear search is optimized with a cache from dispatch value to method.

Here is a comparison of performance when called with 1 and 5 in these cases, all times in ns:

Because both case and multimethods use a cache, we see approximately the same time for both the 1st and 5th case. Multimethods require the invocation of two functions and is about twice as long. cond however is a linear search through the conditions - if the first case happens to be the one that’s hit, this is the fastest option! But if multiple expressions need to be checked, the worst case here is twice as slow as multimethods.

As is commonly the case, if you have prior knowledge about your data, you may be able to leverage that information to optimize your code. If one value tends to dominate in your use case, a quick cond (or if) check that catches it before hitting a broader set of use cases could be a big win. Combining closed (for better performance of known cases) and open (for extensibility) approaches is a useful technique.

There are of course lots more variations that could be tested here - depending on the complexity of the dispatch function, condition expressions, weightings of different use cases, etc any of these options (or a combination) might be the best for you. To know for sure, measure your own use case! But hopefully this helps to build a mental model of the options.

I did not expect these to vary much between 1.6 and 1.7.0-beta2 but several changes seem to have combined to improve the performance in most of these cases too, so I included that in case anyone was curious.

Type-based dispatch performance

Turning to type-based dispatch, it makes the most sense to consider protocols vs multimethods, which have differing capabilities but overlap in the most common scenario of dispatching based on the type of the first argument to the function. Protocols maximally leverage the type-based dispatch built into the JVM.

Here I benchmarked protocols:

(defprotocol TypeProto
  (type-proto [_]))

(extend-protocol TypeProto
  String
  (type-proto [_] "string")
  Long
  (type-proto [_] "long")
  Object
  (type-proto [_] "default"))

versus the same effective call for multimethods:

(defmulti type-multi class)
(defmethod type-multi String [x] "string")
(defmethod type-multi Long [x] "long")
(defmethod type-multi :default [x] "default")

I threw the default case in there to demonstrate how dramatic the improvement is now that this case is being cached in 1.7 (see this previous post for details).

Here’s the comparison of a single call, the default case, and invoking with alternating types (all times in ns):

A few things to notice there. Obviously, caching the default case makes a dramatic performance difference. Second, protocols are about 5x faster than multimethod calls for this particular case of type-based dispatch. You can find older estimates of 100x or more for this difference but I think the 5x difference is a good rule of thumb for modern JVM and Clojure versions.

Generally, this difference in performance between protocols and multimethods is unlikely to be the biggest factor in the performance of your application, but I think protocols are the better default choice for this case.

Finally, it’s also interesting to look at how things change as we go from a monomorphic call (single type) to a bimorphic call (alternating types). Since the alternating “abc”/5 case is doing twice as many calls, we expect it to be about twice as slow and indeed the multimethod one is right there. Interestingly though the protocol case gets slower by 3-4x - we are hurting the ability of the JIT to optimize this case and killing some of the performance gains that protocols are leveraging. It’s still significantly faster than multimethods though. If we pushed this further to a megamorphic (>2 cases) call, you would see further loss in optimization.

For a more detailed discussion on using multimethods and protocols for polymorphism, check out the discussion in chapter 1 of my book with Ben Vandgrift, Clojure Applied, now in beta.