Samplers for rules with few matches

[kaya3]

A "sampler" is a data structure containing the current matches for some set of input patterns. In the current implementation, a sampler is implemented as a pair of arrays (one for the matches, one for index lookups) with sufficient capacity in case every pattern simultaneously matches at every position. This means that no memory allocation ever has to be done in the main loop, but it also wastes memory, particularly when the grids are large and some patterns will only ever have a small number of matches, and this may also impact performance due to cache misses.

Some examples where this optimisation would be relevant:

• In the BasicSnake model, the patterns [RBW] and [RBD] can have at most three simultaneous matches each, and [PGG] can have at most one.
• In the MazesAndLakes model, the patterns [RBB] and [RWW] can have at most 3 * LAND_SEEDS and LAND_SEEDS simultaneous matches respectively.

If a set of patterns will only ever have one match at a time, then the sampler can be replaced with a single variable for the position of the current match (or -1 if there is no match). Otherwise, if the number of matches will only ever be small, then the sampler can be implemented as a single unsorted array, and old matches can be removed by linear search.

The main problem is knowing when this optimisation is possible. The simplest solution would be to let the programmer provide hints for which patterns can't have many matches; or it could be detected using control-flow analysis for grid symbols.