gc-immix-rearchitecture.md

Immix heap + reference counting — GC rearchitecture scope

Status: Phase 0 (a) done — Immix-first is NOT supported by the data. The alloc-vs-sweep-vs-mark breakdown (the Phase 0 (a) result immediately below) shows the per-object pools are not the bottleneck anywhere; the only GC rearchitecture the measured costs justify is reference counting — which was then prototyped and measured as a no-go (its coalescing store barrier taxes the common operation set, +7–26% on construction / property writes / allocation, for a narrow retained-set-only win; gc-reference-counting.md), closing the GC rearchitecture investigation: the broad win is already banked (incremental marking + lazy sweep), and the broad perf frontier is the JIT, not the GC. The Immix heap (Steps 1/3/4) is shelved. The rest of the doc is the design that the measurement redirected. Owner: the GC track (user-directed). Prerequisite reading: handbook/gc.md (the shipped collector) and gc-generational-major.md (why the in-place, non-moving major hit an architectural floor).

Phase 0 (a) result — the data redirects the plan

sample self-time breakdown of the two macros (ReleaseFast, JIT on, --unhardened --allow=eval, ~15–20 s steady-state windows):

splay (large retained set) — ~4,700 leaf samples:

bucket	~share	top functions
mark	~62%	markValue 2165, beginMajorCycle 312, markSymbolKeys 214, markString 166, drains ~50
sweep / free	~10%	sweepObjectsMatureBudget 200, deinitFields 140, finishIncrementalMajor 99
alloc	~2–5%	allocateObject 52, cons/flat string 25, makeDenseArray 23
mutator / JIT	~23%	runFrames, Shape.lookup, arith, property sets

richards (low retention, compute / call-heavy):

bucket	~share	top functions
mutator / JIT / frames	~85%	runFrames 1530, Bistromath ~360, CallFrame/FramePool ~295, JITted code (???) ~200
mark	~1–2%	markValue 20
alloc	~1%	allocateEnvironment 16

Three findings, all against the Immix scoping below:

1. The per-object pools are not the bottleneck anywhere. Allocation is ~2–5% on splay and ~1% on richards. Immix's headline win — bump allocation — addresses a sliver. Step 1 (the Immix heap) does not pay for itself, and its bulk-reclaim only touches the ~5% sweep-walk (deinitFields — half the sweep — frees per-object external resources and survives any heap layout).
2. Where GC dominates (splay), it is the mark (~62%), not alloc or sweep — and the mark is reduced only by RC, not Immix (Immix still traces every live object). RC reclaims splay's acyclic churn on refcount→0 with no trace and never re-examines the stable retained tree, cutting the ~62% to near-zero. RC, not Immix, is the GC lever.
3. Where GC does not dominate (richards, ~85% mutator), no GC rearchitecture helps — the bottleneck is interpreter / JIT / call-frame overhead, the JIT track's domain, not the GC's.

Verdict: do not do Immix-first. The measured costs do not support a block/line heap rewrite. The only GC rearchitecture the data justifies is reference counting (the splay mark) — itself a large, separate change (a coalescing inc/dec barrier on the interpreter's hot store path + a cycle collector) that deserves its own scoping + measure-first Phase 0 (the barrier's hot-path cost vs the mark saved), not the Immix foundation this doc led with. And the scope of even that win is narrow: it helps retained-set workloads (splay); compute-bound workloads (richards) are bottlenecked on the interpreter/JIT, where GC changes do nothing. Cheap measurement, expensive mistake avoided — the same discipline that closed the generational major.

The memory axis — splay's RSS outlier is header size, not a leak

The cross-engine RSS capture (bench-cross --macros) makes splay a ~5× peak-RSS outlier — Cynic ~357 MB vs jsc 55 / v8 71 / hermes 68. It reads like a GC retention bug (removed nodes kept alive by stale roots); it measurably is not. Three checks, ReleaseFast --no-jit --unhardened --allow=eval:

