ReviewOS

zig-utils/zig-js

Map/Set: preserve collision-safe indexes for every key kind

#513
Closed chris opened this 9 days ago ·
9 days ago

Problem

Strong Map/Set acceleration currently maps one deterministic content hash to one ordered-entry position.

  • hashKey returns null for ordinary objects and Symbols because their pointers can move, so every get/has/set/delete with those valid key kinds performs an ordered O(n) scan.
  • One content-hash collision permanently clears and disables the entire collection index.
  • Primitive hashes use a process-predictable zero seed, allowing adversarial inputs to target one deterministic hash function.
  • The index contains only hash values, so it cannot distinguish colliding keys without abandoning acceleration.

This is both a representative collections performance defect and an algorithmic-complexity boundary.

Required outcome

  • Index every ECMAScript Map/Set key kind, including moving-GC objects and Symbols, using the existing relocation-stable cell identity where applicable and stable arena identity otherwise.
  • Give each strong collection an unpredictable owned hash seed; insertion order and all observable semantics remain independent of bucket order.
  • Represent collisions as exact-equality bucket chains (or an equivalent collision-safe structure). A collision may slow only its own bucket and must never disable unrelated keys.
  • Keep the index free of managed pointers so moving collection does not require tracing or relocation.
  • Preserve SameValueZero, -0 canonicalization, all-NaN equality, BigInt value equality, string byte equality, insertion order, tombstones, mutation during iteration, and subclass/user-hook behavior.
  • Allocation failure must fall back to correct ordered lookup without publishing a partially authoritative index. Clear, delete, structured clone, teardown, and repeated insertion/deletion must remain bounded and leak-free.
  • Add deterministic structural growth coverage plus moving-GC, collision, OOM/fault, no-GIL, and TSan coverage. Publish exact-parent representative collection evidence before claiming completion.

Relationships

Part of #475 and #493.

Advances the bounded-memory/index ownership work in #480 and the representative collections row in #460.

9 days ago

Landed c797973a (perf(collections): index identity keys safely (#513)).

This slice adds securely seeded strong-collection indexes for every key kind, relocation-stable object/Symbol identity hashes, exact-equality collision chains, OOM-safe fallback, moving-GC persistence, structured-clone index construction, and an atomic clear/index-reset transaction.

Measured validation:

  • focused collision and allocator-failure witnesses: 2 passed, 0 failed/leaked
  • focused moving-GC identity witness: 1 passed, 0 failed/leaked
  • focused structured-clone witness: 1 passed, 0 failed/leaked
  • four-thread no-GIL object/Symbol Map+Set witness: passed normally and under TSan
  • broader Map/Set filters: 28 executions passed, 0 failed/leaked
  • full sharded unit gate: 1,540 passed, 1 skipped, 0 failed, 0 leaked (186.5 s)

Keeping this issue open. The required test262 subtree diff and exact-parent representative collection timing remain outstanding; no conformance or timing delta is claimed by this commit.

9 days ago

Completed and validated on main.

Final evidence commits:

  • a5558e2e adds a repository-owned, equal-work object/Symbol Map+Set row and anti-specialization variant. The variant reverses lookup order and object layout while retaining the same checksum.
  • 4adcc0dc records three schema-v1 exact-parent raw/report pairs for 7da3715a → c797973a, each with seven order-balanced pairs, no discarded samples, matching checksums, and nominal thermal state.

Exact-parent results:

  • Object/Symbol base row: 0.6190× instructions, 0.8445× cycles, and diagnostic 0.860× wall time.
  • Anti-specialization object/Symbol row: 0.6187× instructions, 0.8119× cycles, and diagnostic 0.815× wall time.
  • Existing string-heavy collections row records the tradeoff at 1.0154× instructions and a noisy diagnostic 1.022× wall ratio.

The instruction measurements are low-dispersion (at most 0.26% RSD on the identity rows). All reports remain explicitly diagnostic-only because cache-miss counters were unavailable; no cache-efficiency publication claim is made.

Exact-parent ReleaseFast test262 is unchanged:

  • Map: parent 204/204, candidate 204/204
  • Set: parent 383/383, candidate 383/383
  • flips 0 cases; regressions 0

Together with the implementation validation in the prior comment—secure per-collection seeds, exact-equality collision chains, every key kind, moving-GC identity, OOM-safe fallback, structured clone, atomic clear, no-GIL, TSan, focused/full unit gates—this satisfies the required outcome. The related bounded-churn follow-up #514 is also complete.

This work advances #475, #493, #480, and #460.

Sign in to comment on this issue.