ReviewOS

zig-utils/zig-gc

perf: splice non-marking owned-cell batches in O(1) lock time

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

Problem

Heap.createBatch amortizes allocation, but short checkpoint batches did not justify privately chaining every header before taking alloc_lock; the first unconditional O(1) splice regressed lower lanes. The downstream profile showed that the general fix required both a genuinely amortized tranche and a thresholded dependency path.

Implemented

For bindings that guarantee all cells use owned storage, batches of at least 64 cells now initialize and chain headers privately while marking is inactive. After taking alloc_lock, zig-gc rechecks marking and nursery state, O(1)-splices the chain, updates counters once, releases the lock, then lets the binding publish its ownership bitmap. Short batches and marking/nursery transitions retain the original compact per-cell path.

The zig-js consumer keeps a lone shared worker on 17-cell checkpoint batches and uses a bounded, explicitly rooted reserve of up to 272 objects only while multiple workers contend.

Acceptance

  • Exact unit coverage for short/large list order, counters, lock boundary, and marking fallback
  • zig-gc normal and ThreadSanitizer suites pass
  • Order-balanced seven-pair zig-js A/B is neutral at one lane and materially improves 2/4/8 lanes
  • Commits and raw evidence are published
9 days ago

Rejected after full-workload A/B; no source changes were committed. The O(1) splice passed all 37 zig-gc tests and preserved exact checksums, but its improvement was not general.

ReleaseFast zig-js shared object_churn, 100 jobs, 7 samples:

  • 1 lane: clean median 193.711 ms; order-preserving candidate 197.376 ms (+1.9%)
  • 2 lanes: clean 349.656 ms; candidate 422.939 ms (+21.0%)
  • 4 lanes: clean reverse-order medians 1,333.820 / 1,555.590 ms; candidate 1,743.677 ms (+30.7% / +12.1%)
  • 8 lanes showed only a noisy modest benefit (candidate three-sample median 5,824.616 ms vs clean seven-sample median 6,430.015 ms), insufficient to justify the lower-lane regressions.

An initially reversed within-batch list order was also tested and rejected; restoring the exact newest-first order did not eliminate the lower-lane regressions. The experiment demonstrates that shortening alloc_lock alone cannot fix this workload while it still publishes a batch every ~17 objects. The next slice belongs in zig-js: safely amortize allocations over a larger checkpoint-bounded tranche, then revisit publication locking if profiles still justify it.

9 days ago

Reopening for the combined downstream design the rejected experiment called for. The splice is now gated to genuinely amortized batches (64+ cells), while zig-js keeps a lone shared worker on its existing 17-cell checkpoint batch and raises only concurrently contended workers to a bounded 272-cell, explicitly rooted reserve. The final order-balanced seven-pair screen is neutral at one lane and materially faster at 2/4/8 lanes; I am finishing the full downstream suite before publishing commits and exact evidence.

9 days ago

Implemented and validated.

Seven-pair medians at 1/2/4/8 lanes: parent 99.901 / 168.035 / 272.951 / 1542.720 ms; candidate 100.562 / 112.393 / 141.772 / 1239.637 ms. One lane is neutral within dispersion; 2/4/8 improve 1.50x / 1.93x / 1.24x, all with 7/7 pair wins and exact checksums. Normal + TSan zig-gc suites and the full 777-test downstream suite are green.

Sign in to comment on this issue.