gc: the budgeted ladder costs 436 instructions per poll — why the obvious precheck is unsound, and why it is only ~4-5x anyway

[proggeramlug]

Summary

gc_runtime_safepoint_poll() evaluates the whole budgeted trigger ladder on every call — 436 instructions to answer "nothing is due" — and on a poll-heavy workload that is ~33% of the program with almost no collection behind it (measured by another session on a String.prototype.replace over 1.1M characters; their null probe puts the ceiling at −39.7%).

The obvious fix is a cheap precheck in front of the ladder. I investigated it and am not proposing it. Filing the analysis because the profile is inviting, the obvious design is unsound in two specific ways, and the payoff is ~5× smaller than a first estimate suggests — so the next person to look at that profile should start from here rather than from scratch.

8df61a817 is not the gap

That commit ("make the 'nothing due' GC check cheap on safepoint polls and trigger checks") does exactly what it says, and all three of its changes are present and working on this path: the out-of-lining is in place, the no-trigger poll returns at gc_idle_step_result() before the cycle machinery, and copying_from_space_in_use_bytes measures 57 instructions per call — it really is O(1).

Its de-duplication was scoped to gc_check_trigger, the allocator-side caller, and that is not an oversight: on that workload gc_check_trigger reaches the ladder 15 times out of 22,031,111. There was nothing there to de-duplicate. 436 instructions is already the cheap version; 33% of a program is 22 million polls multiplied by a small number.

Two soundness constraints, both at one entry point

A precheck must never answer "nothing is due" in a state where the ladder would have fired. Two things break the obvious byte-watermark design, and both are js_gc_memory_pressure — a #[no_mangle] extern "C" the platform host calls:

1. GC_OLD_RECLAIM_PENDING has a setter that fires without allocation. Two of its three production setters are collection-driven and unreachable from a poll that just answered "nothing due". The third is js_gc_memory_pressure(level >= 2) (pressure.rs:81), and it is live in a shipped product — crates/perry-ui-android/src/lib.rs:230 declares it, so Android's onTrimMemory reaches it. The module doc names the dangerous case itself: pressure arrives when a process is idle, which reaches no loop back-edge and pumps no microtasks. An idle process allocates nothing, so every byte count a cheap precheck samples is unchanged. Omitting this flag means answering "nothing due" right after the OS delivers its final warning — silently regressing what [gc] React to OS memory pressure: didReceiveMemoryWarning / onTrimMemory / PSI / dispatch_source adapters #6184 created that entry point to fix, on the platform least able to report it. Two instructions to close.

2. next_arena_trigger_base() can move down without a collection. Of its five non-test writers, two tiny-parse sites lower it but are allocation-gated, one only ever raises, one is the post-collection re-baseline — and pressure.rs:69 clamps it to arena_total_bytes() + 1 MiB and arms it, with no allocation. So "bytes have not grown since last time" does not imply "the ladder would not fire": under a static byte count the threshold can be pulled beneath it. One compare and one bool to close.

Generalisable shape: a cheap precheck is blind to exactly the paths that change state without allocating, and those are usually the host-facing ones.

No new counter is needed — but the memo is not 6 loads

Nothing monotone the allocator already maintains fits as a "nothing happened since" signal: HEAP_GENERATION bumps only on layout changes (thousands of allocations pass without moving it, which is why 8df61a817 could key its from-space cache on it), and ARENA_TOTAL_BYTES tracks committed blocks, so it is unchanged across every allocation that fits the current block.

Good news: none is needed. The ladder's inputs are already cheap TLS loads by design, because the ladder already sits on the gc_malloc hot path — arena_total_bytes is documented as "one TLS load instead of an O(blocks) walk on the gc-trigger hot path", and old_free_bytes is a Cell::get in a "hot-cache slot… which gc_budgeted_due_trigger reads on every gc_malloc". So a sound precheck is a memo on the input tuple, touching no allocation path — and the hot-path-bump risk (#10377's shape: help the axis you are watching, tax the one you are not) does not arise.

But the tuple is 10–12 quantities, not 6, and two are not single loads: copying_from_space_in_use_bytes (57 Ir, already near-minimal — it is the bump pointer plus a cached base, and it is the only fine-grained nursery-allocation signal in the system, so a memo must read it) and malloc_object_count (a RefCell borrow plus len). Reading the tuple costs ~90–110 instructions against 436 — about 4–5×, i.e. 33% → ~7–8%, not the 33% → under 1% a 6-load estimate implies.

