【译】React.js的diff算法

﹏ヽ暗。殇╰゛Y 2022-05-14 02:42 143阅读 0赞

> 原文：[https://calendar.perfplanet.com/2013/diff/][https_calendar.perfplanet.com_2013_diff]

[React][]是facebook开发的用来构造UI界面的JS库。它被设计的时候就从底层去考虑解决性能问题。这篇文章里我将阐述react的diff算法和渲染机制，以此来帮助读者优化自己的应用。

## diff算法 ##

在我们深入到实现细节之前，我们很有必要先看一下React是怎样工作的。

在任何时候，你都是这样去描述你想获得的UI界面。理解render方法的结果并不是实际的DOM这一点很重要。那些结果只是一些轻量的JavaScript对象，我们可以把它们称为虚拟DOM。

React想利用这样的表示方法来寻找上一次渲染到下一次渲染之间能够执行的最少步骤。例如，如果你想先挂载`<MyComponent first={true} />`，然后用`<MyComponent first={false} />`来替换掉它，最后把这个组件卸载，操作DOM的指令可能是这样的：

从无到有：

*  创建节点：`<div className="first"><span>A Span</span></div>`

从一到二：

*  将节点属性`className="first"`替换成`className="second"`
 *  将子节点`<span>A Span</span>`替换成`<p>A Paragraph</p>`

从二到无：

*  移除节点：`div className="second"><p>A Paragraph</p></div>`

### 层级对比 ###

计算一棵树形结构转换成另一棵树形结构的最少操作是一个`O(n^3)`问题。可以想象，[传统解法][Link 1]对我们的实际用例并不友好。React使用了一种简单却强大的技巧，使算法的复杂度接近`O(n)`。

React只会比较两棵树之间的同级节点。这样就彻底的降低了复杂度，并且不会带来什么损失。因为在web应用中不太可能把一个组件在DOM树中跨层级地去移动。它们通常只会在子节点中平级的移动组件，如下图：  
![level by level][]

### 列表 ###

假设我们有一个组件，需要循环渲染5个相同的组件，然后在这5个组件组成的列表的中间位置插入一个新的组件。根据这些仅有的信息，我们很难去在这两个新旧列表之间做好映射关系。

默认的，React会把前一个列表的第一个组件跟下一个列表的第一个组件做对比，以此类推。你可以在组件中设置`key`属性，来帮助React更好的做出映射比对。实际上，通常在子节点中找到一个唯一的key是非常容易的。  
![list and key][]

### 组件 ###

一个React应用通常是由多个用户自定义组件组合而成，最终会转换成一个主要有`div`节点构成的树。React的diff算法处理这些额外的信息时，它只会去比较那些拥有相同类名的组件。

例如，一个`<Header>`组件被`<ExampleBlock>`组件替换时，React会直接移除header组件，然后创建一个example block组件。我们不需要去浪费宝贵的时间来比较两个完全没有相似点的组件。  
![components][]

## 事件代理机制 ##

在DOM节点上挂载事件监听器，响应又慢又吃内存。与此相反，React实现了一种非常流行的叫“事件代理”的技术。React甚至在未来打算重新实现一个兼容W3C标准的事件系统。这意味着IE8的事件处理bug成为了过去时，并且在所有的浏览器中事件名可以得到统一。

让我们来解释一下这是怎么实现的。它会在document的根节点上注册一个事件监听器。当一个事件被触发，浏览器会告诉我们目标DOM节点。为了能够通过DOM层级来传播事件，React不会再虚拟dom上迭代层级。

取而代之的是，我们利用了每一个React组件都会使用唯一的id来编码层级这一事实。我们可以通过简单的字符串操作来获取所有父级的id。通过把注册地事件监听器放在一个hashMap中，我们发现这样做的性能远比把它们关联到虚拟DOM要好。下面的例子展示了事件如何在虚拟DOM上进行分发：

// dispatchEvent('click', 'a.b.c', event)
    clickCaptureListeners['a'](event);
    clickCaptureListeners['a.b'](event);
    clickCaptureListeners['a.b.c'](event);
    clickBubbleListeners['a.b.c'](event);
    clickBubbleListeners['a.b'](event);
    clickBubbleListeners['a'](event);

浏览器会为每一个事件和事件监听器创建一个事件对象。这个事件对象有一个很不错的属性就是你可以维护每一个事件对象的引用，甚至修改它们。但这也意味这很高的内存开销。React会在应用启动的时候为这些对象分配一个内存池。任何需要用到事件对象的时候，都可以从这个内存池获得一个可复用的对象。这样可以显著的减轻垃圾回收的负担。

## 渲染 ##

### 批量处理 ###

任何时候你在一个组件中调用`setState`，React都会将这个组件标记为dirty。在一次事件循环结束后，React会搜索所有被标记为dirty的组件，并对它们进行重新渲染。

这一批量处理意味着在一次事件循环中，DOM只会被更新一次。这个特性是打造高性能应用的关键，通常在编写JavaScript代码时难以实现。然而在React应用中，这一特性是默认实现的。

![batching][]

### 子树渲染 ###

当`setState`被调用时，组件会为了更新子节点而重新构建虚拟DOM。如果你在根元素上执行`setState`，则整个React应用都会被重新渲染，所有组件的`render`方法都会被调用，即使它们没有发生任何改变。这听起来既吓人又低效，但实际上还好，因为我们并没有去改变真实的DOM。

首先，我们来关注UI界面的展示。根据屏幕大小的限制，通常是需要顺序渲染数千到上万不等的元素。对于可管理的整个界面，JavaScript对于业务逻辑的处理已经足够快了。

另一个很重要的点在于，编写React代码时，你通常不需要每次都在根节点上执行`setState`来改变视图。你可以在接受变更事件的一个或几个组件上来执行`setState`。你很少需要一直在根节点上调用`setState`，这就意味着可以把变化限制在与用户发生交互的组件上。

![subtree][]

### 选择性的子树渲染 ###

最后，如果你在组件中实现了如下方法的话，你还可以阻止一些子树的重新渲染：

boolean shouldComponentUpdate(object nextProps, object nextState)

根据该组件前后state/props的对比，你可以通知React不需要改变或者没必要重新渲染。合理地使用这个方法，可以极大提升应用性能。

为了能够使用它，你必须要能够比较JavaScript对象。这里有许多issues值得探讨，比如应该是浅比较还是深比较。如果是深比较，我们是应该使用不可变数据结构还是执行深拷贝？

你还需要记住的是，这个函数会一直执行，所以必须确保它的计算耗时要小于重新渲染组件的耗时，即使这个重新渲染不是必须的。  
![6.png][]

## 总结 ##

这种让React变快的技术并不新鲜。长久以来，我们就知道操作DOM十分费时，你应该对读写操作进行合并，使用事件代理技术性能更好等等…

人们始终在谈论它们，是因为在实践中使用常规的JavaScript代码很难实现它们。而是React如此出众的原因就是，所有这些优化手段都是默认的。这使你很难让自己的应用变慢，就像你不会搬起石头砸自己的脚。

React的性能消耗模型也很容易理解：每一次`setState`都会重新渲染所有子树。如果你想继续压榨性能，尽量减少`setState`的使用频率，并且使用`shouldComponentUpdate`来阻止大型子树的重新渲染。

[https_calendar.perfplanet.com_2013_diff]: https://calendar.perfplanet.com/2013/diff/
[React]: https://reactjs.org/
[Link 1]: https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf
[level by level]: /images/20220514/b3e78688b2f34e68878f695d121a9858.png
[list and key]: /images/20220514/ea6c450892d54bf3bc8a8e949adb34d6.png
[components]: /images/20220514/fce33a9e73b244699d29863ceaacdad0.png
[batching]: /images/20220514/f1c5241b73594341b034e0a2fa6041f1.png
[subtree]: /images/20220514/fd275f7af49c49289f383e9d5de077ba.png
[6.png]: /images/20220514/07d025fcbd3c4390839d9a6085f3d044.png