Skip to content

runtime: string.slice splits astral characters incorrectly and makes suffix parsing quadratic #10061

Closed
Closed
runtime: string.slice splits astral characters incorrectly and makes suffix parsing quadratic#10061
Labels
bugConfirmed defect or regressionparityCompatibility gap with Node.js, ECMAScript, or the supported ecosystemperformanceRuntime, compile-time, build-size, or memory performance

Description

@proggeramlug
proggeramlug
opened on Sep 11, 2026

What happened

The natural parse loop that consumes charCodeAt(0) and then assigns s = s.slice(1) has both a correctness defect and growing copy cost. ASCII reaches 77.22x Node at n=10,000 and times out at 100,000. Unicode fails checksum stability at n=100 and differs from Node at n=1,000. The small reduction below shows that slicing through an emoji yields UTF-8 byte values 195 and 150 where Node exposes the low surrogate and the following character.

Measured against Node v26.5.1 using Perry perry 0.5.1531 at 9495bfc95e2afcfb5a7cb535e440e61ec0722cb1. 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.

string-slice-parse-loop-ascii — TIMEOUT

n Node ms / status Perry ms / status ratio Node checksum Perry checksum
100 0.013911 0.020803 1.50× 464151292 464151292
1000 0.149910 0.439898 2.93× 710929850 710929850
10000 1.571994 121.388708 77.22× 535454277 535454277
100000 14.132584 TIMEOUT — 35382078 —
1000000 263.839459 SKIPPED — 153135489 —

Log(time)/log(n) least-squares slopes: Perry 1.883, Node 1.053, delta 0.830.

Workload: ascii variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. Reads one UTF-16 unit then removes it, including individual emoji surrogate halves; no manual optimized parser. charCodeAt(0) inspects only the current leading code unit, so the checksum itself does not scan a growing prefix. For Unicode, an offset inside an emoji must retain its low surrogate; the source byte-offset helper instead rounds beyond the complete code point.

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

string-slice-parse-loop-unicode — CORRECTNESS

n Node ms / status Perry ms / status ratio Node checksum Perry checksum
100 0.043733 CORRECTNESS — 319467163 —
1000 0.229326 73.777042 321.71× 431622199 399614474
10000 4.082667 TIMEOUT — 36132863 —
100000 40.820291 SKIPPED — 49951631 —
1000000 343.225625 SKIPPED — 481167302 —

Log(time)/log(n) least-squares slopes: Perry unavailable, Node 1.004, delta unavailable.

Workload: unicode variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. Reads one UTF-16 unit then removes it, including individual emoji surrogate halves; no manual optimized parser. charCodeAt(0) inspects only the current leading code unit, so the checksum itself does not scan a growing prefix. For Unicode, an offset inside an emoji must retain its low surrogate; the source byte-offset helper instead rounds beyond the complete code point.

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

perry n=100: CORRECTNESS, exit 1

Error: CORRECTNESS: unstable checksum during warmup

perry n=10000: TIMEOUT, exit -9

Process exceeded 60 s

What is expected / acceptance criteria

  • Match the embedded small reduction exactly: the remaining-code-unit sequence for ä中😀Ö must include the emoji's low surrogate and then Ö. Check empty strings, negative bounds, both halves of astral characters and pre-existing lone surrogates.
  • Eliminate unstable and mismatching checksums in the original Unicode benchmark; do not classify its speed until correctness holds.
  • Remeasure the unchanged ASCII and Unicode loops across increasing sizes and demonstrate removal of repeated full-suffix copying, with before/after timings and slopes.
  • Test sliced strings across moving GC and source lifetime changes; document the memory-retention policy if small slices share a large backing store.

Implementation to inspect

Hypothesis: utf16_offset_to_byte_offset advances over the complete astral character when the requested start lies between its two UTF-16 units. js_string_slice then copies from that rounded byte boundary while storing end-start as the result's UTF-16 length, creating inconsistent payload and length metadata. Separately, string_copy_range copies the remaining suffix on each loop iteration, producing quadratic total bytes. Fix correctness before interpreting Unicode timing. Consider sliced/shared storage or another general strategy for repeated suffix consumption; the appropriate representation must also preserve lone surrogates, lifetime and GC behavior.

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

