I was read­ing Complexity by M. Wal­drop and I started think­ing about cel­lu­lar automa­ton. One thing led to another and I ended up build­ing an instance of Conway’s Game of Life in the browser. I wrote it in Clo­jure­script and if fea­tures the abil­ity to step for­ward and back­wards through sequence, as well as detect end states with some basic cycle detec­tion. It runs in near real­time which was a bit of a feat as Con­way’s Game of Life is a rather CPU inten­sive appli­ca­tion to run a real­time for a pat­tern of any real size. It’s still not quite as fast as a good GoL imple­men­ta­tion should be, but I feel like this appli­ca­tion nev­er­the­less rep­re­sents a bit of a case study of a per­for­mance inten­sive appli­ca­tion writ­ten in Clojurescript.

Initial flailing

When I wrote the appli­ca­tion ini­tial­ly, I took the naive route and rep­re­sented the grid as a sequence of booleans, each rep­re­sent­ing a cell (true for alive, of course). A sec­ond vari­able was used to rep­re­sent the width of the grid. One could find the index for cell [x y] with the for­mula x+grid-width*y. To update the grid, I looped over the sequence with the for macro and looked up the count for adja­cent live cells for each cell. All in all, it was very simple:

(def ^:dynamic *world-width* 25)

(defn get-index [position]
  "Given x and y coordinates, return the index in the grid array
  that corresponds to those coordinates."
  (let [{x :x y :y} position]
    (+ x (* y *world-width*))))

(defn get-position [index]
  "Converts a position into x and y coordinates"
  {:x (mod index *world-width*)
   :y (int (/ index *world-width*))})

(defn adjacent-life [index world]
  "Returns a count of the live cells adjacent to the cell at index"
  (let [xmax (dec *world-width*)
        ymax (int (/ (dec (count world)) *world-width*))
        {x :x y :y} (get-position index)]
    (reduce +
            (for [xo (range -1 2)
                  yo (range -1 2)
                  :let [i (get-index {:x (+ x xo) :y (+ y yo)})]
                  :when (and (not (= i index))
                             (<= 0 (+ x xo) xmax)
                             (<= 0 (+ y yo) ymax))]
              (if (nth world i) 1 0)))))

(defn pass-generation [world]
  "Returns a new iteration of the world according to the rules of
  life."
  (for [index (range (count world))]
    (if (nth world index)
      (case (adjacent-life index world)
        (0 1 4 5 6 7 8) false
        (2 3) true)
      (= 3 (adjacent-life index world)))))

This approach turned out to be painfully slow. I actu­ally thought that there was a bug in the code at first as Fire­fox would dis­play the “slow script” box before the first iter­a­tion would dis­play. I was not sur­prised that the naive approach would be too slow for my purposes; I had antic­i­pated need­ing to opti­mize it, but I sur­prised at how slow it would actu­ally be.

The first things I tried were some sim­ple per­for­mance enhance­ments. I replaced the Clo­jure sequence with a Javascript array by call­ing into-array at every iter­a­tion and that helped. I shrank the size of the grid and that helped as well. I even­tu­ally unrolled the loop in which I looked for adja­cent live cells and that actu­ally made the appli­ca­tion almost bear­able, but it was still very slow.

(defn adjacent-life [index world]
  "Returns a count of the live cells adjacent to the cell at index.
  (Unrolling the internal loop of this function speeds it up immensely.)"
  (let [xmax (dec *world-width*)
        ymax (dec *world-height*)
        {x :x y :y} (get-position index)
        decx (dec x)
        decy (dec y)
        incx (inc x)
        incy (inc y)]
    (+ (if (and (<= 0 decx xmax)
                (<= 0 decy ymax)
                (nth world (get-index {:x decx :y decy})))
         1 0)
       (if (and (<= 0 incx xmax)
                (<= 0 incy ymax)
                (nth world (get-index {:x incx :y incy})))
         1 0)
       (if (and (<= 0 decx xmax)
                (<= 0 incy ymax)
                (nth world (get-index {:x decx :y incy})))
         1 0)
       (if (and (<= 0 incx xmax)
                (<= 0 decy ymax)
                (nth world (get-index {:x incx :y decy})))
         1 0)
       (if (and (<= 0 decx xmax)
                (nth world (get-index {:x decx :y y})))
         1 0)
       (if (and (<= 0 incx xmax)
                (nth world (get-index {:x incx :y y})))
         1 0)
       (if (and (<= 0 decy ymax)
                (nth world (get-index {:x x :y decy})))
         1 0)
       (if (and (<= 0 incy ymax)
                (nth world (get-index {:x x :y incy})))
         1 0))))

(defn pass-generation [world]
  "Returns a new iteration of the world according to the rules of
  life."
  (into-array
   (for [index (range (count world))]
     (if (nth world index)
       (case (adjacent-life index world)
         (0 1 4 5 6 7 8) false
         (2 3) true)
       (= 3 (adjacent-life index world))))))

Search­ing around the web for some typ­i­cal GoL algo­rithms revealed some inter­est­ing results. Some approach­es, such as the Hashlife algorithm were not prac­ti­cal in Javascript as the mem­o­iza­tion required would actu­ally be too slow with­out some seri­ous work. I did try a trick of incre­ment­ing/decre­ment­ing the adja­cency counts when cells came to life or died rather than count­ing the num­ber of adja­cent live cells for each cell each iter­a­tion and that helped immense­ly, but the appli­ca­tion was still too slow.

