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.)

Answer 3

The Joy of Clojure, Chapter 6.4 describes a lazy quicksort algorithm.The beauty of lazy sorting is that it will only do as much work as necessary to find the first x values. So if x << n this algorithm is O(n).

(ns joy.q)

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

(defn qsort [xs]
    (sort-parts (list xs))) 

Answer 4

By examining the main points from mikera's answer, you can see that they are mostly focused on eliminating the overhead introduced by using idiomatic (as opposed to tweaked) Clojure, which would probably not exist in an idiomatic Java implementation:

• primitive arithmetic - slightly easier and more idiomatic in Java, you are more likely to use ints than Integers
• ints for the array indexes - the same
• Use macros rather than functions to break up the code (avoids functional call overhead and boxing) - fixes a problem introduced by using the language. Clojure encourages functional style, hence a function call overhead (and boxing).
• Use loop/recur for maximum speed in the inner loop - in Java you'd idiomatically use an ordinary loop (which is what loop/recur compiles to anyway, as far as I know)

That being said, there actually is another trivial solution. Write (or find) an efficient Java implementation of Quick Sort, say something with a signature like this:

Sort.quickSort(long[] elems)

And then call it from Clojure:

(Sort/quickSort elems)

Checklist:

• as efficient as in Java - yes

• idiomatic in Clojure - arguably yes, I'd say that Java-interop is one of Clojure's core features.

• reusable - yes, there's a good chance that you can easily find a very efficient Java implementation already written.

_{I'm not trying to troll, I understand what you are trying to find out with these experiments I'm just adding this answer for the sake of completeness. Let's not overlook the obvious one! :)}