提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

React 15 Diff 算法详解

2023-02-18 16:47:29 时间

Diff 算法⽤于计算 Virtual DOM 中真正变化的部分，并只针对该部分进⾏原⽣ DOM 操作，⽽不是渲染整个⻚⾯。从⽽保证了每次操作更新后⻚⾯的⾼效渲染。

1.传统的 Diff 算法

传统的递归算法通过循环递归遍历节点进行对比，其复杂度要达到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;
};

2. diff 算法策略

  • 拥有相同类的两个组件将会⽣成相似的树形结构，拥有不同类的两个组件将会⽣成不同的树形结构。
  • 对于同⼀层级的⼀组⼦节点，它们可以通过 UUID（key）进⾏区分。

基于以上前提策略，React 分别对 Tree Diff、Component Diff、Element Diff 进⾏算法优化， 保证整体界⾯构建的性能。

3. 算法过程

3.1 Tree 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 节点。

3.2 Component Diff

在进⾏ Tree Diff 过程中，每层组件级别的对⽐，叫做 Component Diff。

  • 如果对⽐前后，组件的类型相同，则按照原策略继续进⾏ Virtual DOM ⽐较
  • 如果对⽐前后，组件的类型不相同，则需要移除旧组件，创建新组件，并追加到⻚⾯上

如果是同类型的组件，有可能经过⼀轮 Virtual DOM ⽐较下来，并没有发⽣变化。如果能够提前确切知道这⼀点，那么就可以省下⼤量的 Diff 运算时间。

因此，React 允许⽤户通过 shouldComponentUpdate 来判断该组件是否需要进⾏ Diff 算法分析。

如下图所示， 当 component D 变为 component G 时，即使这两个 component 结构相似，⼀旦 React 判断 D 和 G 是不同类型的组件，就不会⽐较两者的结构，⽽是直接删除组件 component D，重新创建component G 及其⼦节点。虽然当两个组件是不同类型但结构相似时，进⾏ Diff 算法分析会影 响性能，但是毕竟不同类型的组件存在相似 DOM 树的情况在实际开发过程中很少出现，因此这种极端 情况很难在实际开发过程中造成重⼤影响。

3.3 Element Diff

Element Diff 对应三种节点操作，分别为 INSERT_MARKUP （插⼊）、 MOVE_EXISTING （移动） 和 REMOVE_NODE （删除）。

  • INSERT_MARKUP ：新的组件类型不在旧集合中，即全新的节点，需要对新节点进⾏插⼊操作。
  • MOVE_EXISTING：旧集合中有新组件类型，且 element 是可更新的类型，这种情况下 prevChild = nextChild ，这时候就需要做移动操作，可以复⽤以前的 DOM 节点。
  • REMOVE_NODE ：旧组件类型，在新集合⾥也有，但对应的 element 不同则不能直接复⽤和更 新，需要执⾏删除操作，或者旧组件不在新集合⾥的，也需要执⾏删除操作。

如下图，⽼集合中包含节点：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 索引：

  • nextId：遍历 nextChildren 时候的 index，每遍历⼀个元素加 1 ;
  • lastIndex：默认为 0，表示上次从 prevChildren 中取出元素时，这个元素在 prevChildren 中的 index
  • _mountIndex：元素在数组中的位置

element diff 逻辑概括

⾸先对新集合的节点进⾏循环遍历， for (name in nextChildren) ，通过唯⼀ key 可以判断新⽼集合中是否存在相同的节点， if (prevChild === nextChild) 。

如果存在相同节点，则进⾏移动操作，但在移动前需要将当前节点在⽼集合中的位置与 lastIndex 进⾏⽐较， if (child._mountIndex < lastIndex) ，则进⾏节点移动操作，否则不执⾏该操作。

这是⼀种顺序优化⼿段，lastIndex ⼀直在更新，表示访问过的节点在⽼集合中最右的位置（即最⼤的位置），如果新集合中当前访问的节点⽐ lastIndex ⼤，说明当前访问节点在⽼集合中就⽐上⼀个节点位 置靠后，则该节点不会影响其他节点的位置，因此不⽤添加到差异队列中，即不执⾏移动操作，只有当 访问的节点⽐ lastIndex ⼩时，才需要进⾏移动操作。

