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.

Really Liking Ruby

class Node

  def initialize(label, left, right)
    @label  = label
    @left   = left
    @right  = right
  end

  attr_accessor :label, :left, :right

  def breadth_first
    unvisited = [self]

    while not unvisited.empty?
      node = unvisited.shift

      yield node

      unvisited << node.left if node.left
      unvisited << node.right if node.right
    end
  end

end

Migrated west until I hit an ocean. From the bayou to Houston to Austin. Skipped the desert and hit a beach. Cold as all hell up the foothills. I-10 always the closest thing to a home I had. Until I ran out of mile markers and there’s only east to go.

Jurassic Park

MALCOLM
The problem with scientific power you’ve used is it didn’t require any discipline to attain it. You read what others had done and you took the next step. You didn’t earn the knowledge yourselves, so you didn’t take the responsibility for it. You stood on the shoulders of geniuses to accomplish something as fast as you could, and before you knew what you had, you patented it, packaged it, slapped it on a plastic lunch box, and now you want to sell it.

HAMMOND
You don’t give us our due credit. Our scientists have done things no one could ever do before.

MALCOLM
Your scientists were so preoccupied with whether or not they could that they didn’t stop to think if they should. Science can create pesticides, but it can’t tell us not to use them. Science can make a nuclear reactor, but it can’t tell us not to build it!

Worst Line of Code and Why

I needed to grab the latest Link object for a certain Forum from Django’s ORM.

Normally, I’d do this with:

link = forum.link_set.order_by('-id')[0]

But for some reason, adding the slice (which adds a limit to the SQL query), was considerably slowing down the call. Whereas, just getting the iterator was fine.

link_qs = forum.link_set.order_by('-id')

Which is disturbing. I haven’t figured out why, but I wanted to get the code I was working on done before figuring out why this query was slow, so I hacked around it.

So, of course, I could just convert that QuerySet to a list and index the list with:

link = list(forum.link_set.order_by('-id'))[0]

But that would load the entire result into memory. My results could potentially be extremely large, so I didn’t want to go down that route.

So I wrote the obvious solution, using the iterator, but only saving the first result. Which turned out to be one of the worst lines of code I’ve ever written.

In all it’s glory:

for link in forum.link_set.order_by('-id'):
    break