HashLife in C++23: Simulating Trillions of Generations Instantly

Conway's Game of Life is a classic cellular automaton, but simulating it over trillions of generations is no small feat. Ryan Keane's GOLDE does exactly that, built from scratch in modern C++23. The key: Bill Gosper's HashLife algorithm, implemented with a canonical quadtree and a precomputed base case of 65,536 patterns.

The Quadtree Node

HashLife represents the universe as a quadtree where each node is immutable and canonical. Keane's LifeNode struct uses raw const pointers—safe because the entire tree is never mutated after creation.

struct LifeNode {
    const LifeNode* NorthWest;
    const LifeNode* NorthEast;
    const LifeNode* SouthWest;
    const LifeNode* SouthEast;
    uint64_t Hash;
    bool IsEmpty;
    constexpr LifeNode(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se);
};

Each node caches its hash and emptiness flag, enabling fast lookup and skipping of empty regions. For a glider in empty space, HashLife descends only into nodes with live cells.

Arena Allocator for Pointer Stability

To maintain canonical nodes, Keane uses a bump-pointer arena (LifeNodeArena) that hands out nodes in contiguous blocks. The custom BlockDeleter paired with std::unique_ptr handles memory automatically.

const LifeNode* LifeNodeArena::emplace(const LifeNode* nw, const LifeNode* ne, const LifeNode* sw, const LifeNode* se) {
    if (m_Current == BlockCapacity) {
        auto* raw = static_cast(::operator new(BlockCapacity * sizeof(LifeNode)));
        m_Blocks.emplace_back(raw);
        m_Current = 0;
    }
    auto* node = m_Blocks.back().get() + m_Current++;
    std::construct_at(node, nw, ne, sw, se);
    return node;
}

std::construct_at avoids raw placement new. The entire codebase has only one raw new call.

Precomputing 65,536 Base Cases

The base case is an 8x8 grid (4x4 sub-quadrants). Each 4x4 pattern fits in a uint16_t. Since there are 16 bits, only 65,536 possible patterns exist. GOLDE precomputes the next state for each at startup.

uint16_t WindowCenter(uint16_t nw, uint16_t ne, uint16_t sw, uint16_t se) {
    return ((nw << 10) & MaskNW) | ((ne << 6) & MaskNE) | ((sw >> 6) & MaskSW) | ((se >> 10) & MaskSE);
}

Nine overlapping 4x4 windows are extracted with bitwise ops, looked up in the table, and recombined. Two generations computed in 13 table lookups, zero branching.

Supporting Toroidal Topologies

HashLife assumes an infinite plane. GOLDE supports toroidal (wrap-around) grids by lying to HashLife: before each step, it copies live cells from edges to ghost cells on the opposite side. After the step, ghost cells are discarded. This is abstracted via a Topology interface.

class Topology {
public:
    virtual void PrepareBorderCells(LifeDataStructure& data) = 0;
    virtual void CleanupBorderCells(LifeDataStructure& data) = 0;
    // ...
};

Future topologies like Klein bottles or spheres just need a new subclass.

Arbitrary Step Sizes

HashLife naturally jumps powers of two. To support user-specified steps (e.g., 1000), GOLDE decomposes the step into powers of two and executes them in sequence, using a Log2MaxIncrement method to cap the jump on bounded grids.

Performance and Code Quality

Keane reports that a pattern like the Breeder can jump billions of generations in the time a naive simulator takes for a few hundred. The codebase uses C++23 features like std::construct_at, std::unique_ptr with custom deleters, and constexpr extensively. The result: a fast, safe, and extensible implementation.

What's Next

GOLDE is open-source. Keane plans to add multi-state rules, QuickLife, and more topologies. Developers interested in cellular automata or high-performance C++ should check out the repository.

Article based on Ryan Keane's blog post "Simulating Infinity in Conway's Game of Life with Modern C++"