Quil draw is extremely slow

[aljones15]

https://forum.processing.org/two/discussion/22937/optimize-my-conway-game-of-life-in-quil-in-clojure

Basically getting less than 1 fps a second on a cellular automata when (time (conway-state s)) is less than a millisecond.

[nbeloglazov]

Hi Andrew. I suspect the problem is with "update" step where you have to calculate new state which involves a lot manipulations and clojure is not particularly effective in these tasks. So you have to explore wonderful world of optimizing clojure code. I suggest you to try using benchmarks libraries like criterium. Measure how long it takes to run update-state.

Looking at your algorithm I think there are some ways to improve it. First of all let's estimate complexity of single update. Let's say you have NxM table. You have N*M cells. And to update each cell you need to find all its neighbors. To find each neighbor you're iterating through all cells so looking up neighbor requires N*M operations. So total complexity of updating cells is:

N*M (updates) * 8 (neighbors) * N*M (cost of finding neighbor) = 8*N^2*M^2

It's not really possible to optimize the first NM because you have to recalculate state of each cell on every update. But we can optimize the getNeighbor to run in O(1) instead of O(NM). For that we need to change the way you store cells. Today you store them as vector, but instead you can store them as map. Instead of:

(def cells [
  {:x 0 :y 0 :alive true} 
  {:x 0 :y 1 :alive false} 
  {:x 1 :y 0 :alive true}
  {:x 1 :y 1 :alive false}])

try following structure:

(def cells {
  [0 0] true
  [0 1] false
  [1 0] true
  [1 1] false})

That way getNeighbor can be written as:

(defn getNeighbor [x y cells]   
  (let [alive? (cells [x y] :none)]
    (if (= alive? :none)
      (rand-nth [true false])
      alive?)))                                                                             

I believe it should drastically improve performance. But try criterium to verify improvements. It is so much fun optimizing code and see execution times go down.

[nbeloglazov]

Hm. I just saw that you checked conway-state execution and got time ~1ms but I still suspect the problem is there. Actually (time (conway-state s)) might not give the result you expect because conway-state returns lazy collection without evaluating it. You should try (time (doall (conway-state s))) instead.

[aljones15]

ok I will try both of those tomorrow. thanks for the update. I was actually using an index based look up before map-indexed then neighbors would (get cells (- index 1) for left etc however in that case I had to make checks for if border cases i.e. to far right or to far left. or on top etc. the new structure looks nice.

[aljones15]

you were right it was the look up data structures I need to spend more time with them thanks. First time I've ever seen it really work. will upload to github soon.