An in-depth analysis of the Diff algorithm in Vue2

The diff algorithm is an efficient algorithm that compares tree nodes at the same level, avoiding the need to search and traverse the tree layer by layer. So how much do you know about the diff algorithm? The following article will give you an in-depth analysis of the diff algorithm of vue2. I hope it will be helpful to you!

Because I often asked about the Diff algorithm when watching live interviews before, and the author himself uses Vue2 a lot, so I plan to study the Diff algorithm of Vue2. In fact, I have wanted to learn it for a long time. Yes, but maybe because I feel that the Diff algorithm is relatively profound, I have been putting off learning it. But recently I was preparing for an interview, so I thought I would learn it sooner or later. Why not take this opportunity to understand the Diff algorithm? The author spent a day on it. After some research, I may not fully understand the essence of the Diff algorithm. Please forgive me.

? This actually counts as the author's study notes, and the author's level is limited. The revised article only represents the author's personal opinion. If there are any errors, you can point them out in the comment area and they will be continuously improved. At the same time, this article is very long, so Readers, please read it patiently. After reading this, the author believes that you will have a deeper understanding of the Diff algorithm. I think this article is better than most of the articles on the Internet currently explaining the Diff algorithm, because this article starts from the problem and teaches everyone how to think, rather than starting directly from the answer, just like reading the answer, which feels meaningless. This article explains step by step Guide everyone to feel the subtlety of the Diff algorithm. At the same time, we also conducted a small experiment to give everyone a more intuitive experience of the Diff algorithm.

Why use Diff algorithm

Virtual DOM

Because the bottom layer of Vue2 uses virtual DOM to represent the page Structural, virtual DOM is actually an object. If you want to know how to generate it, the general process is:

• First parse the template string, which is .vue file
• Then convert it into an AST syntax tree
• Then generate the render function
• Finally call the render function to generate a virtual DOM [Related recommendations: vuejs video tutorial, Web front-end development】

Minimum update

In fact, the framework only uses virtual DOM for performance, because js generates DOM and then displays it Pages consume a lot of performance. If the entire page is regenerated every time it is updated, the experience will definitely not be good. Therefore, you need to find the changes in the two pages, and then just update the changed places with js(possibly Whether it is adding, deleting or updating) It only takes one click, which is the minimum amount of updates. So how to achieve the minimum amount of updates? Then we need to use the Diff algorithm. So what exactly does the Diff algorithm compare? Maybe this is where it is easy to misunderstand the Diff algorithm when you first learn it. In fact, it compares the old and new virtual DOM, so the Diff algorithm is to find the difference, find the difference between the two virtual DOMs, and then reflect the difference to On the page, this achieves the smallest amount of updates. If only the changed places are updated, the performance will definitely be better.

Page update process

In fact, this is more difficult to explain. The author will give a rough introduction. Anyone who has learned Vue knows that one of the characteristics of this framework is data response. What is responsive style, that is, the page is also updated when the data is updated, so how does the page know that it needs to be updated? In fact, this is the clever part of this framework. The general process is as follows:

• As mentioned before, the render function will be run, so when the render function is run, the data will be hijacked, that is, entering Object.defineProperty's get, then dependencies are collected here, then who collects dependencies? It is each component. Each component is a Watcher, which will record all the variables (that is, dependencies) in this component. Of course, each dependency (Dep) will also collect its own location. Watcher of the component;
• Then when the data in the page changes, the set of Object.defineProperty will be triggered. In this function, the data will notify everyone A Watcher updates the page, and then each page will call the update method. This method is patch;
• Then, you need to find the amount of change between the two pages, then you need to use Let’s go to the Diff algorithm
• After finally finding the change amount, we can update the page

In fact, we update while searching. In order to make it easier for everyone to understand, these two Parts are separated

A brief introduction to the Diff algorithm

When asked in an interview what the Diff algorithm is, everyone will definitely say a few words, such as 头头, tail tail, tail head, head Tail, Depth-first traversal (dfs), Comparison of the same layer Similar to these words, although I can say one or two sentences, it is just a taste. In fact, the author read an article about the Diff algorithm published on CSDN, which is a highly read article. The author feels that he did not understand it clearly. Maybe he did not understand it himself, or he understood it but did not explain it clearly. Then the author will use his own Let me share my insights with you.

The premise of Diff algorithm

In order for everyone to understand clearly, here is the function calling process:

• patch
• patchVnode
• updateChildren

Diff algorithmPrerequisite This is very important. You may ask what is the premise? Isn't it just the comparisons mentioned before? It's true but it's also wrong, because the Diff algorithm reaches the head, tail, tail, head, tail mentioned before. The premise of this step is that the nodes compared twice are the same , the similarity here is not exactly the same as everyone thinks, but it is the same if it meets certain conditions. To simplify the explanation, the article only considers one tag that only contains key and tag name (tag), then what I said before is that the key is the same and the tag is the same. In order to prove that the author's statement is somewhat correct, the source code is also posted here:

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 36行
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}

