Intro</h1>
See my previous posts</a> about a Tetris Attack implementation in ClojureScript. The game</a> (as of tag v1.0.3) runs decently on my MacBook Air running Chrome 26. In FireFox 18, the game kind of crawls. Let's try to figure out the problem. I'll be looking at project tag v1.0.3.
Open Chrome DevTools</a>. Navigate to the "Profiles" tab. Refresh the app and select "Collect JavaScript CPU Profile" and click the "Start" button to begin profiling. Use the app for awhile and when you've done some representative tasks, click the red record button (or the "Stop" button) to stop profiling.
Select "Profile 1" and sort by Total %, making sure "Tree (Top Down)" is selected as the view type. I prefer to use this view so that I can drill down the call stack. It's also easier to understand when you have very functional code. For example, if I view the profile in "Heavy (Bottom Up)" mode, then 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.
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.