Keyed-list reconcile: LIS-minimal-move ≠ array-shift-minimal on UIElementCollection (research lever)

[azchohfi]

Context (backlog / de-prioritized research note)

PR #657 made the keyed-middle child reconcile correct (fixed the C1 rotation-identity + H1 stale-oracle bugs) via a right-to-left LIS anchor walk. That correctness costs ~+18.5% keyed-reconcile time (~0.77ms/render at 500 rows / 50% reorder) vs the prior left-to-right version — in exchange for #657's −30.9% / −98K B/render keyed alloc win (the shipped deliverable).

We investigated whether the time was recoverable. It is not, in scope — empirically proven:

• Cost center = move issuance, not bookkeeping. IChildCollection.Move → UIElementCollection.RemoveAt+Insert is O(|from−to|) native array-shift + COM. The oldRelToPanel bookkeeping is ~0.4% of reconcile (so the SIMD attempt in perf(reconciler): SIMD-vectorize keyed-middle index shifts — recover #657 keyed-reconcile time, keep −30.9% alloc #738 recovered ~0%, confirmed by /perf; reference-anchor O(1) would be equally null).
• The +18.5% is intrinsic to correctness. The correct reorder requires the more-expensive R→L moves (avg array-shift 524 vs the buggy L→R's 433). The decisive lr-corr experiment — a correct-oracle, LIS-minimal, cheap-L→R-target algorithm — is still wrong 300/300 ticks, proving no LIS-minimal correct algorithm can use the cheaper short-distance moves. The pre-perf: eliminate per-diff allocations in ChildReconciler + KeyedListDiff #657 speed was a bug artifact (cheap-but-wrong moves every tick).
• Rebuild / detach-reappend is +63% (COM-call-bound).

Decision taken: accept the trade (keep the alloc win + correctness; accept the keyed-time cost). #738 (SIMD) closed as correct-but-no-gain.

The one open research lever (intentionally not pursued now)

A reconciler that minimizes total array-shift distance (Σ|from−to|) subject to COM-call overhead, instead of minimizing move count (LIS). The textbook DOM-optimal LIS (Vue3/Inferno) is not optimal for an array-backed collection where Move ≠ O(1). This is a research-grade reconciler redesign with high correctness risk on a surface that already produced two shipped bugs, for ~0.77ms of headroom on a synthetic stress workload — recommended against unless keyed-list reorder throughput becomes a priority.

Note: the keyed-list /perf leg (StressPerf.KeyedList) and the new Flex/Yoga leg (StressPerf.Flex, added in #737) can now measure any such future work.

Filed for the record so this isn't re-investigated; not an action item.

[azchohfi]

Correction to the research lever (new evidence). The "minimize total array-shift distance (Σ|from−to|)" lever proposed above is disproven — don't pursue it.

A decisive follow-up experiment (la-anchor: a correct left-to-right mirror of #657's right-to-left anchor walk — identical LIS-minimal move count, H1/C1-safe) was measured against #657:

algo	moves	total displacement	wrong/300	reconcile
#657 (correct R→L)	41,405	21.70M	0	7.57ms
la-anchor (correct L→R)	41,405	17.22M (−20.6%)	0	7.53ms (≈identical)

So −20.6% displacement → 0% time recovery. The cost is not displacement — it's the count of WinUI Move/Insert/Remove COM ops (each ≈constant: COM marshal + per-element layout touch). Confirmed by the converse: doubling the count (detach+re-append rebuild) → +63%.

Since LIS already minimizes the move count and every correctness-preserving traversal (R→L or L→R) shares that identical minimal count, #657 sits exactly on the correct-minimal-move floor. There is no reconciler-level lever to recover the time. The only conceivable future recovery is architectural, not algorithmic: reduce the per-move COM cost (batched/native move primitives on IChildCollection) or avoid UIElementCollection moves entirely (virtualization / element recycling). Both are large, out-of-scope changes for ~0.8ms/render on a synthetic stress workload.

Net unchanged: the keyed-time cost is the intrinsic price of the C1/H1 correctness fix; the −30.9% alloc win is the deliverable and stands. #738 (SIMD) closed as correct-but-no-gain.