If you are afraid of confusion, the following You can omit it and it won’t affect the overall understanding. The following is just a judgment added to consider all situations: So if the two virtual DOMs are not the same, there is no need to continue to compare, and if they are the same, there is no need to compare. The similarity here is really exactly the same, that is, the addresses of the two virtual DOMs are the same, so also paste the source code:

function patchVnode(......) {
  if (oldVnode === vnode) {
    return
  }
  ......
}

So far everyone may be confused, now let’s summarize:

• What is compared in the patch function is whether the old and new virtual DOM is key is the same and tag is the same. If they are not the same, just replace them directly. If they are the same, use patchVnode

. Having said so much, the author actually wants to express a point. , that is, the Diff algorithm will be considered only when the two compared virtual DOMs are the same. If they are not consistent, just delete the original one and replace it with the new DOM.

patchVnode function

What is in this function is the real Diff algorithm, so I will introduce it to you based on the source code.

The core code in the source code is from line 638 to line 655 of patch.ts.

In fact, the current introduction of patchVnode is directly introduced to the source code, but you may not know why it is classified in this way, so the author is here to let you understand why it is classified in this way. First of all, Here is a conclusion:

• is the text attribute and the children attribute cannot exist at the same time. This requires everyone to look at the template parsing source code part

Then when comparing old and new nodes, the main comparison is whether there are text and children, then there will be the following nine situations

按照上面的表格，因为如果新节点有文本节点，其实老节点不管是什么都会被替换掉，那么就可以按照 新节点 text 是否存在来分类，其实 Vue 源码也是这么来分类的：

if (isUndef(vnode.text)) {
  // 新虚拟 DOM 有子节点
} else if (oldVnode.text !== vnode.text) {
  // 如果新虚拟 DOM 是文本节点，直接用 textContent 替换掉
  nodeOps.setTextContent(elm, vnode.text)
}

那么如果有子节点的话，那应该怎么分类呢？我们可以按照每种情况需要做什么来进行分类，比如说：

• 第一种情况，我们啥都不用做，因此也可以不用考虑
• 第二种情况，我们应该把原来 DOM 的 textContent 设置为 ''
• 第三种情况，我们也应该把原来 DOM 的 textContent 设置为 ''
• 第四种情况，我们应该加入新的子节点
• 第五种情况，这个情况比较复杂，需要对比新老子节点的不同
• 第六种情况，我们应该把原来的 textContent 设置为 '' 后再加入新的子节点

那么通过以上六种情况 (新虚拟 DOM 不含有 text，也就是不是文本节点的情况)，我们可以很容易地进行归类：

• 分类 1️⃣： 第二种情况 和 第三种情况。进行的是操作是：把原来 DOM 的 textContent 设置为 ''
• 分类 2️⃣： 第四种情况 和 第六种情况。进行的是操作是：如果老虚拟 DOM 有 text，就置空，然后加入新的子节点
• 分类 3️⃣：第五种情况。进行的是操作是：需要进行精细比较，即对比新老子节点的不同

其实源码也是这么来进行分类的，而且之前说的 同层比较 也就得出来了，因为每次比较都是比较的同一个父节点每一个子元素 (这里的子元素包括文本节点和子节点) 是否相同，而 深度优先遍历(dfs) 是因为每次比较中，如果该节点有子节点 (这里的子节点指的是有 children 属性，而不包括文本节点) 的话需要进行递归遍历，知道最后到文本节点结束。

⭕️ 这里需要搞清楚子节点和子元素的区别和联系

然后我们来看看源码是怎么写吧，只看新虚拟 DOM 不含有 text，也就是不是文本节点的情况：

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 递归处理，精细比较
      // 对应分类 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 对应分类 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 对应分类 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 对应分类 1️⃣
    nodeOps.setTextContent(elm, '')
  }
}

