perf(amr): source-centric transposed CSR for the coarse–fine fill adjoint

[kylebeggs]

What

halo_update_adjoint! still runs one scatter-add broadcast per CSR term, and after the forward gather was fused (#84) it is by far the slower half of the exchange. Fusing it bit-identically needs a source-centric transposed CSR built at schedule time; this issue is that work.

Why it was not done in #84

The forward gather is dst-centric and each dst cell is written by exactly one fill, so one broadcast per fill reproduces the per-term loop's arithmetic exactly. The transpose is a scatter, and a fill's term windows collide on shared source cells, so a dst-centric single pass would accumulate into a colliding cell in dst-cell order instead of term order and change the roundoff. Measured on refined forests (x < 0.5, maxlevel 2), counting the scatter-adds a phase issues and how many land on a cell some earlier term of the same fill already wrote:

forest	phase	fills	scatter-adds	colliding
3D 32³, 8³ blocks	interpolation	1024	77 824	40 960
3D 32³, 8³ blocks	restriction	64	9 216	0
3D 32³, 4³ blocks	interpolation	4096	77 824	0
2D 256², 32² blocks	interpolation	64	3 584	1 792
2D 256², 32² blocks	restriction	16	1 280	0

Restriction rows never collide, and interpolation rows only collide once the tangential windows are wider than one cell (blocksize ≥ 6). Fusing "only collision-free rows" was considered and rejected: it makes the exchange's cost depend on the blocksize in a way nothing in the API hints at.

The measured lopsidedness

Min-of-N, alternating processes, three rounds, on this machine (macOS/aarch64, Julia 1.12), µs:

leg	forward (fused)	adjoint (per-term)
3D 32³ / 4³ blocks, BlockField	677	3322
3D 32³ / 4³ blocks, packed	672	3448
3D 32³ / 8³ blocks, packed	205	983
2D 256² / 32² blocks, packed	14.5	46.2

So the adjoint is 3–5× the forward on exactly the geometry #84 was aimed at, and #84's acceptance is met on the forward half only.

Shape of the fix

Emit, alongside each phase's (fills, terms) CSR, a transposed CSR keyed by source cell: for every source cell touched by the phase, the list of (dst cell, weight) contributions in the order the current loop applies them — fills in reverse order, terms within a fill in forward order. The adjoint sweep then walks source cells once, accumulating left to right, which is the same accumulation sequence per cell and therefore bit-identical, followed by the dst zeroing pass.

Things to settle before building it:

• Storage. This is cell-granular, not slab-granular: ~78 k contributions for the 3D interpolation phase above, each needing a block index plus a Cartesian index on both ends. That is the descriptor bloat perf(amr): make GhostFill isbits with an NTuple of terms #42/perf(amr): fuse _run_fills! into one gather pass per coarse-fine fill #84's CSR shape was chosen to avoid, and it is rebuilt on every regrid — measure the build cost and the footprint before committing to it.
• Layout independence. Contributions cannot be precomputed as linear indices: BlockField and PackedBlockField index the same cell differently, so the record has to stay (block, CartesianIndex) and the sweep pays the decode.
• Acceptance. The exchange must stay the exact transpose of the forward (dot-product identity to roundoff), the existing bit-parity testsets in test/exchange_schedule.jl must keep comparing against something that is not a re-written copy of the new loop, and the zero-allocation assertions must hold for both layouts.

Related: #84 (forward fusion), #42 (isbits descriptors).

_{🤖 Filed by Claude — Kyle's ghost cells, my scatter-adds.}