perf(regex): split, replace, matchAll and global exec do quadratic work under Perex — split regressed from ~7x Node to timing out

[proggeramlug]

What happened

Under the Perex engine, four common whole-string regex operations still do, or now do, work that grows with the square of the input. "ab12,cd345;ef6 ".repeat(n).split(/[,; ]+/) was linear and about 7x Node on the pre-Perex runtime; on current main it takes seconds at n=10,000 and the benchmark times out. Global exec loops, matchAll and replace with a callback were already quadratic on the old engine and remain quadratic, timing out at n=100,000 where Node needs about 12 ms. Checksums match Node at every completed size. The Unicode variants of these workloads additionally throw, which is tracked separately.

Measured against Node v26.8.1 using Perry perry 0.5.1545 at 8a058e205385ec8ebb353ce0f231530871ce4a49. This is evidence from that pinned revision, not a claim that current main was remeasured. First reproduce on current main; if it is already fixed, identify the fixing commit and attach the comparison.

Measurements

Times are median milliseconds per workload invocation. Ratios are Perry/Node. A correctness or timeout classification takes precedence over performance; successful smaller-size timings on those rows are diagnostic evidence.

regex-split — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.009743	3.026491	310.63×	705330170	705330170
1000	0.100322	89.910230	896.21×	502537147	502537147
10000	0.998414	TIMEOUT	—	417172305	—
100000	10.670293	SKIPPED	—	155868597	—
1000000	239.836757	SKIPPED	—	536314919	—

Log(time)/log(n) least-squares slopes: Perry 1.473, Node 1.081, delta 0.392.

Workload: Regex baseline, excluded from the main ranking.

Slopes cover different completed sizes: Node [100, 1000, 10000, 100000, 1000000], Perry [100, 1000].

perry n=10000: TIMEOUT, exit -9

Process exceeded 60 s

regex-exec-global — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.012898	0.496530	38.50×	702256350	702256350
1000	0.127505	10.578161	82.96×	275951190	275951190
10000	1.209385	677.357363	560.08×	454333185	454333185
100000	11.887562	TIMEOUT	—	934096856	—
1000000	116.560667	SKIPPED	—	916735987	—

Log(time)/log(n) least-squares slopes: Perry 1.567, Node 0.988, delta 0.579.

Workload: Regex baseline, excluded from the main ranking. Fresh regex in setup resets lastIndex outside timing; n records each contain two nonempty matches.

Slopes cover different completed sizes: Node [100, 1000, 10000, 100000, 1000000], Perry [100, 1000, 10000].

perry n=100000: TIMEOUT, exit -9

Process exceeded 60 s

regex-match-all — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.012705	0.801369	63.08×	702256350	702256350
1000	0.125690	13.645045	108.56×	275951190	275951190
10000	1.272216	714.595513	561.69×	454333185	454333185
100000	12.297022	TIMEOUT	—	934096856	—
1000000	116.738874	SKIPPED	—	916735987	—

Log(time)/log(n) least-squares slopes: Perry 1.475, Node 0.992, delta 0.483.

Workload: Regex baseline, excluded from the main ranking. n records each contain two matches; full iteration makes all matches observable.

Slopes cover different completed sizes: Node [100, 1000, 10000, 100000, 1000000], Perry [100, 1000, 10000].

perry n=100000: TIMEOUT, exit -9

Process exceeded 60 s

regex-replace-callback — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.010074	0.957875	95.08×	363948310	363948310
1000	0.097525	15.420992	158.12×	684918147	684918147
10000	0.958640	726.967271	758.33×	987261466	987261466
100000	12.134925	TIMEOUT	—	620332332	—
1000000	268.444463	SKIPPED	—	994649528	—

Log(time)/log(n) least-squares slopes: Perry 1.440, Node 1.095, delta 0.345.

Workload: Regex baseline, excluded from the main ranking.

Slopes cover different completed sizes: Node [100, 1000, 10000, 100000, 1000000], Perry [100, 1000, 10000].

perry n=100000: TIMEOUT, exit -9

Process exceeded 60 s

What is expected / acceptance criteria