❓我们可以看到源码把分类 1️⃣ 拆开来了，这是因为如果老虚拟 DOM 有子节，那么可能绑定了一些函数，需要进行解绑等一系列操作，作者也没自信看，大致瞄了一眼，但是如果我们要求不高，如果只是想自己手动实现 Diff 算法，那么没有拆开的必要。

作者觉得这么讲可能比网上其他介绍 Diff 算法的要好，其他的可能直接给你说源码是怎么写的，可能没有说明白为啥这么写，但是通过之前这么分析讲解后可能你对为什么这么写会有更深的理解和帮助吧。

updateChildren 函数

同层比较

因为当都含有子节点，即都包含 children 属性后，需要精细比较不同，不能像之前那些情况一样进行简单处理就可以了 那么这个函数中就会介绍大家经常说的 头头、尾尾、尾头、头尾 比较了，其实这不是 Vue 提出来的，是很早就提出来的算法，就一直沿用至今，大家可以参考【snabbdom 库】

? 在这之前我们要定义四个指针 newStartIdx、newEndIdx、oldStartIdx 和 oldEndIdx，分别指向 新头节点、新尾节点、旧头节点 与 旧尾节点

循环条件如下：

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  ......
}

其实这个比较也就是按人类的习惯来进行比较的，比较顺序如下 ：

• 1️⃣ 新头节点与旧头节点：++newStartIdx 和 ++oldStartIdx
• 2️⃣ 新尾节点与旧尾节点：--newEndIdx 和 --oldEndIdx
• 3️⃣ 新尾节点与旧头节点：需要将 旧头节点 移动到 旧尾节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 --newEndIdx 和 ++oldStartIdx
• 4️⃣ 新头节点与旧尾节点：需要将 旧尾节点 移动到 旧头节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 ++newStartIdx 和 --oldEndIdx
• 5️⃣ 如果都没有匹配的话，就把 新头节点 在旧节点列表 (也就是 children 属性的值) 中进行查找，查找方式按照如下：
  • 如果有 key 就把 key 在 oldKeyToIdx 进行匹配，oldKeyToIdx 根据旧节点列表中元素的 key 生成对应的下标
  • 如果没有，就按顺序遍历旧节点列表找到该节点所在的下标
  • 如果在旧节点列表是否找到也分为两种情况：
    • 找到了，那么只要将 新头节点 添加到 旧头节点 之前即可
    • 没找到，那么需要创建新的元素然后添加到 旧头节点 之前
    • 然后把这个节点设置为 undefined

根据循环条件我们可以得到两种剩余情况，如下：

• 6️⃣ 如果 oldStartIdx > oldEndIdx 说明老节点先遍历完成，那么新节点比老节点多，就要把 newStartIdx 与 newEndIdx 之间的元素添加
• 7️⃣ 如果 newStartIdx > newEndIdx 说明新节点先遍历完成，那么老节点比新节点多，就要把 oldStartIdx 与 oldEndIdx 之间的元素删除

其实我们上面还没有考虑如果节点为 undefined 的情况，因为在上面也提到过，如果四种都不匹配后会将该节点置为 undefined，也只有旧节点列表中才有，因此要在开头考虑这两种情况：

• 8️⃣ 当 oldStartVnode 为 undefined：++oldStartIdx
• 9️⃣ 当 oldEndVnode 为 undefined：--oldEndIdx

那么我们来看源码怎么写的吧，其中用到的函数可以查看源码附录：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 439 行至 556 行
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
  	// 情况 8️⃣
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
  	// 情况 9️⃣
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  	// 情况 1️⃣
    patchVnode(...)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  	// 情况 2️⃣
    patchVnode(...)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    // 情况 3️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      )
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    // 情况 4️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  } else {
  	// 情况 5️⃣
    if (isUndef(oldKeyToIdx)) // 创建 key -> index 的 Map
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
    // 找到 新头节点 的下标
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
      : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      // New element
      // 如果没找到
      createElm(...)
    } else {
      // 如果找到了
      vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(...)
        oldCh[idxInOld] = undefined
        canMove &&
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          )
      } else {
        // same key but different element. treat as new element
        createElm(...)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 情况 6️⃣
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(...)
} else if (newStartIdx > newEndIdx) {
  // 情况 7️⃣
  removeVnodes(...)
}

