React diff算法

686 查看

翻译自：http://calendar.perfplanet.com/2013/diff/，感谢Christopher Chedeau！

React是Facebook开发的一个用于构建用户界面的JavaScript库。它从零开始设计的时候就考虑了性能的问题。在这篇文章中，我将介绍React中的diff算法和渲染过程。这样你就能够对自己的应用进行优化。

Diff算法

在开始讨论算法的实现细节之前，我们先简单了解一下React是如何工作的。

var MyComponent = React.createClass({
    render: function() {
        if(this.props.first) {
            return <div className="first">
                <span>A Span</span>
            </div>;
        }
        else {
            return <div className="second">
                <p>
                    A paragraph
                </p>
            </div>;
        }
    }
});

我们需要描述UI的样子。上面代码中render的结果并不是一个实际的DOM节点，而是一些轻量级的JavaScript对象。我们称之为虚拟DOM（Virtual DOM）。

React将使用这种表示方法来尝试找到从一个渲染结果切换到另一个渲染结果的最少步骤。例如，从<MyComponent first={true} />开始，然后替换为<MyComponent first={false} />，最后将它们都删除。下面是DOM指令：

从0到1

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

从1到2

替换属性：替换className="first"为className="second"。

替换节点：替换<span>A Span</span>为<p>A Paragraph</p>。

从2到0

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

按层比较

查找任意两棵树之间最少修改数的时间复杂度是O(n^3)。可以想象到，这很难处理。React使用一种简单但强大的启发式方式来优化到了接近O(n)。

React按层比较两棵树。这样做显著的降低了问题的复杂度，并且由于Web应用中很少将一个组件在不同层之间移动，从而不会产生太多负面影响。Web应用通常只会在子节点之间横向移动。

move_node_level_by_level.png

列表

让我们尝试这样一个组件：首先迭代渲染5个组件，然后在列表中间插入一个新的组件。仅根据这些信息很难在两个列表之间进行映射。

默认情况下，React将两个列表中的组件对应关联。我们也可以为每个组件提供一个key属性。实际上，通常很容易就可以为子节点找到一个唯一的Key。

react_list_key.png

组件

React应用一般由许多用户定义的组件构成。这些组件最终会转换为一个主要由div组成的树。这些附加信息被diff算法利用了。React只会匹配类型相同的组件。

如果一个<Header>被<ExampleBlock>替换，React将删除Header然后创建一个ExampleBlock。我们不需要花费宝贵的时间来匹配两个不一样的组件。

react_component_diff.png

事件代理

给DOM节点增加事件监听器是一个既慢又消耗内存的事情。React实现了一个叫“事件代理”的技术，并且重新实现了一个W3C兼容的事件系统。因此使得IE 8的事件处理不再是一个问题，所有的事件都能够跨浏览器使用。

下面让我解释一下它的实现。首先将单个事件监听器添加到文档的根节点上。当事件被触发后，浏览器给出目标DOM节点。为了在整个DOM树上传递事件。React不是在虚拟DOM进行迭代，而是利用每个React组件的唯一ID。我们可以使用一个简单的字符串来获取所有父节点的ID。通过将事件监听器存储在一个Hash表中，我们发现比将事件添加到虚拟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将它标记为脏节点。在事件循环的最后才重新渲染所有的脏节点。

这种批处理意味着在一个事件循环，准确地说是一次事件循环中对DOM进行更新。这个特性对构建高性能的JavaScript应用一般来说非常难。但在React中，我们默认就可以利用这个特性。

react_render_event_loop.png

渲染子树

当调用setState时，组件会重建子节点的虚拟DOM。如果在根元素上调用setState，整个React应用都会被重新渲染。所有的组件，包括没有发生改变的组件都会调用自己的render方法。这样做效率低的相当可怕，但在实际应用的时候还是可以很好的工作的。因为我们不需要直接操作DOM。

首先，我们讨论的是如何显示用户界面。因为屏幕空间的限制，我们通常需要一次性按顺序显示成千上万个元素。由于整个界面都可以管理，JavaScript能够足够快地处理商业逻辑。

其次，在编写React代码时，我们不需要在每次发生改变后就调用根元素的setState方法。我们只需要接受到改变事件的节点或者它的一些上层节点调用该方法，很少需要上溯到顶部。这意味着变化被局限在用户交互的地方。

react_render_change.png

选择性渲染子树

最后，我们还能够组织一些子树的重新渲染。如果一个组件实现了下面的方法：

boolean shouldComponentUpdate(object nextProps, object nextState)

我们可以基于组件之前的状态或者下一个状态来决定它是否需要重新渲染。如果实现合理的话，这样做能够极大的提高程序的性能。

为了使用这个功能，我们需要能够比较JavaScript对象。但比较的时候又会引发许多事情，比如是“深比较”还是“浅比较”。如果是“深比较”，是否应该使用不可变数据结构或深拷贝。

需要注意的是，这个方法会不断调用，因此需要确保它的计算尽可能耗时较少。

react_render_subtree.png

总结

这种技术能够使React变得更得快已经不是一件新鲜事。我们也已经知道，DOM的处理非常耗时、应该批量进行读写操作、事件代理效率更高...

大家现在还经常讨论它们，因为在正常的JavaScript代码中很难达到这些目标。React让这些优化默认就会发生，高性能应用的开发变得更简单。

React的性能模型非常易于理解：每个setState重新渲染一棵子树。如果想尽量压榨性能，应该尽可能少调用setState或使用shouldComponentUpdate阻止重新渲染大的子树。