Reverse Game of Life

This represents the best version yet of my Game of Life engine, delivering a ~10,000x performance improvement over the first naive implementation through bit manipulation and hardware-accelerated computation. Benchmarks regularly hit 158 billion cell updates per second on a laptop-class CPU, and there is still room to experiment.

The engine automatically detects hardware capabilities and picks the optimal SIMD configuration, supporting widths of 4, 8, or 16 parallel operations. It uses configurable generic parameters UltimateEngine<const N: usize> where N represents the SIMD lane count, allowing compile-time optimization for specific targets.

The engine stores 64 cells per u64 integer, achieving 8x memory efficiency compared to byte-per-cell representations. This bit-packing strategy dramatically improves cache performance and enables vectorized operations on large cell groups simultaneously.

Grid layout uses MSB-first bit ordering with strategic padding which eliminates boundary checks during computation, while SIMD alignment ensures optimal memory access patterns. Pre-computed boundary masks handle edge cases efficiently without conditional branching in the hot path.

The engine leverages Rust's portable SIMD to process multiple 64-bit words simultaneously. Custom shift operations shl() and shr() handle cross-lane bit propagation using rotate_elements_left/right with pre-selected masks to maintain bit continuity across SIMD lanes. Using 8 SIMD lanes represents a 512x speedup compared to byte-per-cell representations.

Memory prefetching on x86_64 architectures uses _mm_prefetch with _MM_HINT_T0 to load next rows into L1 cache before processing, reducing memory latency. The engine processes columns in SIMD-aligned chunks, maximizing instruction-level parallelism and minimizing cache misses.

The core sub_step() function implements an optimized full/half adder algorithm for counting neighbors. Rather than iterating through 8 neighbors individually, it uses a two-stage binary tree reduction to compute neighbor counts for all 64 cells in parallel.

Neighbors are grouped into pairs using XOR for sum bits and AND for carry bits and then combined. The Game of Life rules are applied using bitwise operations: center |= ab; center &= b3 ^ b4; center &= !c0; eliminating conditional branching in the hotpath, allowing the vectorization to remain efficient.

Workloads are divided into row blocks that can be processed independently across threads. The scheduler balances work dynamically to avoid idle cores during uneven workloads.

Prefetch distance is tuned per architecture to maximize cache utilization; block sizes are chosen to maintain cache locality while minimizing synchronization overhead between worker threads.

Wasm SIMD is used when supported, providing significant performance improvements in modern browsers. The engine gracefully handles hardware limitations with automatic fallback to scalar implementations, ensuring compatibility across all platforms while maximizing performance on capable hardware.

Because the UI is powered by wasm-bindgen, the same Rust codebase drives both the native solver and the interactive web experience.

Several optimization vectors remain unexplored. Current benchmarks show memory bandwidth saturation as the primary bottleneck, with CPU utilization plateauing at roughly 50% because of DRAM throughput. Future work includes experimenting with alternative memory layouts, smarter software prefetching, and adaptive block sizes tuned per architecture.

The scalar build already handled ~12 million cell updates per second—which is more than enough for the web demo—but this project is an excuse to chase theoretical limits. GPU-backed variants and distributed solving strategies are on the roadmap.

Let $\Sigma = \{0,1\}$. For a finite grid of size $N \times N$, a configuration is a function:

The Game of Life update rule is represented as:

For each cell $(i,j)$:

where the neighbor count is:

Theorem: The decision problem REV-GOL is NP-Complete.

In other words, REV-GOL asks: "Given a Game of Life configuration $c$, does there exist a predecessor configuration $p$ such that applying one step of the Game of Life rules to $p$ produces $c$?"

REV-GOL $\in$ NP: A nondeterministic algorithm can guess a candidate predecessor $p$ and verify in $O(N^2)$ time that $f(p) = c$.

The verification process simply applies the Game of Life rules to each cell in the guessed configuration and checks if the result matches the given configuration.

We reduce from 3-SAT. Each boolean variable is modeled using paired wires that encode its true/false states, and clause gadgets ensure at least one incident literal satisfies the clause.

The reduction ensures the constructed configuration has a predecessor if and only if the original 3-SAT formula is satisfiable.

Variable gadgets propagate signals along synchronized wires so clauses receive consistent timing. Clause gadgets OR the incoming literals and feed a verification grid.

Additional supporting gadgets handle carry propagation and enforce the timing constraints needed for reversible evolution.

Consider the 3-SAT formula:

Clause 1: $(x_1 \lor \neg x_2 \lor x_3)$ is satisfied when at least one of:

Clause 2: $(\neg x_1 \lor x_2 \lor \neg x_3)$ is satisfied when at least one of:

Thus, $c_\varphi$ has a predecessor if and only if $\varphi$ is satisfiable. Since 3-SAT is NP-complete and REV-GOL $\in$ NP, it follows that REV-GOL is NP-complete.

All progress will be posted on my GitHub first before making its way here.