Why I am not proposing it

Removing polls beats making them cheaper, and that work already exists: #10657 takes the same 33% → ~9% by removing 73% of the polls, with no per-poll cost and no conservatism proof to defend. The precheck lands in the same range while carrying the two external-entry-point terms above plus a memo-invalidation argument that a future edit can silently break.

They do compose — fewer polls × cheaper polls ≈ 33% → ~2% — so this is a reasonable second-order follow-on once #10657 is in. It is not the main event, and I said it was on the strength of a number I had not decomposed.

One more thing for whoever does build it: the ladder is not pure. maybe_seed_object_census_from_allocation sets a flag, walks the young generation (~1M instructions) and replaces the mean feeding the very cap it compares against, once per process. A memo that skips that arm skips the seed. That is still safe — the seed's own trigger is a pure function of an input the memo already carries — but the soundness argument must be made explicitly rather than resting on "the ladder is pure", because it is not.

Original measurement and the null probe are another session's work; the poll-frequency half is #10657.

[proggeramlug]

Update: the alternative this was measured against has been withdrawn, and the sizing argument here has a hole

This issue concluded that a precheck is not worth building, on two grounds: it is only ~4–5× (33% → ~7–8%), and the frequency lever in #10657 reaches the same place with no per-poll cost. The second ground is gone and the first was an argument about one specific design, not about prechecks.

#10657 costs peak RSS, and more than the campaign's budget allows

Measured on replace1m, nine interleaved rounds, arms alternating:

	min	median	mean	max
baseline	504.1 MB	554.2 MB	547.3 MB	599.3 MB
#10657	544.3 MB	627.7 MB	616.3 MB	636.7 MB

Median +13.2%, min +8.0%, 8 of 9 against when paired by round. The −27.9% instruction win is real and so is this. Mechanism: polling 8× less often in Pieces::finish removes the opportunities to collect during a replace, so more garbage accumulates before anything reclaims it. #10657 is now a draft.

The acceptance budget for this campaign is ≤ +10% peak RSS with no pause regression, so this is out of budget on the median, not merely "a tradeoff". That matters for the framing here: the frequency lever does not buy instructions for free, it buys them with memory, and the amount is above what we agreed to spend.

The sizing argument above memoised the wrong thing

The ~90–110 instructions quoted here is the cost of re-reading the ladder's input tuple — 10–12 quantities, two of which are not single loads (copying_from_space_in_use_bytes at 57 Ir, malloc_object_count behind a RefCell borrow). That is what makes the obvious precheck only ~4–5×.

The design that avoids it is to memoise the decision rather than the inputs, keyed on an epoch: one monotonic counter, bumped by every path that mutates any ladder input. The precheck is then a load, a compare and a branch — on the order of four instructions against 436 — and the cost moves onto the state-changing paths, which are rare by construction. That is the 33% → ~0% originally wanted, and because it does not change when collections happen, only how cheaply we decide they should not, it carries none of the RSS bill measured above.

The unsoundness in this issue is not fixed by an epoch — it is made tractable by one

The obstacle documented above stands and is now the entire problem: js_gc_memory_pressure changes state without allocating. It sets the reclaim flag, it can pull the arena threshold down, it is live on Android via onTrimMemory, and it fires when the process is idle — precisely the state a byte-watermark precheck is blindest to.

A watermark cannot see that path. An epoch can, because the path only has to bump the counter. So the proof obligation moves from "is the watermark conservative" (which I do not know how to establish) to membership: does every mutation of every ladder input bump the epoch? That is a chokepoint question, and it is answerable the way other derived-state invalidation in this tree is answered:

1. Structurally — the inputs are reachable only through accessors that bump, so a new mutation site cannot be added without joining the funnel. A comment saying "remember to bump" is not this.
2. By sabotage — remove one bump and show a collection that should have fired does not. If no fixture can be made to fail with a bump removed, that bump is unwitnessed and the membership claim is decoration.

Also still true and still unaddressed: the ladder is not pure. maybe_seed_object_census_from_allocation walks the young generation once per process. Any memo has to either run that once before the memo is armed, or be defined to not cover it.

Status

Reopening this as a design, not a conclusion. It should be built only if (1) can be made structural; if it cannot, it should not be built, and the lever falls back to poll frequency with an RSS bill attached, which is a materially worse trade than the one this issue originally compared against.

[proggeramlug]

The frequency lever is now closed on all three sites, so this is the only remaining move