• Rerun all four full reproducers on the fix and on the pre-Perex revision on one host at 100, 1k, 10k, 100k and 1M. Every size Node completes must complete within the existing 60-second budget, with checksums matching Node at every size.
• Show linear total work: the measured Perry-minus-Node log-log slope delta must be below 0.25 over a shared 1k–100k range for each of the four workloads, and the standalone program's rows must roughly double, not quadruple, per doubling of n.
• split must at minimum return to the pre-Perex engine's linear behaviour and constant factor; report its ratio against Node at 1M alongside the old engine's.
• Confirm by profiling or instrumentation, and record on the issue, where per-attempt positioning cost went — for example that a match attempt resumes from the previous position rather than seeking from the start of the subject — before the change is considered done.
• Preserve semantics with regression coverage: lastIndex read/write and reset-to-0 on failure for g and y, exec result index/input/groups, matchAll requiring the g flag and iterating lazily, zero-width matches advancing by one code point under u and one code unit without it, replacement patterns ($&, $1, $<name>) and callback arguments, and split with captures and a limit.

Implementation to inspect

Same-host before/after. The "old engine" column is the pre-Perex runtime at 9495bfc95e and the "Perex" column is main at 8a058e2053, both built from source with the identical release command and measured sequentially on the same host with the same Node. Perex became the runtime's only regex engine in #10142 (landed via merge train #10146); #10149 then resolved it from crates.io as perex = "0.1".

Before/after, full suite workloads (median ms per invocation, same host):

workload	n	Node	old engine	Perex	old ÷ Node	Perex ÷ Node	Perex ÷ old
regex-split	100	0.010	0.069	3.026	7.1×	310.6×	43.9×
regex-split	1,000	0.100	0.709	89.910	7.0×	896.2×	126.8×
regex-split	10,000	0.998	7.033	TIMEOUT	7.1×	—	—
regex-split	100,000	10.670	72.125	SKIPPED	5.9×	—	—
regex-split	1,000,000	239.837	960.467	SKIPPED	4.0×	—	—
regex-exec-global	100	0.013	0.308	0.497	23.7×	38.5×	1.6×
regex-exec-global	1,000	0.128	12.822	10.578	103.5×	83.0×	0.8×
regex-exec-global	10,000	1.209	1,182.767	677.357	975.0×	560.1×	0.6×
regex-exec-global	100,000	11.888	TIMEOUT	TIMEOUT	—	—	—
regex-exec-global	1,000,000	116.561	SKIPPED	SKIPPED	—	—	—
regex-match-all	100	0.013	0.458	0.801	35.6×	63.1×	1.8×
regex-match-all	1,000	0.126	7.008	13.645	56.6×	108.6×	1.9×
regex-match-all	10,000	1.272	453.259	714.596	365.7×	561.7×	1.6×
regex-match-all	100,000	12.297	TIMEOUT	TIMEOUT	—	—	—
regex-match-all	1,000,000	116.739	SKIPPED	SKIPPED	—	—	—
regex-replace-callback	100	0.010	0.077	0.958	7.7×	95.1×	12.5×
regex-replace-callback	1,000	0.098	4.464	15.421	45.5×	158.1×	3.5×
regex-replace-callback	10,000	0.959	367.627	726.967	369.3×	758.3×	2.0×
regex-replace-callback	100,000	12.135	TIMEOUT	TIMEOUT	—	—	—
regex-replace-callback	1,000,000	268.444	SKIPPED	SKIPPED	—	—	—

• regex-split: Perry slope 1.03 → 1.47 (SLOW → TIMEOUT), Node 1.08
• regex-exec-global: Perry slope 1.79 → 1.57 (TIMEOUT → TIMEOUT), Node 0.99
• regex-match-all: Perry slope 1.50 → 1.48 (TIMEOUT → TIMEOUT), Node 0.99
• regex-replace-callback: Perry slope 1.84 → 1.44 (TIMEOUT → TIMEOUT), Node 1.09

Single-call scaling from a standalone program (one timed call each, not medians; the program is below). Doubling n should roughly double the time for linear work:

probe	Node	old engine	Perex
split ascii n=1000	0.2 ms	2.6 ms	93.0 ms
split ascii n=2000	0.1 ms	1.2 ms	311.3 ms
split ascii n=4000	0.6 ms	2.3 ms	1,157.2 ms
split ascii n=10000	1.2 ms	5.6 ms	6,904.1 ms
exec global ascii n=1000	0.4 ms	12.5 ms	10.2 ms
exec global ascii n=2000	0.5 ms	48.1 ms	33.7 ms
exec global ascii n=4000	0.4 ms	188.1 ms	119.1 ms
exec global ascii n=10000	2.2 ms	1,200.4 ms	771.9 ms

