Brief analysis of Vue Diff algorithm

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

What is the Diff algorithm? In a nutshell, the DIff algorithm is a comparison algorithm, that is, the process of comparing old and new VNodes (to see where changes are needed, and then where changes are made). During the comparison process, the implementation completes the generation of new VNodes without changing the old VNodes.

So how does the Diff algorithm work? In fact, in the last article we covered three scenarios, with high and low performance. So what scheme does Vue use to implement diff algorithm?

In fact, Vue determines which solution the diff algorithm takes based on whether or not you pass in a key:

There arekey, the scheme is adopted3, the implementation ofpatchKeyedChildren()Methods;
There is nokey, the scheme is adopted2, the implementation ofpatchUnkeyedChildren()Methods;

The source code is as follows:

Let’s look at the case where there is no key, using the previous code as an example:

<ul>
  <li v-for="item in letters">{{ item }}</li>
</ul>
Copy the code

Vue calls the patchUnkeyedChildren() method:

The diagram is as follows:

We can find that the above diff algorithm is not efficient:

C 和 DNothing really needs to be changed;
But as a result ofC 被 FThis causes all the following content to be changed once, and finally addedD.

In the case of a key, add the key binding to the previous code (there is no ID, so we assume item is unique) :

<ul>
  <li v-for="item in letters" :key="item">{{ item }}</li>
</ul>
Copy the code

Vue calls patchKeyedChildren() : patchKeyedChildren()

// This method is in the baseCreateRenderer function in packages/ Run-time core/ SRC /renderer.ts

