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.
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.
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.
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)))))
This algorithm does not account for garbage blocks, which have special considerations in both falling and determining what the
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.
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.
create-falling-blocks function to use what we’ve talked about, yields the following results upon profiling.
create-falling-blocksby around that amount.
Anecdotally, v1.0.4 seems smoother than v1.0.3 in Firefox and has better Chrome-performance as well.