Vue3 の差分アルゴリズムの詳細な分析 (詳細なグラフィックとテキストの説明)

この記事では、Vue3 の差分アルゴリズムを画像と文章で詳しく解説します。

この記事では主に Vue3 diff アルゴリズムを分析します。この記事を通じて次のことがわかります。

• diff のメインプロセス、コアロジック

• #diff はノードを再利用、移動、アンインストールする方法です

• サンプル質問もありますので、この記事と組み合わせて分析の練習をすることができます

##Vnode とレンダラーのパッチ処理が特にわからない場合は、最初に次の 2 つの記事を読むことをお勧めします:

Vnode (https://mp.weixin.qq.com/s/DtFJpA91UPJIevlqaPzcnQ)

• # #レンダラー分析 (https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ)

• 1.0
diff

なし

key 子ノード が UNKEYED_FRAGMENT

の場合、処理中にマークされます。

まず、古い自己シーケンスと新しい自己シーケンスを通じて、最小の共通長

commonLength
• が取得されます。
  公開部分
patch
• をループします。

#patch
• 終了し、残りの古いノードと新しいノードを処理します。
  #oldLength > newLength
の場合、古いノードを
• unmount

  # する必要があることを意味します## それ以外の場合は、新しいノードがあり、 mount

  ;
省略されたコードがここに掲載されています。

const patchUnkeyedChildren = (c1, c2,...res) => {
    c1 = c1 || EMPTY_ARR
    c2 = c2 || EMPTY_ARR
    // 获取新旧子节点的长度
    const oldLength = c1.length
    const newLength = c2.length
    // 1. 取得公共长度。最小长度
    const commonLength = Math.min(oldLength, newLength)
    let i
    // 2. patch公共部分
    for (i = 0; i < commonLength; i++) { 
      patch(...)
    }
    // 3. 卸载旧节点
    if (oldLength > newLength) {
      // remove old
      unmountChildren(...)
    } else {
      // mount new
      // 4. 否则挂载新的子节点
      mountChildren(...)
    }
  }

上記のコードからわかるように、key

なしで子ノードを処理する場合、ロジックは依然として非常に単純かつ粗雑です。正確に言うと、

key

を持たない子ノードの処理効率は高くありません。

なぜなら、パブリック部分に直接 patch するのか、新しいノードに直接 mountChildren

するのか (実際には、子ノードを走査して

を実行します) patch 操作)、実際には patch は再帰的に実行されるため、パフォーマンスに影響します。 2.0 diff diff

には、

key# を持つ key サブノード シーケンス があります。 ## サブシーケンス時間では、さらに分割されます。主に以下の状況によって判断されます。

開始位置のノードの種類が同じである。 終了位置のノード タイプは同じです。

同じ部分が処理され、新しいノードが追加されました。

• 同じ部分が処理された後、アンインストールする必要がある古いノードが存在します。
• 最初と最後は同じですが、途中に再利用可能な順序が狂ったノードがあります。
会議では、最初に 3 つの修正点が示されます。すなわち、古いバージョンの開始位置を示す
i = 0

です。および新しいシーケンス

e1 = oldLength - 1
• 、古いシーケンスの終了位置を指します
e2 = newLength - 1
• 、を指します新しいシーケンスの終了位置
• <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>let i = 0 const l2 = c2.length let e1 = c1.length - 1 // prev ending index let e2 = l2 - 1 // next ending index</pre><div class="contentsignin">ログイン後にコピー</div></div> 状況に応じて
diff

処理を開始しましょう。

2.1 開始位置のノード タイプは同じです。

開始位置 同じタイプのノードは、左から右に

diff トラバースされます。

• 新旧のノード タイプが同じ場合、パッチ処理

• ノード タイプが異なる場合、 break、トラバーサルから抜け出す

  diff

