Quicksort in Clojure

Question

I am trying to prove Clojure performance can be on equal footing with Java. An important use case I've found is the Quicksort. I have written an implementation as follows:

(set! *unchecked-math* true)  (defn qsort [^longs a]   (let [qs (fn qs [^long low, ^long high]              (when (< low high)                (let [pivot (aget a low)                      [i j]                      (loop [i low, j high]                        (let [i (loop [i i] (if (< (aget a i) pivot)                                              (recur (inc i)) i))                              j (loop [j j] (if (> (aget a j) pivot)                                              (recur (dec j)) j))                              [i j] (if (<= i j)                                      (let [tmp (aget a i)]                                        (aset a i (aget a j)) (aset a j tmp)                                        [(inc i) (dec j)])                                      [i j])]                          (if (< i j) (recur i j) [i j])))]                  (when (< low j) (qs low j))                  (when (< i high) (qs i high)))))]     (qs 0 (dec (alength a))))   a) 

Also, this helps call the Java quicksort:

(defn jqsort [^longs a] (java.util.Arrays/sort a) a)) 

Now, for the benchmark.

user> (def xs (let [rnd (java.util.Random.)]          (long-array (repeatedly 100000 #(.nextLong rnd))))) #'user/xs user> (def ys (long-array xs)) #'user/ys user> (time (qsort ys)) "Elapsed time: 163.33 msecs" #<long[] [J@3ae34094> user> (def ys (long-array xs)) user> (time (jqsort ys)) "Elapsed time: 13.895 msecs" #<long[] [J@1b2b2f7f> 

Performance is worlds apart (an order of magnitude, and then some).

Is there anything I'm missing, any Clojure feature I may have used? I think the main source of performance degradation is when I need to return several values from a loop and must allocate a vector for that. Can this be avoided?

_{BTW running Clojure 1.4. Also note that I have run the benchmark multiple times in order to warm up the HotSpot. These are the times when they settle down.}

Update

The most terrible weakness in my code is not just the allocation of vectors, but the fact that they force boxing and break the primitive chain. Another weakness is using results of loop because they also break the chain. Yep, performance in Clojure is still a minefield.

Answer 1

This version is based on @mikera's, is just as fast and doesn't require the use of ugly macros. On my machine this takes ~12ms vs ~9ms for java.util.Arrays/sort:

(set! *unchecked-math* true) (set! *warn-on-reflection* true)  (defn swap [^longs a ^long i ^long j]   (let [t (aget a i)]     (aset a i (aget a j))     (aset a j t)))  (defn ^long apartition [^longs a ^long pivot ^long i ^long j]   (loop [i i j j]     (if (<= i j)       (let [v (aget a i)]         (if (< v pivot)           (recur (inc i) j)           (do              (when (< i j)                (aset a i (aget a j))               (aset a j v))             (recur i (dec j)))))       i)))  (defn qsort    ([^longs a]      (qsort a 0 (long (alength a))))   ([^longs a ^long lo ^long hi]          (when          (< (inc lo) hi)        (let [pivot (aget a lo)              split (dec (apartition a pivot (inc lo) (dec hi)))]          (when (> split lo)            (swap a lo split))          (qsort a lo split)          (qsort a (inc split) hi)))      a))  (defn ^longs rand-long-array []   (let [rnd (java.util.Random.)]      (long-array (repeatedly 100000 #(.nextLong rnd)))))  (comment   (dotimes [_ 10]     (let [as (rand-long-array)]       (time        (dotimes [_ 1]           (qsort as)))))   ) 

The need for manual inlining is mostly unnecessary starting with Clojure 1.3. With a few type hints only on the function arguments the JVM will do the inlining for you. There is no need to cast index arguments to int for the the array operations - Clojure does this for you.

One thing to watch out for is that nested loop/recur does present problems for JVM inlining since loop/recur doesn't (at this time) support returning primitives. So you have to break apart your code into separate fns. This is for the best as nested loop/recurs get very ugly in Clojure anyhow.

For a more detailed look on how to consistently achieve Java performance (when you actually need it) please examine and understand test.benchmark.

Answer 2

This is slightly horrific because of the macros, but with this code I think you can match the Java speed (I get around 11ms for the benchmark):

(set! *unchecked-math* true)  (defmacro swap [a i j]   `(let [a# ~a          i# ~i          j# ~j          t# (aget a# i#)]      (aset a# i# (aget a# j#))      (aset a# j# t#)))  (defmacro apartition [a pivot i j]   `(let [pivot# ~pivot]      (loop [i# ~i             j# ~j]        (if (<= i# j#)          (let [v# (aget ~a i#)]            (if (< v# pivot#)              (recur (inc i#) j#)              (do                 (when (< i# j#)                   (aset ~a i# (aget ~a j#))                  (aset ~a j# v#))                (recur i# (dec j#)))))          i#))))  (defn qsort    ([^longs a]     (qsort a 0 (alength a)))   ([^longs a ^long lo ^long hi]         (let [lo (int lo)           hi (int hi)]       (when         (< (inc lo) hi)         (let [pivot (aget a lo)               split (dec (apartition a pivot (inc lo) (dec hi)))]           (when (> split lo) (swap a lo split))           (qsort a lo split)           (qsort a (inc split) hi)))       a))) 

The main tricks are:

• Do everything with primitive arithmetic
• Use ints for the array indexes (this avoids some unnecessary casts, not a big deal but every little helps....)
• Use macros rather than functions to break up the code (avoids function call overhead and parameter boxing)
• Use loop/recur for maximum speed in the inner loop (i.e. partitioning the subarray)
• Avoid constructing any new objects on the heap (so avoid vectors, sequences, maps etc.)