React diff 算法

Posted on | In

1.前言

React 的 diff 算法作为 Virtual DOM 的加速器，其算法上的改进优化是 React 整个界面渲染的基础，以及性能提高的保障，同时也是 React 源码中最神秘、最不可思议的部分，本文从源码入手，深入剖析 React diff 的不可思议之处.

2.传统 diff 算法

传统 diff 算法的复杂度为 O(n^3)，显然这是无法满足性能要求的。React 通过制定大胆的策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数。O(n^3) 到底有多可怕，这意味着如果要展示1000个节点，就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说代价太高了！现今的 CPU 每秒钟能执行大约30亿条指令，即便是最高效的实现，也不可能在一秒内计算出差异情况。

3.详解 React diff

diff 策略

  1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
  2. 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
  3. 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

基于以上三个前提策略，React 分别对 tree diff、component diff 以及 element diff 进行算法优化，事实也证明这三个前提策略是合理且准确的，它保证了整体界面构建的性能。

tree diff

对两棵树进行分层比较，只会对同一层次的节点进行比较(同一个父节点下的所有子节点)。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不在进一步比较。对树进行一次遍历就完成了整个 DOM 树的比较。

当出现节点跨层级移动时，并不会出现移动操作，而是以 A 为根节点的树被整个重新创建，由于影响性能，官方不建议进行 DOM 节点跨层级的操作。

注意：在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。

component diff

  • 同一类型的组件，按原策略继续比较 virtual DOM tree。
  • 不同类型的组件，则判断为 dirty component，替换整个组件下的所有子节点。
  • 同一类型的组件，Virtual DOM 没有任何变化（如果知道），通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

如果结构相似但是不同类型的组件。就不会比较二者的结构，而是直接删除重建。（很少存在）

element diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

  • 插入：新的 component 类型不在老集合里， 即是全新的节点，对新节点执行插入操作。
  • 移动：老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
  • 删除：老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

新老集合进行 diff 差异化对比，通过 key 发现新老集合中的节点都是相同的节点，因此无需进行节点删除和创建，只需要将老集合中节点的位置进行移动，更新为新集合中节点的位置

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

4.总结

  1. React 通过 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；
  2. React 通过分层求异的策略，对 tree diff 进行算法优化；
  3. React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；
  4. React 通过设置唯一 key的策略，对 element diff 进行算法优化；
  5. 建议，在开发组件时，保持稳定的 DOM 结构会有助于性能的提升；
  6. 建议，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。

Reference：
https://zhuanlan.zhihu.com/p/20346379
https://calendar.perfplanet.com/2013/diff/
https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf
https://reactjs.org/docs/reconciliation.html
https://github.com/livoras/blog/issues/13