Map/Set: make size O(1) and compact churn without invalidating iterators

Problem

Strong Map/Set storage keeps an append-only ordered elements list and marks deletions as tombstones.

• Map.prototype.size, Set.prototype.size, native size queries, and set operations rescan the entire historical list, so a nominally constant-time property becomes O(total historical insertions).
• Delete/reinsert churn retains entry cells, tombstones, and index-position side storage indefinitely; clear() shrinks logical length but ordinary deletion never compacts.
• Collection iterators store a physical __i list position, preventing safe in-place compaction while an iterator remains live.
• Map entry iteration currently yields the internal [key, value] storage pair instead of a fresh iterator-result pair. User mutation can therefore alter Map storage outside Map.set and bypass index/write-barrier invariants.

This is a correctness, bounded-memory, and adversarial-complexity boundary.

Required outcome

• Maintain the strong collection live-entry count under the existing elements lock so every size query is O(1), including no-GIL readers racing mutation.
• Return fresh arrays from Map entries() / default iteration; user mutation must never mutate internal Map data.
• Give iteration a stable logical insertion cursor independent of physical storage positions. Preserve deletion, clear, re-add, mutation-during-iteration, forEach, and multiple concurrent iterator semantics exactly.
• Compact tombstones in place at a documented bounded threshold, rebuilding position-only hash chains without managed pointers or allocation once compaction begins.
• Bound retained ordered/index/cursor storage under repeated insert/delete and clear cycles; teardown must release every side structure.
• Keep SameValueZero, insertion order, subclass hooks, structured clone, moving GC, OOM failure atomicity, and no-GIL synchronization intact.
• Add deterministic work/count/capacity growth witnesses, iterator mutation tests, moving-GC, structured-clone, OOM/fault, no-GIL, TSan, and full Map/Set test262 coverage.
• Publish exact-parent representative collections timing and retained-memory evidence before completion.

Relationships

Part of #475, #480, and #493. Follows the collision-safe identity index in #513 and contributes to #460.

First slice landed in 5e7fffbd (perf(collections): make size constant-time (#514)).

Strong Map/Set now maintain the exact live-entry count under elements_lock; insertion, deletion, and clear update it in the same transaction. size, native size queries, and set-operation cardinality are O(1) instead of rescanning all historical entries.

Evidence:

• deterministic churn leaves 4,160 historical positions in each collection while both live counts and public sizes remain exactly 64
• focused Map/Set filters: 30 executions passed, 0 failed/leaked
• four-thread no-GIL identity Map/Set witness passed normally and under TSan
• full sharded unit gate: 1,541 passed, 1 skipped, 0 failed, 0 leaked (143.3 s)

Keeping #514 open for the coupled remaining work: fresh Map iterator entry arrays, stable logical cursors, bounded in-place tombstone compaction, fault coverage, test262, and exact-parent timing/RSS evidence.

Second slice landed in b09f9a55 (fix(collections): isolate Map iterator entries (#514)).

Map.prototype.entries() and the default Map iterator now allocate a fresh observable [key, value] array after releasing the collection lock. Mutating a yielded pair can no longer mutate the internal Map entry cell or bypass Map.set index/write-barrier invariants.

Evidence: the regression mutates two consecutive yielded arrays, preserves both original Map entries, proves distinct result identity, and checks default iteration; focused Map 13/13, focused normal/TSan iterator passes, and full units 1,541 passed / 1 skipped / 0 failed or leaked.

#514 remains open for stable logical cursors, bounded tombstone compaction, fault/test262 coverage, and exact-parent timing/RSS evidence.

Stable-cursor and compaction slice landed in 3c2b69fd (perf(collections): compact stable iterator storage (#514)).

Map/Set iterators now use GC-traced internal slots instead of observable __src / __i / __kind properties. Their monotonic insertion serial is independent of physical storage, and each shared next() advance is serialized under the iterator lock. forEach uses the same logical ordering model, including delete/re-add and clear/add behavior.

Deletion now stable-compacts in place once the historical list has at least 64 slots and tombstones outnumber live entries. Hash-position chains are rebuilt from retained capacity after compaction begins. Serial capacity is reserved before publishing a new element, so OOM cannot leave the element and cursor side storage out of sync. Clear discards current serials without reusing their numbers, and finalization releases the serial side storage.

Evidence:

• the deterministic churn witness now retains 64 slots rather than 4,160, with 64 live Map entries and 64 live Set entries
• active Map iteration survives moving GC, a 129-slot compaction boundary, delete/re-add, and clear/add; mutation-during-forEach also preserves exact order
• a four-thread no-GIL witness drains one shared 1,024-entry iterator exactly once per entry; the same test is TSan-clean
• fault injection proves failed serial reservation publishes no serial or live count, and clear() preserves monotonic serial allocation
• full sharded unit gate: 1,544 passed, 1 skipped, 0 failed, 0 leaked across 1,545 tests (139.3 s)

Keeping #514 open for the remaining full Map/Set test262 delta and exact-parent representative-collections timing/RSS evidence. Those runs are deliberately deferred while an unrelated long-running unit process keeps the host non-idle; no conformance or performance delta is claimed yet.

Completed and validated on main.

Implementation commits:

• 5e7fffbd — maintain synchronized O(1) live size
• b09f9a55 — return fresh Map iterator entry arrays
• 3c2b69fd — stable monotonic logical cursors, bounded in-place tombstone compaction, logical forEach, atomic shared-iterator progression, and GC/OOM/no-GIL coverage
• db6519ce — release compacted and cleared backing capacity
• cbd4cb55 — generation-validated physical cursor hints with one binary fallback seek after layout change
• ae933649 — remove insertion-path backing-lock overhead without weakening backing lifetime
• 363a6437 — check in the complete exact-parent evidence chain

Validation:

• Full unit gate: 1,544 passed, 1 skipped, 0 failed, 0 leaked.
• ReleaseFast test262: Map 204/204 and Set 383/383; exact parent matched, so 0 flips and 0 regressions.
• Four threads consuming one shared iterator drained exactly 1,024 entries in no-GIL mode and remained TSan-clean.
• Focused iterator mutation, repeated churn/capacity, clear teardown, allocation-failure atomicity, and moving-GC tests pass.
• Deterministic capacity witnesses verify bounded retained ordered/index/cursor storage and release on clear/empty compaction.

Exact-parent evidence used 7 order-balanced pairs per comparison, no discarded samples, matching input identities/checksums, and nominal thermal state. The initial stable-cursor/compaction change measured 1.0232× instructions and roughly 1.5% higher median peak RSS; the cursor-hint and lock-elision follow-ups recovered most of the instruction overhead, with the final lock-elision step at 0.9835× instructions and 0.973× wall time versus its exact parent. Raw/report pairs are in docs/.data/ under exact-parent-collections*.

These results are intentionally marked diagnostic-only: cache-miss counters were unavailable, so no cache-efficiency publication claim is made. bun run docs:build remains blocked by unrelated whole-site BunPress manifest drift; this issue changes only evidence data and does not accept that unrelated rendered-tree drift.

This completes the required outcome and contributes the bounded-churn foundation to #475, #480, #493, and #460.