const patchKeyedChildren = (
  c1: VNode[], // Old VNodes, ['A', 'B', 'C', 'D']
  c2: VNodeArrayChildren, // New VNodes, ['A', 'B', 'F', 'C', 'D']
  container: RendererElement,
  parentAnchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  slotScopeIds: string[] | null,
  optimized: boolean
) = > {
  let i = 0
  const l2 = c2.length
  // The position of the last VNode in old VNodes (index)
  let e1 = c1.length - 1 // prev ending index
  // Last VNode position in the new VNodes (index)
  let e2 = l2 - 1 // next ending index
  // 1. sync from start
  // Synchronously traverse the old and new VNodes from the header
  // (a b) c
  // (a b) d e
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = (c2[i] = optimized
      ? cloneIfMounted(c2[i] as VNode)
      : normalizeVNode(c2[i]))
    if (isSameVNodeType(n1, n2)) { // If the old and new vNodes are the same (same type and same key)
      // Start patch
      patch(
        n1,
        n2,
        container,
        null,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
    } else { / / otherwise
      // break out of the loop
      break
    }
    i++
  }
  // 2. sync from end
  // Synchronously traverse the old and new VNodes from the tail
  // a (b c)
  // d e (b c)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = (c2[e2] = optimized
      ? cloneIfMounted(c2[e2] as VNode)
      : normalizeVNode(c2[e2]))
    if (isSameVNodeType(n1, n2)) { // If the old and new vNodes are the same (same type and same key)
      // Start patch
      patch(
        n1,
        n2,
        container,
        null,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
    } else { / / otherwise
      // break out of the loop
      break
    }
    e1--
    e2--
  }
  // 3. common sequence + mount
  // If the old VNodes are traversed and the new VNodes have remaining nodes, add (mount) the remaining new nodes
  // (a b)
  // (a b) c
  // i = 2, e1 = 1, e2 = 2
  // (a b)
  // c (a b)
  // i = 0, e1 = -1, e2 = 0
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
      while (i <= e2) {
        // If null is passed to the first parameter of patch, subsequent mounting operations will be performed
        patch(
          null,
          (c2[i] = optimized
            ? cloneIfMounted(c2[i] as VNode)
            : normalizeVNode(c2[i])),
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
        i++
      }
    }
  }
  // 4. common sequence + unmount
  // If the new VNodes are traversed and the old VNodes are left, remove (unmount) the remaining old nodes
  // (a b) c
  // (a b)
  // i = 2, e1 = 2, e2 = 1
  // a (b c)
  // (b c)
  // i = 0, e1 = 0, e2 = -1
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }
  // 5. unknown sequence
  // If it is an unknown node sequence (i.e. there is an unknown sequence of positions in the middle),
  // Create index map with key.
  // Match the VNodes in the new VNodes from the old VNodes as much as possible (i.e., make maximum use of the old nodes), then remove the remaining VNodes in the old VNodes,
  // Then move the node and mount the new node
  // [i ... e1 + 1]: a b [c d e] f g
  // [i ... e2 + 1]: a b [e d c h] f g
  // i = 2, e1 = 4, e2 = 5
  else {
    const s1 = i // prev starting index
    const s2 = i // next starting index
    // 5.1 build key:index map for newChildren
    // Create an index map based on the key
    const keyToNewIndexMap: Map<string | number.number> = new Map(a)for (i = s2; i <= e2; i++) {
      const nextChild = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if(nextChild.key ! =null) {
        if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
          warn(
            `Duplicate keys found during update:`.JSON.stringify(nextChild.key),
            `Make sure keys are unique.`
          )
        }
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }
    // 5.2 loop through old children left to be patched and try to patch
    // matching nodes & remove nodes that are no longer present
    // Walk through the old node, compare to modify the old node, remove the old node is no longer used
    let j
    let patched = 0
    const toBePatched = e2 - s2 + 1
    let moved = false
    // used to track whether any node has moved
    let maxNewIndexSoFar = 0
    // works as Map<newIndex, oldIndex>
    // Note that oldIndex is offset by +1
    // and oldIndex = 0 is a special value indicating the new node has
    // no corresponding old node.
    // used for determining longest stable subsequence
    const newIndexToOldIndexMap = new Array(toBePatched)
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i]
      if (patched >= toBePatched) {
        // all new children have been patched so this can only be a removal
        unmount(prevChild, parentComponent, parentSuspense, true)
        continue
      }
      let newIndex
      if(prevChild.key ! =null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else {
        // key-less node, try to locate a key-less node of the same type
        for (j = s2; j <= e2; j++) {
          if (
            newIndexToOldIndexMap[j - s2] === 0 &&
            isSameVNodeType(prevChild, c2[j] as VNode)
          ) {
            newIndex = j
            break}}}if (newIndex === undefined) {
        unmount(prevChild, parentComponent, parentSuspense, true)}else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        patch(
          prevChild,
          c2[newIndex] as VNode,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
        patched++
      }
    }
    // move and mount
    // generate longest stable subsequence only when nodes have moved
    // Get the longest increment subsequence to move and mount
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : EMPTY_ARR
    j = increasingNewIndexSequence.length - 1
    // looping backwards so that we can use last patched node as anchor
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex] as VNode
      const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
      if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
          null,
          nextChild,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        if (j < 0|| i ! == increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) }else {
          j--
        }
      }
    }
  }
}
Copy the code

The core steps are as follows:

The diagram is as follows:

The comparison is traversed from the head:
- The old and new nodes are the same (typeAnd the samekeyAlso), continue to compare;
- C 和 F 的 keyDifferent, jump out of the cycle;

Traverse the comparison from the tail:
- The old and new nodes are the same (typeAnd the samekeyAlso), continue to compare;
- B 和 F 的 keyDifferent, jump out of the cycle;

If the old nodes have been traversed and there are additional new nodes, add these new nodes:

If the new nodes have been traversed and there are redundant old nodes, remove these old nodes:

The final case is the unknown node sequence, which is the node with out-of-order in the middle:

Therefore, we can find that when Vue performs diff algorithm, as long as there is a key, it will try its best to optimize the operation by using key:

In the absence ofkeyThe time,diffThe efficiency of algorithm is low;
Keep the same when inserting or reorderingkeyYou can makediffThe algorithm is more efficient;

Now, if you look back at the official explanation of what the key attribute does, is it clearer?

In general, in practical development, when v-for is used, we usually add the key attribute and bind the key attribute to a unique value (such as ID), so that the performance of the diff algorithm is higher.

Brief analysis of Vue Diff algorithm

Related Posts

How to download large files well

CSS selectors: What about fake elements?

Higher-order component implementations and chain calls for printing logs