Skip to main content

Order without recomputing

This renderer reconciles children by the pointer identity of the child object. It never keys, and it never treats a position as an identity. Each child also remembers where it last sat, on itself. So the question arrives on its own:

If identity already gives us the mapping, and the old position is already on the child, why is a longest-increasing-subsequence pass still needed? Store the order in the identity, and a move becomes a link update rather than a rebuilt subsequence.

The narrow answer is that the subsequence is not there to find the children — it is there to decide which of them may stay still. But "why this algorithm and not another" deserves the whole space rather than one rebuttal, so this page enumerates every way this problem is known to be solved and says, for each, what it would cost here. Where a candidate cannot be priced from anything in this repository, it says so and names the row that would settle it.

The problem, and the objective​

Given a sequence of items in an old order, and the same items — plus insertions, minus deletions — in a new order, with a stable identity per item, produce a sequence of DOM operations that realises the new order.

The cost is not comparisons. It is insertBefore calls plus whatever bookkeeping the algorithm needs to decide on them. On the transition where this matters most, the axis prices discovery — stamping survivors, reading old positions, computing the move set — at 3.1250 µs against a hand-written reconciler's 21.6146, or 14.5% (my subtraction on two recorded medians, below; not a run). Every algorithm in this page's Family A and Family C competes inside that 14.5%. The other 85.5% is the moves.

One fact closes most of the space before it opens​

A node may stay where it is only if every node it must remain behind also stays. So the set of nodes that do not move is an increasing subsequence of the old positions, and the minimum number of single-node moves is exactly n minus the length of a maximum increasing subsequence. That is a property of the problem, not a claim about this code; the shipped pass's own header claims only that every backend moving DOM nodes uses it, because two placement passes are interchangeable only if they keep the same rows in place (packages/list-reconcile/src/getExoSequence.ts:1-6).

The incumbent is therefore already optimal on the expensive term. No algorithm can move fewer nodes. Everything below either

  • trades more moves for less bookkeeping (Family A),
  • makes a move cost less than one insertBefore (Family B),
  • makes the bookkeeping cheaper without changing the moves (Family C — where order maintenance lives), or
  • changes the problem so that no move set is derived at all (Family D — where this renderer already has an answer, and it is the one that wins).

The enumeration​

Family A — choose which nodes move​

Same objective, different algorithm. All of these are O(n) or O(n log n) and none allocates a per-row structure that survives the update.

The library names in the left column are attributions from the literature, not readings of those libraries' source. Nothing in this repository checks them, and only the rows marked shipped are claims about code here.

