perf(runtime): push(...chunk) grows near-quadratically, reaching 330x Node at 100k elements

[proggeramlug]

What happened

On measured Perry SHA 9495bfc, building an array with repeated a.push(...chunk) calls over prebuilt 32-element chunks is 2.47x slower than Node at n=1,000, 35.46x at n=10,000 and 330.45x at n=100,000. The Perry benchmark process reaches its 60-second timeout at n=1,000,000. Completed result checksums match, and the ordinary array-push control does not show this growing gap. Here n is the total appended element count, not the number of calls. These measurements describe the pinned baseline only; current main has not been measured.

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.

array-push-spread-chunk — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.002991	0.003758	1.26×	397536938	397536938
1000	0.030248	0.074844	2.47×	60977410	60977410
10000	0.319906	11.345167	35.46×	840530610	840530610
100000	3.336018	1102.388791	330.45×	810288076	810288076
1000000	32.599333	TIMEOUT	—	863996427	—

Log(time)/log(n) least-squares slopes: Perry 1.858, Node 1.012, delta 0.847.

Workload: n is total elements; chunks have 32 elements, with a possibly shorter final chunk. No unbounded call-argument spread.

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

perry n=1000000: TIMEOUT, exit -9

Process exceeded 60 s

What is expected / acceptance criteria

• Rerun the embedded 32-element-chunk benchmark sequentially against Node under the identical timing/checksum protocol. Publish before/after times at every requested size and slopes over explicitly identified common completed sizes; retain matching checksums.
• Appending fixed-size chunks scales approximately linearly in total appended elements on the ordinary dense path, and the n=1,000,000 Perry benchmark process completes within the existing 60-second timeout. Verify that append bookkeeping is bounded by the new elements plus amortized capacity growth, rather than the complete prefix on every call.
• Keep the original array identity, returned push length, element order and aliases correct across capacity growth, forwarding and GC movement; cover empty chunks and the shorter final chunk as well as repeated reuse of a destination.
• Preserve the required iterator behavior for spread: own and prototype Symbol.iterator overrides, throwing iterators, holes, accessors and observable source/destination mutations must retain their proper behavior and evaluation order. Restrict any dense shortcut to cases where its proof is valid.
• Verify mixed numeric/pointer chunks and old-destination/young-element appends under the repository's moving-GC and tracing checks. Incremental layout maintenance must publish every live edge and maintain write barriers; replacing a full scan with incomplete tracing is not an acceptable optimization.
• Check js_array_concat callers and the generic js_array_push_spread_f64 path separately, including source/destination alias cases. Preserve non-mutating Array.prototype.concat semantics where applicable and rerun the ordinary array-push control to catch regressions.

Implementation to inspect

Hypothesis: the typed-local spread path performs a complete GC-layout reconstruction of the growing output after every 32-element append, producing Theta(n^2/32) bookkeeping even though the actual append copies only the new chunk. The source route matters: crates/perry-hir/src/lower/expr_call/local_array_methods.rs:382 creates Expr::ArrayPushSpread for the local array, and crates/perry-codegen/src/expr/array_push.rs:1523 calls js_array_concat. This is distinct from the generic NativeMethodCall push_spread route to js_array_push_spread_f64. In crates/perry-runtime/src/array/concat_reverse.rs:79, js_array_concat grows capacity geometrically if needed and copies src_len elements into the tail, then at line 154 calls rebuild_array_layout_exact over the entire result. crates/perry-runtime/src/array/header_gc_slots.rs:239 passes the full result length to layout_rebuild_exact_from_slots, refreshes numeric layout and, for an old-generation result, replays all slots' write barriers. crates/perry-runtime/src/gc/layout.rs:1114 explicitly allocates/rebuilds the pointer mask and scans every slot. The repeated whole-output scan is a concrete source-backed explanation for the observed curve, but its exact runtime share has not been profiled.

• crates/perry-runtime/src/array/concat_reverse.rs: js_array_concat
• crates/perry-runtime/src/array/header_gc_slots.rs: rebuild_array_layout_exact
• crates/perry-runtime/src/gc/layout.rs: layout_rebuild_exact_from_slots
• crates/perry-codegen/src/expr/array_push.rs: lower

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

Shares array/header_gc_slots.rs and gc/layout.rs with the separate shift-queue performance finding; coordinate any layout-maintenance changes and their GC invariants. The open-issue snapshot and targeted searches found no exact open duplicate. Closed #6386 concerns repeated fixed-size Array.concat results, not this growing destination; closed #8772 concerns short stable method-call spread tails, not ArrayPushSpread's concat helper; closed #7542 supplies iterator-override correctness history that any shortcut must preserve. Open #9983 is a separate array-tracing defect and relevant validation risk, not a demonstrated cause here. All attribution is to SHA 9495bfc; unmeasured current main may differ.

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: perf(runtime): Array.shift queue drain reaches 722x Node at 10k elements and times out at 100k #10060

• Related history/context: [perf] DataView accessors, Array.concat, and regex match-with-groups are 4–30x slower than Hermes #6386

• Related history/context: perf(codegen): direct-call stable methods with short packed spread tails #8772

• Related history/context: spread: a replaced Array.prototype[Symbol.iterator] is ignored by [...arr] #7542

• Related history/context: GC: a 12-element array persistently holds a pointer at index 10 that the slot enumeration never visits (UNENUMERATED, reserved=0x8020) #9983

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/array-push-spread-chunk.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 = 'array-push-spread-chunk'
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

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

Complete standalone benchmark sources

array-push-spread-chunk.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": "array-push-spread-chunk", "category": "arrays", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/array/concat_reverse.rs", "function": "js_array_concat"}, {"file": "crates/perry-runtime/src/array/header_gc_slots.rs", "function": "rebuild_array_layout_exact"}, {"file": "crates/perry-runtime/src/gc/layout.rs", "function": "layout_rebuild_exact_from_slots"}, {"file": "crates/perry-codegen/src/expr/array_push.rs", "function": "lower"}], "hypothesis": "The typed-local spread-push path calls js_array_concat, which rebuilds GC layout across the entire growing output after every chunk, causing quadratic bookkeeping for fixed-size chunks.", "notes": "n is total elements; chunks have 32 elements, with a possibly shorter final chunk. No unbounded call-argument spread.", "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): number[][] {
  const chunks: number[][] = [];
  for (let i = 0; i < n; i += 32) {
    const chunk: number[] = [];
    for (let j = i; j < Math.min(n, i + 32); j++) chunk.push(Math.floor(rnd() * 1000000));
    chunks.push(chunk);
  }
  return chunks;
}

function run(chunks: number[][]): number {
  const a: number[] = [];
  for (let i = 0; i < chunks.length; i++) a.push(...chunks[i]);
  return hashArray(a);
}

// 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: "array-push-spread-chunk", category: "arrays", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

[proggeramlug]

Fixed by #10072, landed on main via merge train #10095 at 241e8ee1c.

The close keyword did not fire because the train merges as its own branch, so closing manually.