What optimizations are in place in MarkovJunior?

[zylkowski]

From readme I can deduce that it's Boyer–Moore algo with some memoization.
How does it work exactly?
Is Boyer-Moore algo only in the inital search of pattern and then only updates changed cells or is it even smarter?

[mxgmn]

Boyer–Moore is used only in the initial search. You can see here that we're making large jumps x += rule.IMX instead of x++.

[kaya3]

From my understanding, there are separate algorithms for the initial scan and for updates. (I'll write as if it's 2D for simplicity.)

The initial scan looks at cells on a rectangular lattice, spaced IMX, IMY apart. It is guaranteed that every match of the pattern overlaps exactly one lattice cell. For each lattice cell, check its colour, and check which offsets in the pattern that that colour can appear at. For each of those possible offsets, do a straightforward check of every cell in the pattern to check for a match at the offset position. (The straightforward check does short-circuit when a non-matching cell is found.)

The update is run for each individual cell that changes. Again, it works by checking the colour at that cell and which offsets in the pattern that colour can appear at, and doing a straightforward check for each possible offset. The upside is that when a cell's colour doesn't match anywhere in the pattern, then no checks need to be done.

There is also an optimisation in that the updates are not done until the node is executed again, so if the node which cares about that pattern is never executed again, updates for that pattern don't need to be processed. It would potentially be possible to revert to the "initial scan" algorithm if there are a large number of updates since the last time the node was executed, but I'm not sure if that happens much in practice anyway - in most models, each node is executed in a tight loop and then never executed again afterwards.