Own string slice semantics and result storage in string/slice_ops.rs and string/mod.rs. Coordinate representation/helper changes with the trim and Unicode indexing tasks. Keep this scope separate from HIR for-of's iteration stride; that is a different correctness issue.

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.5.1 to match this baseline; 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/string-slice-parse-loop-ascii.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 = 'string-slice-parse-loop-ascii'
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: Apple M1 Max; 10 logical cores; arm64.
  • OS: macOS-26.5-arm64-arm-64bit-Mach-O; target: native host.
  • Node: v26.5.1; Perry: perry 0.5.1531; 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: [58.3896484375, 53.017578125, 57.90087890625]; end: [25.240234375, 30.416015625, 24.8681640625].
  • 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

string-slice-astral.ts

Each step records remaining UTF-16 length and first code unit. A 16-step cap bounds the diagnostic if slicing fails to make progress.

function inspect(input: string): string {
  let s = input;
  let out = "";
  for (let i = 0; i < 16 && s.length; i++) {
    out += s.length + ":" + s.charCodeAt(0) + ",";
    s = s.slice(1);
  }
  return out;
}
console.log(inspect("ä中😀Ö"));

Compile this reduction with the same command, substituting its filename. Run each engine once; no size argument is needed.

node (SUCCESS):

5:228,4:20013,3:55357,2:56832,1:214,

perry (SUCCESS):

5:228,4:20013,3:55357,2:195,1:150,

Complete standalone benchmark sources

string-slice-parse-loop-ascii.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": "string-slice-parse-loop-ascii", "category": "strings", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/string/slice_ops.rs", "function": "js_string_slice"}, {"file": "crates/perry-runtime/src/string/mod.rs", "function": "string_copy_range"}], "hypothesis": "Hypothesis: each slice allocates and copies the remaining suffix, so removing one code unit per iteration copies a quadratic total number of bytes.", "notes": "ascii variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. Reads one UTF-16 unit then removes it, including individual emoji surrogate halves; no manual optimized parser. charCodeAt(0) inspects only the current leading code unit, so the checksum itself does not scan a growing prefix. For Unicode, an offset inside an emoji must retain its low surrogate; the source byte-offset helper instead rounds beyond the complete code point.", "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 "aBcD".repeat(n); }
function run(input: string): number {
  let s = input;
  let h = 0;
  while (s.length) {
    h = (h * 31 + s.charCodeAt(0)) % 1000000007;
    s = s.slice(1);
  }
  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: "string-slice-parse-loop-ascii", category: "strings", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();
string-slice-parse-loop-unicode.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": "string-slice-parse-loop-unicode", "category": "strings", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/string/slice_ops.rs", "function": "js_string_slice"}, {"file": "crates/perry-runtime/src/string/mod.rs", "function": "string_copy_range"}, {"file": "crates/perry-runtime/src/string/mod.rs", "function": "utf16_offset_to_byte_offset"}], "hypothesis": "Hypothesis: utf16_offset_to_byte_offset advances over a whole astral character when slice starts between its surrogate halves; js_string_slice then copies the remaining bytes while stamping end-start as UTF-16 length, creating a payload/header mismatch. Repeated full-suffix copies also give quadratic work.", "notes": "unicode variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. Reads one UTF-16 unit then removes it, including individual emoji surrogate halves; no manual optimized parser. charCodeAt(0) inspects only the current leading code unit, so the checksum itself does not scan a growing prefix. For Unicode, an offset inside an emoji must retain its low surrogate; the source byte-offset helper instead rounds beyond the complete code point.", "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 "ä中😀Ö".repeat(n); }
function run(input: string): number {
  let s = input;
  let h = 0;
  while (s.length) {
    h = (h * 31 + s.charCodeAt(0)) % 1000000007;
    s = s.slice(1);
  }
  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: "string-slice-parse-loop-unicode", category: "strings", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

Activity

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 regressionparityCompatibility gap with Node.js, ECMAScript, or the supported ecosystemperformanceRuntime, 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