The final algorithm

The algo­rithm I even­tu­ally set­tled on was actu­ally very simple: I main­tained two sets, one was a list of live cell coor­di­nates and the other was a list of active cell coor­di­nates. The active cells were cells whose state might change dur­ing the next iter­a­tion. Usu­ally this meant that they were adja­cent to a cell whose states had dur­ing changed this iter­a­tion. I’d loop over the active cell list and query the live cell list to find the num­ber of adja­cent cells each time.

(def ^:dynamic *world-width* 50)
(def ^:dynamic *world-height* 40)

(defn adjacent-life [index life]
  "Returns a count of the live cells adjacent to the cell at index"
  (let [xmax (dec *world-width*)
        ymax (dec *world-height*)
        [x y] index
        decx (dec x)
        decy (dec y)
        incx (inc x)
        incy (inc y)]
    (+ (if (contains? life [decx decy])
         1 0)
       (if (contains? life [incx incy])
         1 0)
       (if (contains? life [decx incy])
         1 0)
       (if (contains? life [incx decy])
         1 0)
       (if (contains? life [decx y])
         1 0)
       (if (contains? life [incx y])
         1 0)
       (if (contains? life [x decy])
         1 0)
       (if (contains? life [x incy])
         1 0))))

(defn set-active [index active]
  "Add the cells surrounding the cell at index to the set
  of active cells."
  (let [xmax (dec *world-width*)
        ymax (dec *world-height*)
        [x y] index
        decx (dec x)
        decy (dec y)
        incx (inc x)
        incy (inc y)]
    (reduce conj! active
            [[decx decy]
             [incx incy]
             [decx incy]
             [incx decy]
             [decx y]
             [incx y]
             [x decy]
             [x incy]])))

(defn pass-generation [world-adj]
  "Returns a new iteration of the world according to the rules of
  life."
  (let [world (first world-adj)
        active (second world-adj)]
    (loop [indexes active
           nworld (transient (first world-adj))
           nactv (transient #{})]
      (if (not-empty indexes)
        (let [index (first indexes)]
          (let [adjacencies (adjacent-life index world)]
            (if (contains? world index)
              (if (or (= 2 adjacencies)
                      (= 3 adjacencies))
                (recur (rest indexes) nworld nactv)
                (recur (rest indexes)
                       (disj! nworld index)
                       (set-active index nactv)))
              (if (= 3 adjacencies)
                (recur (rest indexes)
                       (conj! nworld index)
                       (set-active index nactv))
                (recur (rest indexes) nworld nactv)))))
        (vector (persistent! nworld)
                (persistent! nactv))))))

This approach had sev­eral advan­tages. The first was that the grid was the­o­ret­i­cally infinite. There was no prob­lem with edges inter­fer­ing with the game or with a pat­tern inter­fer­ing with itself in a toroidally wrapped grid. The sec­ond was that empty space and still lifes would passed over and skipped. This was actu­ally very fast, still not fast enough, but get­ting there. The one remain­ing detail was to per­form some opti­miza­tions by chang­ing the datas­truc­tures used from Clo­jure ones to native Javascript ones which are much faster.

It’s pos­si­ble to use a Javascript object as a set by using the para­me­ter names as mem­bers and set­ting para­me­ters to true or remov­ing them alto­gether based on mem­ber­ship in the set being mod­eled. It turns out that this is faster than the Clo­jure script Hash­set or Hashmap datatypes. Javascript objects do have the dis­ad­van­tage that they are muta­ble, but I was already using tran­sients for a speed improve­ment any­way. Mak­ing a copy of each object at each iter­a­tion and mod­i­fy­ing the new ver­sions in place was a lot faster than either using the immutable or tran­sient Clo­jure­script datas­truc­tures. In one sense this should­n’t be sur­pris­ing as the Clo­jure­script struc­tures are con­structed out of the Javascript ones and imple­ment a lot func­tion­al­ity on top of them. On the other hand, it’s rather dis­ap­point­ing to real­ize that you might have to break out of the com­fort zone of pure Clo­jure when writ­ing per­for­mance code in Clo­jure­script.

The ultimate performance tip

I don’t usu­ally write a lot of client side code so this is the first time I’ve used a pro­filer on Javascript code, but that was the most impor­tant thing in get­ting this appli­ca­tion as fast as it is. Fire­fox has a built in Javascript pro­filer which was actu­ally amaz­ingly use­ful. Most of the impor­tant per­for­mance improve­ments I imple­mented were because the pro­filer told me that the appli­ca­tion was spend­ing an inor­di­nate amount of time doing some­thing that should have been quick. So the first time I unrolled the inner loop, switch­ing from Clo­jure sets to Javascript objects, and chang­ing the cell rep­re­sen­ta­tion from a pair to a sin­gle inte­ger were all moti­vated by pro­filer infor­ma­tion.

Summary

There are still some improve­ments that I’d like to make to this GoL imple­men­ta­tion. The first is that there still is some sig­nif­i­cant slow­down, mainly in the graph­i­cal aspect. I’m using D3.js rather than can­vas which is ulti­mately a mis­take per­for­mance wise. The abil­ity cre­ate the start­ing pat­terns is still inad­e­quate. Only tog­gling indi­vid­ual cells is sup­ported and the selec­tor isn’t very easy to use. I’d like to cre­ate a library of com­mon pat­terns. Also, I’d like to be able to read the pat­tern from html para­me­ters. Maybe I’ll come back to this later and fix these things but I’m done for now.