Tony Finch – blog

In my post about Hashlife I said that calc1() "is not memoized, but instead relies on calc2() for efficiency". This is wrong.

[calc1() is the function that calculates an arbitrary number of generations into the future; calc2() is the function that calculates 2^(n-2) generations into the future for a square 2^n cells on a side, and its result is cached in the main quadtree.]

Calculating Life efficiently requires skipping over the easy bits as fast as possible, which in most implementations is blank space, but in Hashlife it ought to include any other kind of previously-computed space too. However calc1() can only skip large amounts of space if it is also skipping large amounts of time - a multiple of a large power of two, to be exact. This means that if you are single-stepping, my Hashlife code would separately examine every 4x4 square in the universe. This is particularly dumb when there is inevitably lots of blank space around the edges.

The solution is to memoize the calculation for arbitrary numbers of generations (or at least for 1 <= g <= n^(n-2) for squares 2^n on a side). If you do that, it no longer makes sense to store the result pointers in the squares themselves: instead, bung them all in another hash table that is indexed by the pair of a square and a generation count. Having done that, it also makes sense to evict the population counts from the squares into a third hash table, since they are rarely needed so just waste memory.

The other Hashlife implementations that I was cribbing off do not have this extra cacheing. I wonder if that is why Hashlife has a poor reputation for efficiency? I'll have to do some more implementation to find out.

While I'm here, I should say that David Bell's equivalent of calc1() is interesting because it only examines the past light cone of the region that is being displayed, which saves working on irrelevant far-away areas - though he spoils it by re-doing the recursion for every pixel to be displayed...