Life, part 15

Code for this episode is here.

Where were we? I was gradually changing Abrash's remember the neighbour counts" into Stafford's algorithm from an early 1990s optimization contest. In this series I'm going to illustrate the algorithm in C#, and we'll conjecture along the way how the performance characteristics are different from the original machine language implementation; I'm more interested in the ideas expressed in the algorithm than the exact implementation details.

So far we've got:

• Each cell takes six bits out of a byte; one for its current state, four for the count of its neighbours, and one to express the new state" for a cell that is changing.
• We create a previous changes" list for use on the next tick; by checking whether the new state" and current state" bits are the same, we make adding to the change list idempotent, and thereby deduplicate it.
• The tick algorithm is O(changed cells).

Dave Stafford's observation was that if we can compress six bits per cell" down to five, then we can store three cells in a 16 bit short. That doesn't sound like a win, but in a few episodes we will see why it is - maybe.

A brief aside: when I ask technical interview questions I always try to base them on a problem I actually had to solve in the real job. Back in the day we needed to make sure that VBScript could work on 64 bit Windows machines; it previously had only been compiled to 16 and 32 bit Windows. (Yes, 16 bit; Internet Explorer ran on Windows 3.1 in 1996 when I started on the scripting team.) We immediately ran into a problem that, full disclosure, I had caused.

You see, VBScript used the VARIANT data structure internally to store data, and VARIANT had an unused 32 bit field in the middle of it that I was using to stash a pointer to some supplemental data. The trouble is: the 64 bit version of VARIANT still only had a 32 bit unused field, so we could not stash a pointer in there anymore. So... now what? That's the problem I had to solve.

The interview question was a simplified version of this scenario, and let me tell you, the number of candidates who tried to store 64 pounds of bits in a 32 pound sack boggled the mind. So I will forgive you if you're skeptical right now that there is a way to compress six bits down to five!

How then to do this impossible thing? The key observation is that the reason we need four bits for the living neighbour count is because there are nine possibilities: zero through eight living neighbours. If we only needed to represent eight possibilities then we could do it in three bits. Without further ado, we're going to store three cells in a 16 bit short like this:

• Call the three cells Left, Middle and Right, or L, M, R for short.
• Bit 15 is unused; the original implementation did wrap around" behaviour and used this bit to store whether the triplet was on an edge or not. I'm going to instead continue to use a surrounding rectangle of death" approach.
• Bits 14, 13 and 12 are the next state" of L, M, and R.
• Bits 11, 10 and 9 are the current state" of L, M and R.
• Bits 8, 7 and 6 are a three-bit integer giving the count of living neighbours of Left that are not Middle; we already know the state of Middle in bit 13.
• Bits 5, 4 and 3 are a three-bit integer giving the count of living neighbours of Middle that are not Right or Left.
• Bits 2, 1 and 0 are similarly the living neighbour count of Right not counting Middle.

And that's how we fit 18 pounds into a 15 pound sack.

As usual in this series and in life, I'm going to make an immutable value type that wraps a short and put all the bit twiddling code in methods of the struct:

struct Triplet{ private short triplet; public Triplet(short triplet) { this.triplet = triplet; } // Bit numbers private const int lnext = 14; private const int mnext = 13; private const int rnext = 12; private const int lcur = 11; private const int mcur = 10; private const int rcur = 9; private const int lcount = 6; private const int mcount = 3; private const int rcount = 0; // Bit masks private const int lnm = 1 << lnext; private const int mnm = 1 << mnext; private const int rnm = 1 << rnext; private const int lcm = 1 << lcur; private const int mcm = 1 << mcur; private const int rcm = 1 << rcur; private const int lcountm = 7 << lcount; private const int mcountm = 7 << mcount; private const int rcountm = 7 << rcount; // Getters and setters // I'm going to want the state as both integers and bools because // I do math on them. public bool LeftNext => (lnm & triplet) != 0; public bool MiddleNext => (mnm & triplet) != 0; public bool RightNext => (rnm & triplet) != 0; public int LeftNextRaw => (triplet & lnm) >> lnext; public int MiddleNextRaw => (triplet & mnm) >> mnext; public int RightNextRaw => (triplet & rnm) >> rnext; public Triplet SetLeftNext(bool b) => new Triplet(b ? (lnm | triplet) : (~lnm & triplet)); public Triplet SetMiddleNext(bool b) => new Triplet(b ? (mnm | triplet) : (~mnm & triplet)); public Triplet SetRightNext(bool b) => new Triplet(b ? (rnm | triplet) : (~rnm & triplet)); public bool LeftCurrent => (lcm & triplet) != 0; public bool MiddleCurrent => (mcm & triplet) != 0; public bool RightCurrent => (rcm & triplet) != 0; public int LeftCurrentRaw => (triplet & lcm) >> lcur; public int MiddleCurrentRaw => (triplet & mcm) >> mcur; public int RightCurrentRaw => (triplet & rcm) >> rcur; public Triplet SetLeftCurrent(bool b) => new Triplet(b ? (lcm | triplet) : (~lcm & triplet)); public Triplet SetMiddleCurrent(bool b) => new Triplet(b ? (mcm | triplet) : (~mcm & triplet)); public Triplet SetRightCurrent(bool b) => new Triplet(b ? (rcm | triplet) : (~rcm & triplet)); // I want to be able to access both the raw bits and the logical count. public int LeftCountRaw => (lcountm & triplet) >> lcount; public int MiddleCountRaw => (mcountm & triplet) >> mcount; public int RightCountRaw => (rcountm & triplet) >> rcount; public int LeftCount => MiddleCurrentRaw + LeftCountRaw; public int MiddleCount => LeftCurrentRaw + RightCurrentRaw + MiddleCountRaw; public int RightCount => MiddleCurrentRaw + RightCountRaw; public Triplet SetLeftCountRaw(int c) { Debug.Assert(0 <= c && c <= 7); return new Triplet((c << lcount) | ~lcountm & triplet); } public Triplet SetMiddleCountRaw(int c) { Debug.Assert(0 <= c && c <= 6); return new Triplet((c << mcount) | ~mcountm & triplet); } public Triplet SetRightCountRaw(int c) { Debug.Assert(0 <= c && c <= 7); return new Triplet((c << rcount) | ~rcountm & triplet); }}

Well, that was a little tedious, but it will make the rest of the code read less like bit twiddling.

You know what, I think that is enough for today; the ideas in Stafford's algorithm are interesting but the amount of code you have to write, as we'll see, it's a lot.

Next time on FAIC: We'll implement the algorithm we have so far - rectangular array of cells, rectangle of death, remembering neighbour counts, change list, store next state in the cell - using the Triplet data structure instead. Unsurprisingly, the added bit twiddling is not cheap; will it pay for itself by unlocking an additional optimization? Stay tuned!

For today's extra content: the prettiest spaceship, the Canada Goose. Image from the wiki.

You'll note that it is a glider that pulls along" a pattern behind it that would not otherwise be a spaceship in itself; this situation is called a tagalong". There are also pushalongs" where the spaceship extension goes in the front.