This mechanism is a source-reading hypothesis. The Perex maintainers are checking where each cost actually sits and have not confirmed it yet. Treat the line references as places to look, not as a diagnosis.

At perex_api.rs:15 the runtime sets WORK = 100_000_000, and every split/replace/match entry point creates one Budget::new(api::WORK) for the whole operation (perex_split.rs:80, perex_replace.rs:68, perex_match_search.rs:154, match_all.rs:227). Perex's own documentation on Budget (src/lib.rs, line 27) says it is a "work allowance shared across an entire compile or search operation" that "is never reset when trying another start position". In src/span/bound.rs the span reader seeks toward span.start() one UTF-16 unit at a time from its saved mark, charging the budget one unit per step (the loop at line 161). If each match attempt seeks from the start of the subject rather than resuming from the previous attempt, one attempt costs O(position), a whole split or replace costs O(n²), and a fixed 100M allowance is exhausted once roughly n²/2 exceeds it — at which point the operation throws instead of merely running slowly. RegExp.prototype[@@split] is implemented as the specification's sticky loop in perex_split.rs, trying a match at each successive position, which would explain why split in particular changed from linear to quadratic.

For global exec and matchAll the same per-attempt seek would produce the quadratic independently of the budget: each call starts at lastIndex and, if positioning the reader costs O(lastIndex), a loop over n matches costs O(n²). The pre-Perex engine showed the same shape, attributed in the original report to converting lastIndex between UTF-16 units and bytes on every call, so this part is not new — but the engine replacement was the natural point to remove it, and it remains.

Standalone scaling program

function t(label: string, f: () => number): void {
  const s = performance.now();
  try { const r = f(); console.log(`${label.padEnd(34)} ok     ${(performance.now() - s).toFixed(1).padStart(9)} ms  result=${r}`); }
  catch (e) { console.log(`${label.padEnd(34)} THREW  ${(performance.now() - s).toFixed(1).padStart(9)} ms  ${String(e)}`); }
}
for (const n of [1000, 2000, 4000, 10000]) {
  t(`split ascii        n=${n}`, () => "ab12,cd345;ef6 ".repeat(n).split(/[,; ]+/).length);
  t(`split unicode      n=${n}`, () => "ä中12，Ö漢345；ef6😀".repeat(n).split(/[，；😀]+/u).length);
  t(`replace cb unicode n=${n}`, () => "ä中😀12 Ö漢🦊345;".repeat(n).replace(/[ä中😀Ö漢🦊]+/gu, (m) => "[" + m + "]").length);
  t(`exec global ascii  n=${n}`, () => { const s = "ab12 cd345;".repeat(n), re = /([a-z]+)([0-9]+)/g; let c = 0; while (re.exec(s) !== null) c++; return c; });
}
const vals: string[] = []; for (let i = 0; i < 1000000; i++) vals.push((i % 2 ? "record_" : "!bad_") + i);
t("test literal-in-loop 1M", () => { let c = 0; for (let i = 0; i < vals.length; i++) if (/^[a-z]+_[0-9]+$/.test(vals[i])) c++; return c; });
const hoisted = /^[a-z]+_[0-9]+$/;
t("test hoisted regex  1M", () => { let c = 0; for (let i = 0; i < vals.length; i++) if (hoisted.test(vals[i])) c++; return c; });

The benchmark metadata comments embedded below still name the pre-Perex runtime functions they were written against; #10142 deleted those files. "Implementation to inspect" lists the code paths that exist at the measured revision.

• crates/perry-runtime/src/regex/perex_split_compat.rs: js_string_split_regex
• crates/perry-runtime/src/regex/perex_split.rs: regexp
• crates/perry-runtime/src/regex/exec.rs: js_regexp_exec
• crates/perry-runtime/src/regex/perex_match_search.rs: regexp
• crates/perry-runtime/src/regex/perex_runtime.rs: find
• crates/perry-runtime/src/regex/match_all.rs: js_string_match_all
• crates/perry-runtime/src/regex/perex_replace.rs: regexp

