prefilter, research and reject a lazy DFA cache
Researched two production Pike-VM-family engines directly (RE2's
nfa.cc, rust-lang/regex's regex-automata), fetched and read, not
recalled, specifically for what explains the two weaknesses the last
benchmark found (a*b's nullable loop, dense finditer): both avoid
per-thread malloc/free, RE2 via a Thread free list, regex-automata via
a flat SlotTable indexed directly by NFA state. Also researched
Hyperscan's Teddy (SIMD literal matching) and set it aside: it needs
platform-specific intrinsics, in tension with this project's
single-file, portable-C, simplicity-over-performance priority: a
portable Boyer-Moore-Horspool skip was judged proportionate where
Teddy was not.
Rewrote the Pike VM's memory model accordingly. PikeThread's owned
int64_t* is gone; a committed thread's capture row now lives at a
fixed offset in PikeList.table, indexed directly by instruction PC
(Cox's one-thread-per-PC invariant already made this index unique, so
no allocation is needed to store or discard one). Transient rows
needed mid-closure, before the eventual terminal PC is known, come
from ScratchPool, a fixed block with an explicit free list; a plain
bump/decrement counter was tried first and proven incorrect by hand
before being written into the file (an OP_SPLIT's second branch's row
can outlive several non-branching pushes that reuse an *earlier* row
without reallocating it, which only a real free list handles safely
regardless of release order). The closure stack is pre-sized once
instead of grown by realloc on demand. All three, plus a reusable
best-match buffer and the prefilter below, bundle into one PikeEngine,
built once per top level Pattern_/re_ call and reused across every
match found within it, never cached on PatternImpl itself (that would
make concurrent Pattern_search calls on the same compiled Pattern from
different threads race on shared state, breaking the existing
no-synchronization-needed guarantee for a Pattern nothing mutates).
Extended the literal prefilter from a single leading character to the
full mandatory literal prefix, with a real Boyer-Moore-Horspool
bad-character skip table for BINARY/ASCII mode (UTF8 keeps a
without-skip fallback: a byte-indexed table cannot cover code points
past 0x10FFFF). The skip-ahead only ever applies to where a new
unanchored start is injected, never to advancing sp itself while a
thread from an earlier start position is still alive.
Researched and did not build a lazy DFA state cache (memoizing a
live-instruction-set-plus-byte transition). Not an omission: RE2's own
lazy DFA cannot track submatch boundaries, the same structural reason
applies here, since every call wants at least group 0's span, and a
cached transition only answers whether a match is possible, not which
path was taken; using one would need a two-phase architecture deserving
its own research-and-plan pass. Checked empirically too: a*b, the case
such a cache would help most, has at most two live instructions at any
position for its whole run, so there is no repeated state worth
caching in the first place.
Verified: full 3,252-case suite (four clean runs), a whitebox
dual-engine cross-check extended to also cover finditer/split/BINARY
mode (30,000 + 3,334 + 2,500 comparisons, zero mismatches), a targeted
suite for the new prefilter machinery including the classic
Boyer-Moore-Horspool overlapping-suffix correctness trap (12/12), two
clean AddressSanitizer/UndefinedBehaviorSanitizer passes on each (a
third run of each hit the same pre-existing sandbox flake already
documented, confirmed unrelated by retrying clean).
Measured: literal search went from 0.64x of the backtracking engine's
time (already ahead) to 0.03x (~33x faster), and against POSIX
<regex.h> from roughly 11x slower to roughly 2x *faster* than glibc
outright; a*b (no prefilter benefit at all) improved from 3.45x slower
than backtracking to 1.97x, from the allocation fix alone; dense
finditer over [0-9]+/\w+ improved from 3.2x/5.6x slower to 1.7x/2.8x.
Full tables and citations in concept.md 7.10; README.md, docs/API.md,
USAGE.md, and bench_vs_posix.c's own printed summary updated
throughout with the corrected numbers and the full history, not just
the final ones.
Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY
retoorandClaude Sonnet 5
e4fc067aa6