React 0.3.0: The Virtual DOM and the O(n) Heuristic (2013)

React 0.3.0: The Virtual DOM and the O(n) Heuristic

The JS community is currently obsessed with "Two-Way Data Binding" (looking at you, Angular and Ember). But at JSConf US this month, Facebook introduced React, and it's doing something completely different: One-Way Data Flow. They claim you can just "re-render your entire app on every change" and it will be fast. How? The Virtual DOM.

The Problem with the Real DOM

Updating the DOM is expensive. It triggers reflows and repaints in the browser. If you have a list of 1000 items and change one, most frameworks try to surgically update that one node. React instead says: "Tell me what the UI should look like now, and I'll figure out the minimum number of changes to make it happen."

The Diffing Algorithm

React creates a lightweight tree of JavaScript objects representing your UI. When state changes, it creates a new tree. It then compares (diffs) the old tree with the new one.

In theory, finding the minimum number of modifications to transform one tree into another is an $O(n^3)$ problem. For 1000 nodes, that's a billion comparisons. To make this work in a browser at 60fps, React uses two heuristics:

1. Two elements of different types will produce different trees.
2. The developer can hint at which child elements may be stable across different renders with a key prop.

Keys are Vital

This is why React 0.3.0 shouts at you if you don't provide keys for list items. Without keys, if you insert an item at the top of a list, React thinks every single item has changed. With keys, it knows it just needs to move the existing DOM nodes.

/** @jsx React.DOM */
var TodoList = React.createClass({
  render: function() {
    var createItem = function(itemText, index) {
      // The 'key' helps the reconciliation process!
      return <li key={index + itemText}>{itemText}</li>;
    };
    return <ul>{this.props.items.map(createItem)}</ul>;
  }
});

Batching Updates

React also batches updates. If you call setState three times in one event handler, React won't run the diffing algorithm three times. It waits until the end of the event loop and performs a single update. This reconciliation process is what allows us to write declarative code without sacrificing the performance of manual DOM manipulation.

Aunimeda builds modern web frontends - from single-page applications to complex multi-locale sites.

Contact us to discuss your frontend project. See also: Web Development, Corporate Website Development