element diff 差异对⽐过程

  • 从新集合中取得 B，判断⽼集合中存在相同节点 B，通过对⽐节点位置判断是否进⾏移动操作。 判断过程：B 在⽼集合中的位置 B._mountIndex = 1 ，此时 lastIndex = 0 (⾸次遍历时 默认为 0)，不满⾜ child._mountIndex < lastIndex 的条件，因此不对 B 进⾏移动操作 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) ，其中 prevChild._mountIndex 表示 B 在⽼集合中的位置，则 lastIndex ＝ 1 ，并将 B 的位置 更新为新集合中的位置 prevChild._mountIndex = nextIndex ，此时新集合中 B._mountIndex = 0 ， nextIndex++ 进⼊下⼀个节点的判断。
  • 从新集合中取得 A，判断⽼集合中存在相同节点 A，通过对⽐节点位置判断是否进⾏移动操作 判断过程：A 在⽼集合中的位置 A._mountIndex = 0 ，此时 lastIndex = 1 ，满⾜ child._mountIndex < lastIndex 的条件，因此对 A 进⾏移动操作 enqueueMove(this, child._mountIndex, toIndex) ，其中 toIndex 其实就是 nextIndex ，表示 A 需要移动 到的位置 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) ，则 lastIndex ＝ 1 ，并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex ，此时新集合中 A._mountIndex = 1 ， nextIndex++ 进⼊下⼀个节点的判 断。
  • 从新集合中取得 D，判断⽼集合中存在相同节点 D，通过对⽐节点位置判断是否进⾏移动操作 判断过程：D 在⽼集合中的位置 D._mountIndex = 3 ，此时 lastIndex = 1 ，不满⾜ child._mountIndex < lastIndex 的条件，因此不对 D 进⾏移动操作 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) ，则 lastIndex ＝ 3 ，并将 D 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex ，此时新集合中 D._mountIndex = 2 ， nextIndex++ 进⼊下⼀个节点的判 断。
  • 从新集合中取得 C，判断⽼集合中存在相同节点 C，通过对⽐节点位置判断是否进⾏移动操作 判断过程：C 在⽼集合中的位置 C._mountIndex = 2 ，此时 lastIndex = 3 ，满⾜ child._mountIndex < lastIndex 的条件，因此对 C 进⾏移动操作 enqueueMove(this, child._mountIndex, toIndex) 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) ，则 lastIndex ＝ 3 ，并将 C 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex ，此时新集合中 C._mountIndex = 3 ， nextIndex++ 进⼊下⼀个节点的判 断，由于 C 已经是最后⼀个节点，因此 diff 到此完成。

以上主要分析新⽼集合中存在相同节点但位置不同时，对节点进⾏位置移动的情况，其他情况如：新集合中有新加⼊的节点且⽼集合存在需要删除的节点类似。

当然，React Diff 还是存在些许不⾜与待优化的地⽅，如下图所示，若新集合的节点更新为：D、A、 B、C，与⽼集合对⽐只有 D 节点移动，⽽ A、B、C 仍然保持原有的顺序，理论上 Diff 应该只需对 D 执 ⾏移动操作，然⽽由于 D 在⽼集合的位置是最⼤的，导致其他节点的 _mountIndex < lastIndex，造成 D 没有执⾏移动操作，⽽是 A、B、C 全部移动到 D 节点后⾯的现象。

在开发过程中，尽量减少类似将最后⼀个节点移动到列表⾸部的操作，当节点数量过⼤或更新操作过于频繁时，在⼀定程度上会影响 React 的渲染性能。

4. 算法源码

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])
      );
    }
  }
}

5.总结

Diff 算法的⼤致流程：

  1. 有⼀个全局变量 updateDepth 来标识递归的深度，进⾏ Diff 算法之前 +1，Diff 算法结束之后 -1。当其重新变为 0 的时候表示整个 Diff 算法结束了，可以拿更新队列 diffQueue 来更新 DOM 了
  2. Diff 算法只对同个⽗元素的同级⼦元素进⾏对⽐。如果元素的 type 和 key（如果有的话）相同，视 为同⼀个元素，进⾏更新；否则替换掉。
  3. Diff 使⽤了⼀个局部变量：lastIndex ——记录已经处理的就列表中最靠后的元素。当元素的 ._mountIndex ⼤于 lastIndex 的时候，不需要移动元素。因为移动元素不会对前⾯对元素产⽣任何影响，因此可以省略这个动作，由于很多时候⼤部分元素处于这种情况下，因此这个局部变量 提升了性能（有时候很明显）。需要注意的是如果把列表中最后⼀个元素移到最前⾯，那么 boolean shouldComponentUpdate(object nextProps, object nextState) lastIndex 就会⼤于后⾯对⽐的所有元素，导致的后果就是列表中所有元素都将被移动。

相关文章