> it did just occur to me that a HashSet could be used, which would save a small amount of memory without introducing the performance issue. I was indeed think

> it did just occur to me that a HashSet could be used, which would save a small amount of memory without introducing the performance issue. I was indeed thinking of keeping the "occupied" coordinates in a set-like structure. Not sure how a boolean is stored - is it 8 bits, or a single bit? Either way, just storing two (eg) 64 bit coordinates should trivially align (ish)? The trick would be to quickly be able to go over all occupied cells and their neighbors in order to build "tomorrow's" board. I suppose the new board might serve as a cache/state helper of sorts, but I think the logic would have to be a bit more complicated. Maybe it's possible to go from a 1d algorithm to a 2d one by making sure there's a list of occupied cells sorted by their place on a Hilbert curve? My intuition tells me it's simpler to go center out, than row-by-row (if we store only occupied cells, we need to deal with the empty row "above" our first occurrence somehow - it might be easier to "push" out). I'd probably have to try and sketch this out on paper though :) At any rate, I just immediately though storing sn extra dead/alive bit seemed a bit redundant and possibly alignment unfriendly if only "really" needed a list/set of occupied cells. But perhaps the most pragmatic way of changing just the data structure (and more or less keep the algorithm (with the caveat that I haven't actually looked at the code!))- would be to split each generation in two - a list of live and list of dead cells - each accessible via their coordinates in a quick manner.