lifelib
lifelib is a collection of header files for simulation and manipulation of patterns in cellular automata. Examples of programs heavily reliant on lifelib are apgluxe, slmake, Shinjuku, Skopje and HoneySearch.
The code is written in C++11 and inline x86_64 assembly code, with a Python script for code generation. As such, it can be included in C++ programs running on machines with x86_64 CPUs, and is compatible with Linux, Mac OS X, and Windows (via Cygwin).
Iterators
The main iterator implemented in lifelib is ulife. This uses a backend, which is a function to operate on a 32 × 32 square of cells and return the 16 × 16 centre after applying a cellular automaton, and a container, which dictates how the backend should be invoked in order to simulate an arbitrary pattern. Backends are inherently rulespecific, whereas containers are ruleagnostic. There are two containers which are compatible with ulife, namely the HashLifebased pattern and the more conventional upattern.
The vlife iterator is also supported for the upattern, facilitating a slight performance improvement over ulife for chaotic patterns in 2state range1 cellular automata.
Data structures
lifelib introduces three data structures for storing patterns, namely pattern, upattern, and bitworld. The first two of these are ulifecompatible containers capable of simulation of multistate patterns; the bitworld can only be used for storage and editing of 2state patterns.
Patterns and lifetrees
The pattern is the most powerful and useful container, representing a finite set of cells on an infinite plane. Instead of storing its contents within the object, the object merely refers to a node in an external structure known as a lifetree. This means that regular patterns are highly compressed, copying a pattern is a fast O(1) operation, and similar patterns share much of the same space in memory. Patterns can be moved (or coerced) between lifetrees, but this takes time O(L), where L is the length of the macrocell encoding of the pattern.
Patterns are implemented in such a way that they can be used as immutable data structures; running a pattern returns an advanced copy of the object, rather than modifying the original object. They support editing operations such as shifting, rotation/reflection, boolean operations, and Kronecker products. Advancing a pattern uses a HashLifeinspired algorithm, falling back on the ulife iterator for the base case of returning the 16 × 16 centre of a 32 × 32 quartet of leaves. There is a further optimisation for oscillators and spaceships of a known period p: instead of advancing by N generations, it advances the pattern by N modulo p, translating by the appropriate amount if the pattern is a spaceship. This means that a periodic pattern can sensibly be "advanced" by a negative number of generations, which is particularly useful for building glider streams.
A lifetree is a garbagecollected container which represents a collection of unique 2^{n} × 2^{n} square tiles ('nodes') as pointers to their children, with a base case of 16 × 16 'leaves' stored directly. If a node is not part of a pattern, and the memory of the lifetree steps over a userdefined threshold, the node will be deleted in a garbage collection step to save memory. Lifetrees do not support concurrency, so taking advantage of multicore architectures (as in apgsearch) requires using one lifetree per CPU core.
The 'HashLife memory' is stored in the lifetree, so multiple patterns sharing a lifetree will naturally take advantage of each others' memoized computations. This means that after running a piheptomino, it will take less time to subsequently run a house.
Uncompressed patterns
The upattern is implemented as a collection of overlapping 32 × 32 square tiles, as in Life128 and its relatives. The tiles overlap in such a way that the disjoint centres are either 28 × 28 (if the upattern is designed to run vlife), or 16 × 16 (if the upattern is designed to run ulife). It is slightly faster than the original implementation of vlife, owing to using an std::unordered_map instead of an std::map as its underlying data structure. Unlike the pattern container, a upattern stores its data internally and does not perform any compression. However, it keeps track of which tiles need to be updated, taking advantage of stable and period2 tiles. Although it is chiefly designed for an infinite plane, it can run a toroidal universe equally quickly.
The bitworld is simply a container for a finitelysupported blackandwhite image, with support for basic editing operations and the retrieval of connected clusters of cells. Vectors of bitworlds are also used for converting between the pattern and upattern datastructures, conversion from RLE, and the determination of apgcodes.
StreamLife
Lifelib contains a variant of a lifetree, called a streamtree, which implements a new algorithm called StreamLife. This is based on Hashlife, but is tailored to handle antiparallel streams of gliders and standard spaceships. As such, it can gain a significant speed boost on certain patterns such as the Demonoid and Orthogonoid. The additional calculations mean that StreamLife tends to be slower on other patterns, so the regular lifetree is almost always preferable. StreamLife is only available for Lifelike cellular automata.
Comparison of data structures
The salient differences between the data structures are summarised below:
pattern  upattern  bitworld  
Data representation  Hashed quadtree  Unordered map  Ordered map 
Data location  External (in a lifetree)  Internal  Internal 
Number of layers  Arbitrary  Arbitrary  1 
CA algorithms  HashLifebased  vlifebased  None 
Compatible iterators  ulife  ulife, vlife  None 
Algorithm optimisations  Regular patterns  stable/p2 ash  None 
Supported topologies  Infinite plane  Torus, infinite plane  Infinite plane 
Editing features  Advanced  None  Basic 
Maximum radius  2^{4 000 000 000}  32 000 000 000  16 000 000 000 
Backends
Backends are created at compiletime by Python modules called genera. These generate C++ and x86_64 assembly code for a given rule, using specialised SIMD instructions to gain a performance advantage. A Python script (called rule3asm.py) decides which of the genera are appropriate for the given rules, calls them, and builds linking code.
There are 17 genera as of version ll2.18. These include the following six 2state families:
 lifelike: An implementation of arbitrary Lifelike cellular automata using SSE2/AVX/AVX2 instruction sets, choosing a Boolean circuit from a precomputed table;
 isotropic: A lookuptable approach for simulating nonB0 isotropic nontotalistic cellular automata;
 ltl: A vectorised implementation of Larger than Life, supporting a maximum range of 7;
 hrot: An implementation of higher range outertotalistic rules, supporting a maximum range of 5;
 isotropichexot: An implementation of outertotalistic hexagonal neighbourhood rules;
 isotropichex: An implementation of isotropic nontotalistic hexagonal rules.
