[perf] GC valid-pointer set is a full-heap BTreeSet rebuilt per cycle — replace with page-metadata classification

[proggeramlug]

Problem

The per-cycle valid-pointer set is a BTreeSet of every object in every arena (nursery + survivors + longlived + old) plus the malloc registry, rebuilt from scratch on every fallback minor and every full collection, then probed per traced edge.

• Structure: gc/trace.rs:10-50
• Builder walks all 5 regions: gc/trace.rs:285-342 (region list arena/walk.rs:119-141)
• Per-edge probes: gc/trace.rs:481 and :410 (O(log n) after a range prefilter)
• Rebuilt each fallback minor + full: gc/cycle.rs:1026-1039

On a 500 MB heap with ~4M objects this is roughly 0.4–1.5 s of BTreeSet insertion before marking even starts, and it scales with total heap — old-gen growth directly inflates minor pauses.

Proposed fix

Replace membership testing with the page-metadata classification the copying path already uses (gc/copying.rs:68-102 — classify_heap_space + plausible_gc_header), or a per-block object-start bitmap. Keep the BTree only for conservative interior-pointer floor lookups, which only the forced-conservative-scan path needs.

Context

Found by the 2026-07-09 GC audit (pause/scalability dimension). This is the single biggest latency lever in the collector: it dominates every fallback pause. Related: #6083 was closed after the debt-pacer rework, but the default (alloc-point) collection path still runs this builder synchronously.

[proggeramlug]

Analysis + sequencing (design complete)

Mapping the membership choke point (ValidPointerSet::contains, gc/trace.rs:115) and its callers settles how this should land:

Caller split

• Precise queries — NaN-boxed POINTER_TAG edges from real fields/roots (trace.rs:410/431/481/509). Input is known to be a real pointer.
• Conservative queries — raw stack words / raw-ptr fallback (roots.rs:626/640/682/705/1638/1641/1731). Ambiguous.

Crux (already resolved in earlier analysis): the exact set is mandatory wherever conservative scan runs. Conservative roots are marked + traced (roots.rs:611 try_mark_conservative_word: nursery targets are MARKED + push_mark_seed, i.e. traced; only old targets are pin-only). A heuristic classifier can false-positive → trace garbage → crash. And in default production, automatic alloc-point collections force conservative scan, so those cycles keep the exact lookup_set. globalThis.gc() also forces conservative scan. The copied-minor path already classifies (post-#6208) and never builds the set. Net: today there is no precise-only cycle that builds the exact set unnecessarily — so the "skip the O(heap) build" win has no target in the current default configuration.

The win unlocks only with #6180 Stage 2 (precise/incremental collections as the default). Those cycles don't force conservative scan, so their precise contains queries could be routed through a page-metadata classifier and skip the BTreeSet build.

Why it must be co-designed with Stage 2, not shipped standalone: the classifier (classify_arena/classify_malloc + plausible_gc_header, generalized from CopyingPointerSet::classify) is a live heap check; contains is a build-time snapshot. They agree on stop-the-world cycles (no concurrent allocation during marking) but diverge precisely on incremental cycles (objects allocated after the build walk are live/classifier-valid but absent from the snapshot). So the differential-verification harness — the de-risker — can only be meaningfully exercised on the incremental cycles Stage 2 introduces; a standalone harness validated on stop-the-world cycles would prove nothing about the path where the classifier would actually replace the set.

Decision: keep this open and implement it as part of the #6180 Stage-2 work (flip PERRY_GC_INCREMENTAL default-on), where: (a) the classifier primitive lands with a real precise-cycle caller, (b) the differential harness runs against genuine incremental cycles (assert classifier == exact on precise queries; the expected snapshot-vs-live divergences become the concurrent-alloc barrier's responsibility), (c) the exact set is skipped only on cycles proven not to run conservative scan. No standalone code change now — it would be speculative groundwork with no present-config effect and an unverifiable harness.

[proggeramlug]

Shipped in #6239 (merged): budgeted cycles build NO exact valid-pointer census — membership resolves through classifier_valid_object_start (exact malloc-registry membership ∪ plausible arena header on an arena-classified page), differentially verified as a census superset across the full suite (PERRY_GC_VERIFY_CLASSIFIER=1, 1227/0). Synchronous cycles keep the exact set (their conservative scan requires exactness — traced conservative words cannot tolerate heuristic false positives), and classifier-mode cycles never conservative-scan. Honest measurement note: the census removal's RSS effect was small (the BTreeSet attribution in this issue was disproven — the real RSS levers were pacing gain + age-bump gating, also in #6239); the census skip's wins are the O(heap) build COST per budgeted cycle and unblocking the #6180 default-on flip.