1. The live count plateaus exactly at the tree size. A fixed 2000-node tree driven through 40 rounds of 80 insert+remove (size held constant, __collectGarbage() each round) holds the post-GC object count flat at 192,192 = 2000 × 96 objects/node, round after round. Removed nodes' payloads are reclaimed; a false-root leak would grow the count ~304K over the run. It grows by zero. The card-marking dirty list is clean.
2. RSS scales linearly with node count — 2000→102 MB, 4000→195 MB, 8000→371 MB. A per-object cost with no fixed retained offset, not an accumulating set.
3. The cost is the header. @sizeOf(JSObject) = 408 B; splay's live set is genuinely ~768K objects (8000 × 96: one SplayTree.Node + 63 payload nodes + 32 array-exotics per tree node) → 313 MB of headers alone, +25 MB JSString headers +~20 MB string bytes ≈ the 357 MB observed. V8/JSC hold the identical 768K-object tree in 55–71 MB because their object is ~48 B: a fixed header plus out-of-line property/element stores reached by one pointer each.

So splay's RSS is bounded by the inlined-everything JSObject layout — two StringArrayHashMaps (empty in shape mode) + inline_slots[4] + elements + ~110 B of null-on-every-plain-object type-specific slots (Promise / RegExp / Proxy / iterator state) — not by anything the collector retains. The lever is shrinking the header: object-layout / IC-substrate work, not GC. Same shape as the CPU finding above — the collector is no more the bottleneck for splay's memory than the pools are for its CPU. Reaching the ~70 MB field needs the V8-style out-of-line redesign of property/element storage (the uniform-header + storage-substrate change Step 1 already contemplates — challenges #2/#3); the cold type-specific slots are a smaller, independent ~112 B win via the existing extension pointer. Neither is a collector change, so the generational/RC scoping below does not move this number.

Stage A landed — the cold clusters are behind extension

The ~112 B win is now realized. Four cold per-kind clusters moved off the base JSObject into JSObjectExtension (reached by the existing one pointer), each read only when a get*/set* helper or a cheap inline brand says the object is of that kind — a plain {key,left,right,value} data object (splay's Node) has no extension and pays nothing:

• Iterator state (40 B) — array_like_iter / map_set_iter / regexp_string_iter / iter_record / iter_helper.
• RegExp state (24 B) — regexp_source / regexp_flags (GC-marked, snapshot-serialized) + regex_perlex (recomputed on demand).
• Key anchors (24 B) — the borrowed-key JSString roots; moving them behind the extension also let the minor-cycle skip predicate (objectScanSkippable) drop its direct key_anchors check, since every anchor write now sets needs_internal_scan.
• Proxy pointers (24 B) — proxy_target / proxy_handler / proxy_target_fn, gated by a new cheap inline is_proxy bool brand so the property-op hot path (a proxy is brand-checked on every get/set) stays a single load rather than three pointer reads.

Result: @sizeOf(JSObject) 408 B → 296 B (−112 B, −27.5%). Measured same-laptop, splay (8000-node tree) peak RSS 391 MB → 303 MB (−88 MB, −22.5 %) — and the −88 MB drop equals the per-object header saving times splay's live-object count (768K × 112 B ≈ 86 MB), confirming the RSS is the header, exactly as diagnosed. test262 is byte-identical (0 regressions across the built-ins + language trees, ~45 k fixtures) and the --gc-threshold=1 verifiers stay green. Reaching the ~70 MB field still needs the out-of-line property/element redesign (Step 1); Stage A is the self-contained down payment.

Stage B — the two remaining moves, split by a bright line (the JIT)

Stage A moved the cold clusters (fields null on a plain object). The rest of the header is the storage fields — empty on a shape-mode object but still resident: properties/property_flags (40 B each), own_key_order (24 B), elements (24 B), sparse_elements+is_sparse+sparse_length (~28 B), inline_slots[4] (32 B), the then-separate overflow_slots (24 B; now the overflow role of secondary_values), and shape (8 B). A survey of the property/element substrate splits these into two moves along one hard constraint: Bistromath (the JIT) bakes header offsets into emitted machine code.

B1 — the dict-mode representation (JIT-safe, object-layout lane). SHIPPED. properties, property_flags, and own_key_order are the dictionary representation. They are empty on every shape-mode object (splay's Nodes, all plain literals — a shaped object stores values in inline_slots, never the bag), and the JIT deopts to the interpreter for dict-mode objects and never reads these fields. So they moved into a lazily-allocated DictStore reached by one pointer (originally dict_store, now the tagged aux_store), allocated only on demoteFromShape / first bag write, read through propsConst/propsMut (and the flags/order pair). Shape-mode objects never allocate it, so the is_pristine fast-death and the shape/IC hot path are undisturbed — the same pattern as the extension sidecar. The global object is the one always-dict-backed exception: GlobalBindings.bindToObject eager-allocates its store so the allocator-free map() accessor stays valid. Result: header 296 → 200 B (−96 B; 408 → 200 overall, −51%); measured same-laptop, splay peak RSS 303 → 229.5 MB (−73.5 MB, matching 768K × 96 B). test262 byte-identical (0 regressions across the built-ins + language trees, ~45 k fixtures); test-fast + --gc-threshold=1 verifiers green (no panic / poison / pristine violation). The gates held identically to Stage A: both GC markers (markValue's iterOwnNamedKeys walk; objectHoldsYoungSymbolKey / markSymbolKeys reach the bag/shape keys), verifyRememberedSet (the write-barrier dirty contract on every bag write), deinitFields, the pristine assert, and the snapshot comptime classification + serialize.

B1b — the sparse indexed store (SHIPPED). sparse_elements (the u32 → Value dictionary-mode indexed map, populated only on the rare sparse array exotic) moved into the existing extension sidecar — reusing that pointer, so it saves the full 24 B with no new field. The hot is_sparse brand + sparse_length stay inline (they gate the dense/sparse split on the element hot path and pack into padding), so the dense element path never touches the extension. Sparse values ride the value write barrier (setIndexed) exactly as before. Header 200 → 176 B; test262 byte-identical, --gc-threshold=1 verifiers green. The dense elements vector is deliberately NOT moved — it is the array hot path (every dense index read/write) and belongs to a perf-sensitive "packed JSArray" redesign, not a cold move. So header now stands at 176 B (408 → 176 overall, −57 %); the remaining big fields — inline_slots[4], the then-separate overflow_slots (now secondary_values), and shape — are all JIT-baked and only move under B2.

B1c — overlay the two secondary value-vector headers (SHIPPED). Shape-mode named properties need an overflow vector only after the four inline slots fill; dense indexed objects need an elements vector. The common objects measured in splay use one role or the other, yet every object currently pays for both 24-byte ArrayListUnmanaged(Value) headers. secondary_values overlays those headers without moving either vector's payload. It starts as the dense-elements header. On the first named-slot spill, the elements header moves to an exact-sized cold auxiliary record only if that same object actually has indexed storage, and secondary_values becomes the overflow-slot header. The secondary_is_overflow transition is monotonic, so layout.object.overflow_items_ptr remains one direct JIT load even after a later shape demotion. A tagged auxiliary store composes the rare mixed elements-plus-dictionary case from stable child pointers; ordinary shaped objects and ordinary dense arrays allocate no new sidecar.

This is a deliberately smaller step than JavaScriptCore's Butterfly, which lays property and indexed storage around one out-of-line allocation. SpiderMonkey's NativeObject and Hermes' JSObject instead keep direct slots plus separate out-of-line storage. The overlay keeps Cynic's existing element and compiled-slot access shapes, trading a cold allocation only for the uncommon object that uses both roles.

The representation is not ECMAScript-observable: §10.1 ordinary-object property operations and §10.4.2 array-exotic indexed semantics must remain identical. The implementation gate therefore includes both construction orders for mixed named/indexed objects, deletion and shape demotion, snapshot round trips, GC marking/deinit under allocation pressure, and the JIT layout proof. test262's property/array buckets and the SES hardened- primordial suite remain unchanged.

Result: the later packed-brand baseline falls from 168 → 144 B per JSObject (−24 B, −14.3%). On the pinned remote box, interpreter Splay falls from 201,856 → 183,664 KiB peak RSS (−18,192 KiB / −17.77 MiB, −9.01%), matching the 768,000-live-object prediction (18,000 KiB) within allocator/page noise. It also gets slightly faster: absolute p50 688.05 → 660.14 ms (−4.1%), while the interleaved five-pair comparison reports 0.968× with 4.9% ratio spread. The adjacent interpreter micro smokes (array_iter, property read/write, object allocation, constructor array build) show no stable regression; their small ±3–8% movements carry 11.7–26.0% spread except Splay's low-noise result. ReleaseSafe unit tests, the SES suite, allocation-pressure Array/Object/object-expression buckets, and the JIT layout/Bistromath/Ohaimark proofs stay green.

B2 — the hot-field / uniform-header move (JIT lane, the actual ~75 MB target). shape + inline_slots + the overlaid secondary_values header are still resident hot-path storage. Moving them fully out-of-line to reach ~90 B is where the 4× RSS outlier actually closes, but it is machine-code-coupled: src/runtime/jit/layout.zig is the single source of truth for object.shape / object.inline_slots / object.overflow_items_ptr / inline_slot_cap, and emitLoadSlot / emitStoreSlot plus four shape-guard emit sites in bistromath.zig read them raw, guarded by an executable proof test (layout.zig "machine loads match Zig reads"). B2 must: (1) redefine layout.object.* relative to the out-of-line store, (2) rewrite the two slot-emit helpers + the shape-guard sites to dereference the store pointer first (one extra indirection on the hottest compiled read), (3) update the proof test, and (4) resolve the pristine-death tension — a lazily-allocated slot store makes every shape-mode object allocate on first property write, which would regress exactly the profiled hot workloads unless the "empty baseline store" is special-cased in assertPristineFieldsClean / deinitFields (mirroring how elements_pooled returns a pooled buffer rather than freeing). That JIT-substrate coupling plus the pristine redesign puts B2 in the JIT/IC lane, not the object-layout lane; B1 is the self-contained increment that ships first.

Why

The shipped collector is a generational, non-moving, per-object-pool mark-sweep: young/mature ArrayList(*Kind) lists per kind, std.heap.MemoryPool slabs for three kinds (object / env / string-header) and the bare allocator for four more, sticky-bit minors, card marking, incremental major marking, lazy sweep. Two architectural weak points remain — and gc-generational-major.md proved the in-place fix for the second is foreclosed for a non-moving collector:

1. Per-object pools. Allocation is a pool free-list pop; freeing is a per-object pool destroy; objects of a kind are scattered (no contiguity); freed slots are never returned to the OS. Allocation is on the hot path of every new, every closure, every array growth.
2. The mark is O(live), every major. markValue re-traces the whole live set; on a large stable retained set (splay) that is ~34% of CPU re-marking an unchanged tree. The generational-major attempt to skip it is information-theoretically foreclosed non-moving (you cannot establish unreachability without a full trace or reference counting).

The modern answer to both — and the current state of the art — is LXR (Zhao, Blackburn & McKinley, Low-Latency, High-Throughput Garbage Collection, 2022, arXiv:2210.17175): an Immix region/line heap (fixes #1; adds locality + bulk reclaim + optional defrag) plus reference counting (fixes #2 — reclaim without tracing; "they depend on tracing, which in the limit and in practice does not scale") with concurrent tracing only for cycles. This doc scopes adopting that design, in two steps, measure-first.

The clean part — what stays

The storage-survey is encouraging: the mark substrate is interface-stable and carries over nearly unchanged, because it operates at the Value/pointer level, not the storage level. KEEP:

• mark colour (mark_color / live_color), marking_phase, the mark worklists
  • drainMarkWorklist[Budget], the Dijkstra write barrier, the card-marking dirty list remembered set, weak-aware marking + the ephemeron fixpoint, the conservative native-stack scan, handle scopes, and the incremental safe-point hooks.

REPLACE — purely the storage substrate: the 7 per-kind young/mature ArrayList(*Kind) pairs, the 3 QuarantinedPool/MemoryPool slabs + the 4 direct-allocator kinds, the per-kind allocate* functions, and the sweepList/promoteYoungList type-dispatch + swapRemove walk. The mark phase touches storage through a narrow interface — iterate live objects; read/write a per-object mark_color/generation/dirty/pinned; free dead — so the swap is contained in principle (the friction is below).

Step 1 — the Immix heap (foundation, non-moving first)

Replace the per-kind pools + lists with a single block/line heap:

• Blocks (e.g. 32 KiB) carved into lines (e.g. 128–256 B). Allocation bump-points into the current line's hole; an object that doesn't fit skips to the next hole/line; a fresh block is grabbed when the current fills.
• Line marks fall out of object marks (a line is live iff it holds a live object). Sweep reclaims empty lines/blocks wholesale (bulk, vs per-object pool destroy) and recycles partially-free blocks' holes.
• Large-object space (LOS) for objects above a line/block threshold (big JSFunctions, large JSBigInt limb arrays, ArrayBuffer payloads) — separately managed, not bump-allocated.
• Generational, non-moving. Keep the young/mature distinction at block granularity; the sticky-bit minors + card-marking remembered set carry over (they're mark substrate). No evacuation in Step 1 — only fully-empty lines/blocks reclaim; fragmentation is accepted and addressed later (Step 3). This keeps the non-moving contract (FFI, handle scopes, raw native pointers held across safe-points) intact.

Standalone wins: bump allocation (vs pool pop), bulk empty-region reclaim, allocation locality. The mark is still a trace — Step 1 does not reduce markValue; it fixes allocation, reclaim, and locality. splay's mark CPU is Step 2's job.

Step 2 — reference counting on Immix (the trace-scaling fix)

LXR's core: reclaim most objects by reference counting (a coalescing inc/dec barrier on pointer stores), reclaiming acyclic garbage immediately (no trace), and run tracing only to collect cycles (infrequently, eventually concurrently). For splay — an acyclic tree with acyclic payloads — RC reclaims the churn directly and the trace all but disappears. This is the piece that reduces the mark CPU rather than hiding it, and it is what makes the heap scale. It is not optional here — see challenge #1.

Cynic-specific challenges (the Phase 0 must weigh these honestly)

This is not a clean port; Cynic's object model adds real friction:

1. Objects own external heap resources. A JSObject owns a property map + accessor maps + element buffers; JSString owns its byte payload; JSGenerator a register file; JSBigInt a limb array. These need explicit deinit on object death. Immix reclaims at line granularity — a dead object sharing a line with a live one is not individually reclaimed, so its external resources would leak until the line frees. Mark-sweep Immix must therefore still per-object-sweep-for-deinit (eroding the bulk-reclaim win), or pull those resources into the managed heap, or lean on RC for prompt per-object deinit (refcount→0). This is the strongest reason Step 2 (RC) is what makes the structure pay — and a reason Step 1 alone may underwhelm.
2. No uniform object header. Line sweep must identify an object's type + size from its address. Today only four kinds share a HeapKind tag (function/object/symbol/bigint); JSString/Environment/JSGenerator are distinguished by Value tag / context, not a header tag. Immix needs a uniform header (type + size) on every managed object — a layout change to every heap struct.
3. Wide size variance. JSObject ~408 B, several headers ~48 B, big JSFunctions / BigInts / ArrayBuffers far larger → the LOS split + the line-fit policy must be tuned to the real distribution (Phase 0 measures it).
4. The RC barrier cost. A coalescing inc/dec barrier runs on the interpreter's hot store path; it must not erase the win. Measure-first.
5. Untrusted-input robustness. Every change is in the never-abort-the-host path; a botched line-sweep or RC barrier is a UAF on adversarial JS. The verifier-first discipline + gc-stress --gc-threshold=1 carry over, and (for the eventual concurrent cycle-tracer) extend to data races.

Phase 0 — measure + prototype, decide go/no-go

Before any rewrite, establish that the foundation pays and size the design:

• (a) Cost breakdown. Instrument the macros (splay, richards, ctor_array_build) to split GC+alloc CPU into alloc (pool draw) vs sweep/free (per-object deinit + pool destroy) vs mark (markValue). If alloc+sweep is a meaningful slice, the Immix foundation pays directly; if it's almost all mark, Step 1 buys little and the value is concentrated in Step 2 (RC) — which reframes the sequencing (maybe RC-first on the existing pools).
• (b) Object-size + external-resource census. Per kind: count, size distribution, and the fraction of objects owning external heap resources (the deinit-promptness exposure, challenge #1). Sizes the LOS threshold, the line size, and how badly #1 bites.
• (c) Bump-allocator microprototype. A standalone block/line bump allocator vs the current MemoryPool, on the measured size distribution — confirm the alloc-throughput delta in isolation before committing to the rewrite.
• (d) Prior-art deep read. LXR + the Immix paper (Blackburn & McKinley 2008) — block/line sizing, the hole-finding allocator, line marking, the RC coalescing barrier, cycle collection — pulled into the design before building.

If Phase 0 shows the foundation doesn't pay (mark-dominated, or the external-resource friction outweighs the bump/locality win), stop and write that up — exactly the discipline the generational-major Phase 0 owed (it priced the marking saved but not the RSS traded).

Phased plan (each gated)

1. Immix heap, non-moving — uniform header + block/line bump allocator + LOS
   • line-sweep, generational (block-level young/mature, card marking kept). Gate: conformance byte-identical, gc-stress --gc-threshold=1, an alloc/locality A/B on the macros.
2. Reference counting on Immix — coalescing inc/dec barrier + a cycle collector (backup trace). Gate: a differential against the tracing collector (identical surviving set), gc-stress, the macro A/B (the splay markValue fix).
3. (optional) Opportunistic evacuation — defrag fragmented blocks via limited copying; needs pointer-updating, so it breaks non-moving — gated separately, behind a full audit of raw pointers held across safe-points.
4. (optional) Concurrent cycle tracing — move the backup trace off-thread (the LXR design), with the race-robustness gate (ThreadSanitizer + concurrent interleaving stress + the verifier extended to the concurrent barrier).

Risk register

• Biggest blast radius in the engine — a heap-storage and collector rewrite; months, not weeks. The keep/replace boundary (mark substrate stays) bounds it, but Step 1 alone touches every allocate*, the sweep, and every heap struct's header.
• Value may be back-loaded. External-resource ownership (challenge #1) can make Step 1 (mark-sweep Immix) underperform until Step 2 (RC) lands; the win may not show until the second phase.
• The RC barrier may tax the interpreter's hot path (Phase 0 (c)/(d) sizes it).
• Non-moving contract is preserved through Steps 1–2; Step 3 (evacuation) breaks it and must be gated behind the raw-pointer audit.
• It may not pay at all. Phase 0 is the gate. A well-supported "the per-object pools are not the bottleneck — the mark is, and only RC moves it, so do RC-first / don't bother with Immix" is a valid and cheaper-to-reach outcome, and writing that up is a real result.