new Array(n) above 1M elements makes every indexed write a string-keyed property set (quadratic fill)

[proggeramlug]

Summary

new Array(n) with n > 1_000_000 allocates a zero-capacity array header carrying the full logical length. Every subsequent indexed write then satisfies index < length && index >= capacity, which routes unconditionally to array_sparse_index_property_set — a string-keyed property set. Filling such an array is therefore quadratic with a memcmp in the inner loop, and never completes for realistic sizes.

The cliff is exact and sharp: 1,000,000 slots fills in 1 ms; 1,000,001 does not finish.

Reproducer

function fillAndVerify(slots: number): string {
  const t0 = Date.now();
  const v: number[] = new Array(slots);
  for (let i = 0; i < slots; i++) v[i] = i;
  const fillMs = Date.now() - t0;

  let bad = 0;
  for (let i = 0; i < slots; i++) {
    if (v[i] !== i) bad++;
  }
  return `slots=${slots} fill_ms=${fillMs} wrong_values=${bad} ok=${bad === 0}`;
}

for (const slots of [250000, 500000, 1000000, 1100000, 1500000]) {
  console.log(fillAndVerify(slots));
}
console.log('done');

perry compile repro.ts -o repro && ./repro

Actual

slots=250000 fill_ms=1 wrong_values=0 ok=true
slots=500000 fill_ms=1 wrong_values=0 ok=true
slots=1000000 fill_ms=1 wrong_values=0 ok=true
<hangs — the 1,100,000 row does not complete within 240 s>

Expected

All five rows complete in single-digit ms with ok=true. For reference, the same loop against a Float64Array, or against new Array() + push, is ~1–3 ms.

Environment

• perry 0.5.1519, main @ d9bd897777
• macOS 15 (Darwin 25.5.0), aarch64
• Release build, default flags

Root cause

crates/perry-runtime/src/array/alloc.rs:186 — a large fresh holey array is given the full logical length but a zero-capacity backing store:

const MAX_FRESH_DENSE_ARRAY_LENGTH: u32 = 1_000_000;
let arr = if length > MAX_FRESH_DENSE_ARRAY_LENGTH {
    let arr = js_array_alloc(0);
    unsafe { (*arr).length = length; }
    arr

That is deliberate and reasonable on its own (it avoids reserving ~32 GiB for new Array(2**32-1)).

The problem is the consumer. crates/perry-runtime/src/array/indexing.rs:1923:

// If index is within bounds, just set it
if index < length {
    if is_frozen { return arr; }
    if index >= (*arr).capacity {
        let value = value_handle.get_nanbox_f64();
        array_sparse_index_property_set(arr, index, value);   // <-- quadratic
        return arr;
    }

With capacity == 0 and length == n, every write to such an array takes this branch.

Note the extend path immediately below already guards this exact hazard, using DENSE_ARRAY_GAP_LIMIT (indexing.rs:24) to keep sequential growth dense — and its comment names the consequence explicitly:

sequential growth (for (i...) arr[i] = v, gap 0) must stay dense no matter how large the array gets — routing it through string-keyed property sets is quadratic and hung the 10M-element 03_array_write benchmark for 6 hours

The in-bounds branch never consulted that rule. So the guard exists, but only on the path that extends length, not on the path that fills a pre-sized array.

Impact

This blocks native rendering in a real app. perry-three's renderer.ts::uploadGeometry does:

const vertices: number[] = new Array(vertexCount * 12);

For a moderate scene that is ~2.4M slots, so the first frame never completes. Observed in Claude-of-Duty: the window opens, all engine init phases finish, then the process pins one core at 100% indefinitely. A sample shows the expected signature:

perry_runtime::gc::barrier::write_barrier_slot_decoded   2027
perry_runtime::array::header::array_named_property_set   1199
_platform_memcmp                                          859

Warning for whoever fixes this

The obvious fix — in that in-bounds branch, grow the dense store when the gap is small, mirroring the extend path — produces silent data corruption, at least as I wrote it. It looks like a complete success on timing:

slots	before	after naive fix
1,500,000	>180 s	93 ms
2,000,000	>180 s	173 ms

…but the values do not survive:

slots	result
900,000 (below threshold, patch inactive)	wrong_values=0
1,200,000 (above threshold, patch active)	wrong_values=524290, v[0] === undefined

Writes go missing — slots read back as holes. I did not establish why. js_array_grow itself looks correct (it copies the old buffer and HOLE-initializes [old_capacity, new_capacity)), so the suspects are the array layout/marking side tables, or codegen's inline array-store tier, which begins handling these writes inline once capacity becomes non-zero and may not agree with how the large-fresh-holey array was marked.

Any candidate fix should be gated on a value-verification harness — write then read back every slot, both above and below the threshold — not on timings. The timing number here is actively misleading.

Possible directions

1. Make the in-bounds branch grow the dense store, as above — but reconcile it with the layout/marking and the inline store tier. Correct in principle; the naive version is not sufficient.
2. Raise MAX_FRESH_DENSE_ARRAY_LENGTH. Cheap and low-risk, but only moves the cliff, and eagerly commits memory (8 * n bytes) for arrays that may stay sparse.
3. Have the large-fresh-holey representation grow dense on first sequential write, i.e. treat the first write to a capacity-0/large-length array as an allocation decision rather than a store decision.

Happy to test any patch against the repro above.

[proggeramlug]

Closing: fixed in #9434 (grow large pre-sized arrays densely) with regression test issue_9371_large_presized_array.rs. In release candidate r27.