Diff 算法⽤于计算 Virtual DOM 中真正变化的部分,并只针对该部分进⾏原⽣ DOM 操作,⽽不是渲染整个⻚⾯。从⽽保证了每次操作更新后⻚⾯的⾼效渲染。
传统的递归算法通过循环递归遍历节点进行对比,其复杂度要达到O(n3),大体实现代码如下:
const diffLeafs = function (beforeLeaf, afterLeaf) {
// 获取较⼤节点树的⻓度
let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
// 循环遍历
for (let i = 0; i < count; i++) {
const beforeTag = beforeLeaf.children[i];
const afterTag = afterLeaf.children[i];
if (beforeTag === undefined) {
// 添加 afterTag 节点
res.push({ type: "add", element: afterTag });
} else if (afterTag === undefined) {
// 删除 beforeTag节点
res.push({ type: "remove", element: beforeTag });
} else if (beforeTag.tagName !== afterTag.tagName) {
// 节点名改变时,删除 beforeTag 节点,添加 afterTag 节点
res.push({ type: "remove", element: beforeTag });
res.push({ type: "add", element: afterTag });
} else if (beforeTag.innerHTML !== afterTag.innerHTML) {
if (beforeTag.children.length === 0) {
res.push({
type: "changed",
beforeElement: beforeTag,
afterElement: afterTag,
HTML: afterTag.innerHTML,
});
} else {
// 递归⽐较
diffLeafs(beforeTag, afterTag);
}
}
}
return res;
};
基于以上前提策略,React 分别对 Tree Diff、Component Diff、Element Diff 进⾏算法优化, 保证整体界⾯构建的性能。
Tree Diff 即对树进⾏逐层对⽐的过程,两棵树只会对同层次的节点进⾏⽐较。既然 WebUI 中的 DOM 节点跨层级的移动操作少到可以忽略不计,React 只会对相同颜⾊⽅框内的 DOM 节点进⾏⽐较,即同⼀个⽗节点下的所有⼦节点。当发现节点已经不存在,则该节点及其⼦节点会 被完全删除掉,不会⽤于进⼀步的⽐较。
当 DOM 节点进⾏跨层级操作时,Diff 算法会如何处理?
如下图所示,A 节点(包括其⼦节点)被整个移动到 D 节点下⾯去,由于 React 只会简单的考虑同级节 点的位置变换,⽽对于不同层级的节点,只有创建和删除操作,所以当根节点发现 A 节点消失了,就会 删除 A 节点及其⼦节点,当 D 发现多了⼀个⼦节点 A,就会创建新的 A 作为其⼦节点。此时,Diff 算法的执⾏过程是:create A => create B => create C => delete A
由此可⻅,当出现节点跨层级的移动时,并不会出现想象中移动操作,⽽是会进⾏删除,重新创建的动 作,这是⼀种很影响 React 性能的操作。因此 React 官⽅也不建议进⾏ DOM 节点跨层级的操作。
在开发组件时,保持稳定的 DOM 结构会有助于性能的提升。例如,可以通过 CSS 隐藏或 显示节点,⽽不是真的移除或添加 DOM 节点。
在进⾏ Tree Diff 过程中,每层组件级别的对⽐,叫做 Component Diff。
如果是同类型的组件,有可能经过⼀轮 Virtual DOM ⽐较下来,并没有发⽣变化。如果能够提前确切知道这⼀点,那么就可以省下⼤量的 Diff 运算时间。
因此,React 允许⽤户通过 shouldComponentUpdate 来判断该组件是否需要进⾏ Diff 算法分析。
如下图所示, 当 component D 变为 component G 时,即使这两个 component 结构相似,⼀旦 React 判断 D 和 G 是不同类型的组件,就不会⽐较两者的结构,⽽是直接删除组件 component D,重新创建component G 及其⼦节点。虽然当两个组件是不同类型但结构相似时,进⾏ Diff 算法分析会影 响性能,但是毕竟不同类型的组件存在相似 DOM 树的情况在实际开发过程中很少出现,因此这种极端 情况很难在实际开发过程中造成重⼤影响。
Element Diff 对应三种节点操作,分别为 INSERT_MARKUP (插⼊)
、 MOVE_EXISTING (移动)
和 REMOVE_NODE (删除)
。
如下图,⽼集合中包含节点:A、B、C、D,更新后的新集合中包含节点:B、A、D、C,此时新⽼集合 进⾏ Diff 差异化对⽐,发现 B != A,则创建并插⼊ B ⾄新集合,删除⽼集合 A;以此类推,创建并插⼊ A、D 和 C,删除 B、C 和 D。
针对这种情况,React 提出优化策略:允许开发者对同⼀层级的同组⼦节点,添加唯⼀ key 进⾏区分, 虽然只是⼩⼩的改动,性能上却发⽣了翻天覆地的变化。
新⽼集合所包含的节点,如下图所示,新⽼集合进⾏ diff 差异化对⽐,通过 key 发现新⽼集合中的节点 都是相同的节点,因此⽆需进⾏节点删除和创建,只需要将⽼集合中节点的位置进⾏移动,更新为新集 合中节点的位置,此时 React 给出的 diff 结果为:B、D 不做任何操作,A、C 进⾏移动操作即可。
那么,如此⾼效的 diff 到底是如何运作的呢?先搞清楚 3 个 index 索引:
element diff 逻辑概括
⾸先对新集合的节点进⾏循环遍历, for (name in nextChildren) ,通过唯⼀ key 可以判断新⽼集合中是否存在相同的节点, if (prevChild === nextChild) 。
如果存在相同节点,则进⾏移动操作,但在移动前需要将当前节点在⽼集合中的位置与 lastIndex 进⾏⽐较, if (child._mountIndex < lastIndex) ,则进⾏节点移动操作,否则不执⾏该操作。
这是⼀种顺序优化⼿段,lastIndex ⼀直在更新,表示访问过的节点在⽼集合中最右的位置(即最⼤的位置),如果新集合中当前访问的节点⽐ lastIndex ⼤,说明当前访问节点在⽼集合中就⽐上⼀个节点位 置靠后,则该节点不会影响其他节点的位置,因此不⽤添加到差异队列中,即不执⾏移动操作,只有当 访问的节点⽐ lastIndex ⼩时,才需要进⾏移动操作。
element diff 差异对⽐过程
以上主要分析新⽼集合中存在相同节点但位置不同时,对节点进⾏位置移动的情况,其他情况如:新集合中有新加⼊的节点且⽼集合存在需要删除的节点类似。
当然,React Diff 还是存在些许不⾜与待优化的地⽅,如下图所示,若新集合的节点更新为:D、A、 B、C,与⽼集合对⽐只有 D 节点移动,⽽ A、B、C 仍然保持原有的顺序,理论上 Diff 应该只需对 D 执 ⾏移动操作,然⽽由于 D 在⽼集合的位置是最⼤的,导致其他节点的 _mountIndex < lastIndex,造成 D 没有执⾏移动操作,⽽是 A、B、C 全部移动到 D 节点后⾯的现象。
在开发过程中,尽量减少类似将最后⼀个节点移动到列表⾸部的操作,当节点数量过⼤或更新操作过于频繁时,在⼀定程度上会影响 React 的渲染性能。
function _updateChildren(nextNestedChildrenElements, transaction, context) {
var prevChildren = this._renderedChildren;
var removedNodes = {};
var mountImages = [];
// 获取新的⼦元素数组
var nextChildren = this._reconcilerUpdateChildren(
prevChildren,
nextNestedChildrenElements,
mountImages,
removedNodes,
transaction,
context
);
if (!nextChildren && !prevChildren) {
return;
}
var updates = null;
var name;
var nextIndex = 0;
var lastIndex = 0;
var nextMountIndex = 0;
var lastPlacedNode = null;
for (name in nextChildren) {
if (!nextChildren.hasOwnProperty(name)) {
continue;
}
var prevChild = prevChildren && prevChildren[name];
var nextChild = nextChildren[name];
if (prevChild === nextChild) {
// 同⼀个引⽤,说明是使⽤的同⼀个component,所以我们需要做移动的操作
// 移动已有的⼦节点
// NOTICE:这⾥根据nextIndex, lastIndex决定是否移动
updates = enqueue(
updates,
this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
);
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex);
// 更新component的.mountIndex属性
prevChild._mountIndex = nextIndex;
} else {
if (prevChild) {
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex);
}
// 添加新的⼦节点在指定的位置上
updates = enqueue(
updates,
this._mountChildAtIndex(
nextChild,
mountImages[nextMountIndex],
lastPlacedNode,
nextIndex,
transaction,
context
)
);
nextMountIndex++;
}
nextIndex++;
lastPlacedNode = ReactReconciler.getHostNode(nextChild);
}
// 移除掉不存在的旧⼦节点,和旧⼦节点和新⼦节点不同的旧⼦节点
for (name in removedNodes) {
if (removedNodes.hasOwnProperty(name)) {
updates = enqueue(
updates,
this._unmountChild(prevChildren[name], removedNodes[name])
);
}
}
}
Diff 算法的⼤致流程: