ReviewOS

zig-utils/zig-gc

Perf: specialize hashing for the live payload index

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

Downstream evidence: zig-utils/zig-js#62

Problem

Every managed-cell allocation inserts its payload address into the heap's exact live-payload index. The index currently uses std.AutoHashMapUnmanaged(usize, *Header), whose generic integer auto-hash runs Wyhash for each already-aligned pointer. A symbolized allocation-churn profile in zig-js attributes most Heap.create samples to indexPayloadLocked, making hash/index maintenance the dominant collector-side allocation cost rather than slab allocation itself.

Scope

  • retain the exact payload-to-header hash index and its safe all-list fallback;
  • replace generic integer auto-hashing with a well-distributed pointer-specialized mixer that discards guaranteed alignment bits;
  • preserve insertion, lookup, removal, OOM fallback, parallel allocation locking, concurrent marking, sweep, and teardown behavior;
  • measure the downstream allocation-heavy workload before and after;
  • avoid changing public collector semantics or requiring embedder changes.

Acceptance criteria

  • Exact managed-payload lookup and wild/stale-pointer rejection remain covered.
  • Allocation, sweep removal, collection, and deinit keep index membership correct.
  • Parallel/concurrent collector tests remain race-safe.
  • The downstream bounded-object-churn benchmark materially improves with identical checksums.
  • Full zig-gc tests pass; batch TSan with the downstream publication gate.
9 days ago

First experiment rejected after measurement. Replacing AutoHashMapUnmanaged's generic integer hash with a pointer-alignment-aware Murmur finalizer passed the focused exact/wild-pointer test, but the downstream ten-sample one-job median moved from about 12.84 ms to 13.19 ms at the same checksum (10195248). The zig-gc worktree was restored clean; no commit was made.

This rules out generic Wyhash as the primary cost. The symbolized stacks point to maintaining/probing the per-cell exact hash index itself. The next viable design should avoid an index insertion for every allocation—likely by separating trusted same-heap barriers from broad maybe-managed inputs or by using backing-slab ownership metadata—while retaining safe rejection of wild, stale, arena-owned, and foreign-heap pointers. Issue remains open for that structural design.

9 days ago

Closing this narrower hash-function experiment as superseded by #4. The measured pointer-specialized hash regressed the downstream median, while #4 implemented the structurally sound approach: slab-owned allocations avoid the duplicate per-cell index and generic/delegated allocations retain the safe fallback. There is no remaining work specific to changing the hash mixer.

Sign in to comment on this issue.