Diff算法

发布于 2024-03-12  137 次阅读

概览

在render阶段，对于update的组件，他会将当前组件与该组件在上次更新时对应的Fiber节点比较（也就是俗称的Diff算法），将比较的结果生成新Fiber节点。

官网对diff算法的介绍：https://zh-hans.reactjs.org/docs/reconciliation.html#the-diffing-algorithm

  1. 不同类型的元素：React拆卸原有的树，生成新的树
    1. 卸载时：
      1. DOM节点销毁；
      2. 执行componentWilUnmount()；
    2. 新建时：
      1. 执行UNSAFE_componentWillMount()，然后执行componentDidMount()；
  2. 同一类型的元素：
    1. 保留DOM节点，仅对比更新有改变的属性
    2. 对比同类型的组件元素：
      1. 组件更新时，组件实例保持不变，保证state不变，更新组件的props以保证与新的元素一致，调用UNSAFE_componentWillReceiveProps()、UNSAFE_componentWillUpdate() 以及 componentDidUpdate() 方法；
      2. 调用render，执行diff
        1. React 同时遍历两个子元素的列表；当产生差异时，生成一个 mutation

在子元素列表结尾新增

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li> // 只需要新增元素即可
</ul>

在子元素列表头部新增

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

// 销毁子元素列表，新建新的子元素列表，有性能问题
<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

使用keys：直接比较key值定位，所以key传index也会有性能问题

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

官网总结：

  1. 该算法不会尝试匹配不同组件类型的子树。如果你发现你在两种不同类型的组件中切换，但输出非常相似的内容，建议把它们改成同一类型。在实践中，我们没有遇到这类问题；
  2. Key 应该具有稳定，可预测，以及列表内唯一的特质。不稳定的 key（比如通过 Math.random() 生成的）会导致许多组件实例和 DOM 节点被不必要地重新创建，这可能导致性能下降和子组件中的状态丢失；

结合render和commit阶段，一个DOM节点最多有4个节点与之相关：

  1. current Fiber。如果该DOM节点已在页面中，current Fiber代表该DOM节点对应的Fiber节点；
  2. workInProgress Fiber。如果该DOM节点将在本次更新中渲染到页面中，workInProgress Fiber代表该DOM节点对应的Fiber节点；
  3. DOM节点本身；
  4. JSX对象。即ClassComponent的render方法的返回结果，或FunctionComponent的调用结果。JSX对象中包含描述DOM节点的信息；

diff算法：对比1 4 生成2

Diff的瓶颈及处理方法

diff操作本身也会带来性能损耗，React文档中提到，即使在最前沿的算法中，将前后两棵树完全比对的算法的复杂程度为 O(n^3)，其中n是树中元素的数量；如果在React中使用了该算法，那么展示1000个元素所需要执行的计算量将在十亿的量级范围。这个开销实在是太过高昂；

为了降低算法复杂度，React的diff会预设三个限制：

  1. 只对同级元素进行diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React会忽略；
  2. 两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点；
  3. 开发者可以通过 key prop来暗示哪些子元素在不同的渲染下能保持稳定；

Diff是如何实现的

Diff的入口函数是reconcileChildFibers：会根据newChild（即JSX对象）类型调用不同的处理函数

地址：https://github.com/facebook/react/blob/1fb18e22ae66fdb1dc127347e169e73948778e5a/packages/react-reconciler/src/ReactChildFiber.new.js#L1280

// 根据newChild类型选择不同diff函数处理
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
): Fiber | null {

  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) {
    // object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        // 调用 reconcileSingleElement 处理
      // // ...省略其他case
    }
  }

  if (typeof newChild === 'string' || typeof newChild === 'number') {
    // 调用 reconcileSingleTextNode 处理
    // ...省略
  }

  if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
    // ...省略
  }

  // 一些其他情况调用处理函数
  // ...省略

  // 以上都没有命中，删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

根据同级的节点数量将Diff分为两类：

  1. 当newChild类型为object、number、string，代表同级只有一个节点
  2. 当newChild类型为Array，同级有多个节点

单节点Diff

以类型为object为例，执行reconcileSingleElement

  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) {
    // 对象类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        // 调用 reconcileSingleElement 处理
      // ...其他case
    }
  }

地址：https://github.com/facebook/react/blob/1fb18e22ae66fdb1dc127347e169e73948778e5a/packages/react-reconciler/src/ReactChildFiber.new.js#L1141

