Post-Rice Haze

Dead Simple Concurrency with Clojure

Concurrency is hard. In an environment where processors don’t get faster, we just get more of them, concurrency is going to get more important. We’ll take these as givens.

Enter Clojure. Promising a vast array of interesting features promising to make concurrency easier.

So in my attempts to learn the language, my goal was to get something running concurrently as quickly as possible. I started with merge sort.

(use 'clojure.contrib.seq-utils)

; merge side of the merge sort. naive tail recursive solution.
(defn ms-merge [left right]
  (loop [head [] l left r right]
    (if (empty? l) (concat head r)
      (if (empty? r) (concat head l)
        (if (> (first l) (first r))
          (recur (conj head (first r)) l (rest r))
          (recur (conj head (first l)) (rest l) r))))))

; split side of the merge sort. naive recursive solution.
(defn naive-merge-sort [l]
  (if (< (count l) 2) l
    (apply ms-merge (map naive-merge-sort (split-at (/ (count l) 2) l)))))

This naive solution is slow and clearly doesn’t use both my cores.

With a total running time of 21.98s to sort a shuffled list of 1M integers.

From here, I split the process between my cores.

; wrapper around merge sort that just delegates both sides
; to threads running the naive solution.
(defn parallel-merge-sort [l]
  (apply ms-merge (pmap naive-merge-sort (split-at (/ (count l) 2) l))))

The approach is just to split the input in half and sort both sides in different threads. This is trivial to do using pmap. The end job of merging these two together is easy enough and tail-recursive, so the downside of running the merge on just a single thread is less than you think (roughly 0.9% of total processing time).

And with a total running time of 16.25s to sort a shuffled list of 1M integers.

In this, I don’t use Clojure’s key win, STM, just the pmap syntactic sugar around managing multiple threads, so I’m only getting a little benefit from Clojure.

Also, this only splits the task into two parts, therefore only making use of at most two cores. Not a completely portable solution.

But the fact that my “hello world” in a new language uses both my cores this easily, is impressive.