Three ways to extend an interval, on the same search

Three ways to extend an interval, on the same search

A search for 8-character patterns within 1 error over 8,192 characters of a 21-symbol alphabet, 6 patterns, counted in bit-vector ranks. The published shape asks about every character of the alphabet at every node: 1,478,400. The compound walk makes each of those questions cheaper by returning the rank and the smaller-count from one descent, which is 11x. Enumerating the interval's symbols removes the questions instead, which is 78x — and the 55.8% of extensions that found nothing are what it removed. All three visit the same live intervals in the same order and report the same occurrences; that is the check, and it is what makes this a plate about cost.

Drawn at 700 × 222, wide on the page. Everything above is what savings-ladder returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

6 essays call savings-ladder. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.