runtime/gc: cycle collector does O(reachable) work per pass → quadratic when a short-lived object references a large live structure

[InauguralPhysicist]

Perf gap surfaced by a consumer (eigen-sheet #29, large-grid recalc).

Minimal reproducer (quadratic)

big is {}
for i in range of N:
    dict_set of [big, str of i, i]
c is 0
for i in range of N:
    st is {"ref": big, "i": 0, "x": i}   # short-lived, REFERENCES big
    c is c + st.x

Wall clock: N=2000 -> 0.34s, 4000 -> 1.12s, 8000 -> 4.69s — O(N^2).

Controls that are LINEAR (isolating the cause):

• REUSE one st (mutate, don't recreate): 8000 -> 0.02s
• Pass a big-referencing st to a function: 8000 -> 0.02s
• Build one growing dict-of-lists-of-dicts (no short-lived refs): 8000 -> 0.7s

So the quadratic is specifically: a short-lived object that reaches a large
live structure, created/collected repeatedly.

Mechanism (from the source)

eigenscript.c: if (live >= g_gc_threshold) gc_collect_cycles();, and after a
pass g_gc_threshold = g_gc_captured_live * 2. When the short-lived objects are
collected each pass, captured_live stays small, so the threshold stays small
and collections happen frequently; each gc_collect_cycles() appears to do
trial-deletion proportional to the reachable set (which includes big, size N).
Frequent collections × O(N) reach = O(N^2).

Consumer impact

eigen-sheet's recalc evaluates each formula with a st state that references the
sheet's large vals/cells dicts. A dependency chain / large sheet made recalc
quadratic. Mitigations applied downstream (reusing one st, dropping a
per-formula result dict, an O(V+E) in-degree topo-sort) cut the constant ~5x but
can't remove the asymptotic — it's in the collector.

Ask

Make a cycle-collection pass not O(total reachable) — e.g. bound trial-deletion
to the actual candidate cycle roots, a generational/incremental scheme, or scale
the threshold by heap size so passes stay geometric. This is a memory-model core
concern (the memory model is the moat), so flagging with the repro rather than
prescribing the fix.

Reported by eigen-sheet #29.