Editing Hashlife (section)

===Caching and superspeed===
The quadtree can be augmented to in a node also [[memoization|cache]] the result of an update on the contents of that node. There is not enough information in a <math> 2^k \times 2^k </math> square to determine the next timestep contents on the whole of that square, but the contents of a <math> 2^{k+1} \times 2^{k+1} </math> square centered at the same point determine the next timestep contents of the <math> 2^k \times 2^k </math> square. This level ''k'' node for that next timestep is offset by <math>2^{k-1}</math> cells in both the horizontal and vertical directions, so even in the case of [[still life (cellular automaton)|still life]] it would likely not be among the level ''k'' nodes that combine into the <math> 2^{k+1} \times 2^{k+1} </math> square, but at level ''k''–1 the squares are again in the same positions and will be shared if unchanged.

Practically, computing the next timestep contents is a recursive operation that bottom–up populates the cache field of each level ''k'' node with a level ''k''–1 node representing the contents of the updated center <math> 2^{k-1} \times 2^{k-1} </math> square. Sharing of nodes can bring a significant speed-up to this operation, since the work required is proportional to the number of nodes, not to the number of cells as in a simpler representation. If nodes are being shared between quadtrees representing different timesteps, then only those nodes which were newly created during the previous timestep will need to have a cached value computed at all.

'''Superspeed''' goes further, using the observation that the contents of a <math> 2^{k+1} \times 2^{k+1} </math> square actually determine the contents of its central <math> 2^k \times 2^k </math> square for the next <math> 2^{k-1} </math> timesteps. Instead of having a level ''k'' node cache a level ''k''–1 node for the contents 1 step ahead, we can have it cache one for the contents <math>2^{k-2}</math> steps ahead. Because updates at level ''k'' are computed from updates at level ''k''–1, and since at level ''k''–1 there are cached results for advancing <math>2^{k-3}</math> timesteps, a mere two rounds of advancing at level ''k''–1 suffice for advancing by <math>2^{k-2}</math> steps at level ''k''.

In the worst case 2 rounds at level ''k''–1 may have to do 4 full rounds at level ''k''–2, in turn calling for 8 full rounds at level ''k''–3, etc., but in practice many subpatterns in the tree are identical to each other and most branches of the recursion are short. For example the pattern being studied may contain many copies of the same [[spaceship (CA)|spaceship]], and often large swathes of empty space. Each instance of these subpatterns will [[hash function|hash]] to the same quadtree node, and thus only need to be stored once. In addition, these subpatterns only need to be evaluated once, not once per copy as in other Life algorithms. 

For sparse or repetitive patterns such as the classical [[gun (CA)|glider gun]], this can result in tremendous speedups, allowing one to compute ''bigger'' patterns at ''higher'' generations ''faster'', sometimes [[exponential growth|exponentially]]. A generation of the various [[breeder (CA)|breeders]] and [[spacefiller (CA)|spacefillers]], which grow at [[polynomial]] speeds, can be evaluated in Hashlife using [[logarithmic growth|logarithmic]] space and time.

Since subpatterns of different sizes are effectively run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display; they simply advance the starting pattern a given number of steps, and are usually run from the [[command line]]. More recent programs such as [[Golly (program)|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 [[hash function|hashing]] and building the [[quadtree|tree]]; but later, enough data will be gathered and its speed will increase tremendously – the rapid increase in speed is often described as "[[exponential growth|exploding]]".