深入diff 算法
2021-03-31 12:28
标签：描述 css dirty 树形结构 ace rup 方法 opera elements diff 作为 Virtual DOM 的加速器，其算法上的改进优化是React页面渲染的基础和性能保障，本节从源码入手，深入剖析diff算法。 React 中醉值得称道的莫过于Virtual DOM与diff的完美结合，尤其是其高效的diff算法，可以帮助我们在页面蔌渲染的时候，计算出Virtual DOM真正变化的部分，并只针对该部分进行的原生DOM操作，而不是渲染整个页面，从而保证了每次操作后，页面的高效渲染。 计算一个树形结构转换成另一个树形结构的最少操作，是一个复杂且值得研究的问题，传统 diff 算法通过循环递归的方法对节点进行操作，算法复杂度 为O(n3)，其中n为树中节点的总数，这效率太低了，如果 React 只是单纯的引入 diff 算法，而没有任何的优化的话，其效率远远无法满足前端渲染所需要的性能。那么React 是如何实现一个高效、稳定的 diff 算法。 React 将 Virtual DOM 树转换为 actual DOM 树的最小操作的过程称为调和， diff 算法便是调和的结果，React 通过制定大胆的策略，将 O(n3)的时间复杂度转换成 O(n)。 下面是 React diff 算法的 3 个策略： 基于以上三个策略，React 分别对 tree diff、component diff 以及 element diff 进行算法优化。 对于策略一，React 对树的算法进行了简介明了的优化，即对树进行分层比较，两颗树只会对同一层级的节点进行比较。 既然 DOM 节点跨层级的移动，可以少到忽略不计，针对这种现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只对相同层级的DOM节点进行比较，即同一父节点下的所有子节点，当发现该节点已经不存在时，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个DOM树的比较。 那么就会有这样的问题： 如果出现了 DOM 节点跨层级的移动操作，diff 会有怎样的表现喃？ 我们举个例子看一下： 如下图2-1，A节点（包括其子节点）整个需要跨层级移动到D节点下，React会如何操作喃？ 由于 React 只会简单的考虑同层级节点的位置变换，对于不同层级的节点，只有创建和删除操作。当根节点R发现子节点中A消失了，就会直接销毁A；当D节点发现多了一个子节点A，就会创建新的A子节点（包括其子节点）。执行的操作为： create A —> create B —> create C —> delete A 所以。当出现节点跨级移动时，并不会像想象中的那样执行移动操作，而是以 A 为根节点的整个树被整个重新创建，这是影响 React 性能的操作，所以 官方建议不要进行 DOM 节点跨层级的操作。 在开发组件中，保持稳定的 DOM 结构有助于性能的提升。例如，可以通过CSS隐藏或显示节点，而不是真正的移除或添加 DOM 节点。 React 是基于组件构建应用的，对于组件间的比较所采取的策略也是非常简洁、高效的。 如上图3-1，当 D 组件变成 G 时，即使这两个组件结构相似，但一旦 React 判断D和G是两个不同类型的组件时，就不会再比较这两个组件的结构，直接进行删除组件D， 重新创建组件G及其子组件。虽然这两个组件是不同类型单结构类似，diff 算法会影响性能，正如 React 官方博客所言： 不同类型的组件很少存在相似 DOM 树的情况，因此，这种极端因素很难在实际开发过程中造成重大影响。 当节点处于同一层级时，diff 提供三种节点操作： 下面由三个例子加深我们的理解 例1：旧集合A、B、C、D四个节点，更新后的新集合为B、A、D、C节点，对新旧集合进行 diff 算法差异化对比，发现 B!=A，则创建并插入B节点到新集合，并删除旧集合中A，以此类推，创建A、D、C，删除 B、C、D。如下图4-1 React发现这样操作非常繁琐冗余，因为这些集合里含有相同的节点，只是节点位置发生了变化而已，却发生了繁琐的删除、创建操作，实际上只需要对这些节点进行简单的位置移动即可。 针对这一现象，React 提出了优化策略： 允许开发者对同一层级的同组子节点，添加唯一key进行区分，虽然只是小小的改动，但性能上却发生了翻天覆地的变化。 例2：看下图 进行对新旧集合的 diff 差异化对比，通过 key 发现新旧集合中包含的节点是一样的，所以可以通过简单的位置移动就可以更新为新集合，React 给出的 diff 结果为：B、D不做任何操作，A、C移动即可。 步骤： 初始化，lastIndex = 0， nextIndex = 0 从新集合取出节点B，发现旧集合中也有节点B，并且B.__mountIndex = 1，lastIndex = 0，不满足 B._mountIndex
从新集合取出节点A，发现旧集合中也有节点A，并且A.__mountIndex = 0，lastIndex = 1，满足 A._mountIndex
依次进行操作，可以根据下面代码执行的步骤实现，这里不再赘述 操作为：深入diff 算法
一. 传统的 diff 算法
二. diff 源码解读
1. diff 策略
2. tree diff
// updateChildren 源码
updateChildren: function (nextNestedChildrenElements, transaction, context) {
updateDepth ++;
var errorThrown = true;
try {
this._updateChildren(nextNestedChildrenElements, transaction, context);
errorThrown = false;
} finally {
updateDepth --;
if (!updateDepth) {
if (errorThrown) {
clearQueue();
} else {
processQueue();
}
}
}
}
图2-1 DOM层级变换
3. component diff
shouldComponentUpdate()来判断该组件是否需要大量 diff 算法分析。
图3-1 component diff4. element diff
// INSERT_MARKUP
function makeInsertMarkup(markup, afterNode, toIndex) {
return {
type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
content: markup,
fromIndex: null,
fromNode: null,
toIndex: toIndex,
afterNode: afterNode
}
}
// MOVE_EXISTING
function makeMove(child, afterNode, toIndex) {
return {
type: ReactMultiChildUpdateTypes.MOVE_EXISTING,
content: null,
fromIndex: child._mountIndex,
fromNode: ReactReconciler.getNativeNode(child),
toIndex: toIndex,
afterNode: afterNode
}
}
// REMOVE_NODE
function makeRemove(child, node) {
return {
type: ReactMultiChildUpdateTypes.REMOVE_NODE,
content: null,
fromIndex: child._mountIndex,
fromNode: node,
toIndex: null,
afterNode: null
}
}
图4-1 节点 diff
图4-2 对节点进行 diff 差异化对比
updateChildren1: function(prevChildren, nextChildren) { // 旧集合 新集合
var updates = null
var name
// lastIndex 是 prevChildren 中最后一个索引，nextIndex 是 nextChildren 中每个节点的索引
var lastIndex = 0
var nextIndex = 0
for (name in nextChildren) { // 对新集合的节点进行循环遍历
if (!nextChildren.hasOwnProperty(name)) {
continue
}
var prevChild = prevChildren && prevChildren[name]
var nextChild = nextChildren[name]
// 通过唯一的key判断新旧集合是否有相同的节点
if (prevChild === nextChild) { // 新旧集合有相同的节点
// 如果子节点的 index 小于 lastIndex 则移动该节点
if (prevChild._mountIndex ) {
// 获取移动节点
let moveNode = makeMove(prevChild, lastPlacedNode, nextIndex)
// 存入差异队列
updates = enqueue(
updates,
moveNode
)
} // 这是一种顺序优化手段，lastIndex 一直在更新表示访问过的节点一直在prevChildren最大的位置，如果当前访问的节点比 lastIndex 大，说明当前访问的节点在旧结合中就比上一个节点靠后，则该节点不会影响其它节点的位置，因此不插入差异队列，不要执行移动操作，只有访问的节点比 lastIndex 小时，才需要进行移动操作。
// 更新lastIndex
lastIndex= Math.max(prevChild._mountIndex, lastIndex)
// 将prevChild的位置更新为在新集合中的位置
prevChild._mountIndex = nextIndex
} else {
if (prevChild) {// 如果没有相同节点且prevChild存在
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex)
}
}
// 进入下一个节点的判断
nextIndex ++
}
// 如果存在更新，则处理更新队列
if (updates) {
processQueue(this, updates)
}
// 更新 DOM
this._renderedChildren = nextChildren
}
function enqueue(queue, update) {
// 如果有更新，将其存入 queue
if (update) {
queue = queue || []
queue.push(update)
}
return queue
}
// 处理队列的更新
function processQueue (inst, updateQueue) {
ReactComponentEnvironment.processChildrenUpdates(
inst,
updateQueue
)
}
例3：看下图
图4-3 创建、移动、删除节点
可以看出在这个例子中，有新增的节点，还有需要删除的节点，具体怎么操作，请大胆的尝试一下吧
5. 源码
_updateChildren: function(nextNestedChildrenElements, transaction, context) {
var prevChildren = this._renderedChildren // 旧集合
var removedNodes = {} // 需要删除的节点集合
var nextChildren = this._reconcilerUpdateChildren(prevChildren, nextNestedChildrenElements, removedNodes, transaction, context) // 新集合
// 如果不存在 prevChildren 及 nextChildren，则不做 diff 处理
if (!prevChildren && !nextChildren) {
return
}
var updates = null
var name
// lastIndex 是 prevChildren 中最后一个索引，nextIndex 是 nextChildren 中每个节点的索引
var lastIndex = 0
var nextIndex = 0
var lastPlacedNode = null
for (name in nextChildren) { // 对新集合的节点进行循环遍历
if (!nextChildren.hasOwnProperty(name)) {
continue
}
var prevChild = prevChildren && prevChildren[name]
var nextChild = nextChildren[name]
// 通过唯一的key判断新旧集合是否有相同的节点
if (prevChild === nextChild) { // 新旧集合有相同的节点
// 如果子节点的 index 小于 lastIndex 则移动该节点，并加入差异队列
updates = enqueue(
updates,
this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
)// 这是一种顺序优化手段，lastIndex 一直在更新表示访问过的节点一直在prevChildren最大的位置，如果当前访问的节点比 lastIndex 大，说明当前访问的节点在旧结合中就比上一个节点靠后，则该节点不会影响其它节点的位置，因此不插入差异队列，不要执行移动操作，只有访问的节点比 lastIndex 小时，才需要进行移动操作。
// 更新lastIndex
lastIndex= Math.max(prevChild._mountIndex, lastIndex)
// 将prevChild的位置更新为在新集合中的位置
prevChild._mountIndex = nextIndex
} else {
if (prevChild) {// 如果没有相同节点且prevChild存在
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex)
// 通过遍历 removedNodes 删除子节点 prevChild
}
// 初始化并创建节点
updates = enqueue(
updates,
this._mountChildAtIndex(nextChild, lastPlacedNode, nextIndex, transaction, context)
)
}
// 进入下一个节点的判断
nextIndex ++
lastPlacedNode = ReactReconciler.getNativeNode(nextChild)
}
// 如果父节点不存在，则将其子节点全部移除
for (name in removedNodes) {
if (removedNodes.hasOwnProperty(name)) {
updates = enqueue(
updates,
this._unmountChild(prevChildren[name], removedNodes[name])
)
}
}
// 如果存在更新，则处理更新队列
if (updates) {
processQueue(this, updates)
}
this._renderedChildren = nextChildren
}
function enqueue(queue, update) {
// 如果有更新，将其存入 queue
if (update) {
queue = queue || []
queue.push(update)
}
return queue
}
// 处理队列的更新
function processQueue (inst, updateQueue) {
ReactComponentEnvironment.processChildrenUpdates(
inst,
updateQueue
)
}
// 移动节点
moveChild: function(child, afterNode, toIndex, lastIndex) {
// 如果子节点的 index 小于 lastIndex 则移动该节点
if (child._mountIndex