Skip to content

new Array(n) above 1M is still quadratic when the array is a module-level binding #9784

Description

@proggeramlug

The two programs below have line-for-line identical bodies. Only the binding's scope differs.

// A — inside a function: FAST
function fill(slots: number): string {
  const values: number[] = new Array(slots);
  for (let i = 0; i < slots; i++) values[i] = i;
  let s = 0; for (let i = 0; i < slots; i++) s = (s + values[i]) % 1000000007;
  return `${slots} ${s} ${values[slots-1]}`;
}
console.log(fill(1000001));
// B — at module top level: HANGS
const slots = 1000001;
const values: number[] = new Array(slots);
for (let i = 0; i < slots; i++) values[i] = i;
let s = 0; for (let i = 0; i < slots; i++) s = (s + values[i]) % 1000000007;
console.log(slots, s, values[slots-1]);
node perry
A, function scope 0.11 s 0.49 s
B, module scope 0.13 s >30 s, killed

The threshold is exact: 1,000,000 elements complete in 0.44 s; 1,000,001 do not complete in 30 s.

Why this is not #9371

#9371 was closed on 2026-09-02. Its fix (#9434) is real, but its regression test crates/perry/tests/issue_9371_large_presized_array.rs fills the array inside a function, which is arm A above — the half that works. The module-scope arm was never covered, and reproduces unchanged on main@12efed1222.

Same module-global-vs-local shape as #9342.

Repro

secret-tests/scratchpad/audit0901/cliff_fn.ts and cliff_mod.ts; also secret-tests/cases/adversarial/recent/33_large_presized_array_cliff.ts, currently the adversarial suite's only timeout.

Done when

B completes in the same order of magnitude as A, case 33 matches node, and issue_9371_large_presized_array.rs grows a module-scope arm.

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

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions