Intro
See my previous posts about a Tetris Attack implementation in ClojureScript. The game (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. 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 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 function called from step (our game loop function). Drilling into resolve-grid, we see that most of the time is spent in create-falling-blocks, and a function it calls should-block-fall?. This method starts a chain of calls that builds a list of occupied spaces each time it’s invoked.
Let’s come up with a more efficient algorithm for detecting falling blocks.
Falling
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
A simple recursive algorithm for knowing if a block is falling in clojure-esque pseudocode
(defn falling? [block]
(if (in-bottom-row? block)
false
(if (nil? (block-below block))
true
(falling? (block-below block)))))
Simplification
This algorithm does not account for garbage blocks, which have special considerations in both falling and determining what the block-below 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
One other improvement in performance is to memoize the falling values as we call falling?. There is a memoize function built into Clojure. The trick is that we want the function to be memoized but recursive. This is a good StackOverflow question 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:
(def falling?
(memoize (fn [block]
(if (in-bottom-row? block)
false
(if (nil? (block-below block))
true
(falling? (block-below block)))))))
Not only is the definition of falling more clearly and elegantly stated, but the memoization should result in greater efficiency.
Results
Rewriting the create-falling-blocks function to use what we’ve talked about, yields the following results upon profiling.
create-falling-blocks by around that amount.
Anecdotally, v1.0.4 seems smoother than v1.0.3 in Firefox and has better Chrome-performance as well.