Are clojure multimethods slow by nature

Question

I was looking at the clojure.core function re-groups:

(defn re-groups [^java.util.regex.Matcher m]
    (let [gc  (. m (groupCount))]
      (if (zero? gc)
        (. m (group))
        (loop [ret [] c 0]
          (if (<= c gc)
            (recur (conj ret (. m (group c))) (inc c))
             ret))))) 

And thought that it would be "better" to rewrite it as a multimethod:

(defmulti re-groups (fn [^java.util.regex.Matcher m] (.groupCount m)))
(defmethod re-groups 0 [m] (.group m))
(defmethod re-groups :default [m]
        (let [idxs (range (inc (.groupCount m)))]
             (reduce #(conj %1 (.group m %2)) [] idxs))) 

Yet when comparing the times I was surpised to see the rewrite is 4 times slower:

clojure.core: "Elapsed time: 668.029589 msecs"
multi-method: "Elapsed time: 2632.672379 msecs" 

Is this a natural result of multimethods or is there something else wrong here?

Erst

You seem to be using multimethods as a kind of pattern matching construct here. That's really not the purpose of multimethod, which is (multi) dispatching. Think of it like a superset of what's possible in object-orientated languages. For single-dispatch (like normal OO stuff) use protocols. For pattern-matching use this: github.com/swannodette/match – Stouthearted

Also, the clojure.core code is the way it is precisely for performance reason, so most other implementations will be slower. – Stouthearted

Answer 1

Clojure multimethods allow runtime polymorphic behavior based on arbitrary dispatch functions. This is very powerful for building ad-hoc hierarchies and abstractions, but you pay a performance hit for such flexibility. You may wish to re-implement your solution with a protocol. Only use multimethods when you need complete runtime type flexibility.

Kumler

I had consider a protocol but from the documentation The resulting functions dispatch on the type of their first argument, and thus must have at least one argument and what is needed is a dispatch on the value of the argument. – Erst

Answer 2

in general anything that does more will take more time. because multimethods offer a variety of ways to dispatch they will take longer than protocols you I have to answer your question "yes, when compared to protocols".

In practice start with protocols and go to multimethods when you have to (and it looks like you need them). you can't make the computer faster with code, but you can make it do less

Riding

Answer 3

I think the reason your multi-method implementation is slower may also be because you are using reduce on a lazy sequence (provided by range) instead of the loop/recur on an incrementing index that is used in clojure.core. Try copying the loop part of the implementation of clojure.core/re-groups into your second defmethod and see if that doesn't increase the performance.

It is hard to say without seeing your test case, but if there are a lot of groups in the matcher, you may be spending much more time in reducing the groups into a vector than in the multi-method dispatch. If there are few groups though, then the multi-method dispatch will be a more significant portion of the time spent. In either case, having the same implementation will eliminate a potential contributing factor to the timing difference and help you to get a better feel for the actual overhead in multi-method dispatch.

Another thing you might consider is the possibility that the slowdown is due to reflection. Try setting *warn-on-reflection* to true and see if it complains. Maybe another strategic type hint may help.

Perinephrium

I used this to get the timings: (time (count (map re-matches (cycle [#"[-+]?[0-9]+/([0-9])+" #"([-+]? [0-9]+)/([0-9])+" #"[-+]?[0-9]+/[0-9]+" #"hamster"]) (take 200000 (for [x (range) y (range x)] (str x "/" y)))))) – Erst