4 Memoizing immutable quadtrees to make a better Life

The chapter introduces Conway’s Game of Life as a simple but surprisingly rich cellular automaton, then uses it as a playground for exploring better representations and faster algorithms. It starts with the basic rules for births, survival, and death, showing classic patterns like still lifes, oscillators, and gliders, and emphasizes that the real goal is not the game itself but the algorithmic thinking behind it. From there, it contrasts a straightforward array-based implementation with more advanced approaches, making the broader point that performance can improve either by tuning an existing method or by reframing the problem entirely.

The first implementation stores the world in a fixed rectangular grid and computes each tick by scanning every cell, counting neighbors, and writing the next state into a second array before swapping. This version is easy to understand and reasonably fast, especially with small optimizations like a dead border, byte storage instead of booleans, and the use of SIMD or GPU hardware, but it remains fundamentally linear in the number of cells. The chapter then sketches a more selective strategy based on change tracking: if a region is empty or stable and surrounded by dead cells, it can be skipped, reducing work to the active part of the grid instead of the whole board.

The main contribution is the HashLife approach, which models the board as an immutable quadtree and uses memoization to deduplicate identical substructures. Because quads are immutable and repeatedly recurring patterns can be shared, memory use depends more on irregularity than on raw grid size, and a general memoizer lets the implementation cache both quad construction and stepping results. The recursive stepping algorithm exploits the fact that larger quads contain enough information to predict the future of their centers, then combines those results to advance by powers of two ticks at a time. Although naïve memoization can create huge caches and memory pressure, the chapter shows that in practice the method can become extraordinarily fast for Life patterns that settle into repeated structure, ultimately approaching constant-time stepping on stable worlds.

Death from loneliness: every cell will be dead in two ticks. Dark cells are alive; light cells are dead.

 The block, beehive, pond, tub, boat, and snake are unchanging still lifes.

The blinker is the simplest oscillator.

The first spaceship

 A 2-quad consists of four 1-quads, but there are only two 0-quads.

We can get away with reusing one of the 1-quads, slightly reducing the memory burden.

 A 1-quad is indexed from −1,−1 in the southwest corner to 0,0 in the northeast corner. A 2-quad is indexed from −2,−2 in the southwest corner to 1,1 in the northeast corner. The coordinates of the central cells are always the same for quads with more than one cell.

A 2-quad is “embiggened” so that we have a 3-quad with the cells of the 2-quad in its center. Notice what happens to the northeast portion of the 2-quad when we place it in the 3-quad.

 If we’re given only a 2-quad and want to step it ahead one tick, we know only what the 1-quad at its center will be next. Cells are labeled with the variable names that represent them in the code in listing 4.8.

 Given a 3-quad, we can extract nine 2-quads from it and step each of them forward one tick to get nine 1-quads one tick in the future.

 Given nine 1-quads all one tick in the future, we can form them into four 2-quads. We take the center 1-quad from each of those four 2-quads and use them to build a 2-quad that’s the center of the original 3-quad one tick in the future.

 Given nine 1-quads, all one tick in the future from the original 3-quad, we can form them into four 2-quads. Instead of simply taking their centers, we step each of those 2-quads forward one tick. That gives us a 1-quad from each 2-quad, and from them, we build a 2-quad that’s the center of the original 3-quad two ticks in the future, not one.

• The specific problem we looked at in this chapter is recreational, not practical. I’ve never had to evolve a cellular automaton trillions of generations to solve an on-the-job problem. Fun is a good enough reason to do anything.
• The techniques we used in this chapter deeply affected my work, however. I’ve have often used memoization as a technique for deduplicating complex data structures and trading cache space for improved performance. I’ve also had to consider how to tune the performance of those caches to ensure they don’t become memory leaks.
• Most important, learning about the HashLife algorithm got me into the habit of asking whether I can use any aspect of the specific problem to advantage when designing an algorithm. It reminds me to look for frame-changing attacks on problems when incremental improvements on existing algorithms have gone as far as they productively can.

FAQ