PetaMem

The previous post - pperl 0.6.12+ - Shall we play a game? - closed with a promise: the next release will compete in every benchmark of the Computer Language Benchmarks Game with the best scripted language entry there. The current build already takes several rows outright; the tally belongs to the release post. This one is about a row where the promise cannot be kept with the guns we have. On regex-redux the opponent is V8's Irregexp, a compiler that turns regular expressions into machine code, and no amount of work on the Perl JIT will close that gap, because the time is not spent in Perl ops at all. The answer is a second compiler: ReJIT.

The promise, and the scoreboard so far

The promise stands as written: every Game benchmark, against the best scripted entry, with a general-purpose JIT rather than one tailored to benchmark code. Several rows already go to the current build; publishing the numbers before the release they belong to would repeat the mistake of printing tables that age in our favour, so they wait. What does not wait is the row that dictated new machinery.

regex-redux: outgunned at home

regex-redux is the Game's regular-expression benchmark: nine alternation patterns counted over a DNA sequence with //g, five IUB-code substitutions with s///g, essentially all of it inside the regex engine. Regular expressions are the domain Perl defined; this should be a home game.

It is not. pperl runs the workload through its regex engine - the Rust reimplementation of perl5's backtracker - at perl5 parity: roughly nine billion instructions on our measurement input, for pperl and perl5 alike. node retires 1.33 billion on the same input. That is a factor of seven, in instruction count, before anyone talks about clock speed.

The reason node is there is Irregexp, V8's regex compiler. It is a backtracker, like perl's engine - leftmost-greedy, capture semantics and all - but it does not interpret a pattern, it compiles the pattern to native code: character classes become mask-and-compare instructions, backtracking becomes a pop and an indirect jump, and each subject encoding gets its own code object. Against that, an interpreter dispatching per character through a switch is structurally behind, however tight the switch.

And this is the point where the existing JIT cannot help. The pperl JIT compiles Perl ops; on this row over 99% of the instructions retire inside a single op, the match itself. An engine gap cannot be closed from the op side. Hence the second compiler.

ReJIT

ReJIT compiles regular expressions to machine code, and the design decision worth explaining is what it compiles. There are three architectures in the field. Irregexp compiles its own pattern graph. RE2-class engines (rust-regex, V8's linear mode) run guaranteed-linear automata over a restricted semantics. PCRE2's JIT does neither: it compiles the interpreter's own compiled-pattern bytecode, arm by arm, and falls back to the interpreter for whatever it declines.

ReJIT takes the PCRE2 shape. perl's regex compiler already does the hard front-end work - parsing, optimization, trie construction with Aho-Corasick start classes, anchoring and substring analysis - and its output, the regnode program, is the specification of what a match must do. ReJIT compiles that program to native code through the same Cranelift backend the op JIT uses, and splices in behind the engine's public boundary: patterns it admits get compiled code, patterns it declines keep the stock engine, permanently and at zero per-match cost. Compiling the engine's own program rather than reinventing a pattern representation is what makes fidelity a construction property instead of a test-suite aspiration.

Irregexp still gets mined - for mechanics, not architecture: the heap-grown backtrack stack of code addresses, captures as a register array saved and restored through that stack, one compiled body per subject encoding, compilation deferred until a pattern is demonstrably hot.

What we will not ship is an RE2-style linear engine, for two reasons. First, perl already ships the tier such an engine would occupy: the substring and start-class presearch machinery in front of the matcher is a prefilter, and duplicating it buys nothing. Second, a breadth-first engine cannot express the backtracking-order phenotype - which branch wins, what $1 holds under alternation, what (*SKIP) and its relatives do - and in Perl that phenotype is observable behaviour, not an implementation detail.

Where the instructions go

We took a census of the row before designing the tier. 83% of the instructions are the count loop, 16% the substitutions, 1% everything else. The interesting split is inside the count loop.

perl's optimizer builds its trie - and the Aho-Corasick scan that makes trie'd alternations fast - only when every branch of the alternation starts with a literal. Five of the nine count patterns qualify and run comparatively fast. The other four start a branch with a character class ([cgt]gggtaaa|tttaccc[acg] and friends), get no trie and no start class, and are scanned branch by branch from every position. Those four cost 64% of the count phase - about 55% of the entire benchmark.

So the single biggest target is exactly the shape perl's optimizer refuses to optimize: a class-headed alternation, compiled into a machine-code scan loop. The trie'd scan is the second target, at roughly a quarter of the row. All fifteen patterns of the benchmark sit inside the first compiled subset - no captures, no lookaround, no backreferences anywhere in the row.

Captures are in that first subset anyway. In our 1,844-file test corpus, $1-style extraction outnumbers backreferences 268 to 14; a captureless tier would compile the counting workloads and decline nearly every extracting one, which is the majority real-world shape of =~.

Semantics are not negotiable

The house rules from the previous post apply unchanged: every gap is fixed as a general construct or not at all, and the semantics are perl's, byte for byte.

One example of why compiled-regex prior art cannot simply be copied. In /(?:(a)|(b))+/ matched against "ab", perl leaves $1 holding "a" - a quantified group retains the last successful value of its inner captures across iterations. ECMAScript clears them at each iteration entry, so JavaScript reports capture 1 undefined, and Irregexp implements exactly that. Copying its register-clearing verbatim would be a wrong-match bug by construction. The engines agree on almost everything; the tier is built for the places they do not.

The enforcement is mechanical, not stylistic. In test mode every compiled match is re-run through the stock engine and compared - not the verdict alone, but the full capture state, since a divergence there stays invisible until $' or @- is read much later. perl's own regression corpus runs under that differential mode, including the 2,210-case table it maintains for the engine and the variants of it that force the trie optimization off and on. And the perl-specific machinery that does not compile - (?{...}) code blocks, pattern recursion, locale-dependent folding - is declined at admission and stays on the stock engine, which remains the universal fallback.

Staging

ReJIT lands in stages: the instrumentation and the differential oracle first, then the scan-loop tier described above, then quantifier depth, then the utf8 axis. For the scan-loop tier alone our prediction on the regex-redux row is a 3-5x reduction in instruction count - printed here so the release post can be checked against it.

As always: no dates. This is to update status: the promise from the previous post now has its missing weapon under construction.

• Richard C. Jelinek, PetaMem s.r.o.