retoorandClaude Sonnet 5
e4fc067aa6
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
Examples
Each program here is self-contained (main, no shared helper code) and
isolates one distinct feature rather than being a general purpose tool; the
one exception is rxgrep.c, a small grep-like program that ties several of
the same features together into something actually usable from a shell.
../USAGE.md walks through the same API surface function by
function, with smaller inline snippets; these programs are complete,
runnable, and closer to what real code doing this specific thing looks
like.
Build all of them with make examples from the repository root (or
make all / make example for just rxgrep, the default). Each is also a
single cc -I. file.c libregexx.a -o file invocation away from being built
directly, no build system required.
| Program | Demonstrates |
|---|---|
rxgrep.c |
A complete grep-like CLI: all three data modes via -m, Pattern_search/finditer for line and per-match output, Pattern_subn for --sub, reading from a real file or a pipe. Run ./rxgrep --help. |
binary_scan.c |
BINARY mode: a byte-range character class ([\x00-\xff]) matching raw bytes 0-255, including an embedded NUL and an embedded 0x0A, neither of which is a terminator or a line break in this mode the way it would be to a C string function or a line-oriented reader. This is the one thing ASCII/UTF8 mode cannot do, since both introduce either a restricted classification or a decoding step. |
utf8_scripts.c |
UTF8 mode: \w recognizing letters across Latin, Greek, Cyrillic, and CJK text (not only ASCII), and the resulting difference between Match_span (code point units) and Match_span_byte (byte units) once a match spans characters that are more than one byte wide. |
ascii_logparse.c |
ASCII mode doing what it is ordinarily used for: parsing structured, line-oriented text with named groups ((?P<name>...)) and reading fields back out by name via Match_group/Pattern_groupindex_lookup, not by a numeric position the caller has to remember. |
redos_atomic.c |
Two-part: first, that the textbook (a+)+b ReDoS shape is now fixed automatically, with no atomic group, because it has no backreference and so runs on the Pike VM (README.md "The Pike VM"); second, a variant with a backreference added specifically to force it back onto the backtracking engine, where the same shape is exponential again and an atomic group ((?>...)) is still the pattern author's own necessary fix. |
empty_match_rule.c |
Pattern_finditer/Pattern_split reproducing a real CPython interpreter's undocumented empty-match retry rule exactly (\d*? against "123abc456" yields 16 matches, not 9), found by probing a real interpreter directly rather than by reading its documentation. |
large_file_search.c |
Input_from_file's mmap-backed reading on a generated 100MB file, with the elapsed time and peak resident memory printed directly so they can be checked against the measured figures in ../README.md "Memory footprint" rather than taken on faith. |
bench_vs_posix.c |
A direct, timed comparison against the C standard library's own <regex.h> (POSIX regcomp/regexec) on six scenarios at multi-megabyte/multi-hundred-thousand-line scale, using only pattern syntax valid in both engines, every one of them Pike VM eligible. Reported honestly across the whole history, not just the current numbers: a literal search first regressed from roughly 22x slower than glibc to roughly 70x once the Pike VM existed without a prefilter, then recovered through a single-character prefilter (roughly 11x-13x) to a Boyer-Moore-Horspool literal prefilter plus an allocation-free thread model (concept.md 7.10) that now runs it roughly 2x faster than glibc outright; the adversarial (a+)+b scenario also beats glibc outright, with no atomic group needed. |
Every program below was compiled and actually run while writing it; the claims in its top-of-file comment (what a real CPython interpreter does, what timing difference an atomic group makes, and so on) are checked against that program's own printed output, not written by hand and left unverified.