How do I make this imperative (arrays, loops, etc) Clojure code run half as fast as Java?

Question

I've read that there are ways of coaxing the Clojure compiler into producing code that rivals the performance of similar code in Java, at least for code that already looks a lot like the Java code you want it to turn into. That's sound reasonable to me: idiomatic, high level Clojure code might have performance in the ballpark of what I'm used from CPython or MRI, but "ugly" Java-like code runs more or less like Java. This is a tradeoff I appreciate in Haskell, for example. Low level Haskell code with mutable arrays, loops and what not runs under GHC with appropriate compiler flags about as fast as it does in C (and then some high-tech libraries can sometimes squeeze similar performance out of prettier, higher level code).

I want help learning how to get my Java-like Clojure code to run as fast as in Java. Take this example:

(defn f [x y z n]
  (+ (* 2 (+ (* x y) (+ (* y z) (* x z))))
     (* 4 (+ x y z n -2) (- n 1))))

(defmacro from [[var ini cnd] & body]
  `(loop [~var ~ini]
     (when ~cnd
       ~@body
       (recur (inc ~var)))))

(defn g [n]
  (let [c (long-array (inc n))]
    (from [x 1 (<= (f x x x 1) n)]
      (from [y x (<= (f x y y 1) n)]
        (from [z y (<= (f x y z 1) n)]
          (from [k 1 (<= (f x y z k) n)]
            (let [l (f x y z k)]
              (aset c l (inc (aget c l))))))))
    c))

(defn h [x]
  (loop [n 1000]
    (let [^longs c (g n)]
      (if-let [k (some #(when (= x (aget c %)) %)
                       (range 1 (inc n)))]
        k
        (recur (* 2 n))))))

(time (print (h 1000)))

It takes about 85 seconds using Clojure 1.6 on my (admittedly) slow machine. Equivalent code in Java runs in about 0.4 seconds. I'm not greedy, I just want to get the Clojure code to run in, say, around 2 seconds.

The first thing I did was enable *warn-on-reflection* but sadly, with that lonely type hint there are no further warnings. What am I doing wrong?

This gist contains both the Java and Clojure versions of the code.

Answer 1

Unfortunately *warn-on-reflection* doesn't warn you about primitive boxing - which I think is the main problem here. You want to be using unboxed primitive arithmetic at all times for maximum speed.

The following hints should help you optimise this:

• Do a (set! *unchecked-math* true) to get faster primitive numerical operations
• Try initialising your loops with (long ~ini). You want to force the use of primitives this way
• Try putting a primitive hint ^long n to the function g
• Try type-hinting your long array ^longs c - this should hopefully make Clojure use the faster primitive aget.
• Type hint f as a primitive function ^long [^long x ^long y ^long z ^long n] or similar. This is very important, otherwise f will return boxed numbers....

If you succeed in eliminating all the boxed numbers, then this kind of code should be nearly as fast as pure Java.