S2 sort at target scale (50k rows) never settles: 515ms of transition work against a 400ms window

[blove]

Found while researching #452's scaling behaviour. No interaction had ever been measured at target scale. Doing so:

S2 sort, 50,000 rows	pretable	tanstack
status	partial ×3 — "the surface never held still for 2 frames within 48"	completed ×3
latency	unreportable	~33ms
settle	>400ms, never	~100ms

Decomposition

The row model is DOM-free, so the transition can be timed directly in Node (createLocalRowModel + S2 dataset, sort one column, wait for ready), sweeping transitionBudgetMs:

S2 hypothesis (3,000 rows)              S2 target (50,000 rows)
budget 0.25ms -> 41.3ms  (101 slices)   budget 0.25ms -> 589.9ms  (1834 slices)
budget 1ms    -> 26.4ms                 budget 1ms    -> 585.2ms
budget 4ms    -> 21.3ms                 budget 4ms    -> 602.7ms
budget 1000ms -> 22.2ms  (11 slices)    budget 1000ms -> 515.4ms  (195 slices)

Two different problems by scale:

1. At 3k, the yield tax is ~46% of wall time. DEFAULT_BUDGET_MS = 0.25 (cooperative-transition.ts:75) buys a quarter-millisecond of work per scheduler hop, and the hop costs about as much. Raising the budget to ~4ms nearly halves the sort. This alone closes most of pretable's interaction latency is ~2x TanStack's on S2 sort and filter #452's measured 2x at hypothesis scale.
2. At 50k, the work itself is ~515ms — ~10µs per row. Per insertRecord (cooperative-transition.ts:556-588): a full queryPlan.evaluate per row (re-runs every active column accessor and re-evaluates ALL filters even when only the sort changed, against a fresh per-plan cache — compiled-query.ts:1298, 1373-1465), a record freeze, a persistent HAMT insert, and an O(log n) AVL insert. TanStack sorts the same 50,000 rows in ~33ms total: rows.slice().sort(compareRows) over cached values (createSortedRowModel.js:81-83, verified synchronous with no chunking anywhere in the installed package).
3. Note maxUnitsPerSlice = 256 caps slices even at effectively-synchronous budgets (195 hops at 50k regardless), so budget tuning alone cannot fix target scale.

Levers, in order of measured ceiling

• Budget/duty-cycle: 0.25ms → ~4ms adaptive. Measured: 41.3 → 21.3ms at 3k. Cheap, low-risk, immediately closes most of the hypothesis-scale gap.
• Sort-only metadata reuse: a sort change rebuilds every row's metadata from a cold cache. When filters/groups are unchanged, prior evaluation results (or at least filter verdicts and unchanged sortKeys) should carry over. Bounded by the evaluate share of the 10µs/row.
• Bulk rebuild path: sorting 50k precomputed sortKeys with Array.sort and bulk-building the tree bottom-up is O(n log n) with array constants; 50k incremental persistent inserts is the same complexity with tree constants. The persistent structures earn their keep on INCREMENTAL change; a full re-sort is exactly the case where they do not.
• Progress publishes: the transition publishes nothing until complete (cooperative-transition.ts:328-331 by design), so at target scale the user sees a frozen sort for half a second. Worth a design discussion — partial sorts are arguably worse than a spinner, but "nothing for 590ms" is worst.

Relation to #452

#452's 2x-at-3k is roughly half yield tax (fixable by budget) and half per-row work (levers 2-3). This issue is the same root causes at a scale where they breach the harness window entirely. Fixing the budget alone would NOT fix this — the 50k wall time barely moves across budgets.

[blove]

Lever 1 (slice budget) is REFUTED in the browser, and the change is not shipping. Recording the full A/B so nobody re-walks this path on the Node numbers alone.

What happened

Implemented the split budget (flat 4ms, grouped kept at 0.25ms — the grouped gate requires it: at 4ms rebuild_slice_max_ms failed repeatably at 9.3–10.4 against the 8ms bound, because the budget is checked between units and a slice overruns by one worst-case grouped unit). All 329 row-model tests green, gate green, Node decomposition confirmed 41.3 → 21.3ms for a 3k sort.

Then the real browser, S2 sort at 3k, 5 repeats per variant, same machine window, one variable:

budget	interaction_latency_ms	frames to first change	frame interval
0.25ms (shipped)	50–59	6	8.3ms
1ms	67–76	7–8	8.3ms
4ms	65–74	7–8	8.3ms

The frame interval is steady everywhere, so this is not jank — the pipeline genuinely takes 1–2 more frames end-to-end at the bigger budgets, while the model's own wall time (Node-isolated) improves by ~20ms. The browser inverts the Node curve.

Why (hypothesis, not established)

The end-to-end latency is model transition + renderer replacement + React render, stitched through scheduler.postTask hops. At 0.25ms, dozens of tiny macrotasks appear to run back-to-back between rendering opportunities; at ≥1ms, slice boundaries seem to attract render opportunities, spreading the same work across more frames. Something in Chromium's macrotask/rendering interleaving rewards many-small over few-large here, and the 1ms result (as bad as 4ms) says the threshold is low. Understanding this properly needs a trace of the slice/frame timeline, not more A/Bs.

What this means for the issue

• The interaction fix must come from work reduction — lever 2 (sort-only metadata reuse) and lever 3 (bulk rebuild) — not from scheduling. Those go to a spec; the Node decomposition stands as their input (515ms of work at 50k is real regardless of slicing).
• The Node harness is fine for decomposing WORK but must not be used to predict browser latency: the scheduler environments differ (postTask vs MessageChannel fallback, and rAF interleaving exists only in the browser).
• The grouped budget's tightness is now understood and documented: it is not conservatism, it is the gate's 8ms slice bound minus one worst-case grouped unit.

The verification chain worked exactly as intended: #461's blocking metric plus the A/B protocol caught a regression that unit tests, the gate, and the Node model all missed.