Self Calls, Type Hints, and Memoization

January 20, 2016

Clojure and ClojureScript handle the optimization of self calls slightly differently and this post explores consquences of the difference.

I don't claim to fully appreciate the underlying tradeoffs, but hopefully this exposition gets you thinking.




Let's say you would like to optimize this definition of fib:

(defn fib [n]
  (if (< n 2)
    n
    (+ (fib (dec n))
      (fib (dec (dec n))))))

Currently, it calculates (fib 41) in 5.6 seconds on my computer in Clojure 1.7.

The first thing I'll try is type-hinting it so to eliminate the use of boxed math:

(defn ^long fib [^long n]
  (if (< n 2)
    n
    (+ (fib (dec n))
      (fib (dec (dec n))))))

This causes the run time to drop to 4 seconds.

But… because of the way self calls are handled by the Clojure compiler, the type hint is in the wrong place for this self call. It needs to be after the function name.

(defn fib ^long [^long n]
  (if (< n 2)
    n
    (+ (fib (dec n))
      (fib (dec (dec n))))))

That drops it to 2 seconds.

If you try this with Clojure 1.8.0, there are improvements in that the final version runs in 1.8 seconds. And, interestingly, while the second, incorrectly hinted version compiles under 1.8.0, it doesn't work at runtime, leading to AbstractMethodError Method user$fib.invokePrim(J)Ljava/lang/Object; is abstract user/fib (NO_SOURCE_FILE:-1).

Now, one huge optimization for the fib definition above is to employ memoization. If you start with the non-type-hinted version and then 

 (def fib (memoize fib))

then Clojure calcluates (fib 41) instantaneously.

Now, let's take a look at fib in ClojureScript 1.7.228, running in JavaScriptCore (using Planck).

If you take the unhinted version, you get a run time of about 2.5 seconds to calculate (fib 41) in Planck. There is no type hinting available that would make this run any faster.

For numeric primitives, there is no boxing to worry about in ClojureScript. And, since JavaScript engines fundamentally need to optimize in the face of dynamic typing, they must resort to observing use patterns and optimizing to machine-level primitives when possible, de-opting if assumptions becomes untrue, etc.

What about memoization? It turns out that ClojureScript optimizes the self call by dispatching directly to it. If you look at the difference between the JavaScript emitted for fib and for, say (defn f [x] (fib x)), you will see that fib uses 

cljs$user$fib.call(null, x)

instead of

cljs.user.fib.call(null,x)

So, if you do (def fib (memoize fib)), you'll see no improvement. Since memoization is so important for this way of defining fib, can you employ it in ClojureScript?

Sure. There are probably a bajilliion ways to skin this cat. Here's one

(def fib
  (let [fib
        (memoize
          (fn [fib n]
            (if (< n 2)
              n
              (+ (fib fib (dec n))
                (fib fib (dec (dec n)))))))]
    (partial fib fib)))

Now what about type hinting self calls in ClojureScript?

Consider this function. It looks to see if a collection contains a value, where the collection could be a recursive tree. 

(defn contains-val? [x coll]
  (if (seq coll)
    (if (coll? (first coll))
      (or (contains-val? x (first coll))
          (contains-val? x (rest coll)))
      (or (= x (first coll))
          (contains-val? x (rest coll))))
    false))

The semantics of this function aren't important for this post. What I'm interested in is whether we can use a ^boolean hint to eliminate the checked if embedded in the or calls. If you follow what we learned with Clojure and self calls, and put the type hint after the function name, as in 

(defn contains-val? ^boolean [x coll]
   ...)

then you'll see that a call to cljs.core.truth_ remains in the emitted JavaScript. But if you instead move it before the function name

(defn ^boolean contains-val?  [x coll]
   ...)

then you'll see that the emitted JavaScript is much more efficient, even being able to make use of the JavaScript || operator.

If you are curious, you can do some compiler archeaology on Clojure and ClojureScript to learn more about self calls. There are interesting tickets related to this subject, including:

Special thanks to Nicola Mometto for pointing out how to properly type-hint the call to fib in Clojure.

Tags: Clojure ClojureScript