如果问为什么这么比较，回答就是经过很多人很多年的讨论得出的，其实只要记住过程就行了，如果想要更深了解 Diff 算法，可以去 B 站看【尚硅谷】Vue源码解析之虚拟DOM和diff算法

v-for 中为什么要加 key

这个问题面试很常见，但是可能大部分人也就只会背八股，没有完全理解，那么经过以上的介绍，我们可以得到自己的理解：

• 首先，如果不加 key 的话，那么就不会去 Map 里匹配 (O(1))，而是循环遍历整个列表 (O(n))，肯定加 key 要快一点，性能更高
• 其次，如果不加 key 那么在插入或删除的时候就会出现，原本不是同一个节点的元素被认为是相同节点，上面也有说过是 sameVnode 函数判断的，因此可能会有额外 DOM 操作

为什么说可能有额外 DOM 操作呢？这个和插入的地方有关，之后会讨论，同理删除也一样

证明 key 的性能

我们分为三个实验：没有 key、key 为 index、key 唯一，仅证明加了 key 可以进行最小化更新操作。

实验代码

有小伙伴评论说可以把代码贴上这样更好，那么作者就把代码附上 ?：

<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>
  <style>
    .box {
      display: flex;
      flex-direction: row;
    }
    .item {
      flex: 1;
    }
  </style>
</head>

<body>
  <div id="app">
    <div>
      <div>
        <h3 id="没有-nbsp-key">没有 key</h3>
        <p v-for="(item, index) in list">{{ item }}</p>
      </div>
      <div>
        <h3 id="key-nbsp-为-nbsp-index">key 为 index</h3>
        <p v-for="(item, index) in list" :key="index">{{ item }}</p>
      </div>
      <div>
        <h3 id="key-nbsp-唯一">key 唯一</h3>
        <p v-for="(item, index) in list" :key="item">{{ item }}</p>
      </div>
    </div>
    <button @click="click1">push(4)</button>
    <button @click="click2">splice(1, 0, 666)</button>
    <button @click="click3">unshift(999)</button>
    <br /><br />
    <button @click="click4">pop()</button>
    <button @click="click5">splice(1, 1)</button>
    <button @click="click6">shift()</button>
  </div>
  <script>
    var app = new Vue({
      el: &#39;#app&#39;,
      data: {
        show: false,
        list: [1, 2, 3],
      },
      methods: {
        click1() {
          this.list.push(4);
        },
        click2() {
          this.list.splice(1, 0, 666);
        },
        click3() {
          this.list.unshift(999);
        },
        click4() {
          this.list.pop();
        },
        click5() {
          this.list.splice(1, 1);
        },
        click6() {
          this.list.shift();
        }
      },
    })
  </script>
</body>

</html>

增加实验

实验如下所示，我们首先更改原文字，然后点击按钮**「观察节点发生变化的个数」**：

在队尾增加

在队内增加

在队首增加

删除实验

在队尾删除

在队内删除

在队首删除

实验结论

增加实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

删除实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

通过以上实验和表格可以得到加上 key 的性能和最小量更新的个数是最小的，虽然在 在队尾增加 和 在队尾删除 的最小更新量相同，但是之前也说了，如果没有 key 是要循环整个列表查找的，时间复杂度是 O(n)，而加了 key 的查找时间复杂度为 O(1)，因此总体来说加了 key 的性能要更好。

写在最后

本文从源码和实验的角度介绍了 Diff 算法，相信大家对 Diff 算法有了更深的了解了，如果有问题可私信交流或者评论区交流，如果大家喜欢的话可以点赞 ➕ 收藏 ?

源码函数附录

列举一些源码中出现的简单函数

setTextContent

function setTextContent(node: Node, text: string) {
  node.textContent = text
}

isUndef

function isUndef(v: any): v is undefined | null {
  return v === undefined || v === null
}

isDef

function isDef<T>(v: T): v is NonNullable<T> {
  return v !== undefined && v !== null
}

insertBefore

function insertBefore(
  parentNode: Node,
  newNode: Node,
  referenceNode: Node
) {
  parentNode.insertBefore(newNode, referenceNode)
}

nextSibling

function nextSibling(node: Node) {
  return node.nextSibling
}

createKeyToOldIdx

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

（学习视频分享：vuejs入门教程、编程基础视频）

The above is the detailed content of An in-depth analysis of the Diff algorithm in Vue2. For more information, please follow other related articles on the PHP Chinese website!