执行流程：

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  
  // 首先判断是否存在对应DOM节点
  while (child !== null) {
    // 上一次更新存在DOM节点，接下来判断是否可复用

    // 首先比较key是否相同
    if (child.key === key) {

      // key相同，接下来比较type是否相同

      switch (child.tag) {
        // ...省略case
        
        default: {
          if (child.elementType === element.type) {
            // type相同则表示可以复用
            // 返回复用的fiber
            return existing;
          }
          
          // type不同则跳出switch
          break;
        }
      }
      // 代码执行到这里代表：key相同但是type不同
      // 将该fiber及其兄弟fiber标记为删除
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key不同，将该fiber标记为删除
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 创建新Fiber，并返回 ...省略
}
  1. 先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用；
  2. 删除逻辑：
    1. 当child !== null且key相同且type不同时执行deleteRemainingChildren将child及其兄弟fiber都标记删除；
    2. 当child !== null且key不同时仅将child标记删除；
// current fiber
ul > li li li
// JSX
ul > p

需要根据第一个li与p是否相同判断

  1. key相同type不同，当前fiber和后续sibling fiber删除；
  2. key不同，type也不同，删除当前fiber，前往下一个sibling fiber；

Example：

// 更新前
<div>a</div>
// 更新后
<p>a</p>

// key为null，一致，但type不同，不能复用

// 更新前
<div key="xxx">a</div>
// 更新后
<div key="ooo">a</div>

// key不同，不需要看type，不能复用

// 更新前
<div key="xxx">a</div>
// 更新后
<p key="ooo"a</p>

// key不同，不需要看type，不能复用

// 更新前
<div key="xxx">a</div>
// 更新后
<div key="xxx">b</div>

// key type都相同，props中children不同，更新子元素

多节点Diff

对于多节点的functionComponent，reconcileChildFibers的newChild参数类型为Array，执行reconcileChildrenArray

if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
    // ...省略
}

概览

同级多个节点的diff，归纳为：

  1. 节点更新
// 更新前
<ul>
  <li key="0" className="before">0<li>
  <li key="1">1<li>
</ul>

// 更新后 情况1 —— 节点属性变化
<ul>
  <li key="0" className="after">0<li>
  <li key="1">1<li>
</ul>

// 更新后 情况2 —— 节点类型更新
<ul>
  <div key="0">0</div>
  <li key="1">1<li>
</ul>
  1. 节点新增或减少
// 更新前
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
</ul>

// 更新后 情况1 —— 新增节点
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
  <li key="2">2<li>
</ul>

// 更新后 情况2 —— 删除节点
<ul>
  <li key="1">1<li>
</ul>
  1. 节点位置变化
// 更新前
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
</ul>

// 更新后
<ul>
  <li key="1">1<li>
  <li key="0">0<li>
</ul>

Diff思路

针对节点更新

  1. 新增：执行新增逻辑
  2. 删除：执行删除逻辑
  3. 更新：执行更新逻辑

前提：操作优先级一样，但实际开发中，React团队发现，相较于新增和删除，更新组件发生的频率更高。所以Diff会优先判断当前节点是否属于更新。

Q：同级比较能否使用双指针算法提高遍历速度？

不可以

待更新对象为JSX，其中newChildren为数组格式，但current fiber 是链表格式，同级的fiber节点是由sibling指针形成的单链表，不支持双指针遍历；

newChildren[0]与fiber比较，newChildren[1]与fiber.sibling比较

无法针对数组和链表进行比较，所以不可行

react团队提供的思路：2轮遍历

  1. 处理 更新 的节点；
  2. 处理非 更新 的节点；

第一轮遍历

地址：https://github.com/facebook/react/blob/1fb18e22ae66fdb1dc127347e169e73948778e5a/packages/react-reconciler/src/ReactChildFiber.new.js#L818

  1. let i = 0，遍历newChildren，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用；
  2. 如果可复用，i++，继续比较newChildren[i]与oldFiber.sibling，可以复用则继续遍历；
  3. 如果不可复用，分两种情况：
    1. key不同导致不可复用，立即跳出整个遍历，第一轮遍历结束；
    2. key相同type不同导致不可复用，会将oldFiber标记为DELETION，并继续遍历；
  4. 如果newChildren遍历完（即 i === newChildren.length - 1 ）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束；

其中，3 4可以完成当前遍历

3：此时newChildren没有遍历完，oldFiber也没有遍历完

// 更新前
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
            
// 更新后
<li key="0">0</li>
<li key="2">1</li>
<li key="1">2</li>

// 第一个节点可复用，遍历到key === 2的节点发现key改变，不可复用
// 跳出遍历，等待第二轮遍历处理

// oldFiber: key === 1、key === 2未遍历
// newChildren剩下key === 2、key === 1未遍历

4：可能newChildren遍历完，或oldFiber遍历完，或他们同时遍历完