• <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>// i &lt;= 2 &amp;&amp; i &lt;= 3 while (i &lt;= e1 &amp;&amp; i &lt;= e2) { const n1 = c1[i] const n2 = c2[i] if (isSameVNodeType(n1, n2)) { // 如果是相同的节点类型，则进行递归patch patch(...) } else { // 否则退出 break } i++ }</pre><div class="contentsignin">ログイン後にコピー</div></div> 上記ではコードの一部を省略していますが、メインのロジックには影響しません。 コードからわかるように、トラバース時には、関数のグローバル コンテキストで事前に宣言された 3 つのポインターを使用してトラバースの判断を行うことがわかります。

開始位置と同じ位置を完全に移動できることを確認します (

i <= e1 && i <= e2

)。

異なるタイプのノードに遭遇すると、

diff

はトラバーサルから抜け出します。

#2.2 終了位置のノード タイプは同じです

開始位置は同じですdiff End は、シーケンスの終わりから開始して

diff

を走査します。

このとき、テールポインタ

e1 と e2 をデクリメントする必要があります。

//  i <= 2 && i <= 3
// 结束后： e1 = 0 e2 =  1
while (i <= e1 && i <= e2) {
  const n1 = c1[e1]
  const n2 = c2[e2]
  if (isSameVNodeType(n1, n2)) {
    // 相同的节点类型
    patch(...)
  } else {
    // 否则退出
    break
  }
  e1--
  e2--
}

コードからわかるように、diff

ロジックは基本的に最初のロジックと同じであり、同じタイプの

patch が処理されます。

さまざまなタイプ

break、ループ走査から抜け出します。 そして、末尾ポインタをデクリメントします。

2.3 トラバーサルの同じ部分が完了しました。新しいシーケンスに新しいノードがあり、それらをマウントします。

上記 2 つの処理後

patch最初と最後に同じパーツを持つノードが完成したら、次のステップは、新しいシーケンスで新しいノードを patch 処理することです。

<p>在经过上面两种请款处理之后，如果有新增节点，可能会出现 <code>i > e1 && i <= e2的情况。

这种情况下意味着新的子节点序列中有新增节点。

这时会对新增节点进行patch。

// 3. common sequence + mount
// (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
    // nextPos < l2，说明有已经patch过尾部节点，
    // 否则会获取父节点作为锚点
    const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
    while (i <= e2) {
      patch(null, c2[i], anchor, ...others)
      i++
    }
  }
}

从上面的代码可以知道，patch的时候没有传第一个参数，最终会走mount的逻辑。

可以看这篇 主要分析patch的过程

https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ

在patch的过程中，会递增i指针。

并通过nextPos来获取锚点。

如果nextPos < l2，则以已经patch的节点作为锚点，否则以父节点作为锚点。

2.4 相同部分遍历结束，新序列中少节点，进行卸载

如果处理完收尾相同的节点，出现i > e2 && i <= e1的情况，则意味着有旧节点需要进行卸载操作。

// 4. common sequence + unmount
// (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++
  }
}

通过代码可以知道，这种情况下，会递增i指针，对旧节点进行卸载。

2.5 乱序情况

这种情况下较为复杂，但diff的核心逻辑在于通过新旧节点的位置变化构建一个最大递增子序列，最大子序列能保证通过最小的移动或者patch实现节点的复用。

下面一起来看下如何实现的。

2.5.1 为新子节点构建key:index映射

// 5. 乱序的情况
// [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

const s1 = i // s1 = 2
const s2 = i // s2 = 2

// 5.1 build key:index map for newChildren
// 首先为新的子节点构建在新的子序列中 key：index 的映射
// 通过map 创建的新的子节点
const keyToNewIndexMap = new Map()
// 遍历新的节点，为新节点设置key
// i = 2; i <= 5
for (i = s2; i <= e2; i++) {
  // 获取的是新序列中的子节点
  const nextChild = c2[i];
  if (nextChild.key != null) {
    // nextChild.key 已存在
    // a b [e d c h] f g
    // e:2 d:3 c:4 h:5
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

结合上面的图和代码可以知道：

• 在经过首尾相同的patch处理之后，i = 2，e1 = 4，e2 = 5

• 经过遍历之后keyToNewIndexMap中，新节点的key:index的关系为 E : 2、D : 3 、C : 4、H : 5

• keyToNewIndexMap的作用主要是后面通过遍历旧子序列，确定可复用节点在新的子序列中的位置

2.5.2 从左向右遍历旧子序列，patch匹配的相同类型的节点，移除不存在的节点

经过前面的处理，已经创建了keyToNewIndexMap。

在开始从左向右遍历之前，需要知道几个变量的含义：

// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
// 从旧的子节点的左侧开始循环遍历进行patch。
// 并且patch匹配的节点 并移除不存在的节点

// 已经patch的节点个数
let patched = 0
// 需要patch的节点数量
// 以上图为例：e2 = 5; s2 = 2; 知道需要patch的节点个数
// toBePatched = 4
const toBePatched = e2 - s2 + 1
// 用于判断节点是否需要移动
// 当新旧队列中出现可复用节点交叉时，moved = true
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
// 注意 旧节点的 index 要向右偏移一个下标

// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// 并且旧节点Index = 0 是一个特殊的值，用于表示新的节点中没有对应的旧节点

// used for determining longest stable subsequence
// newIndexToOldIndexMap 用于确定最长递增子序列
// 新下标与旧下标的map
const newIndexToOldIndexMap = new Array(toBePatched)
// 将所有的值初始化为0
// [0, 0, 0, 0]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

• 变量 patched 用于记录已经patch的节点
• 变量 toBePatched 用于记录需要进行patch的节点个数
• 变量 moved 用于记录是否有可复用节点发生交叉
• maxNewIndexSoFar用于记录当旧的子序列中存在没有设置key的子节点，但是该子节点出现于新的子序列中，且可复用，最大下标。
• 变量newIndexToOldIndexMap用于映射新的子序列中的节点下标 对应于 旧的子序列中的节点的下标
• 并且会将newIndexToOldIndexMap初始化为一个全0数组，[0, 0, 0, 0]

知道了这些变量的含义之后 我们就可以开始从左向右遍历子序列了。

遍历的时候，需要首先遍历旧子序列，起点是s1，终点是e1。

遍历的过程中会对patched进行累加。

卸载旧节点

如果patched >= toBePatched，说明新子序列中的子节点少于旧子序列中的节点数量。

需要对旧子节点进行卸载。

// 遍历未处理旧序列中子节点
for (i = s1; i <= e1; i++) {
    // 获取旧节点
    // 会逐个获取 c d e
    const prevChild = c1[i]
    // 如果已经patch 的数量 >= 需要进行patch的节点个数
    
    // patched刚开始为 0
    // patched >= 4
    if (patched >= toBePatched) {
      // all new children have been patched so this can only be a removal
      // 这说明所有的新节点已经被patch 因此可以移除旧的
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
}

如果prevChild.key是存在的，会通过前面我们构建的keyToNewIndexMap，获取prevChild在新子序列中的下标newIndex。

获取newIndex

// 新节点下标
let newIndex
if (prevChild.key != null) {
  // 旧的节点肯定有key, 
  // 根据旧节点key  获取相同类型的新的子节点  在 新的队列中对应节点位置
  // 这个时候 因为c d e 是原来的节点 并且有key
  // h 是新增节点 旧节点中没有 获取不到 对应的index 会走else
  // 所以newIndex在开始时会有如下情况
  /**
   * node  newIndex
   *  c       4
   *  d       3
   *  e       2
   * */ 
  // 这里是可以获取到newIndex的
  newIndex = keyToNewIndexMap.get(prevChild.key)
}

以图为例，可以知道，在遍历过程中，节点c、d、e为可复用节点，分别对应新子序列中的2、3、4的位置。

故newIndex可以取到的值为4、3、2。

如果旧节点没有key怎么办？

// key-less node, try to locate a key-less node of the same type
// 如果旧的节点没有key
// 则会查找没有key的 且为相同类型的新节点在 新节点队列中 的位置
// j = 2: j <= 5
for (j = s2; j <= e2; j++) {
  if (
    newIndexToOldIndexMap[j - s2] === 0 &&
    // 判断是否是新旧节点是否相同
    isSameVNodeType(prevChild, c2[j])
  ) {
    // 获取到相同类型节点的下标
    newIndex = j
    break
  }
}

如果节点没有key，则同样会取新子序列中，遍历查找没有key且两个新旧类型相同子节点，并以此节点的下标，作为newIndex。

newIndexToOldIndexMap[j - s2] === 0 说明节点没有该节点没有key。

如果还没有获取到newIndex，说明在新子序列中没有存在的与 prevChild 相同的子节点，需要对prevChild进行卸载。

if (newIndex === undefined) {
  // 没有对应的新节点 卸载旧的
  unmount(prevChild, parentComponent, parentSuspense, true)
}

否则，开始根据newIndex，构建keyToNewIndexMap，明确新旧节点对应的下标位置。

时刻牢记newIndex是根据旧节点获取的其在新的子序列中的下标。

// 这里处理获取到newIndex的情况
// 开始整理新节点下标 Index 对于 相同类型旧节点在 旧队列中的映射
// 新节点下标从 s2=2 开始，对应的旧节点下标需要偏移一个下标
// 0 表示当前节点没有对应的旧节点
// 偏移 1个位置 i从 s1 = 2 开始，s2 = 2
// 4 - 2 获取下标 2，新的 c 节点对应旧 c 节点的位置下标 3
// 3 - 2 获取下标 1，新的 d 节点对应旧 d 节点的位置下标 4
// 2 - 2 获取下标 0，新的 e 节点对应旧 e 节点的位置下标 5
// [0, 0, 0, 0] => [5, 4, 3, 0]
// [2,3,4,5] = [5, 4, 3, 0]
newIndexToOldIndexMap[newIndex - s2] = i + 1
// newIndex 会取 4 3 2
/** 
 *   newIndex  maxNewIndexSoFar   moved
 *       4            0          false
 *       3            4           true
 *       2        
 * 
 * */ 
if (newIndex >= maxNewIndexSoFar) {
  maxNewIndexSoFar = newIndex
} else {
  moved = true
}

在构建newIndexToOldIndexMap的同时，会通过判断newIndex、maxNewIndexSoFa的关系，确定节点是否发生移动。

newIndexToOldIndexMap最后遍历结束应该为[5, 4, 3, 0]，0说明有旧序列中没有与心序列中对应的节点，并且该节点可能是新增节点。

如果新旧节点在序列中相对位置保持始终不变，则maxNewIndexSoFar会随着newIndex的递增而递增。

意味着节点没有发生交叉。也就不需要移动可复用节点。

否则可复用节点发生了移动，需要对可复用节点进行move。

遍历的最后，会对新旧节点进行patch，并对patched进行累加，记录已经处理过几个节点。

// 进行递归patch
/**
 * old   new
 *  c     c
 *  d     d
 *  e     e 
*/
patch(
  prevChild,
  c2[newIndex],
  container,
  null,
  parentComponent,
  parentSuspense,
  isSVG,
  slotScopeIds,
  optimized
)
// 已经patch的
patched++

经过上面的处理，已经完成对旧节点进行了卸载，对相对位置保持没有变化的子节点进行了patch复用。

接下来就是需要移动可复用节点，挂载新子序列中新增节点。

2.5.3 移动可复用节点，挂载新增节点

这里涉及到一块比较核心的代码，也是Vue3 diff效率提升的关键所在。

前面通过newIndexToOldIndexMap，记录了新旧子节点变化前后的下标映射。

这里会通过getSequence方法获取一个最大递增子序列。用于记录相对位置没有发生变化的子节点的下标。

根据此递增子序列，可以实现在移动可复用节点的时候，只移动相对位置前后发生变化的子节点。

做到最小改动。

那什么是最大递增子序列？

• 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
• 而递增子序列，是数组派生的子序列，各元素之间保持逐个递增的关系。
• 例如：
• 数组[3, 6, 2, 7] 是数组 [0, 3, 1, 6, 2, 2, 7] 的最长严格递增子序列。
• 数组[2, 3, 7, 101] 是数组 [10 , 9, 2, 5, 3, 7, 101, 18]的最大递增子序列。
• 数组[0, 1, 2, 3] 是数组 [0, 1, 0, 3, 2, 3]的最大递增子序列。

已上图为例，在未处理的乱序节点中，存在新增节点N、I、需要卸载的节点G，及可复用节点C、D、E、F。

节点CDE在新旧子序列中相对位置没有变换，如果想要通过最小变动实现节点复用，我们可以将找出F节点变化前后的下标位置，在新的子序列C节点之前插入F节点即可。

最大递增子序列的作用就是通过新旧节点变化前后的映射，创建一个递增数组，这样就可以知道哪些节点在变化前后相对位置没有发生变化，哪些节点需要进行移动。

Vue3中的递增子序列的不同在于，它保存的是可复用节点在 newIndexToOldIndexMap的下标。而并不是newIndexToOldIndexMap中的元素。

接下来我们看下代码部分：

// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
// 移动节点 挂载节点
// 仅当节点被移动后 生成最长递增子序列
// 经过上面操作后，newIndexToOldIndexMap = [5, 4, 3, 0]
// 得到 increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
// j = 0
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 从后向前遍历 以便于可以用最新的被patch的节点作为锚点
// i = 3
for (i = toBePatched - 1; i >= 0; i--) {
  // 5 4 3 2
  const nextIndex = s2 + i
  // 节点 h  c  d  e 
  const nextChild = c2[nextIndex]
  // 获取锚点
  const anchor =
    nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
  // [5, 4, 3, 0] 节点h会被patch，其实是mount
  //  c  d  e 会被移动
  if (newIndexToOldIndexMap[i] === 0) {
    // mount new
    // 挂载新的
    patch(
      null,
      nextChild,
      container,
      anchor,
      ...
    )
  } 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--
    }
  }
}

从上面的代码可以知道：

• newIndexToOldIndexMap を通じて取得される最大増加サブシーケンスは [2]
• j = 0
• トラバースするときは右から左にトラバースしてアンカー ポイントを取得します。patch を通過した兄弟ノードがある場合はその兄弟ノードがアンカー ポイントとして使用され、そうでない場合は親ノードが使用されます。アンカー ポイント
• newIndexToOldIndexMap[i] === 0 として使用され、新しいノードが追加されたことを示します。ノードを mount する必要がある場合は、null を patch の最初のパラメーターに渡すだけです。 h node が最初に patch になることがわかります。
• それ以外の場合は、moved が true であるかどうかが判断されます。前の分析により、 ノード C とノード E の位置が前方変更と後方変更中に変更されたことがわかります。
• したがって、ノードはここに移動されます。この時点では、j は 0、i## であることがわかります。 # 現時点では **2**、i !== sinneringNewIndexSequence[j] は true、C node は移動されません。代わりに j-- を実行してください。
その後、
• j なので、D ノードと E ノード が移動されます。

この時点で、

Vue3 diff アルゴリズムの学習分析が完了しました。

ここに誰でも使える例を示します。練習のためにこの記事の分析プロセスと組み合わせることができます:

分析のために最初の画像だけを見ることができ、分析が完了した後は分析できます。 、2 番目と 3 番目の写真で分析を実行できます。

写真 1:

##写真 2 および 3:

##概要

上記の学習分析を通じて、Vue3

の

diff アルゴリズムが最初に同じノードを終了することがわかります patch処理後、新しいノードがマウントされ、古いノードがアンインストールされます。 サブシーケンスの状況が故障しているなど、より複雑な場合は、再利用可能なノードが最初に検出され、再利用可能なノードの位置マッピングを通じて最大増加サブシーケンスが構築されます。サブシーケンスを # にインクリメントします。 ##ノードをマウントして移動します。

diff

の効率を向上させ、ノードの再利用の可能性を最大限に高めるため。 [関連する推奨事項: vue.js チュートリアル]

以上がVue3 の差分アルゴリズムの詳細な分析 (詳細なグラフィックとテキストの説明)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。