Annoying things

• An active PS/2 to USB keyboard adaptor that doesn't work with my old :CueCat, so I can't use the :cc with my Mac.
• An old laptop PC with a flaky CDROM drive that refuses to read most OS install media, so I'm stuck with ancient FreeBSD and no wireless support until I can upgrade.
• The :cc's stupid habit of typing Alt+F10 before the encoded barcode data, which occasionally gives Mozilla the heebie-jeebies or even accidentally kills it.
• LibraryThing in overload mode refusing to let me log in again.

On the other hand, one of my old bug reports reminded me how to get a SHARP PC-AR10 working with FreeBSD-4.X without much trouble, and when LT deigns to let me log in its import features are really easy to use.

A little more Hashlife

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...