React 的 diffing 算法

2021-02-03 本文已影响0人 Lia代码猪崽

参考资料

一、为什么需要 diffing 算法？

在某一时间节点调用 React 的 render() 方法，会创建一棵由 React 元素组成的树。在下一次 state 或 props 更新时，相同的 render() 方法会返回一棵不同的树。React 需要基于这两棵树之间的差别来判断如何有效率的更新 UI 以保证当前 UI 与最新的树保持同步。

这个算法问题有一些通用的解决方案，即生成将一棵树转换成另一棵树的最小操作数。然而，即使在最前沿的算法中，该算法的复杂程度为 O(n<sup> 3 </sup>)，其中 n 是树中元素的数量。

如果在 React 中使用了该算法，那么展示 1000 个元素所需要执行的计算量将在 十亿 的量级范围。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法：

二、diffing 算法的复杂程度为？

O(n)

三、能做到如此低的算法复杂程度的两个假设基础

两个不同类型的元素会产生出不同的树；
开发者可以通过 key、prop 来暗示哪些子元素在不同的渲染下能保持稳定；

在实践中，我们发现以上假设在几乎所有实用的场景下都成立。

四、diffing 算法具体对比

总结：

对比不同类型的普通元素：当根节点为不同类型的元素时，React 会拆卸原有的树并且建立起新的树。
对比同一类型的普通元素：① 元素的属性改变时，React 会保留 DOM 节点，仅比对及更新有改变的属性。② 特殊的 style 属性改变时，React 仅更新有所更变的 style 里的属性。
对比同一类型的组件元素：不改变组件的 state；更新组件的 props；调用实例的相关方法；递归新旧结果。
对子节点进行递归：① 在子元素列表末尾新增元素时，更新开销比较小，只新增末尾元素。② 将新增元素插入到表头，那么更新开销会比较大，会重建每一个子元素。

1. 对比不同类型的元素

当根节点为不同类型的元素时，React 会拆卸原有的树并且建立起新的树。举个例子，当一个元素从 <a> 变成 <img>，从 <Article> 变成 <Comment>，或从 <Button> 变成 <div> 都会触发一个完整的重建流程。

当拆卸一棵树时，对应的 DOM 节点也会被销毁。组件实例将执行 componentWillUnmount() 方法。当建立一棵新的树时，对应的 DOM 节点会被创建以及插入到 DOM 中。组件实例将执行 UNSAFE_componentWillMount() 方法，紧接着 componentDidMount() 方法。所有跟之前的树所关联的 state 也会被销毁。

在根节点以下的组件也会被卸载，它们的状态会被销毁。比如，当比对以下更变时：

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

React 会销毁 Counter 组件并且重新装载一个新的组件。

注意：

这些方法被认为是过时的，在新的代码中应该避免使用它们：

UNSAFE_componentWillMount()

2. 对比同一类型的元素

当对比两个相同类型的 React 元素时，React 会保留 DOM 节点，仅比对及更新有改变的属性。比如：

<div className="before" title="stuff" />

<div className="after" title="stuff" />

过对比这两个元素，React 知道只需要修改 DOM 元素上的 className 属性。

当更新 style 属性时，React 仅更新有所更变的属性。比如：

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

通过对比这两个元素，React 知道只需要修改 DOM 元素上的 color 样式，无需修改 fontWeight。

在处理完当前节点之后，React 继续对子节点进行递归。

3. 对比同类型的组件元素

当一个组件更新时，组件实例保持不变，这样 state 在跨越不同的渲染时保持一致。React 将更新该组件实例的 props 以跟最新的元素保持一致，并且调用该实例的 UNSAFE_componentWillReceiveProps()、UNSAFE_componentWillUpdate() 以及 componentDidUpdate() 方法。

下一步，调用 render() 方法，diff 算法将在之前的结果以及新的结果中进行递归。

注意：

这些方法已过时，在新代码中应避免使用它们：

UNSAFE_componentWillUpdate()

UNSAFE_componentWillReceiveProps()

流程大概如图所示

4. 对子节点进行递归

在默认条件下，当递归 DOM 节点的子元素时，React 会同时遍历两个子元素的列表；当产生差异时，生成一个 mutation。

在子元素列表末尾新增元素时，更新开销比较小。比如：

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

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

React 会先匹配两个 <li>first</li> 对应的树，然后匹配第二个元素 <li>second</li> 对应的树，最后插入第三个元素的 <li>third</li> 树。

如果只是简单的将新增元素插入到表头，那么更新开销会比较大。比如：

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

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

React 不会意识到应该保留 <li>Duke</li> 和 <li>Villanova</li>，而是会重建每一个子元素。这种情况会带来性能问题。

五、diffing 算法对子节点进行递归的优化 —— Keys

为了解决对子元素进行递归时更新开销会比较大的问题，React 支持 key 属性。

当子元素拥有 key 时，React 使用 key 来匹配原有树上的子元素以及最新树上的子元素。以下例子在新增 key 之后使得之前的低效转换变得高效：

<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>

现在 React 知道只有带着 '2014' 的 key 元素是新元素，带着 '2015' 以及 '2016' 的 key 元素仅仅移动了。

现实场景中，产生一个 key 并不困难。你要展现的元素可能已经有了一个唯一 ID，于是 key 可以直接从你的数据中提取：

<li key={item.id}>{item.name}</li>

当以上情况不成立时，你可以新增一个 ID 字段到你的模型中，或者利用一部分内容作为哈希值来生成一个 key。这个 key 不需要全局唯一，但在列表中需要保持唯一。

最后，你也可以使用元素在数组中的下标作为 key。这个策略在元素不进行重新排序时比较合适，如果有顺序修改，diff 就会变得慢。

当基于下标的组件进行重新排序时，组件 state 可能会遇到一些问题。由于组件实例是基于它们的 key 来决定是否更新以及复用，如果 key 是一个下标，那么修改顺序时会修改当前的 key，导致非受控组件的 state（比如输入框）可能相互篡改导致无法预期的变动。

在 Codepen 有两个例子，分别为展示使用下标作为 key 时导致的问题，以及不使用下标作为 key 的例子的版本，修复了重新排列，排序，以及在列表头插入的问题。

六、性能会有所损耗的假设

请谨记协调算法是一个实现细节。React 可以在每个 action 之后对整个应用进行重新渲染，得到的最终结果也会是一样的。在此情境下，重新渲染表示在所有组件内调用 render 方法，这不代表 React 会卸载或装载它们。React 只会基于以上提到的规则来决定如何进行差异的合并。

我们定期探索优化算法，让常见用例更高效地执行。在当前的实现中，可以理解为一棵子树能在其兄弟之间移动，但不能移动到其他位置。在这种情况下，算法会重新渲染整棵子树。

由于 React 依赖探索的算法，因此当以下假设没有得到满足，性能会有所损耗：

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