// 更新前
<li key="0" className="a">0</li>
<li key="1" className="b">1</li>
            
// 更新后 情况1 —— newChildren与oldFiber都遍历完
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
            
// 更新后 情况2 —— newChildren没遍历完，oldFiber遍历完
// newChildren剩下 key==="2" 未遍历
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
<li key="2" className="cc">2</li>
            
// 更新后 情况3 —— newChildren遍历完，oldFiber没遍历完
// oldFiber剩下 key==="1" 未遍历
<li key="0" className="aa">0</li>

第二轮遍历

newChildren 和 oldFiber 同时遍历完

不需要第二轮的遍历，直接进行 update，diff结束；

  1. newChildren没遍历完，oldFiber遍历完

已有的DOM节点都对比结束，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement；

地址：https://github.com/facebook/react/blob/1fb18e22ae66fdb1dc127347e169e73948778e5a/packages/react-reconciler/src/ReactChildFiber.new.js#L869

  1. newChildren遍历完，oldFiber没遍历完

本次更新比之前的节点数量少，有节点被删除了。所以需要遍历剩下的oldFiber，依次标记Deletion；

地址：https://github.com/facebook/react/blob/1fb18e22ae66fdb1dc127347e169e73948778e5a/packages/react-reconciler/src/ReactChildFiber.new.js#L863

  1. newChildren与oldFiber都没遍历完

意味着有节点更新了位置

如何处理更新后的节点

由于有节点改变了位置，所以不能再用位置索引i对比前后的节点，那么如何才能将同一个节点在两次更新中对应上呢--key

为了快速的找到key对应的oldFiber，我们将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中。

const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

接下来遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber

标记节点是否移动

如何判断节点是否移动？参照物是什么？

我们的参照物是：最后一个可复用的节点在oldFiber中的位置索引（用变量lastPlacedIndex表示）。

本次更新中节点是按newChildren的顺序排列。在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个，即一定在lastPlacedIndex对应的可复用的节点在本次更新中位置的后面；

所以只需要比较遍历到的可复用节点在上次更新时是否也在lastPlacedIndex对应的oldFiber后面，就能知道两次更新中这两个节点的相对位置改变没有；

我们用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引。如果oldIndex < lastPlacedIndex，代表本次更新该节点需要向右移动；

lastPlacedIndex初始为0，每遍历一个可复用的节点，如果oldIndex >= lastPlacedIndex，则lastPlacedIndex = oldIndex；

Demo

每个字母代表一个节点，字母的值代表节点的key

demo 1

// 之前
abcd

// 之后
acdb

===第一轮遍历开始===
a（之后）vs a（之前）  
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;

继续第一轮遍历...

c（之后）vs b（之前）  
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点

将剩余oldFiber（bcd）保存为map

// 当前oldFiber：bcd
// 当前newChildren：cdb

继续遍历剩余newChildren

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
此时 oldIndex === 2;  // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;

如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动

在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：bd
// 当前newChildren：db

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：b
// 当前newChildren：b

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===

最终acd 3个节点都没有移动，b节点被标记为移动

demo 2

// 之前
abcd

// 之后
dabc

===第一轮遍历开始===
d（之后）vs a（之前）  
key改变，不能复用，跳出遍历
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === dabc，没用完，不需要执行删除旧节点
oldFiber === abcd，没用完，不需要执行插入新节点

将剩余oldFiber（abcd）保存为map

继续遍历剩余newChildren

// 当前oldFiber：abcd
// 当前newChildren dabc

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
此时 oldIndex === 3; // 之前节点为 abcd，所以d.index === 3
比较 oldIndex 与 lastPlacedIndex;
oldIndex 3 > lastPlacedIndex 0
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：abc
// 当前newChildren abc

key === a 在 oldFiber中存在
const oldIndex = a（之前）.index; // 之前节点为 abcd，所以a.index === 0
此时 oldIndex === 0;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 0 < lastPlacedIndex 3
则 a节点需要向右移动

继续遍历剩余newChildren

// 当前oldFiber：bc
// 当前newChildren bc

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index; // 之前节点为 abcd，所以b.index === 1
此时 oldIndex === 1;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 1 < lastPlacedIndex 3
则 b节点需要向右移动

继续遍历剩余newChildren

// 当前oldFiber：c
// 当前newChildren c

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index; // 之前节点为 abcd，所以c.index === 2
此时 oldIndex === 2;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 2 < lastPlacedIndex 3
则 c节点需要向右移动

===第二轮遍历结束===

所以，尽量减少节点从后面移动到前面的操作

  1. abcd -> acdb：b移动到最右边
  2. abcd -> dabc：abc移动到最右边

最后更新于 2024-03-12
啥也没有呀