Next, there are Generations analogues of the above, with little overhead over the 2state counterpart, giving another six genera:
 generations (currently does not support B0 rules, unlike the 2state counterpart);
 isogeny (isotropic generations);
 gltl (Larger than Life + Generations).
 ghrot (Higherrange outertotalistic + Generations).
 isogenyhexot (hexagonal Generations).
 isogenyhex (isotropic hexagonal Generations).
Additionally, there are four genera with more than 2 states which do not fit into the Generations category:
 bsfkl: An implementation of Brian Prentice's BSFKL rules.
 deficient: An implementation of 83bismuth38's Deficient rules.
 genext: An implementation of M. I. Wright's Extended Generations rules.
 eightbit: An implementation of custom rule files using Golly formats.
Finally, Tom Rokicki mentioned that Conway's Game of Life can be computed in 19 Boolean operations (amortized), whereas the generic lifelike approach requires 23 logic gates. Rokicki's improvement was subsequently implemented as a separate genus, placed at the top of the list to give priority over the generic lifelike implementation:
 b3s23life (19operation implementation of Conway's Game of Life).
Performance
The algorithms in lifelib are optimised for speed. Comparing likewithlike, it tends to outperform Golly's algorithms in the majority of cases, with a few exceptions. Tom Rokicki compiled a very comprehensive and accurate performance comparison here.
In terms of memory, each lifetree nonleaf node occupies 32 bytes and each leaf node occupies 16 + 32N bytes, where N is the number of bitlayers in the pattern. This is intermediate between 32 and 64bit Golly in terms of both memory usage and maximum pattern size. 64bit Golly can theoretically support larger patterns than lifelib, but you would need more than 256 GB of memory in order to take advantage of this.
Other functionality
In addition to running and editing patterns, lifelib features other functionality:
 Fast periodicity detection, which can detect oscillator and spaceship periods below 2^{24} and certain higher periods;
 Determination of apgcodes of patterns in both 2state and multistate rules;
 Separation of objects and components of pseudoobjects in nonB0 Lifelike cellular automata;
 Subroutines less directly associated with cellular automata, such as calculation of minimum spanning trees, primality testing, and integer factorisation.
See also
External links
