skip to content

When Vue 3's renderer patches a list of child vnodes, how does its keyed algorithm differ from the unkeyed one?

level: middleimportance: should knowfreq 45%

answer

  1. index pairing versus key matching
  2. prefix and suffix trimmed first
  3. key-to-index map for the middle
  4. longest increasing subsequence

basics

~20 s

Unkeyed patching pairs old and new children by index, patches the shared length, then mounts or unmounts the tail. Keyed patching trims a matching prefix and suffix, matches the rest by key, and moves only nodes outside the longest increasing subsequence.

solid answer

~40 s

Vue 3's **unkeyed** path (`patchUnkeyedChildren`) is positional: it patches `old[i]` against `new[i]` for the common length, then unmounts the extra old children or mounts the extra new ones. It never moves anything, so stateful children stay with their position. The **keyed** path (`patchKeyedChildren`) first syncs a common prefix, then a common suffix, as long as type and key match. If only additions or only removals remain, it mounts or unmounts them. Otherwise it builds a `key -> new index` map, patches each surviving old child, unmounts children whose key vanished, and — only if something moved — computes the **longest increasing subsequence** of old positions so those nodes stay put and every other node is moved or mounted. In development, duplicate keys trigger a warning.

go deeper

for a junior

Recall that without keys Vue matches children by position, and with keys it matches them by identity.

for a middle

Explain the prefix and suffix sync, the key map for the middle, and that only nodes outside the longest increasing subsequence are moved.

for a senior

Diagnose reorder bugs and slow list updates by asking which path ran, whether keys are unique and stable, and how many moves an operation needs.

for a principal

Weigh positional versus keyed patching for very large lists, and when to change the data operation rather than tune the diff.

## Two algorithms, one entry point When the renderer patches an element or fragment whose children are arrays, it has to decide which old child corresponds to which new one. Vue 3's renderer (`packages/runtime-core/src/renderer.ts`) has two routines for that: - `patchUnkeyedChildren` — used when the compiler marked a fragment as unkeyed, for example a `v-for` without `:key`. - `patchKeyedChildren` — used for keyed fragments, and also for any two arrays that come without a compiler flag (the source comment reads "two arrays, cannot assume anything, do full diff"). Unkeyed nodes inside it fall back to matching a keyless node of the same type. ## The unkeyed path: pair by index The unkeyed routine is short and cheap: 1. Take `commonLength = min(old.length, new.length)`. 2. Patch `old[i]` against `new[i]` for every `i` below that length. 3. If the old list was longer, unmount the remaining old children; if the new one was longer, mount the remaining new ones. Nothing is ever moved. If the first of five rows is removed, rows 0-3 are patched with the data that used to belong to rows 1-4 and the last DOM node is unmounted. For plain text rows that is fine — often faster. For rows that hold **their own state** (a component's local refs, an `<input>` value, focus, a running transition) the state stays with the *position*, so it ends up next to the wrong data. ## The keyed path: five steps `patchKeyedChildren` treats keys (together with vnode type) as identity: 1. **Sync from the start.** While `old[i]` and `new[i]` have the same type and key, patch them and advance. 2. **Sync from the end.** Do the same from the tails. 3. **Only additions left.** If the old list is exhausted, mount the remaining new children at the right anchor. 4. **Only removals left.** If the new list is exhausted, unmount the remaining old children. 5. **Unknown middle.** Build a map from key to new index. Walk the remaining old children: find each one's new position by key, unmount it if it has none, otherwise patch it and record its old position in a `newIndexToOldIndexMap`. While doing so, track whether positions ever went backwards; if they did, something **moved**. If something moved, the renderer computes the **longest increasing subsequence** (`getSequence`) of that map. The nodes on that subsequence are already in the right relative order and are left in place. Walking the new list backwards, it then mounts children that had no old counterpart and moves every node not on the subsequence to its anchor. ## Why the prefix/suffix and the subsequence matter - Most real list updates are an append, a prepend, a single removal or a single insert; steps 1-4 handle them without building any map. - The subsequence minimizes **DOM moves**, which are the expensive part. Moving one row from the top to the bottom of a keyed list costs one move, not one per shifted row. - A fully reversed list has a subsequence of length one, so almost every node moves — the algorithm is still correct, just not cheap. ## Side by side | Aspect | Unkeyed | Keyed | |---|---|---| | Matching | By index | By type and key | | Moves DOM nodes | Never | Only nodes outside the longest increasing subsequence | | Component state on reorder | Stays with the position | Travels with the item | | Removal of item 0 of N | N-1 patches plus one unmount | One unmount | | Extra bookkeeping | None | Key map and subsequence when items moved | | Dev warning | None | `Duplicate keys found during update:` | ## Practical consequences - A key that is **not unique** confuses the key map; Vue warns in development because two new children claim the same old node. - Using the **array index as key** makes the keyed algorithm behave positionally again, because index keys follow position. - Unkeyed patching is not a bug in itself: for stateless, static-shaped rows it avoids key bookkeeping. The trade-off is correctness for stateful rows versus a little less work. Choosing what to use as a `v-for` key, and the general idea of keys as identity, are covered by their own topics; this question is about what Vue's renderer does with the keys it is given.

  • Why does Vue 3's keyed patch compute the longest increasing subsequence only when something moved?
    If every surviving old child kept its relative order, the old positions recorded for the new list are already increasing, so no node needs moving and the subsequence would be the whole list. The renderer tracks whether a new index ever went backwards and skips the subsequence computation entirely when it did not.
  • In Vue 3, what happens if a keyed list contains two children with the same key?
    In development the renderer warns `Duplicate keys found during update:` with the key. The key map can hold only one new index per key, so one of the duplicates cannot be matched to its old node and is mounted or unmounted instead of patched, which can scramble state and cause extra DOM work.

saying these in an interview costs you the question

  • Says unkeyed patching moves DOM nodes to follow the data.
  • Believes the keyed algorithm moves every node whose index changed.
  • Thinks the longest increasing subsequence decides which nodes to unmount.
  • Claims index keys give the same benefit as stable ids when reordering.
  • Assumes duplicate keys are silently harmless in Vue 3.