Skip to content
Experiments

The crest sieve

A trigram index prunes nothing on a pattern with no literal in it. Crest prunes 67% of those files anyway.

Every trigram index in the field shares one blind spot. Feed it a pattern built from character classes and repetition, with no literal substring to extract, and the candidate set is the entire corpus; the index contributes nothing and you pay for a full walk. This is not an implementation gap, it is what the data structure is for.

Crest is a different necessary condition. Rather than asking which literals a match must contain, it computes a lower bound on the longest run of characters from each class the pattern requires, then checks that bound against a per-file sidecar. A file whose longest run of digits is 3 cannot contain a match demanding 7 of them, and you know that without reading it.

The whole calculus rounds down. Any construct the AST walk cannot certify contributes nothing to the bound, unsafe caseless folds and non-ASCII classes decline to zero, so under-pruning is the only failure mode available. It cannot hide a match; it can only fail to save you time. That is the property that makes it shippable, and it is machine-checked against the production matcher on every run rather than argued.

The count-cousin is the control. Same forced bound, but counting occurrences of the class across the file instead of measuring its longest run: it prunes 3.3% where the run prunes 67%. Population is not the right question. The run is.

What this does not prove

  • The speedup is measured on the narrow slate the sieve was built for: eight literal-free class-repetition patterns the trigram index prunes 0% on. It is not a corpus-wide result and is not presented as one.
  • A sidecar is more state to build, persist and keep fresh, on top of the index that already exists.