Self Calls, Type Hints, and Memoization
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
(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
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.
fib and for, say
(defn f [x] (fib x)), you will see that
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
(defn ^boolean contains-val? [x coll] ...)
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