Updating the comparison this issue was originally closed against. Three sites in the regex path have now been probed with the same change (nine interleaved rounds on replace1m):

• Pieces::finish — +13.2% peak RSS, retired to draft (over the ≤ +10% budget)
• collection loop — free, shipped as perf(regex): stride the replace collection loop's safepoint poll #10666; but worth only −3.5% on the template workload
• output loop — +3.7% slower in instructions on the allocating workload and +10.7% mean RSS; not attempted

Detail and the static criterion that predicts which is which are in #10665.

The conclusion for this issue: the ~33% cannot be bought by polling less. The one site that was free to stride was the small one; every large win sits where the poll is doing real work, on both throughput and memory. That removes the alternative this issue was closed against, and it removes the fallback named at the end of my last comment — "poll frequency with an RSS bill attached" is not actually available at the sites that carry the cost.

So the position is now binary. Either the epoch-keyed memo's membership obligation can be made structural — every mutation of every ladder input bumps the counter, enforced by construction rather than by a comment, and sabotage-provable by removing one bump — in which case the whole 33% is available with no pacing change and no RSS bill. Or it cannot, and the honest answer is that this 33% stays and the issue should be closed as won't-fix rather than left open as a temptation.

Nothing here changes the obstacles already documented above: js_gc_memory_pressure mutating state without allocating remains the hard case, and the ladder is still not pure (maybe_seed_object_census_from_allocation walks the young generation once per process).

[proggeramlug]

Retraction: "the 33% cannot be bought by polling less" was wrong, and the cause was an untuned constant

My previous comment concluded that the frequency lever was closed on all three sites and that the position was binary — epoch memo or won't-fix. That is wrong, and I am retracting it.

The stride constant in the retired #10657 was 4096, inherited from api::QUANTUM rather than chosen. Re-measured at 512, same change, plain main, nine interleaved rounds on replace1m:

	4096 (retired)	512
template replace, instructions	−27.9%	−27.8%
replace1m, instructions	—	−9.4%
callback ASCII / Unicode	−6.6% / −5.3%	−6.6% / −5.3%
peak RSS median	+13.2%	+0.3% (mean +0.1%, max −0.4%)

The instruction win survives essentially intact and the RSS bill disappears. Pieces are two or three units, so 512 still removes ~99% of the polls while giving the collector eight times the openings to reclaim. The memory cost was never inherent to the lever — it was that one constant.

