* runtime: pin the ScrCycHdr layout the LLVM backend hardcodes
scr_cyc_mark_live is a static inline, so there is no symbol for the LLVM
backend to call — it open-codes the retain hook as a raw `store i32 0` at
obj-16 and reaches the cycle header at obj-32. Three sites emit that
(llvm/shapes.ts, llvm/classes.ts, llvm/emitter.ts), which makes the C
struct's size and its `color` offset a real ABI between the runtime header
and hand-written IR. The stored VALUE is part of that ABI too: the emitted
store is the literal 0, not the enumerator, so SCR_CYC_BLACK's numeric value
is pinned as surely as the offsets are.
Nothing enforced any of it. llvm-runtime-abi.test.ts mechanically checks that
every `declare @scr_*` agrees with its C prototype, but that is the FUNCTION
ABI; a struct-offset skew is invisible to it, to the type system, and to the
C compiler. Narrowing `color` and putting another field in the freed bytes
compiles clean and silently zeroes that field on every retain; reordering the
color enum compiles clean and makes every retain write the wrong color.
Assert the four properties the emitted IR actually depends on, so the next
edit to this struct or that enum fails the build instead of miscompiling.
The three layout assertions bake in 64-bit pointers and size_t, which every
current target has. A 32-bit port would trip them — correctly: the backend's
hardcoded -16/-32 would need fixing too.
* runtime: collect cycles generationally
A trial-deletion pass costs O(objects reachable from its candidates), and a
candidate inside a large live structure reaches all of it. Collecting every
256 candidates therefore made total collection work quadratic in a growing
live heap: the V8 splay benchmark spent 749ms per iteration, ~99% of it in
the collector re-walking a tree that was entirely live and never garbage.
Make the collector generational, in the shape CPython uses for this same
algorithm. Each header carries a generation; a pass names the oldest one it
will walk and skips anything above it, exactly as it already skips NULL and
immortals; survivors are promoted so later nursery passes never re-walk
them. A pass then costs what was allocated since the last one rather than
the whole heap.
Restricting the walk stays sound because trial deletion is already
conservative in the safe direction: an edge from a skipped older object is
never trial-deleted, so its target keeps that count and reads as externally
referenced — the same answer the collector gives for a stack reference.
What it gives up is cycles that span generations, and the full pass (which
skips nothing, and so is exactly the old algorithm) is what finds those.
Three things that are load-bearing and were not obvious:
- A restricted pass may spare a candidate ONLY because the edge keeping it
alive came from a generation it refused to walk. The candidate buffer is
the collector's only root set and markRoots consumes the entry, so
dropping such a survivor retires the one record that the object is a
possible cycle root — and a dead cycle whose members were all spared that
way is then invisible to every later pass, full ones included. So a
restricted pass hands its survivors back as candidates. A full pass needs
none of this: it walked every edge, so rc > 0 there is a genuine outside
reference and Bacon-Rajan's own reasoning retires the candidate.
- Live data that is unlinked INTO a dead cycle grows no counter: those
objects were tallied when they were allocated, and they are not in the
nursery. A heap-growth trigger alone therefore never fires for a program
that churns its long-lived structures, so the mature candidate buffer's
own size is a second full-pass trigger.
- Restricting the walk leaves one edge accounted by NOBODY. markGray does
not trial-delete an edge into a skipped generation, and the teardown
contract has free_fn release exactly the UNTRACED children — because every
traced edge was supposed to have been decremented by markGray. So freeing
a white object that holds a traced edge into an older generation drops the
edge while the target keeps the count, and that phantom reference reads as
an external one to every later pass, full ones included: the target and
everything it links to would never be reclaimable again.
The white set pays those edges off explicitly, in two halves, because the
walk cannot do it inline — a release there could free a survivor that
scr_promote still points at, or cascade into the white set mid-teardown.
Each target is PINNED with a retain while `gen` still holds the values the
walk filtered on, and after the teardowns the pin is dropped and the edge
given up for real. Two decrements per entry, because the pin is one of
them; a single release would only undo the pin and leave the phantom edge
where it was. The pin is also what makes the second decrement safe, since
a teardown's releases of untraced children can reach a cycle-headered
object — that is how they re-buffer survivors. One entry per skipped edge,
so several edges sharing a target settle it once each. Nothing pinned can
be in the white set: a skipped older object's edges were never
trial-deleted, so anything it references was scan-blacked rather than
whitened, by the same conservatism above.
The event loop's between-turns collection now runs one scheduled pass
instead of scr_collect_cycles(); a full sweep per turn would walk the whole
live heap every turn, which is the cost the generations exist to avoid.
scr_collect_cycles() stays the exit / session-reset sweep, where the RC
audit runs straight after and wants nothing reclaimable left.
757-cycle-cross-generation.ts covers the third point: a live list mutated
until its nodes promote, then dead nursery cycles holding traced edges into
it. Unaccounted, the sanitized lane reports 60 objects live at exit — the
whole list, held by phantom counts.
Measured, best-of-7 against the previous collector:
splay 620.45ms -> 1.45ms (428x)
deltablue 1.25 -> 0.81 (1.55x)
richards 1.196 -> 1.162 (1.03x)
crypto/navier-stokes/raytrace/regexp unchanged
an LRU cache (200k entries, 200k ops) 32137ms -> 93ms (345x)
a large live cache + 500 event-loop turns 3095ms -> 776ms (4.0x)
The trade is space: floating cyclic garbage is now a bounded fraction of the
live heap instead of a fixed candidate count, so peak RSS on
cyclic-garbage-heavy programs runs ~1.4x the old collector's. Bounded and
flat in run length, not a leak — verified by holding a 200k-object live heap
while churning 200k dead cycles per round for 30 rounds.
Test lanes show byte-identical failure sets against the previous collector:
Linux sanitized 164, Linux plain 528, macOS differential corpus 66 — all
pre-existing on those machines, none introduced or fixed here.
* runtime: bound scheduled mature cycle backlog
* runtime: rearm cycle trigger after candidate deaths
- Stamp all publishable packages at v0.0.22.
- Publish release notes for persistent builds and external coverage types.
- Refresh the compiler surface manifest for the release.
- Pin the supported fetch surface to an explicit Node and Undici profile.
- Generate deterministic WebIDL, AbortSignal, and stream differential campaigns.
- Match Node stream pull scheduling while preserving typed source identity.
- Stamp all publishable packages at v0.0.21.
- Publish release notes for the contract-sidecar fixes.
- Refresh the compiler surface manifest for the release.
- Stamp all publishable packages at v0.0.20.
- Publish release notes for the contract-sidecar improvements.
- Refresh the compiler surface manifest for the release.
Jimmy Miller