Source reading narrows the investigation; it does not establish exclusive runtime/compiler attribution. No compiler or runtime changes were made to obtain these measurements.

Agent scope and coordination

These three issues are owned by the Perex maintainers, who have taken them and are confirming cost attribution before splitting ownership. Do not start a source fix without coordinating on the issue first, so work does not collide. Changes belong in the Perex crate and/or the runtime adapter under crates/perry-runtime/src/regex/perex_*. The acceptance numbers should be re-measured against the same pre-Perex revision on one host, as above, not against the original September 11 sweep, which ran on a different machine.

Implementation work can proceed in separate branches. Serialize benchmark runs on any shared host; parallel timing runs invalidate small performance comparisons. Preserve language semantics and moving-GC safety.

• Coordinate with this benchmark task: bug(regex): split and replace throw "Regular expression work limit exceeded" on 32,000-unit strings Node handles in under a millisecond #10164

• Coordinate with this benchmark task: perf(regex): RegExp.prototype.test costs ~1.5 µs per call under Perex — 44x slower than the old engine even with the regex hoisted #10166

• Related history/context: Make Perex the runtime's only regular-expression engine #10142

• Related history/context: Merge train 170: #10142 #10146

• Related history/context: Merge train 172: #10148 #10149

Reproduce and remeasure

Everything needed for the workload is embedded below; no private repository, fixture, npm package, or shared prelude is required. Save a complete benchmark block under its indicated filename in /tmp/perry-builtin-repro/. Use Node 26.8.1 to match this measurement; it runs these TypeScript files directly.

From the Perry checkout/branch being evaluated:

mkdir -p /tmp/perry-builtin-repro
cargo build --release --locked -p perry -p perry-runtime-static -p perry-stdlib-static
export PERRY_RUNTIME_DIR="$PWD/target/release"
export TZ=UTC LC_ALL=en_US.UTF-8
git rev-parse HEAD
node --version
target/release/perry compile /tmp/perry-builtin-repro/regex-split.ts --no-auto-optimize -o /tmp/perry-builtin-repro/app

To reproduce the historical baseline, use the pinned commit above in a separate checkout and build the compiler and both libraries there. Repeat compilation for each additional benchmark below. Run this small driver from the same checkout, changing name and sizes for that benchmark:

import json, math, subprocess
name = 'regex-split'
sizes = [100, 1000, 10000, 100000, 1000000]
result_on_stderr = False
stopped = set()
points = {"node": [], "perry": []}
for n in sizes:
    pair = {}
    for engine, cmd in [("node", ["node", f"/tmp/perry-builtin-repro/{name}.ts"]),
                        ("perry", ["/tmp/perry-builtin-repro/app"])]:
        if engine in stopped: continue
        try:
            p = subprocess.run(cmd + [str(n)], capture_output=True, text=True, timeout=60)
        except subprocess.TimeoutExpired:
            print(engine, n, "TIMEOUT"); stopped.add(engine); continue
        if p.returncode:
            print(engine, n, "ERROR", p.returncode, p.stderr, p.stdout); continue
        r = json.loads(p.stderr if result_on_stderr else p.stdout)
        pair[engine] = r
        points[engine].append((n, r["ms_per_run"]))
        print(engine, r)
    if len(pair) == 2:
        print("ratio", n, pair["perry"]["ms_per_run"] / pair["node"]["ms_per_run"],
              "checksum_match", pair["perry"]["checksum"] == pair["node"]["checksum"])
def slope(rows):
    if len(rows) < 2: return None
    x = [math.log(n) for n, t in rows]; y = [math.log(t) for n, t in rows]
    mx = sum(x)/len(x); my = sum(y)/len(y)
    return sum((a-mx)*(b-my) for a,b in zip(x,y))/sum((a-mx)**2 for a in x)
print("slopes", {engine: slope(rows) for engine, rows in points.items()})

Record before/after results from the same unchanged source, engine versions and host. The measured driver uses seeded setup outside timers, at least 200 ms AND five warmup runs, then seven samples with at least 20 ms measured work each. Fresh input is prepared before each timer for mutating workloads. The median per-run time is reported, with checksum consistency checked on every invocation. Timeouts cover setup, warmup and sampling, not just one builtin call.

Environment and limits