candidatemovesbookkeepingwhy it wins or loses here
Longest increasing subsequence (Vue 3, ivi, and this renderer)minimal, by the fact aboveone number[] in, two arrays out per reordering updateshipped. Its cost is the one term this family can still argue about, and it is unmeasured here — see below
Naive: move everything not in placeup to nnonethe honest rival: with the subsequence forced empty, the placement pass moves every surviving row it does not keep (packages/list-reconcile/src/reconcileExoOrder.ts:72-90). Nobody has counted the difference. This is the one candidate in the whole page that could beat the incumbent on a real transition, and it is untested
Greedy ascending run (React's lastPlacedIndex)between the two — a greedy increasing run, not a maximum onenone beyond a running maximumthis renderer already computes exactly that running maximum, for a different purpose: inOrder skips the subsequence whole when no survivor is out of order (packages/list-reconcile/src/reconcileExoOrder.ts:46-60). Adopting React's rule would mean stopping there and moving more nodes — the same trade as the naive row, with a smaller saving
Two-ended prefix/suffix scan (Vue 2, Snabbdom, Inferno)depends on the shapefour cursorsshipped, and it runs first. The position-only path and the two contiguous-splice paths are this technique; the subsequence is only what is left when they cannot answer (:108-129). It is why GROW-SHRINK/exodra measures level with the hand-written general floor in the table below, which the run refuses as a bound in either direction
Edit-script diffing (Myers, Hunt–Szymanski, Wu)minimal edits, which is a different objectiveO(nd) time and an O(n)–O(n²) tableit optimises insert/delete counts and treats a move as a delete plus an insert. Here a move is one call and a delete is a teardown plus a rebuild, so minimising edits maximises the expensive thing. Never considered here — my judgement
Cycle decomposition of the permutationminimal transpositions, n − (number of cycles)one visited-flag per rowswaps are not the primitive. insertBefore moves one node into a position; realising a transposition takes two of them. Minimal transpositions and minimal insertions are different numbers, and the second is what the LIS gives. Never considered here — my judgement
Patience / LCS-based diffing——not a separate candidate: patience diff is a longest-increasing-subsequence pass over matched positions. It is the incumbent under another name

Family B — make one move cost less​

These leave the move set alone and attack the price of a move. None is shipped.

candidatewhat it would buywhy it is not here
Run moves (Range, or a DocumentFragment round trip)k contiguous movers in fewer callsthe movers are scattered because the subsequence already kept the long runs still, so there is usually little contiguity left to batch. The one place a contiguous run is known in advance is a caller telling the list the move, and move relocates one row per call, one insertBefore each (packages/dom/src/dom/factories/createExoChildList.ts:82-99). Unpriced. What would settle it is a GROW-SHRINK or REORDER row that is the shipped op path with the run relocated through a fragment
CSS order / grid placementzero DOM mutations — a permutation becomes n style writesit changes visual order only: hit-testing, tab order, selection and assistive technology continue to see the document order. It also costs a write per row where a move set costs a call per mover, so it loses on the shapes this renderer is fast on. It works only inside a flex or grid container, which a children port cannot assume. Never considered here — my judgement
Detach the region, rebuild it, reattachone insertion instead of manythis is Family D's rebuild row, and the numbers there are against it

Family C — answer "where was this child" faster​

This is where order-maintenance structures sit, and the whole family competes for one term only: what it costs to find out where each child was. In a program with no framework in it that term is 3.1250 µs of 21.6146, 14.5% — the whole of it, stamping and subsequence included. That figure bounds the floor's discovery and not this renderer's, whose own version of the same machinery carries a per-row record and a Map. The four rungs below were finally run in the shuffled recording; two of them resolve, two are refused as under the axis's own resolution bar, and two of the four price things no structure here would touch.

candidateper-row costwhat it answersstatus
A field on the child (index)one slot in an object that already existsold position, membership and the subsequence's input, in one loadremoved: the shipped reconciler stopped reading it, so the child list stopped writing it — reconcileExoOrder works from the caller's own mirror of keys (packages/list-reconcile/src/reconcileExoOrder.ts:94-130)
Read it off the documentnothing storedold position, by walking back from the region's end anchorwas shipped as a plugin and is not in the tree today — the seam it stood in is now a whole package over two backend doors (packages/list-reconcile/src/reconcileExoOrder.ts)
A Map from key to old position, rebuilt per updatea hash entry per row of the changed middle, per updateold position and membershipwhat ships today: a Map from key to its first old position plus an Int32Array chain for repeated keys, built only over the middle that differs and dropped when the pass ends (packages/list-reconcile/src/reconcileExoOrder.ts:17-34). An earlier node-keyed table that outlived the pass, and so pinned every element the list ever held, is gone
Order maintenance (Dietz–Sleator; Bender et al.)a label, and prev/next if insertion is to be O(1)does A come after B in O(1), insert-after in amortised O(1)the subject of this page. It answers a question this pass asks once and answers already — see the next section
Order-statistic / balanced tree keyed by position (splay, AVL with subtree counts)a tree node per rowrank in O(log n), and a move is a spliceit answers rank, which the renderer has as an integer for free, and it pays a pointer chase where the incumbent pays an array index. Never considered here — my judgement
Successor structures over a bounded universe (van Emde Boas, y-fast tries)a universe-sized or hash-backed indexsuccessor in O(log log u)the renderer never asks for a successor: the new order is the successor list, handed over. Never considered here — my judgement

Family D — do not derive a move set at all​

candidatestatusevidence
Be told what changed (a transition calling the child list's own insert / move / remove)shipped, and it is the answer10.9× and 4.81×, in the tables below
Rebuild instead of reorderingmeasured, and the numbers are against itexodraKept 3.3 against exodra 10.2 on toggle, and WIDE/exodra·kept 56.25 against WIDE/exodra 115.625 — below
Do not have the rows (windowing)shipped as an application technique, not a reconciler onea sliding window preserves ascending order, so anyMoved stays false and the subsequence is skipped whole. It removes this problem rather than solving it

The two tables everything above quotes​

rowmedian (ms)what it is
exodraOps0.075four mutations, told to the list as operations
exodra0.815the same four, handed over as a new array and diffed
rowmedian (µs)what it is
GROW-SHRINK/exodraOps1.2656told
GROW-SHRINK/exodra6.0938deriving — level with the hand-written floor beneath it, because the two-ended paths recognise this shape
GROW-SHRINK/floor·diff6.0938a hand-written general reconciler, deriving
REORDER/floor·told18.4896handed the minimum move set in advance
REORDER/floor·diff21.6146the hand-written general reconciler
REORDER/exodra33.8542this renderer, on a shuffle
WIDE/exodra·kept56.25the same app keeping what the reference rebuilds
WIDE/floor51.5625a hand-written program that rebuilds
WIDE/exodra115.625the shipped app, rebuilding
rowmedian (ms)what it is
exodraKept3.3a block that survives being taken out and comes back with one insertion
exodra10.2the same block rebuilt

My arithmetic on those medians, not a run: being told is 10.9× the deriving path on list-update and 4.81× on GROW-SHRINK; keeping is 3.1× rebuilding on toggle and 2.06× on WIDE. Read the WIDE pair with the axis's own caveat: exodra·kept is a diagnostic row that "keeps what the reference rebuilds", and the file says outright that it bounds nothing (packages/benchmarks/src/benchmarks/axes/floors/update-floor.ts:208-212).

The update-floor figures here are re-read from update-floor.shuffled.json. The earlier recording of that axis is withdrawn — its phases ran in a rigid rotation, so its resolution bar was measuring where a row had been declared rather than what the program did; nothing in the renderer changed between the two runs.

Why Family D comes first​

Telling the child list directly already skips the diff, the old-position table and the subsequence entirely: a transition that knows what changed calls the command, nothing is derived — insert, move and remove are three short bodies on the child list (packages/dom/src/dom/factories/createExoChildList.ts:64-108). "A move updates a link rather than rebuilding a subsequence" is not a design this renderer lacks — it is the design it ships, and the link it updates is the document.

So the case any Family A or C candidate has to serve is what is left after that: a list that reorders by handing over a new order rather than the move. Counted in this repository's own examples and benchmarks:

wherereorderstells the child list the move
packages/benchmarks/src/benchmarks/axes/list/reconcile.tsx:340yes — 30 shuffles of 200 rows per batchno (a new array)
packages/benchmarks/src/benchmarks/axes/list/list-reconcile.tsx:673yes — one run move per cycleno (the plain array the diffing rows share)
packages/benchmarks/src/benchmarks/axes/floors/update-floor.ts:1676-1678yes — the REORDER transitionno
packages/examples/no-build/global.htmlyes — rotateno — the rotated array goes to reconcileExoOrder
packages/examples/no-build/esm.htmlyes — rotateno — the rotated array goes to reconcileExoOrder
every other list in the examplesno—

Five: three in the benchmark suite, written to measure the general path, and the rotate in the no-build pair, which hands over a new array where one move would say it. That is not an argument that the general path is unimportant — it is what a caller that does not track its own moves falls back to, and it must be correct and fast for exactly that reader. It is an argument that the population any new structure would serve is, here and today, the population that already has a cheaper answer one call away and does not take it.

What the reconciler actually asks, pass by pass​

Every question the diffing path puts, in order. The last column is why Family C's most interesting member does not apply.

passthe questionkindanswered by an order structure?
prefix scanis the key now at position i the key that was at i? (packages/list-reconcile/src/reconcileExoOrder.ts:110)identity equalityno — not an order question
tail scanthe same, walking back from the end (:113-116)identity equalityno
fast pathsdid the middle only grow, or only shrink? (:117-128)two integer comparesno
resolvewhere was this key, and was it here at all? (:17-34)a hash lookup in a Map built for this passno — such a structure has no absolute position; that is its defining property
removalswhich old rows did nobody claim? (:39-41)a rank of zerono
ascending?at < last over the survivors' ranks (:47-53)an order comparisonyes, and it is already one integer compare on a value in a register
subsequencewhich maximal subset of the old positions is increasing? (:66)an optimisation over the whole permutationno
placeis this row in the increasing run the subsequence kept? (:72-89)a bit set from the subsequenceno

Eight questions. One is a comparison, and it is the cheapest line in the pass — each survivor's rank compared with the one before it, integers the loop has already loaded, whose whole output is a boolean deciding whether the subsequence runs at all. The question that costs is the seventh, and it is not a comparison query. An oracle answering is A before B perfectly and for free would leave it exactly where it is.

The subsequence is comparison-shaped, and that changes nothing. getExoSequence touches its input only through < and a !== 0 sentinel (packages/list-reconcile/src/getExoSequence.ts:12-33), so it could run over opaque labels from an order structure with no change to the algorithm. That is the strongest form of the idea and it still loses: the same O(n log n) binary search would run with an indirect comparison in place of an integer compare, inside the binary search itself (packages/list-reconcile/src/getExoSequence.ts:21-27).

Membership comes from the hash, and an order label would not replace it. A key that is not in the caller's mirror of what was shown has no entry in the pass's Map and is built as new (packages/list-reconcile/src/reconcileExoOrder.ts:26-34). An order structure carries relative order and no membership, so it would sit beside that lookup rather than replacing it.

And it cannot replace the arrays it would sit beside. The reconciler's own state is the caller's array of keys, shown, rewritten in place or replaced by the return value (packages/list-reconcile/src/reconcileExoOrder.ts:117-130). The child list keeps its own order array of children, and that one is not scratch either: it is published to the child list in front so that list can end at this one's first node, so it is emptied in place and never handed out (packages/dom/src/dom/factories/createExoChildList.ts:14-16).

Does identity make the per-element price already paid?​

This is the strongest form of the intuition, and it is a fair question with a three-part answer. An order-maintenance structure needs a stable per-element node. A key-based renderer must derive a key and map it to something; this one already holds the item object, and a record already hangs off every child.

The allocation: yes, already paid. TExoDomChild exists per child regardless, it is built whole in one literal, and until recently it carried a position field, index, which was removed once nothing read it (packages/dom/src/dom/types/TExoDomChild.ts). A label, or a prev/next pair, could be two or three more slots in that same literal rather than a new object per row. Adding a field there is a thing this package has already done: node itself went in that way. The owner's intuition holds on this point and it should be recorded as holding.

The width: not paid, and the number usually quoted does not bound it. The measured hazard beside that literal is about growing an object after construction: "an earlier attempt to cut per-node allocations made a build 11% slower, and the lesson recorded from it was about V8's in-object sizing, not allocation counts" (a measurement note whose source file is no longer in the tree), which is why ExoDomChildBody assigns every field in its constructor — "a field added later spills the object out of its in-object store" (packages/dom/src/dom/factories/createExoDomChildFactory.ts:64). The sentence this page used to quote here, naming the regression as a fact about TExoDomChild's own literal, is no longer in that file and was not re-cited to another: what survives is the rule and the 11% figure above, neither of which prices a widened literal. A wider literal is a different thing from a grown object, and that figure does not price it. What would price it is a mount-floor or initial-render A/B with the literal widened by three slots and nothing else changed. No such row exists, and this page cannot tell you what three more slots per child cost.

The maintenance: not paid, and this is the part identity does not help with. Today nothing per child records a position at all: the child list's order array is the only record, and a splice keeps it right (packages/dom/src/dom/factories/createExoChildList.ts:52-85). A structure whose value is its links has no equivalent: a link is either right or it is not, and label space runs out and has to be rebuilt. So a splice that stores nothing per element today would start costing per-element work on paths that reorder nothing.

And none of it changes the outcome, because the price being paid or unpaid is not what decides this. Even at zero cost per element, the structure answers the fifth question in the table above — the one already answered in a register — and does not answer the subsequence, which is the one with the work in it.

What the subsequence buys is unmeasured, and the file says so​

The claim under audit is the incumbent's, not the challenger's. getExoSequence used to quote "3 moves vs 7 on a 10-row rotation, 38 vs 48 on a 50-row shuffle" against a naive "reposition everything out of place" pass. Those figures were attributed to a test file that does not exist here, and they resolve to no row in packages/benchmarks/measurements/ (packages/list-reconcile/README.md:46-52). So minimising moves is, in this repository, an unmeasured premise — and Family A's naive row is the candidate that premise is holding off.

One thing makes the doubt larger than the deleted figures suggested:

  • The cost side is bounded and small. REORDER/floor·diff minus REORDER/floor·told is what discovery costs a program with no framework in it: 3.1250 µs, 14.5% of the deriving floor and 9.2% of this renderer's 33.8542 (my subtraction on two recorded medians, not a run) — stamping, position reads and the subsequence together.

The row that would settle it is a REORDER row that is the shipped renderer with the placement pass handed an empty subsequence, gated by the same step-by-step markup diff every other row on that axis passes, and differenced against REORDER/exodra. A negative difference kills the subsequence; a positive one prices what it saves. That row still does not exist. The axis's floor·seq rung, which priced the other half — what the computation costs, separately from what it saves — was run once and is now struck with the reconciler it decomposed (packages/benchmarks/src/benchmarks/axes/floors/update-floor.ts:1736-1740); it came back at +0.0000 µs over floor·record, a difference the run refuses as a number because it sits under 4× its floor-scale null of 0.260417 µs. So the computation is somewhere between nothing and a quarter of a microsecond, and what it saves is still unmeasured.

Which of the four rungs any of this would move​

update-floor carried four nested attribution rungs for the REORDER gap, and the shuffled recording is the only one to have executed them — all four are struck now, because the reconciler they decomposed is deleted (packages/benchmarks/src/benchmarks/axes/floors/update-floor.ts:239-243). Each rung is the row above it with exactly one substitution:

rungwhat it pricesmeasuredmoved by a Family C structure?
floor·recordthe position and survival tables moving onto per-row records+0.2604 µs over floor·diff — refused as a number, under 4× the floor-scale null of 0.260417 µsit would add to this term: more slots per record
floor·seqthe shipped subsequence instead of the floor's+0.0000 µs over floor·record — refused as a number, same barat most this one, and it was predicted the smallest
floor·placethe shipped placement walk, including its DOM read per moved child+6.5104 µs over floor·seq — the largest single rung on the ladderno
floor·registrythe item-to-child Map, 200 lookups per transition+3.3854 µs over floor·placeno — it had been predicted the largest named part, at least 5.0 µs, derived from a measured 35.5 ns per Map operation

Two things the run changed. The registry prediction missed: it named the registry as the largest named part at 5.0 µs or more, and the registry came in at 3.3854 µs behind the placement walk's 6.5104. And the two rungs a Family C structure could touch are precisely the two the run cannot resolve — both sit under the axis's own resolution bar, so what an order structure would displace is somewhere between nothing and about half a microsecond, on a gap of 12.2396.

So the idea reaches one term, the term measured smallest and refused as a number, and enlarges another. If the gap is the placement walk and the registry, this addresses the wrong one — and the two rungs that carry almost all of it, at 9.8958 µs of the 12.2396 between them, are the two no storage change would move.

Where the old order lives is a separable question​

The strongest evidence that where the old order lives is not the term is that the placement pass does not care where its input came from.

The shipped reconciler reads the old position off its own mirror of what it showed. Reading it off the document instead — walking back from the region's end anchor to build the same shown array — would feed the same placement pass, because that pass takes the old order as the shown array it is handed (packages/list-reconcile/src/reconcileExoOrder.ts:5-14). No such reconciler is in the tree; the argument depends only on the two questions being separable.

A third backend refuses the pass outright, and its reason is about the destination rather than the storage: @exodra/term's region is an array and the new order is one store, so a subsequence would compute an answer nothing then reads. That is the shape of an argument that removes the pass: it names a destination where a move costs nothing. Family C names a different place to keep the input.

Two things that are not this, and survive​

A command that carries a permutation. The child list answers four commands — insert, move, remove, removeAll (packages/list-reconcile/src/types/TExoPlacedChildren.ts). A move relocates one row, so a re-sort cannot be told as one; a whole new order goes through reconcileExoOrder and the same diff, and the only wholesale path is an empty order, which clears the list outright (packages/list-reconcile/src/reconcileExoOrder.ts:102-106). That is a real gap, it is in the command set rather than in the storage, and it is where a caller that re-sorts would be served. It would not remove the subsequence either. Being handed the new order is not being handed the move set; minimising moves is a function of the permutation, however you learned it. The axis has a row for being handed the answer — floor·told — and says of it that it is "THE MAXIMAL FREE LUNCH and it is not a technique anybody could ship" (packages/benchmarks/src/benchmarks/axes/floors/update-floor.ts:134-138).

The interface. If somebody wants to build any of this, there is a door, and it does not require the argument above to be wrong. Reconciling is a whole package that stands on two doors the backend already has — c.createExoNode to make a row and the children port to place one — so a second strategy is a second function, not a fork of the renderer (packages/list-reconcile/src/createExoChildrenReconciler.ts, over packages/list-reconcile/src/reconcileExoOrder.ts). A third strategy costs the people who do not install it nothing, and it would be measured against REORDER/exodra on an axis that already exists.

What this page does not settle​

  • It is an argument from the code and from recorded rows, not a run. No axis was executed to write it. Every figure in the three gated tables is a median already recorded in packages/benchmarks/measurements/; every ratio in the prose is arithmetic on those medians and is labelled where it appears.
  • It does not prove the subsequence is worth its computation. It says the opposite: that claim is unmeasured here, Family A's naive row is the live challenger, and the row that would settle it is named.
  • It cannot price a wider TExoDomChild. Three more slots per child is the one cost in the order-maintenance case that identity might genuinely have already paid, and nothing here measures object width.
  • It prices nothing in Family B. Run moves and CSS ordering are named, argued from their semantics, and left unmeasured.
  • It does not rule out these structures for a different problem. The argument is about the question this reconciler puts. A renderer whose region is not a document, or whose caller asks where does this go relative to that, is asking something else, and nothing here transfers.