junz91

React的diff算法（翻译）

• 标签: React

React的diff算法可以将虚拟DOM的变化反应到真实DOM上，这是React实现高性能的关键之一。
原文

一、Diff Algorithm

首先来看看使用React建立节点的大致模型：

1
2
3
4
5
6
7
8
9
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>; 
    } 
  } 
});

render返回的结果并不是真实的DOM节点，它们只是轻量的JavaScript对象，叫做虚拟DOM。React要做的事就是找到从一种状态向另一种状态转化的最佳方式，比如我们先挂载了<MyComponent first={true} />，然后我们使用<MyComponent first={false} />来替换它，最后再卸载，以下是React操作的大致步骤：

挂载

  • 创建节点：<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>；

Level by Level

找到React节点从一个状态转换为另一个状态时所需的最少修改步骤数，是一个O(n^3)复杂度的问题。React使用了一种简单但是强大的启发式算法来解决这个问题，将复杂度很好的控制在O(n)。
React调节DOM树是层级式的调整策略（Level by Level），这种方式大大地减少了复杂度，但同时不适用于DOM树节点之间发生层级变换的情况。React之所以这么做是基于：绝大部分时候组件之间只是在同一层级上横向移动，很少会发生层级间的变换。
enter description here

List

假设我们有一个组件需要渲染五个其它组件，每插入一个组件都是在组件列表的中间。如此想要找到两个组件列表之间的映射关系是很难的。React默认是把前一个组件列表和组件和后一个组件列表的组件一一对应，第一个组件对应第一个，第二个对应第二个等。当然你也可以使用key属性来控制列表组件之间的对应关系。
enter description here

Components

一个React应用通常由很多用户自定义的组件组合而成，这些组件一般都包含了很多div。React的diff算法只会作用在相同类型的组件之间，比如使用<Header>替换<ExampleBlock>时，React会直接移除原有的元素，然后用新的元素代替。
enter description here

二、Event Delegation

将事件监听器附着在每一个DOM节点上是非常消耗资源的，React使用事件代理机制来提高性能，实际上React几乎重新实现了一个符合W3C标准的事件代理机制（这提高了浏览器兼容度）。为了使得事件在DOM层级之间传播，React利用了组件很重要的一条性质——每个组件都有一个独一无二的id。
React将组件ID散列，然后与事件监听器一一对应，形成一个哈希表，当一个组件的事件被触发时，React可以很快的找到对应的事件处理程序。这样的方式比直接把事件附着在虚拟DOM上要高效许多。
找到对应的事件处理程序之后再根据event对象的属性来决定执行的细节，完成整个事件代理机制。此外React在启动时建立了一个事件对象池，每当一个事件被触发时React都会从这个池子中重用内存，这样的方式大幅地减少了触发JavaScript引擎垃圾回收的次数。

三、Rendering

Batching

在一个组件上使用setState时，这个组件会被标记为”dirty“，在事件循环的最后React会重新渲染这些有dirty标记的组件。批处理意味着在一次事件循环中只进行一次组件更新，这是构件高性能应用的关键之一，这种机制用JavaScript实现比较麻烦，但是在React中这是默认的机制。
enter description here

Sub-tree Rendering

当setState()被调用时，React会重新构建虚拟DOM的子树，如果你是在根节点调用的，那么这会导致整个DOM被重新渲染。这听起来很不合理，也很不高效，但实际上这不会太影响性能，因为React并没有去改变真正的DOM结构。
首先，JavaScript在操纵DOM元素方面是非常快速的，一般都能满足我们的业务逻辑。在React中开发者不会每次一有数据变换就在根节点上调用setState，而是仅在组件收到数据改变事件时才重新setState。这意味着会被定位在触发的地方，很少会一直传播到根节点。
enter description here

Selective Sub-tree Rendering

现在到了关键的地方，React提供一个函数给开发者来自定义一个组件是否应该被重新渲染：

1
2
3
4
5
6
boolean shouldComponentUpdate(object nextProps, object nextState)

//使用方式
shouldComponentUpdate: function(nextProps, nextState) {
  return this.props.value !== nextProps.value;
}

shouldComponentUpdate返回true时执行更新，否则不更新。实际中，状态发生改变可能是频繁的，这就要求我们的判别函数要足够快速，特别是我们的状态是一个很大的对象时。
enter description here

四、Conclusion

使得React高效的技术并不是首次出现，比如我们早已知道操纵真实DOM会非常耗费时间，分批读写属性更高效，事件委托技术等等。
React优秀的原因之一便是集成并很好的实现了包括但不限于上述的技术，这让你的应用想变慢都难！
总结起来React的性能耗费模型也是很简单的：setState会导致节点的子树被重新渲染，如果想要获得高性能表现，你需要做的是尽量低频地调用setState，并且使用shouldComponentUpdate来阻止某些不必要的重新渲染。