Hashlife Computes Repetition Once
Hashlife makes enormous Life simulations practical by recognizing repeated regions and remembering their futures.
A straightforward Life simulator stores cells and advances every location one generation at a time. Hashlife, devised by Bill Gosper in 1984, changes the unit of work. It divides the universe into a tree of square regions and gives identical regions the same stored representation.
Because Life is deterministic, the same region with the same surroundings has the same future. Hashlife caches that result. When the region appears again elsewhere or later, the simulator reuses its computed future instead of replaying every cell update. Nested regions let it skip increasingly large blocks of generations, so regular patterns can be followed absurdly far into the future.
The speed is not universal. Hashlife gains its leverage from repetition and can perform badly on chaotic patterns; Golly’s documentation recommends another engine in those cases. That trade-off matters when viewing a breeder: the visible pattern grows through local rules, while the simulator advances it by recognizing that much of its structure has already happened. Golly is the program that makes that choice of engine practical.