So this is the campaign's most-repeated finding for the third time in two days: an inherited constant nobody derived turned out to be load-bearing. The others: #10494's 1-in-64 stride basis (chosen as a margin, not derived — see #10665), and the term ordering in #10669, where asking the type table first cost +0.07–0.12%. In each case the number looked like a detail and decided the outcome.

I retired a good change on an untuned constant, and then wrote up the retirement as a structural conclusion about the lever. The structural conclusion did not survive one re-measurement.

What the question actually is now

Not "epoch memo or nothing" but: how much of the ladder's cost exists outside the regex path?

The 33% was measured on a regex-replace workload, and the frequency fix is per-call-site — it does nothing for any other loop in Perry that polls per short iteration, and each of those still pays the full 436. So:

• if poll sites are numerous and spread across subsystems, the epoch memo remains the general answer and only its regex share has shrunk;
• if regex was the main offender, the residual is small and won't-fix becomes easy to justify.

That is a code-reading question — how many poll call sites exist, in which subsystems, and what the poll:allocation ratio is — and it is being answered now alongside the gc_malloc hot-path question. The soundness analysis in this issue is unaffected either way: js_gc_memory_pressure still mutates state without allocating, the ladder is still impure, and the memo is still only viable if copying_from_space_in_use_bytes and malloc_object_count can be stored without taxing allocation. What has changed is the size of the prize those obstacles are guarding.

[proggeramlug]

Closing: the epoch-keyed memo is not viable, and the reason is structural rather than a cost

Read-only investigation against origin/main @ 60922041c. Nothing built. Three findings, in increasing order of how decisively they close this.

1. The design already exists, where it pays

copying_from_space_in_use_bytes is already an epoch-keyed memo, keyed on exactly the mechanism proposed here. arena/from_space.rs:86-101 splits the sum into sealed bytes and the block currently being bumped, memoises the sealed part behind heap_generation() — a counter advanced by every HeapChange scope, with the funnel enforced by debug_assert_heap_change_open — invalidates on Arena::set_current (block.rs:579-581), and cross-checks every cached answer against the full walk in debug builds.

That is the structural-membership design from this thread, already written, including the debug verifier. So the pattern is sound and the codebase agrees. The 57 instructions are not a walk — they are the irreducible cost of the memo's own read.

ARENA_TOTAL_BYTES and OLD_GEN_IN_USE_BYTES are the same story (block.rs:1094-1130, walk.rs:369): already delta-maintained, precisely because the ladder reads them on every gc_check_trigger. The codebase has already done this move everywhere it pays. The two quantities this issue asked about are the two it didn't, and in each case the reason turns out to be visible in the code.

2. Why those two resist, specifically

copying_from_space_in_use_bytes — the residue after the memo is blocks[current].offset, the live bump pointer. It is written by compiled code with no call into the runtime: perry-codegen/src/lower_call/new_alloc.rs:528 emits the store directly into LLVM IR, as do the array-literal and packed-loop paths. The whole inline fast path is seven instructions — load offset, add size, load limit, compare, branch, store, gep. Maintaining a separate counter there would add ~3–4 instructions per allocation, on a path that runs thousands of times per ladder evaluation (arena_cell_alloc reaches gc_check_trigger only when try_alloc_current fails, i.e. about once per 1 MB block fill). That is #10377's shape in its purest form, and no small-live-set probe would ever show it.

malloc_object_count — maintainable trivially (~3 instructions inside the MALLOC_STATE.with block gc_malloc already enters), and pointless: gc_malloc calls gc_check_trigger() at malloc.rs:247, immediately before the objects.push at :273. One ladder evaluation per allocation, one count mutation per allocation — a 1:1 ratio. An epoch keyed on it bumps every time the memo would be consulted. Hit rate zero.

3. The general statement, which is what actually closes this

The ladder is a "have we allocated enough yet?" question. Its inputs are the allocation counters. An epoch that bumps on every input mutation therefore bumps on every allocation — so the memo's hit rate is structurally zero on exactly the workloads that run the ladder most.

Of the ladder's nine inputs (policy.rs:3471-3519), three change per allocation by construction. No amount of care about membership fixes that; a memo whose key changes as often as its value is not a memo.

Two further impurities beyond the one noted earlier, for the record: GC_YOUNG_LEAF_BORN_OLD is consumed at the top of the ladder (policy.rs:3482-3487) and makes that arm non-repeatable — already handled by DueTriggerMemo — and the ladder itself writes back the inline bump offset (from_space.rs:117-119), so a memo that skips the ladder skips that writeback. (Every walker calls sync_inline_arena_state() for itself, so this is probably harmless; not audited, flagged as reasoning rather than result.) maybe_seed_object_census_from_allocation is hoistable cheaply — one Cell<bool> — and was never the blocker.

4. The poll-frequency half is regex-local

gc_runtime_safepoint_poll has exactly three call sites in the workspace: the event-loop pump tail (lib.rs:758), the microtask-drain boundary (promise/microtasks.rs:387) — both once-per-tick — and regex/perex_runtime.rs:58, which fans out to ~46 references across 15 regex modules and is the only fine-grained one. Nothing outside crates/perry-runtime/src/regex/ polls per short iteration.

So the poll-side argument for keeping this open does not survive the stride fix, which closes that half at its own call sites.

5. What remains, and the shape it should take — a watermark, not a memo

The residual is real but different: gc_check_trigger runs the same 436 instructions once per gc_malloc, in every workload, forever. And the 436 is not arithmetic — it is ~13 thread-local lookups (enumerated in trigger_path_hot_slot_indices, policy.rs:3362-3422) plus a RefCell borrow plus the from-space memo read. The arms themselves are already counter >= watermark comparisons.

The promising shape is therefore to collapse the arms into a single "next check at" scalar and one counter — and for the young-gen arm, to use the inline allocator's existing limit word as a trip-wire. alloc_sample::inline_limit (arena/alloc_sample.rs:162-171) already clamps that limit to force a return to the runtime at a chosen byte count, at zero added inline cost, because it is just a different value in a compare the allocator already performs. Setting state.size = min(block.size, offset + (cap − sealed)) at each sync/reset point would make "is the nursery cap due" a branch that already happens.

That is a real design, it does not touch the compiled bump sequence, and it is measurable. It has not been costed, and js_inline_arena_slow_alloc would need an extra arm to distinguish a trip-wire from a genuine block-full. Anyone picking it up should start there.

Closing as won't-fix. The memo is refuted; the poll half is regex-local and handled elsewhere; the watermark is a different piece of work and should be opened on its own evidence rather than inherited from this thread.