perf(runtime): Array.shift queue drain reaches 722x Node at 10k elements and times out at 100k

[proggeramlug]

What happened

On measured Perry SHA 9495bfc, draining a fresh number[] with while (q.length) q.shift() is 721.77x slower than Node at n=10,000. The Perry benchmark process reaches its 60-second timeout at n=100,000. Completed runs have matching order-sensitive checksums. Node's queue drain also becomes expensive at large sizes and its n=1,000,000 benchmark process times out; this issue does not assume universally constant-time Node shift. 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-shift-queue — TIMEOUT

n	Node ms / status	Perry ms / status	ratio	Node checksum	Perry checksum
100	0.004038	0.034798	8.62×	534569475	534569475
1000	0.053744	1.570074	29.21×	965032923	965032923
10000	0.850686	613.996667	721.77×	663245961	663245961
100000	983.526375	TIMEOUT	—	987888354	—
1000000	TIMEOUT	SKIPPED	—	—	—

Log(time)/log(n) least-squares slopes: Perry 2.123, Node 1.736, delta 0.387.

Workload: See the complete source below.

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

perry n=100000: TIMEOUT, exit -9

Process exceeded 60 s

node n=1000000: TIMEOUT, exit -9

Process exceeded 60 s

What is expected / acceptance criteria

• Rerun the embedded benchmark sequentially against Node with the same source, sizes, warmup, seven-sample median and 60-second process timeout; retain matching checksums and report before/after times plus slopes over explicitly identified common completed sizes.
• The n=100,000 Perry benchmark process completes within the existing timeout, and the dense queue drain demonstrates materially reduced growth in total work as n increases; document the chosen representation or algorithm rather than claiming improvement from a constant-factor-only change.
• For the ordinary dense fast path, avoid a mandatory copy and complete GC-layout rebuild of every survivor on every removal; verify that any lazy offset, compaction or equivalent bookkeeping preserves array indexing, aliases, length, subsequent push/pop and empty-array reuse.
• Preserve JavaScript shift behavior for empty arrays, holes, inherited indexed properties, indexed getters/setters, non-writable length and frozen arrays, including side effects and abrupt-completion order on the generic path.
• Validate pointer-bearing and mixed arrays under the repository's GC stress checks, including moving collection, old-to-young edges, growth/forwarding and repeated drain/refill. Removed values must not remain roots solely because stale storage is retained, and live surviving slots must remain traceable.
• Rerun array-push and the shared layout-mutator checks affected by the implementation; publish any tradeoff in allocation, retained capacity or RSS alongside the queue timings. Preserve timeout outcomes for Node rather than treating them as completed samples.

Implementation to inspect

Hypothesis: every successful dense shift moves and reclassifies the surviving prefix, making a full drain quadratic and amplifying the gap beyond raw byte movement. The typed-local path is explicit: crates/perry-hir/src/lower/expr_call/local_array_methods.rs:425 emits Expr::ArrayShift; crates/perry-codegen/src/expr/logical_collections.rs:1191 calls js_array_shift_f64. In crates/perry-runtime/src/array/push_pop.rs:1520, that function first guards exotic receivers, then its dense arm calls ptr::copy for length-1 elements, decrements length and calls rebuild_array_layout. The latter, in crates/perry-runtime/src/array/header_gc_slots.rs:167, rebuilds GC slot layout over the surviving length, refreshes numeric layout and replays every surviving slot's write barrier for old-generation arrays. Repeating this over lengths n-1 through zero yields a quadratic amount of survivor work. The exotic path separately preserves observable HasProperty/Get/Set/Delete ordering and must remain correct. This is source attribution, not a sampled profile proving the fraction spent in each helper.

• crates/perry-runtime/src/array/push_pop.rs: js_array_shift_f64

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 crates/perry-runtime/src/array/header_gc_slots.rs and crates/perry-runtime/src/gc/layout.rs with the separate fixed-chunk push(...chunk) performance finding. Coordinate changes to array storage, tracing and layout maintenance so those fixes use compatible invariants. Open issue #9983 concerns incomplete array slot tracing; it is related GC risk, not an established cause of this performance result. The open-issue snapshot and targeted shift/spread/concat searches found no exact open duplicate. #8410 is a broader Node-performance tracker with a different benchmark corpus. No conclusion is made about whether unmeasured current main has already changed this behavior.

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): push(...chunk) grows near-quadratically, reaching 330x Node at 100k elements #10058

• 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

• Related history/context: tracking: close the remaining 7 losing rows vs Node (12/19 won, geomean 0.7775x) #8410

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-shift-queue.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-shift-queue'
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-shift-queue.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-shift-queue", "category": "arrays", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/array/push_pop.rs", "function": "js_array_shift_f64"}], "hypothesis": "The generic shift path may move surviving elements on every removal.", "notes": "", "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): number[] { return numbers(n); }
function run(q: number[]): number {
  let h = 0;
  while (q.length) h = (h * 31 + q.shift()!) % 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;
  
  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: "array-shift-queue", category: "arrays", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

[proggeramlug]

Fixed by #10077, landed on main via merge train #10113 at 1f9b33f2d.

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