Skip to content

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

Open
Open
perf(regex): split, replace, matchAll and global exec do quadratic work under Perex — split regressed from ~7x Node to timing out#10165
Labels
bugConfirmed defect or regressionperformanceRuntime, compile-time, build-size, or memory performance

Description

@proggeramlug
proggeramlug
opened on Sep 13, 2026

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.

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.

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();

Activity

  1. proggeramlug
    added
    bugConfirmed defect or regression
    performanceRuntime, compile-time, build-size, or memory performance
    on Sep 13, 2026

  2. proggeramlug commented on Sep 13, 2026

    @proggeramlug
    proggeramlug
    on Sep 13, 2026
    ContributorAuthor

    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.

    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.

  3. proggeramlug
    added 11 commits that reference this issue on Sep 13, 2026

    perf(regex): split searches forward instead of trying every position (#…

    d7e2ae7

    perf(regex): split searches forward instead of trying every position (#…

    b9ec0ba

    gc: record the forward-split test counter's holder verdict (#10165)

    d61fe85

    perf(regex): bind subject and program once per split/replace/match (#…

    302e07b

    perf(regex): split searches forward instead of trying every position (#…

    846ef07

    gc: record the forward-split test counter's holder verdict (#10165)

    96f8688

    perf(regex): bind subject and program once per split/replace/match (#…

    08ff2c9

    perf(regex): split searches forward instead of trying every position (#…

    d216989

    gc: record the forward-split test counter's holder verdict (#10165)

    b8e411e

    fix(regex): do not cap RegExp operations by work (#10164)

    6176e28

    fix(regex): do not cap RegExp operations by work (#10164)

    0ec7ee1

  4. proggeramlug commented on Sep 13, 2026

    @proggeramlug
    proggeramlug
    on Sep 13, 2026
    ContributorAuthor

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

    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):

    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

  5. proggeramlug commented on Sep 13, 2026

    @proggeramlug
    proggeramlug
    on Sep 13, 2026
    ContributorAuthor

    Same-host rerun of the full reproducers, as the acceptance list asks.

    Setup: perrymaster (Linux x86_64, 16 logical CPUs, shared with other lanes; load average 11–23 during the runs), Node v26.8.1, hostile-benchmarks/runtime/run.py --filter regex, release builds from source.

    Verdict: not closable yet

    regex-split

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.016 ms 0.07 ms (4.1×) 0.27 ms (16.6×) = Node
    1,000 0.106 ms 0.71 ms (6.7×) 4.82 ms (45.4×) = Node
    10,000 1.579 ms 7.22 ms (4.6×) 25.55 ms (16.2×) = Node
    100,000 16.860 ms 72.98 ms (4.3×) 355.55 ms (21.1×) = Node
    1,000,000 328.399 ms 769.88 ms (2.3×) TIMEOUT —

    Log-log slope over 1k–100k: Node 1.100, main 0.934 (delta -0.166), pre-Perex 1.005.

    regex-exec-global

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.023 ms 0.47 ms (20.2×) 0.84 ms (36.1×) = Node
    1,000 0.220 ms 22.12 ms (100.3×) 8.14 ms (36.9×) = Node
    10,000 2.011 ms 1,209.51 ms (601.6×) 62.98 ms (31.3×) = Node
    100,000 19.646 ms TIMEOUT 716.54 ms (36.5×) = Node
    1,000,000 184.496 ms SKIPPED TIMEOUT —

    Log-log slope over 1k–100k: Node 0.975, main 0.972 (delta -0.003), pre-Perex n/a (a size did not complete).

    regex-match-all

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.020 ms 0.38 ms (19.4×) 1.34 ms (67.8×) = Node
    1,000 0.131 ms 14.65 ms (111.7×) 13.95 ms (106.3×) = Node
    10,000 2.124 ms 481.64 ms (226.7×) 137.25 ms (64.6×) = Node
    100,000 21.345 ms TIMEOUT 830.76 ms (38.9×) = Node
    1,000,000 128.473 ms SKIPPED TIMEOUT —

    Log-log slope over 1k–100k: Node 1.106, main 0.887 (delta -0.218), pre-Perex n/a (a size did not complete).

    regex-replace-callback

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.016 ms 0.08 ms (5.0×) 1.63 ms (100.3×) = Node
    1,000 0.174 ms 4.33 ms (24.9×) 14.93 ms (85.8×) = Node
    10,000 1.115 ms 376.66 ms (337.9×) 164.58 ms (147.7×) = Node
    100,000 18.501 ms TIMEOUT 1,736.29 ms (93.8×) = Node
    1,000,000 394.274 ms SKIPPED memory-limit RangeError —

    Log-log slope over 1k–100k: Node 1.013, main 1.033 (delta +0.019), pre-Perex n/a (a size did not complete).

    regex-exec-global-unicode

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.034 ms 0.61 ms (18.0×) 0.99 ms (29.4×) = Node
    1,000 0.442 ms 33.82 ms (76.6×) 33.80 ms (76.5×) = Node
    10,000 3.423 ms 2,981.25 ms (870.9×) 3,344.79 ms (977.2×) = Node
    100,000 40.625 ms TIMEOUT TIMEOUT —
    1,000,000 426.049 ms SKIPPED SKIPPED —

    Log-log slope over 1k–100k: Node 0.982, main n/a (a size did not complete), pre-Perex n/a (a size did not complete).

    regex-match-all-unicode

    n Node pre-Perex 9495bfc95 main 5d3bf85f9 checksums (main)
    100 0.046 ms 0.72 ms (15.8×) 1.80 ms (39.4×) = Node
    1,000 0.434 ms 18.46 ms (42.6×) 46.24 ms (106.7×) = Node
    10,000 3.744 ms 741.78 ms (198.1×) 2,639.47 ms (705.0×) = Node
    100,000 44.060 ms TIMEOUT TIMEOUT —
    1,000,000 382.383 ms SKIPPED SKIPPED —

    Log-log slope over 1k–100k: Node 1.004, main n/a (a size did not complete), pre-Perex n/a (a size did not complete).

    https://claude.ai/code/session_01Da12JXeG5XuVBma5yWp5C9

  6. proggeramlug commented on Sep 13, 2026

    @proggeramlug
    proggeramlug
    on Sep 13, 2026
    ContributorAuthor

    Non-ASCII rows rerun after #10205 (JS-level searches resume from the previous call's position), landed via train 182 as 0956673b5. Same host, harness and Node v26.8.1 as the earlier rerun. The pre-Perex (9495bfc95) and pre-#10205 (5d3bf85f9) columns are copied from that run.

    Neither issue meets its acceptance list yet, for the reasons above and in the earlier comment.

    regex-exec-global-unicode

    n Node pre-Perex 9495bfc95 5d3bf85f9 (before #10205) 0956673b5 (with #10205) checksum
    100 0.045 ms 0.61 ms 0.99 ms 0.64 ms (14.0×) = Node
    1,000 0.324 ms 33.82 ms 33.80 ms 5.60 ms (17.3×) = Node
    10,000 3.878 ms 2,981.25 ms 3,344.79 ms 61.13 ms (15.8×) = Node
    100,000 32.132 ms TIMEOUT TIMEOUT 614.73 ms (19.1×) = Node
    1,000,000 318.011 ms SKIPPED SKIPPED TIMEOUT —

    regex-match-all-unicode

    n Node pre-Perex 9495bfc95 5d3bf85f9 (before #10205) 0956673b5 (with #10205) checksum
    100 0.032 ms 0.72 ms 1.80 ms 0.86 ms (27.3×) = Node
    1,000 0.316 ms 18.46 ms 46.24 ms 8.46 ms (26.8×) = Node
    10,000 3.213 ms 741.78 ms 2,639.47 ms 84.51 ms (26.3×) = Node
    100,000 31.088 ms TIMEOUT TIMEOUT 946.93 ms (30.5×) = Node
    1,000,000 328.592 ms SKIPPED SKIPPED TIMEOUT —

    regex-replace-callback-unicode

    n Node pre-Perex 9495bfc95 5d3bf85f9 (before #10205) 0956673b5 (with #10205) checksum
    100 0.012 ms 0.22 ms 0.99 ms 0.98 ms (84.2×) = Node
    1,000 0.144 ms 8.13 ms 10.04 ms 10.23 ms (70.9×) = Node
    10,000 1.196 ms 748.77 ms 185.94 ms 115.96 ms (96.9×) = Node
    100,000 28.077 ms TIMEOUT 1,725.68 ms 1,754.77 ms (62.5×) = Node
    1,000,000 437.341 ms SKIPPED memory-limit RangeError memory-limit RangeError —

    regex-split-unicode

    n Node pre-Perex 9495bfc95 5d3bf85f9 (before #10205) 0956673b5 (with #10205) checksum
    100 0.010 ms 0.09 ms 0.51 ms 0.25 ms (24.6×) = Node
    1,000 0.108 ms 0.89 ms 2.80 ms 2.40 ms (22.3×) = Node
    10,000 1.189 ms 8.91 ms 33.98 ms 24.03 ms (20.2×) = Node
    100,000 12.283 ms 90.83 ms 279.64 ms 254.28 ms (20.7×) = Node
    1,000,000 273.272 ms 934.07 ms TIMEOUT TIMEOUT —

    regex-test-literal-unicode

    n Node pre-Perex 9495bfc95 5d3bf85f9 (before #10205) 0956673b5 (with #10205) checksum
    100 0.002 ms 0.01 ms 0.24 ms 0.15 ms (71.0×) = Node
    1,000 0.021 ms 0.11 ms 2.77 ms 1.55 ms (72.2×) = Node
    10,000 0.211 ms 1.15 ms 15.57 ms 15.46 ms (73.2×) = Node
    100,000 2.053 ms 11.63 ms 157.62 ms 159.85 ms (77.9×) = Node
    1,000,000 20.091 ms 114.78 ms 2,013.81 ms 1,599.12 ms (79.6×) = Node

    https://claude.ai/code/session_01Da12JXeG5XuVBma5yWp5C9

  7. proggeramlug
    added a commit that references this issue on Sep 13, 2026

    perf(regex): replace without exec result objects when every step is t…

    90354eb

  8. proggeramlug commented on Sep 16, 2026

    @proggeramlug
    proggeramlug
    on Sep 16, 2026
    ContributorAuthor

    Rerun at every size now that #10215 is fixed

    #10215 (arrays of ~9M+ elements holding heap strings corrupting) was the reason the 1M rows could not be trusted; it landed in train 186, so here is the full sweep. Same host as the earlier reruns (perrymaster), Node v26.8.1, release builds from source, --no-auto-optimize, each size given the harness's 60 s process budget covering at least 5 warm-ups and 7 samples. Perry is main at 33690c563 (v0.5.1580, after train 201).

    Four of the eight now complete at 1M; four still exceed the budget. Every completed row matches Node's checksum at every size.

    regex-split

    n Node main x Node checksum
    100 0.010 ms 0.219 ms 23.0x = Node
    1,000 0.095 ms 2.128 ms 22.4x = Node
    10,000 0.991 ms 21.215 ms 21.4x = Node
    100,000 10.608 ms 218.548 ms 20.6x = Node
    1,000,000 240.403 ms 3883.172 ms 16.2x = Node

    regex-split-unicode

    n Node main x Node checksum
    100 0.010 ms 0.224 ms 21.6x = Node
    1,000 0.111 ms 2.267 ms 20.5x = Node
    10,000 1.056 ms 21.797 ms 20.6x = Node
    100,000 12.643 ms 214.484 ms 17.0x = Node
    1,000,000 266.168 ms 4005.514 ms 15.0x = Node

    regex-replace-callback

    n Node main x Node checksum
    100 0.010 ms 0.330 ms 33.0x = Node
    1,000 0.096 ms 3.207 ms 33.4x = Node
    10,000 0.968 ms 41.518 ms 42.9x = Node
    100,000 12.010 ms 413.099 ms 34.4x = Node
    1,000,000 275.524 ms TIMEOUT >60 s — —

    regex-replace-callback-unicode

    n Node main x Node checksum
    100 0.011 ms 0.365 ms 33.1x = Node
    1,000 0.106 ms 4.064 ms 38.2x = Node
    10,000 1.085 ms 40.789 ms 37.6x = Node
    100,000 19.891 ms 429.205 ms 21.6x = Node
    1,000,000 335.314 ms TIMEOUT >60 s — —

    regex-match-all

    n Node main x Node checksum
    100 0.013 ms 0.407 ms 32.2x = Node
    1,000 0.125 ms 3.958 ms 31.6x = Node
    10,000 1.242 ms 40.684 ms 32.8x = Node
    100,000 12.321 ms 434.500 ms 35.3x = Node
    1,000,000 123.279 ms 4291.779 ms 34.8x = Node

    regex-match-all-unicode

    n Node main x Node checksum
    100 0.031 ms 0.556 ms 17.9x = Node
    1,000 0.306 ms 5.429 ms 17.7x = Node
    10,000 3.058 ms 55.778 ms 18.2x = Node
    100,000 30.436 ms 584.858 ms 19.2x = Node
    1,000,000 304.821 ms TIMEOUT >60 s — —

    regex-exec-global

    n Node main x Node checksum
    100 0.013 ms 0.278 ms 21.3x = Node
    1,000 0.125 ms 2.856 ms 22.8x = Node
    10,000 1.232 ms 28.562 ms 23.2x = Node
    100,000 11.527 ms 305.772 ms 26.5x = Node
    1,000,000 118.293 ms 3055.277 ms 25.8x = Node

    regex-exec-global-unicode

    n Node main x Node checksum
    100 0.031 ms 0.424 ms 13.5x = Node
    1,000 0.309 ms 4.351 ms 14.1x = Node
    10,000 3.087 ms 43.320 ms 14.0x = Node
    100,000 30.712 ms 467.876 ms 15.2x = Node
    1,000,000 307.591 ms TIMEOUT >60 s — —

    Where this leaves the two issues

    Completing at 1M for the first time: regex-split (16.2× Node), regex-split-unicode (15.0×), regex-match-all (34.8×) and regex-exec-global (25.8×). On the 2026-09-13 rerun exec and matchAll completed only to 100k.

    Still over the 60 s budget at 1M: both regex-replace-callback rows, regex-match-all-unicode and regex-exec-global-unicode. These are what block acceptance on #10164 and #10165. Note the shape: the two that time out on the non-ASCII side complete comfortably at 100k (19.2× and 15.2×), so the wall is between 100k and 1M rather than a per-call constant, and replace with a callback times out on both encodings while split completes on both.

    Ratios are otherwise flat in n, which is what the earlier reruns established and this confirms: 20–23× for split, 32–35× for matchAll, 21–27× for exec, 33–43× for callback replace. No row shows a slope that grows with size up to 100k.

    Two things worth recording for whoever takes the remaining four:

  9. proggeramlug commented on Sep 16, 2026

    @proggeramlug
    proggeramlug
    on Sep 16, 2026
    ContributorAuthor

    Two of the four 1M "timeouts" are a harness budget artifact, not a cliff

    Correcting my own framing from earlier today. I reported four rows exceeding the 60 s budget at n=1,000,000 and called the shape "a cliff between 100k and 1M". For two of them that is wrong, and anyone chasing it would be chasing something that does not exist.

    Run outside the harness with a 600 s ceiling, same binaries, same host (main at 33690c563):

    workload ms per run at 1M wall for the full protocol × Node checksum
    regex-match-all-unicode 6,785.2 83 s 22.3× = Node
    regex-exec-global-unicode 5,345.7 64 s 17.4× = Node
    regex-replace-callback 7,986.8 103 s 29.0× = Node
    regex-replace-callback-unicode 8,672.5 114 s 25.9× = Node

    All four complete and all four match Node's checksum. The 60 s budget covers at least five warm-up runs plus seven samples — twelve runs — so a workload taking 5–8 s per run needs 60–100 s of budget to report at all. The timeout therefore restates the Perry/Node ratio; it carries no information about asymptotics.

    For regex-match-all-unicode and regex-exec-global-unicode that is the whole story. Their 1M ratios (22.3× and 17.4×) sit in the same band as their 100k ratios (19.2× and 15.2×), so they are linear and there is nothing between 100k and 1M to find.

    The two replace rows ARE superlinear, and it is GC

    regex-replace-callback, ms per run, same binary:

    n 100k 200k 250k 300k 350k 400k 700k 1M
    ms 413.1 864.3 1,184.6 1,772.5 2,394.2 2,829.7 5,743.9 7,986.8
    µs per 1k records 4.13 4.32 4.74 5.91 6.84 7.07 8.21 7.99

    Per-unit cost roughly doubles between 200k and 700k and then flattens — a transition, not an asymptotic blow-up. PERRY_GC_DIAG names it:

    n=200k n=700k
    cycles 179 698
    triggers — 1,178 OldGenBytes fulls vs 218 ArenaBytes minors
    step_us 1.70 s 29.58 s
    mark barrier armed 0.97 s 24.82 s
    GC share of wall 230‰ 567‰

    At 700k more than half of the run is collection, and the per-cycle cost has grown 4.5× (9.5 ms → 42.4 ms) because each cycle meets a larger live heap. At 200k the median collection frees 0 bytes — over half of them reclaim nothing at all.

    So the remaining work on this issue is the full cadence on an allocating regex loop, not the engine and not the per-call path.

    One caution for whoever takes it, learned the hard way today: the obvious fix is not simply "fire fewer cycles". I tried exactly that (#10377, now withdrawn) and it cut cycles by 79 % at 700k while making the workload 8–16 % slower, because fewer cycles meet a bigger heap — more marking each, and a longer armed-barrier window taxing every write in between. Any candidate needs measuring on this workload at n ≥ 700,000, where the cost lives; a small-live-set reproducer cannot show it.

  10. proggeramlug commented on Sep 17, 2026

    @proggeramlug
    proggeramlug
    on Sep 17, 2026
    ContributorAuthor

    The replace rows' cost is now attributed; full detail on #10164 to keep it in one place.

    Short version: it is not the engine and not GC pacing. str.replace(/re/g, "template") runs the direct fast path from #10225, which retains every match span before emitting, and that path holds ~8 KB of live heap per match — 1.6 GB live on a 2.2 MB subject at n=200,000, 121× Node. The same replacement expressed as a callback holds a flat live heap and sits at 14.5× Node. Adding a named group, which declines the fast path, drops live heap 6.7× (406 MB → 60 MB at n=50,000) and is faster than the fast path by n=100,000.

    So the fast path is a net loss above roughly 100k matches, and the acceptance evidence behind it only covered short subjects. Options and the measurement recipe are on #10164.

  11. proggeramlug commented on Sep 18, 2026

    @proggeramlug
    proggeramlug
    on Sep 18, 2026
    ContributorAuthor

    The quadratic is gone; what is left is a constant factor of ~10x

    Retested on current main. The scaling exponent this issue is named for no longer reproduces.

    Log-log slopes over the same Unicode workloads, three decades of input, against Node 26.5.1 on the same host:

    workload Perry slope now Node slope recorded on this issue
    split(/[，；😀]+/u) 0.96 – 1.03 1.08 Perry 1.862, Node 1.090
    replace(/[ä中😀Ö漢🦊]+/gu, cb) 1.02 – 1.08 0.99 —

    Milliseconds, median of the run:

    chars Perry split Node split Perry replace+cb Node replace+cb
    ~1,600 1 1 1 2
    ~16,000 3 0 6 6
    ~160,000 38 3 54 6
    ~1,600,000 349 36 645 58

    Perry's slope is now indistinguishable from Node's. Nothing times out: 1.6 million characters splits in 349 ms and replaces in 645 ms, where this issue records TIMEOUT and UNSUPPORTED two decades earlier.

    So the title is no longer accurate. "split regressed from ~7x Node to timing out" is now "split is 9.7x Node and linear" — which is approximately the ~7x this issue cites as the pre-regression baseline, not a regression from it. The replace-with-callback row is 11.1x.

    I would suggest rescoping rather than closing, because the remaining gap is real and is the natural successor to this issue: split, replace-with-callback, matchAll and global exec are linear but cost roughly 10x Node per character. That is a constant-factor problem with a different cause and a different fix from the quadratic, and keeping it under a title about quadratic work and timeouts will mislead whoever picks it up. Happy to retitle this one and replace the description with the current evidence, or close it and open the narrower issue — say which you prefer.

    Worth noting for whoever takes that: #10412 rewrote the string-template replace path to record pieces natively (1,870 MB -> 108 MB RSS, 45 s -> 3.3 s at n=200,000) and deliberately did not touch the callback rows, because a callback requires the traced JS piece list. The 11.1x replace-with-callback row above is exactly that untouched path, so it is the obvious first place to look.

    Two of the four "1M timeouts" recorded on this issue are harness-budget artifacts rather than cliffs, which is already noted in the thread and still stands.

    Measured on c8cf45056 plus the adoption in #10580 — a fixed ~300-instruction per-call saving, which cannot change a scaling exponent, so the slope conclusion is independent of it. Absolute milliseconds came from a host running other sessions' builds; they are shape evidence, and the ~10x ratios should be re-taken on a quiet host before anyone quotes them as a target.

  12. proggeramlug commented on Sep 18, 2026

    @proggeramlug
    proggeramlug
    on Sep 18, 2026
    ContributorAuthor

    First bite out of the remaining constant factor: #10605, the callback row −27.2%

    Following the rescope above — the quadratic is gone, what is left is a constant factor of ~10x, and replace-with-callback was the worst row. #10605 takes 27% off it.

    Attribution first. Profiling the callback path against the template path on the same ASCII input (the template path is #10412's, which deliberately did not touch callbacks):

    subsystem callback template
    collector 40.4% (28.4 B instr) 32.2% (8.9 B)
    JS array ops 11.7% (8.2 B) ~0%
    exception / try frames 5.3% (3.7 B) 2.4% (0.7 B)
    regex engine 11.6% (8.2 B) 26.1% (7.3 B)

    The engine does the same work in both arms — 8.2 B against 7.3 B — which is what says the difference is host machinery rather than matching. The callback path's extra ~43 B instructions are 46% collector and 19% JS array operations.

    Cause. Each match built a fresh JS array to carry the replacer's arguments: js_array_alloc(0), then a push per argument that reallocated as it grew, each push opening a handle scope and a caught frame. call then read the whole array straight back out into native slots and dropped it. For an ordinary replacer nothing could observe it; a proxy replacer is the exception, since its apply trap really does receive an arguments array.

    Fix. Those native slots are already the collector's roots — call binds each to the shadow stack before invoking the replacer. Binding first and writing the arguments into them removes the array entirely, and a value is rooted from the moment it is written, so producing the next one may allocate and collect. Proxy replacers keep the array path.

    Result, both arms on one commit, arms verified distinct by md5: callback ASCII 30.3x → 22.1x Node, Unicode 21.1x → 16.3x, and the string-template control unchanged at +0.0%. On this issue's own workload, 137 ms → 60 ms at 150,000 characters.

    One thing worth recording here rather than only in the PR: with the reused buffer's reset removed, the entire 3,984-test lib suite still passed. Nothing in it covers a capture that participates in one match and not the next, which is the only shape a stale slot shows up in. That gap is now closed by a regression test which also asserts it reached the direct path, so it cannot pass against the exec-object fallback.

    Remaining on this issue after #10605: the string-template row is still ~16x Node and the collector is still the largest single consumer on both paths, so the next question is what is actually being allocated per match rather than per call.

  13. proggeramlug commented on Sep 27, 2026

    @proggeramlug
    proggeramlug
    on Sep 27, 2026
    ContributorAuthor

    Partial progress: #11543 landed and cuts host-side split / string-template replace overhead on ASCII subjects. encodeURI(s).split(/%..|./) is −43.3% instructions/iter, "a-b-c".replace(/-/g, "+") is −14.7%, and validator/sanitize is −4.2%. None of that is in the matcher.

    What remains for this issue:

  14. proggeramlug commented on Sep 28, 2026

    @proggeramlug
    proggeramlug
    on Sep 28, 2026
    ContributorAuthor

    Progress: #11548 landed perex 0.1.11 (the PerryTS/perex#3 matcher), under the owner-approved one-time publish-age override. Instructions: jsonwebtoken decode −61%, uuid v4 −48%, v7 −34%, v5_parse −28%, nanoid −30%, uuid/jws regex micro −65%/−84%; commander +0.4%; RSS flat. Together with #11543 this is the planned matcher + host work; leaving it open for the remaining gap to Node.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugConfirmed defect or regressionperformanceRuntime, compile-time, build-size, or memory performance

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions