Vue Diff Algorithm #10

sufuwang · 2023-03-03T06:05:55Z

概述

Vue Diff 算法的迭代历程：简单 Diff 算法 => 双端 Diff 算法 => 快速 Diff 算法

简单 Diff 算法思路简单，但它的 VDom 移位策略性能较差，双端 Diff 算法和快速 Diff 算法是通过修改 VDom 的对比策略来追求极致性能，双端 Diff 算法使用平行和交叉对比的方式来进行移位的判断，所以需要大量的对比，不是较好的解决办法，快速 Diff 算法借助最长递增子序列，仅需少量对比即可得知需要移位的 VDom 。在此基础上，快速 Diff 算法借鉴文本 Diff 算法对 VDom 进行预处理，以减少 VDom 的对比范围

sufuwang · 2023-03-03T07:21:51Z

简单 Diff 算法

使用 Key 来修改可以复用的 DOM 节点

根据 Key 值，判断哪些节点需要移位：缓存一个新节点在旧节点集合中的最大索引 maxIndex ，新 VDom 索引小于这个最大索引 maxIndex 时，表明当前节点需要被移位

const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]


// 遍历 newVDoms ，使用 Key 值判断索引
// 1. newVDoms[0] 在 oldVDoms 的索引是 2 , 则当前最大索引是 2
// 2. newVDoms[1] 在 oldVDoms 的索引是 0 , 当前索引 < 最大索引, 所以 newVDoms[1] 需要移动
// 3. newVDoms[2] 在 oldVDoms 的索引是 1 , 当前索引 < 最大索引, 所以 newVDoms[2] 需要移动

以最大索引 maxIndex 所处的 DOM 元素为起点，按照 newVDoms 的顺序修改 DOM 元素位置
若 newVDoms 中有节点不存在于 oldVDoms ，表现为 Key 不存在，按照 newVDoms 的顺序挂载新 DOM 节点
若 oldVDoms 中有节点不存在于 newVDoms，表现为 Key 不存在，则根据 Key 删除对应 DOM 节点

sufuwang · 2023-03-03T07:30:42Z

简单 Diff 算法的弊端

简单 Diff 算法在判断哪些节点需要移位时，存在性能问题

const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]

// 简单 Diff 算法需要移动 Key 为 0 和 1 的两个 DOM 节点
// 最优的移位策略应该是移动 Key 为 2 的 DOM 节点即可

双端 Diff 算法的优点

在相同场景下，双端 Diff 算法所需要的 DOM 移动次数 <= 简单 Diff 算法所需要的 DOM 移动次数

sufuwang · 2023-03-03T10:19:03Z

双端 Diff 算法

双端 Diff 算法在一次对比中，对 2 个新 VDom 和 2 个旧 VDom 分别进行横向和交叉对比

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

// 1. 第一次对比: newStartIndex = 0, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 2
//    a. newVDoms[0] & oldVDoms[0]
//    b. newVDoms[2] & oldVDoms[2]
//    c. newVDoms[2] & oldVDoms[0]
//    d. newVDoms[0] & oldVDoms[2]
//    第 a,b,c 种情况，VDom 的 Key 不同，表示不可以复用，则不做任何操作
//    第 d 种情况下两个 VDom 的 Key 相同，表示可以复用，则更新节点，因为 d 属于交叉对比，则需要移位
//    所有操作结束后，更新所有索引。因为刚才操作的是 newStartIndex & oldEndIndex 位置上的索引
//    所以对 newStartIndex 加 1，对 oldEndIndex 减 1，故 newStartIndex = 1, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 1

// 2. 第二次对比: newStartIndex = 1, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 1
//    a. newVDoms[1] & oldVDoms[0]
//    b. newVDoms[2] & oldVDoms[1]
//    c. newVDoms[1] & oldVDoms[1]
//    d. newVDoms[2] & oldVDoms[0]
//    第 c,d 种情况，VDom 的 Key 不同，表示不可以复用，则不做任何操作
//    第 a,b 种情况下两个 VDom 的 Key 相同，表示可以复用，则更新节点即可
//    所有操作结束后，更新索引。因为刚才操作的是 newStartIndex & newEndIndex & oldStartIndex & oldEndIndex 位置上的索引
//    所以对 newStartIndex & oldStartIndex 加 1，对 newEndIndex & oldEndIndex 减 1，故 newStartIndex = 2, newEndIndex = 1, oldStartIndex = 1, oldEndIndex = 0

//    因为 newEndIndex > newStartIndex & oldStartIndex > oldEndIndex，所以结束循环

极端情况下的双端 Diff 算法

每次对比时，不是一定会出现可复用的 VDom，需要一些额外的操作，来打破这种窘境

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
]

// 1. 第一次对比: newStartIndex = 0, newEndIndex = 3, oldStartIndex = 0, oldEndIndex = 3
//    a. newVDoms[0] & oldVDoms[0]
//    b. newVDoms[3] & oldVDoms[3]
//    c. newVDoms[3] & oldVDoms[0]
//    d. newVDoms[0] & oldVDoms[3]
//    会发现这四种对比，发现可以复用的 VDom

// 2. 额外的操作: 遍历 oldVDoms，找到可以复用的 VDom（索引为 tarIndex），更新对应元素后，把 oldVDom[tarIndex] 置为 undefined，然后 newStartIndex 加 1

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'o-3' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  undefined,
  { key: 3, type: 'p', children: 'o-3' },  // oldEndIndex
]
// 3. 第二次对比: newStartIndex = 1, newEndIndex = 3, oldStartIndex = 0, oldEndIndex = 3

新增 VDom

// 第一次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第二次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },  // oldEndIndex
  { key: 2, type: 'p', children: 'o-2' },
]

// 第三次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },  // newEndIndex
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex oldEndIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

// 第四次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex newEndIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [			   // oldEndIndex
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]
// oldVDoms 已经遍历完毕，所以索引 newStartIndex 对应的元素应该被新增

删除 VDom

// 第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newStartIndex newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第三次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]                                          // newStartIndex
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldStartIndex oldEndIndex
]
// newVDoms 已经遍历完毕，所以索引 oldStartIndex 对应的元素应该被删除

sufuwang · 2023-03-04T07:51:51Z

快速 Diff 算法

前置 VDom 和后置 VDom

这是快速 Diff 算法的预处理阶段，借鉴文本 Diff 算法，对 VDoms 的前缀元素和后缀元素进行 DOM 更新，这个过程中不会涉及 DOM 移位

// 前置 VDom 的对比: 从第一个 VDom 向前遍历
// 前置 VDom 的第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 2, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
]

// 前置 VDom 的第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
]
// 此时 newVDoms[newStartIndex].key !== oldVDoms[oldStartIndex].key
// 所以停止遍历

// 后置 VDom 的对比: 从最后一个 VDom 向前遍历
// 后置 VDom 的第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldEndIndex
]

// 后置 VDom 的第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },  // newEndIndex
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldEndIndex
  { key: 1, type: 'p', children: 'o-1' },
]
// 此时 newVDoms[newEndIndex].key !== oldVDoms[oldEndIndex].key
// 所以停止遍历

新增和删除 VDom

前面的代码示例中，最后的索引对比结果是 oldEndIndex 小于 oldStartIndex 表明不需要删除 DOM 节点，
newStartIndex 小于 newEndIndex 表明需要新增 DOM 节点。索引对比情况反之，则需要删除 DOM 节点

VDom 移位

快速 Diff 算法借助 newVDoms 索引表和最长递增子序列完成移位判断

const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 3, type: 'p', children: 'n-1' },
  { key: 4, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
  { key: 7, type: 'p', children: 'n-4' },
  { key: 5, type: 'p', children: 'n-5' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 4, type: 'p', children: 'o-4' },
  { key: 5, type: 'p', children: 'o-5' },  // oldEndIndex
]

// 1. 判断前置 VDom 和 后置 VDom
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 4, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
  { key: 7, type: 'p', children: 'n-4' },  // newEndIndex
  { key: 5, type: 'p', children: 'n-5' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 4, type: 'p', children: 'o-4' },  // oldEndIndex
  { key: 5, type: 'p', children: 'o-5' },
]

// 后面的逻辑，不包括已经更新的前缀 VDom 和后缀 VDom

// 2. 建立 newVDoms 的索引表: { [newVDom.key]: newVDoms.indexof(VDom) }
//    => { 3:0, 4:1, 2:2, 7:3 }

// 3. 建立 source 数组: [ oldVDoms.indexof(newVDom.key) ]
//    => [2, 3, 1, -1]

// 4. 根据 source 数组，计算最长递增子序列
//    [2, 3, 1, -1] => [2, 3] => [0, 1]

// 5. 遍历最长递增子序列与 oldVDoms.slice(oldStartIndex, oldEndIndex + 1)
//    所以索引为 oldStartIndex 和 oldStartIndex + 1 的两个 oldVDom 不用进行移位
//    又因为 source 数组的最后一项是 -1，即 oldVDoms 中不存在此 newVDom
//    故索引为 oldStartIndex + 2 的 oldVDom 需要进行移位
//    故索引为 newStartIndex + 3 的 newVDom 需要进行新增

sufuwang self-assigned this Mar 3, 2023

sufuwang added Protocol Algorithm and removed Protocol labels Mar 3, 2023

sufuwang added Vue and removed Algorithm labels Mar 4, 2023

sufuwang mentioned this issue Mar 5, 2023

React Diff Algorithm #12

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Vue Diff Algorithm #10

Vue Diff Algorithm #10

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 4, 2023 •

edited

Loading

Vue Diff Algorithm #10

Vue Diff Algorithm #10

Comments

sufuwang commented Mar 3, 2023 • edited Loading

概述

sufuwang commented Mar 3, 2023 • edited Loading

简单 Diff 算法

sufuwang commented Mar 3, 2023 • edited Loading

简单 Diff 算法的弊端

双端 Diff 算法的优点

sufuwang commented Mar 3, 2023 • edited Loading

双端 Diff 算法

极端情况下的双端 Diff 算法

新增 VDom

删除 VDom

sufuwang commented Mar 4, 2023 • edited Loading

快速 Diff 算法

前置 VDom 和后置 VDom

新增和删除 VDom

VDom 移位

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 3, 2023 •

edited

Loading

sufuwang commented Mar 4, 2023 •

edited

Loading