reduce</code> is shown as taking up a large percentage of time. So far we use a very trivial algorithm to detect falling blocks. Profiling shows that the code that detects falling blocks is a bottle-neck and so must be improved. Take a look at the image which shows that 70% of time is spent in the
resolve-grid</code> function called from
step</code> (our game loop function). Drilling into
resolve-grid</code>, we see that most of the time is spent in
create-falling-blocks</code>, and a function it calls
should-block-fall?</code>. This method starts a chain of calls that builds a list of occupied spaces each time it's invoked. <img class="aligncenter size-medium wp-image-4757" alt="profiling_v1.0.3" src="http://jamie.ly/wordpress/wp-content/uploads/2013/04/profiling_v1.0.3-300x175.png" width="300" height="175" /></a> Let's come up with a more efficient algorithm for detecting falling blocks.
Falling</h1> So what does it mean for a block to be falling? A block is falling if there is no block beneath it in the grid. One might create a grid representing the data structure and fill this in, iterating from the bottom up. Another way to do this is to define a block falling recursively.
Recursively</h1> A simple recursive algorithm for knowing if a block is falling in clojure-esque pseudocode [code lang="clojure"] (defn falling? [block] (if (in-bottom-row? block) false (if (nil? (block-below block)) true (falling? (block-below block))))) [/code]
Simplification</h1> This algorithm does not account for garbage blocks, which have special considerations in both falling and determining what the
block-below</code> is. Another simplification is that the grid must be passed in to perform the lookups for blocks that are below the current block. Instead of passing the grid in though, we may want to consider passing in blocks as linked-lists of columns by row. This would fit with the algorithm above. If we pass in lists of columns then we can also reduce the number of checks needed for block-below.
Memoization</h1> One other improvement in performance is to memoize the falling values as we call
falling?</code>. There is a
memoize</code> function built into Clojure. The trick is that we want the function to be memoized but recursive. This is a good StackOverflow question</a> that explains how to create a memoized recursive function. The first answer seems like what we need, but refs don't seem to be supported in clojurescript. Instead, we write our method using the style in the second answer, which requires binding the var to the namespace. Rewriting the example above, we get something like: [code lang="clojure"] (def falling? (memoize (fn [block] (if (in-bottom-row? block) false (if (nil? (block-below block)) true (falling? (block-below block))))))) [/code] Not only is the definition of falling more clearly and elegantly stated, but the memoization should result in greater efficiency.
Results</h1> Rewriting the
create-falling-blocks</code> function to use what we've talked about, yields the following results upon profiling.
<img class="aligncenter size-medium wp-image-4758" alt="profiling_v1.0.4" src="http://jamie.ly/wordpress/wp-content/uploads/2013/04/profiling_v1.0.4-300x161.png" width="300" height="161" /></a></code></pre> We have increased idle % from around 3% in tag v1.0.3 to around 20% in tag v1.0.4, and lowered % time in
create-falling-blocks</code> by around that amount. Anecdotally, v1.0.4 seems smoother than v1.0.3 in Firefox and has better Chrome-performance as well.