the (k+1)-th level compared to one at the kth. For sparse or repetitive patterns such as the classical glider gun, this can result in tremendous speedups, allowing one to compute bigger patterns at higher generations faster, sometimes exponentially. To take full advantage of this feature, subpatterns from past generations should be saved as well. Since different patterns are allowed to run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display, but simply compute a preset result for a starting pattern, usually run from the command line. More recent programs such as Golly, however, have a graphical interface that can drive a Hashlife-based engine. The typical behavior of a Hashlife program on a conducive pattern is as follows: first the algorithm runs slower compared to other algorithms because of the constant overhead associated with hashing and building the tree; but later, enough data will be gathered and its speed will increase tremendously – the rapid increase in speed is often described as "exploding". Drawbacks Like many memoized codes, Hashlife can consume significantly more memory than other algorithms, especially on moderate-sized patterns with a lot of entropy, or which contain subpatterns poorly aligned to the bounds of the quadtree nodes (i.e. power-of-two sizes); the cache is a vulnerable component. It can also consume more time than other algorithms on these patterns. Golly, among other Life simulators, has options for toggling between Hashlife and conventional algorithms. Hashlife is also significantly more complex to implement. For example, it needs a dedicated garbage collector to remove unused nodes from the cache. Due to being designed for processing generally predictable patterns, chaotic and explosive rules generally operate much more poorly under Hashlife than they would under other implementations. See also Purely functional data structure, of which the hashed quadtree is one Hash consing, which was the key strategy used in the original implementation of Hashlife. References External links HashLife from Eric Weisstein's Treasure Trove of Life Tomas Rokicki's implementation of hashlife Entry in the Life Lexicon Explanation of the algorithm from Dr. Dobb's Journal Gosper's Algorithm (Hashlife) Explained Cellular automaton software