[perf] Quadratic async/promise/timer structures + object-keyed Map O(n) + permanent TIMER_REF_STATES leak

[proggeramlug]

Severity: performance (super-linear blowups on common shapes)
Found by: audit fable-audit-perry-2.md (several measured).

A cluster of runtime data structures that go quadratic or leak on idiomatic workloads:

1. process.nextTick queue drains with Vec::remove(0) — O(n²). crates/perry-runtime/src/builtins/globals.rs:980,1008-1014. A burst of n ticks memmoves ~n²/2 entries. Fix: VecDeque::pop_front (the promise TASK_QUEUE two files over already does this). Good first issue.
2. Promise.all keeps per-pending-element state in a global Vec scanned in full on every settle. promise/combinators.rs:22,41-59,858-861; PROMISE_OVERFLOW_REACTIONS and PROMISE_SETTLE_LISTENERS (then.rs:255-389) have the same shape — any non-empty table taxes every unrelated settle. Promise.all of 10k pending promises ≈ 100M comparisons. Fix: key by promise (HashMap<usize, SmallVec<…>>) or hang an intrusive reaction list off the Promise.
3. Timers: three unsorted Mutex<Vec>s, full-scanned several times per loop turn, and TIMER_REF_STATES grows forever. timer.rs:331,504-521 — one i64→bool entry per timer ever created, never removed (self-documented). A server arming a per-request timeout leaks unboundedly and locks the map per liveness probe. Fix: BinaryHeap per queue + id-tombstone map + cached next-deadline atomic + fold ref-state into the timer record.
4. PROMISE_CONTEXTS (AsyncLocalStorage bookkeeping) churns a HashMap insert per .then + O(K) key scan per settle even when ALS is never used. promise/mod.rs:570-687. Fix: inline the snapshot into Promise, or gate on an "ALS ever instantiated" flag.
5. Object/BigInt-keyed Map/Set operations are O(n) each → O(n²) workloads. map.rs:751-830 restricts the hash index to non-pointer keys; object keys take a linear scan. Measured 1,793× slower than string keys (20k inserts+gets: 7,173 ms vs 4 ms). Object-keyed Maps are the default cache/registry idiom. Fix: a movable-safe identity hash (lazily assign a 32-bit id in the GcHeader spare bits, index by id).
6. One user Object.freeze/defineProperty permanently disables the dynamic-write fast path process-wide. GLOBAL_DESCRIPTORS_IN_USE (descriptor_state.rs:86,338,468) gates transition_fast + the in-function transition-cache path (field_set_by_name.rs:54,916); perf(runtime,codegen): stop unrelated descriptor installs disabling the class-field inline fast path (#5654) #6057 fixed the read side only. Fix: gate on the receiver's OBJ_FLAG_HAS_DESCRIPTORS + the existing object_proto_may_intercept_key check instead of the global.

Confidence: high (source; items 1/2/5 also probe/measured).

[proggeramlug]

Status pass — 4 of the 6 items are already fixed or in flight, so this issue currently overstates what is open. Breaking it down against main today:

#	Item	Status
1	process.nextTick drain Vec::remove(0) → O(n²)	✅ Fixed — builtins/globals.rs now uses a VecDeque + pop_front
2	Promise.all per-element state in a globally-scanned Vec	❌ Open — PROMISE_ALL_STATES is still RefCell<Vec<(usize, PromiseAllState)>>
3	Timers: unsorted Vecs + permanent TIMER_REF_STATES leak	✅ Fixed — bounded by TIMER_REF_STATES_CAP (#6257); single-pass scans in #6285
4	PROMISE_CONTEXTS churn per .then	✅ Fixed — #6267 (PromiseContextStore)
5	Object/BigInt-keyed Map O(n) (measured 1,793×)	🔄 In flight — #6285
6	One Object.freeze disables the dynamic-write fast path process-wide	❌ Open

So the live work is items 2 and 6.

On item 6 specifically, the fix the issue proposes is right and the precedent already exists — #5654/#6057 established that receiver-level descriptors are vetted per-receiver via OBJ_FLAG_HAS_DESCRIPTORS, and only prototype-level installs need a process-wide disable. But that was applied to the read side only; field_set_by_name.rs:54 and :916 still gate on the global GLOBAL_DESCRIPTORS_IN_USE.

Porting it to the write side is not a mechanical swap: a setter installed on a prototype intercepts writes to instances whose own OBJ_FLAG_HAS_DESCRIPTORS is clear, so the per-receiver flag alone is not sufficient — it has to be paired with the proto-interception check, exactly as the read side does. Getting that pairing wrong silently bypasses a setter, which is worse than the perf cost it fixes. Worth doing carefully with a targeted parity test (Object.defineProperty(Proto, 'x', {set}) + a plain-object write) rather than as a quick gating tweak.

I've split the remaining two out rather than churn this umbrella further — happy to take either.

[proggeramlug]

Follow-up on item 2 (Promise.all per-element state in a globally-scanned Vec). I started on it and backed out — the suggested fix ("key by promise, HashMap<usize, SmallVec<…>>") is not a drop-in, and the reason is worth recording so the next person doesn't find out halfway through.

PROMISE_ALL_STATES is not just a lookup table; it is a GC root side-table, and two things depend on it being a positionally-indexed Vec:

1. The incremental root scanner resumes by position. promise/scanners.rs:559 walks it with a PromiseRootScanState { index, slot } cursor — states[state.index], state.slot 0..4 — so a step-bounded GC increment can stop and resume mid-table. A HashMap has no stable positional cursor to resume from, and the mutator can insert/remove between increments.

2. Evacuation rewrites the key in place. The scanner calls visit_metadata_usize_slot(key) (scanners.rs:568/597/640, combinators.rs:74) — when a promise moves, the GC edits the key. Doing that inside a HashMap silently breaks the hash invariant: the entry stays in the bucket for its old hash and becomes unfindable. cleanup_copied_minor_all_states_for_gc has the same shape (Rekey(new_key) mutates the key in place).

So a correct fix has to either:

• keep a positionally-stable backing store and add a separate index that survives rekeying (the index must be rebuilt, not mutated, whenever the GC rewrites keys); or
• take the issue's second suggestion — hang an intrusive reaction list off the Promise itself — which removes the global table (and therefore both problems) but changes the Promise layout and its tracing.

The second is the better end state and is what I'd recommend, but it is a real change to promise tracing, not a data-structure swap. The same caveat applies to PROMISE_OVERFLOW_REACTIONS / PROMISE_SETTLE_LISTENERS, which the issue notes share the shape.

Not blocked — just bigger than it reads. Flagging rather than landing a half-verified change to the GC root path.

[proggeramlug]

Landed: #6285 (plus #6126 and #6257 earlier). Per-item status of the six:

#	Item	Status
1	process.nextTick Vec::remove(0) O(n²)	✅ #6126
2	Promise.all / settle-listener / overflow-reaction full-table scans per settle	❌ still open
3	Timers: unsorted Vecs + TIMER_REF_STATES leak	✅ leak bounded (#6257); ✅ drain Vec::remove(i) → single-pass partition (#6285). BinaryHeap redesign still open
4	PROMISE_CONTEXTS / AsyncLocalStorage churn	❌ still open
5	Object/BigInt-keyed Map O(n) per op	✅ #6285
6	One Object.freeze disables the dynamic-write fast path process-wide	❌ still open

Item 5 measured (20k inserts + 20k gets, same machine): object-keyed insert+get 7,692 ms → 4 ms (~1,900×, matching the audit's 1,793×); object-keyed has ×20k 3,737 ms → 0 ms. Implemented as MAP_PTR_INDEX, mirroring Set's SET_INDEX: a new GcRewriteHookKind::MapIndex rebuilds it from the rewritten entries buffer, since stored key bits go stale whenever the moving GC evacuates a pointee. The three rewrite call sites each open-coded a == GcRewriteHookKind::SetIndex check, so they now route through one shared run_gc_rewrite_hook dispatch.

Correctness bug found and fixed while doing item 5: bigint Map keys were indexed by raw pointer bits — the old comment misidentified BIGINT_TAG as 0x7FFE (that's INT32_TAG; bigints are 0x7FFA). So on main before this PR, m.set(10n, "ten"); m.get(10n) returned undefined across distinct allocations, and the indexed bits went stale across a GC move. jsvalue_eq now compares bigints by mathematical value per SameValueZero (23.1.3.9).

Also found while gating item 3: Perry fired an expired timer batch in creation order rather than deadline order — filed as #6287 and fixed in #6289 (folded into #6285). It turned out to be two divergences, the second of which rules out the obvious fix: setImmediate runs in the check phase, so an expired setTimeout must fire ahead of an earlier-scheduled immediate — and since an immediate carries a ~now deadline, a naive sort-by-deadline would have made that case worse. The landed fix is kind-aware: (timeouts by deadline) then (immediates FIFO), with stable sorts preserving the same-deadline-creation-order and immediate-FIFO semantics Perry already had right.

Items 2, 4, 6 and the timer BinaryHeap redesign remain — leaving this open for them. Item 2 in particular needs the same GC-rekeying treatment as the Map index (promises move), which is why it wasn't bundled in.