• CPU: AMD Ryzen 7 7700X 8-Core Processor; 16 logical cores; x86_64.
• OS: Linux-6.17.0-23-generic-x86_64-with-glibc2.39; target: native host.
• Node: v26.8.1; Perry: perry 0.5.1545; build: release from source.
• Compile flag: --no-auto-optimize; compiler and both matching runtime archives were rebuilt together.
• The pinned source revision and compiler/runtime/Node artifact hashes were unchanged throughout the sweep.
• Load average at measurement start: [3.537109375, 4.07470703125, 5.009765625]; end: [3.58251953125, 3.47265625, 4.1953125].
• Host contention limits precise constant-factor claims; repeat on a quiet host before asserting an improvement.
• Timings include timer overhead and checksum calculation. String hashes bound lookup count, not Unicode lookup cost; indexed consumption may also force Node string materialization.

Minimal correctness reductions

This issue is a performance workload; the complete checksum-gated reproducer follows.

Complete standalone benchmark sources

regex-split.ts — sizes [100, 1000, 10000, 100000, 1000000]

Size meanings and fresh-input policy are in the leading metadata. result_on_stderr for this file: False.

// @runtime {"name": "regex-split", "category": "regex", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/regex/replace_expand_fancy.rs", "function": "js_string_split_regex_n"}], "hypothesis": "Hypothesis: regex split first owns a copy of the source, materializes a Vec of parts, then allocates runtime strings and the result array.", "notes": "Regex baseline, excluded from the main ranking. ", "asynchronous": false, "output_stderr": false, "fresh_input": false}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): string { return 'ab12,cd345;ef6 '.repeat(n); }
function run(input: string): number {
  const parts = input.split(/[,; ]+/);
  let h = parts.length;
  for (let i = 0; i < parts.length; i++) h = (h * 31 + hashString(parts[i])) % 1000000007;
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  const preparedInput = setup(n);
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = preparedInput;
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = preparedInput;
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "regex-split", category: "regex", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

regex-exec-global.ts — sizes [100, 1000, 10000, 100000, 1000000]

Size meanings and fresh-input policy are in the leading metadata. result_on_stderr for this file: False.

// @runtime {"name": "regex-exec-global", "category": "regex", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/regex/exec.rs", "function": "js_regexp_exec"}], "hypothesis": "Hypothesis: global exec repeatedly converts lastIndex between UTF-16 and bytes and allocates match/capture results.", "notes": "Regex baseline, excluded from the main ranking. Fresh regex in setup resets lastIndex outside timing; n records each contain two nonempty matches.", "asynchronous": false, "output_stderr": false, "fresh_input": true}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): {s: string, re: RegExp} { return {s: 'ab12 cd345;'.repeat(n), re: /([a-z]+)([0-9]+)/g}; }
function run(input: {s: string, re: RegExp}): number {
  let h = 0;
  let match = input.re.exec(input.s);
  while (match !== null) {
    h = (h * 31 + match.index + hashString(match[0])) % 1000000007;
    match = input.re.exec(input.s);
  }
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = setup(n);
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = setup(n);
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "regex-exec-global", category: "regex", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

regex-match-all.ts — sizes [100, 1000, 10000, 100000, 1000000]

Size meanings and fresh-input policy are in the leading metadata. result_on_stderr for this file: False.

// @runtime {"name": "regex-match-all", "category": "regex", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/regex/match_all.rs", "function": "js_string_match_all_value"}], "hypothesis": "Hypothesis: matchAll materializes every match before returning an iterator, adding memory and upfront allocation compared with lazy iteration.", "notes": "Regex baseline, excluded from the main ranking. n records each contain two matches; full iteration makes all matches observable.", "asynchronous": false, "output_stderr": false, "fresh_input": false}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): string { return 'ab12 cd345;'.repeat(n); }
function run(input: string): number {
  let h = 0;
  for (const match of input.matchAll(/([a-z]+)([0-9]+)/g))
    h = (h * 31 + match.index! + hashString(match[0])) % 1000000007;
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  const preparedInput = setup(n);
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = preparedInput;
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = preparedInput;
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "regex-match-all", category: "regex", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

regex-replace-callback.ts — sizes [100, 1000, 10000, 100000, 1000000]

Size meanings and fresh-input policy are in the leading metadata. result_on_stderr for this file: False.

// @runtime {"name": "regex-replace-callback", "category": "regex", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/regex/replace_expand.rs", "function": "js_string_replace_regex_fn"}], "hypothesis": "Hypothesis: regex replacement snapshots match data into owned strings, invokes the callback for each match, and copies the final output.", "notes": "Regex baseline, excluded from the main ranking. ", "asynchronous": false, "output_stderr": false, "fresh_input": false}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): string { return 'ab12 cd345;'.repeat(n); }
function run(input: string): number {
  return hashString(input.replace(/[0-9]+/g, (match) => '[' + match + ']'));
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  const preparedInput = setup(n);
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = preparedInput;
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = preparedInput;
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "regex-replace-callback", category: "regex", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

[proggeramlug]

Cost placement: whole-subject decode and program revalidation on every call — uncharged, on Perry's side

The ASCII quadratic (ASCII split at 6.9 s for n=10,000; the global exec loop) is not the budget charge from #10164. It is work that happens on every search and is never charged, so it never throws.

• execute_with_resources runs on every call. It calls program(…) → BoundProgram::new (full program revalidation via Program::from_words, charged) and then builds BoundSubject::new(HeapSubject::new(input)) (perex_api.rs:221).
• Binding a WTF-8 subject calls Input::wtf8 (src/binding.rs:119), which decodes every scalar of the whole string (src/input.rs:67) with no budget in scope.
• Split calls this once per position (perex_split.rs:142); a global exec / matchAll / replace loop calls it once per match.

So a split of an n-unit string decodes the whole string n times. At n ≈ 150,000 that is about 2.3e10 bytes decoded, which fits the measured 6.9 s. The same per-call binding happens in the non-ASCII variants, on top of the charged seek in #10164.

Proposed direction (Perry side): in split, replace, matchAll and the builtin global loops, when exec is the builtin, bind the program and subject once per operation and pass those bindings into the loop instead of rebinding inside execute_with_resources. That removes this cost within one operation. Per-call loops written in JavaScript (a while (re.exec(s)) loop) need the cross-call reuse described on #10166.

Status: placement from reading source, by the Perex maintainer and checked line by line against perry main b5a82cfeae and the published perex 0.1.0 crate. It is not yet measured. Ownership and scheduling are awaiting a maintainer decision, so please do not start source changes yet.

Related: #10164, #10166.

[proggeramlug]

Status: the Perry-side changes for this issue have landed on main.

• perf(regex): bind once per split/replace/match, and split searches forward (#10165) #10174 (train 177, Merge train 177: #10174 #10187): bind the subject and program once per split/replace/global match, and split searches forward instead of trying every position.
• perf(regex): resume searches and capture reads from the previous position (#10164) #10181 (train 179, Merge train 179: #10181 #10194): resume from the previous position within an operation.
• perf(regex): bind a RegExp's program and subject in constant work across calls (#10166) #10183 (train 180, Merge train 180: #10183 #10195, perex 0.1.3): bind in constant work across calls, so JS exec/matchAll/test loops no longer rebind per call.

Where the per-attempt positioning cost went: it was per-search rebinding (an uncharged Input::wtf8 decode plus program revalidation) and a nearer-end seek per search. It was placed on this issue and on the PRs, which carry fault injections showing each witness fails without its fix.

Same-host A/B from #10183, release builds, n = 40,000 (Node in brackets):

• ASCII: global exec loop 15.8 s → 0.34 s (9 ms); matchAll 19.1 s → 0.70 s (8 ms); test with /g 14.3 s → 0.23 s (5 ms). All linear.
• split on the reproducer: 582 → 33 ms after perf(regex): bind once per split/replace/match, and split searches forward (#10165) #10174.

Remaining gaps against the acceptance list:

• Non-ASCII exec/matchAll loops are still quadratic: 42–44 s at n = 40,000, against 7–8 ms on Node. This is the documented one-seek-per-call fallback; the position hint across calls was excluded.
• Patterns with required text after a class quantifier are O(lastIndex) per search in Perex. The fix is on perex main for 0.1.4.
• The same-host rerun of all four reproducers at 100 to 1M against the pre-Perex revision, with slope deltas, has not been done.

https://claude.ai/code/session_01Da12JXeG5XuVBma5yWp5C9