Like a ton of bricks!

If I could get four cells into 15 bits could I somehow get five into 16 bits? At this point anything seemed possible. The key would be to find a way to further reduce the neighbor counts. I thought about all sorts of arrangements of cells: diamonds, stars, l-shapes. I even considered mixing different arrangements together so there would be clusters of different shapes that tiled perfectly. You may laugh but it became helpful to look at floor tile patterns and brick walls so I could super-impose ideas over them.

Nothing quite worked. The diamond pattern was the best candidate but it required at least 17 bits (and that was if I dropped the edge bit.) I kept trying anyway. You can almost always find a wall to stare at.

Then it hit me. I had been so dumb! The answer was right in front of me!

My life grid was laid out like a simple matrix where every 2x2 group of cells was clustered in a 16-bit word. Each cluster has eight neighbors- perfectly and neatly aligned.

But a brick wall is staggered so every brick has only six neighbors! I had blown it all along! Why hadn't I thought of this before? Six neighbors instead of eight is a significant improvement!

I can update the upper and lower blocks with one 32-bit operation. Checking neighbors to see if they need to go into the change-list is now 25% faster. This would have been a big speedup for the original Qlife. It will make the new version much faster.

Why couldn't I see this sooner? I was stuck in the rut of thinking like a programmer thinks about matrices. It wasn't until I opened my mind to consider tiling other shapes that I could conceive of it.

This optimization leads to other ideas. The old Qlife handled each possible state change with a unique subroutine. It might not be necessary to do that anymore since checking and updating neighbors just got cheaper. If you can get away from special-casing each update you'll get better cache behavior. It's something to think about.


On to Part 8. Final thoughts

Back to the main page