Nazanin De's Blog

Projects, Ideas and thoughts

Deep dive into React Reconciliation

When people use React they are always wondering whether their application is fast enough with all these subtree components rerendering on every state changes.Even I myself was curious about how React does all these DOM manipulation in such a clever way. Let me start from the beginning:

So, How browsers construct the DOM, render it and display the HTML page?

Before the browser can render the page it has to build the DOM and CSSOM. So we need to ensure both HTML and CSS will deliver to the browser as fast as possible since browser's rendering engines are single threaded which means almost everything except network operations happens in the same thread.

As soon as the CSSOM tree has been created browser goes through two processes: applying layout and painting each tree node. Applying layout means calculating the exact coordinates where a DOM node should appear on the screen. Painting means actually rendering the pixels and applying stylistic properties. You can observe all these processes using your browser network tab.

What is the problem with DOM?

Well, the actual DOM was never optimized for dynamic UI applications. We can do some manipulation on the DOM with Javascript or libraries such as jQuery but even those did not do much in optimizing DOM operations. Think of all these modern websites with thousands of UI elements. Trying to move thousands of divs or remove hundreds of images is hard to do in such huge pages.

There are two solutions solving this problem:

1- Shadow DOM
Shadow DOM addresses the DOM tree encapsulation problem and it is a V3C standard available in chrome 35+.
That means using normal DOM your component is not encapsulated enough so the styles applied to your component can get applied to other parts of the page too. This is the issue we encounter often using components with the same class names.
So basically with shadow DOM the templates, shadow DOM, custom elements and packaging of your web component works together and you can specify which part to use from your web component. You can read more about shadow DOM here.

2- Virtual DOM

Virtual DOM built on top of the actual DOM which utilizes DOM in very small efficient operations. It is a lightweight implementation of the DOM and events system. Manipulating in-memory representation of the DOM is faster and more efficient than manipulating the real browser DOM, and events system implements all events in a cross-browser way, including bubbling. You even get some HTML5 events in IE8!

How Virtual DOM works?

Virtual DOM quickly diff the current state of the UI with the desired state and compute the minimal set of DOM mutations (which are quite expensive) to achieve it. It sometimes also patch together all these changes such that the UI is updated all at once in a single animation frame.
All the optimizations happened here!!

How diffing works?

Differentiating between virtual DOM and DOM itself means to generate minimum number of operations to transform one tree into another. This is a very complex problem which has been analyzed and studies over years. They are algorithms such as state of art which has a complexity of O(n^3) but this complexity is too huge for working with complex and modern UIs. Imagine editing thousands of divs require one million comparisons which is not doable in less than a second with current CPUs. So what React did was to implement a non-optimal O(n) algorithm using heuristics based on two assumptions:

1- If two components has the same class they produce the same tree _ and not is true.

2- providing unique stable key for elements across all renderers is feasible

React diff strategies

Reconciliation is the process by which React updates the DOM with each new render pass. When a component's props or state change, React decides whether an actual DOM update is necessary by constructing a new virtual DOM and comparing it to the old one. Only in the case they are not equal, will React reconcile the DOM, applying as few mutations as possible. There are two different comparison approaches:

1- Pair-wise diff

Pair-wise diff is between two nodes and handled in three different use cases:

1.1- Different node types

renderA: <p>Hello</p>  
renderB: <span>Hello</span>  
=> [removeNode <p>Hello</p>], [insertNode <span>Hello</span>]

1.2- DOM Nodes

renderA: <p id="first" />  
renderB: <p id="second" />  
=> [replaceAttribute id "second"]

1.3- Custom Components

React uses new component attributes and calls componentWillReceiveProps() and componentWillUpdate() on old ones to differentiate custom components. As long as those methods gets called on the older components it becomes operational and its render() method gets called and diff algorithm restarts with the new result.
On top of these React provides shouldComponentUpdate() component lifecycle function which is triggered before the re-rendering process starts.

shouldComponentUpdate: function(nextProps, nextState) {  
  return true;
}

You can implement this function to bypass the rendering for your component but you need to be careful to have pretty fast and efficient logic in there since React calls this function pretty often.

2- List-wise diff

List-wise diff is comparing list of children which is basically children reconciliation.
React goes over both lists of children and whenever finds difference it generates a mutation.

renderA: <ul><li>Cat</li></ul>  
renderB: <ul><li>Cat</li><li>Mat</li></ul>  
=> [insertNode <li>Mat</li>]

There is a problem with having out children list differ from the beginning. Then the differentiation algorithms such as Levenshtein distance cannot recognize what to insert. In order to solve this issue we can use key attribute for each child.

Conclusion

Although using virtual DOM is pretty efficient and fast but it also has some drawbacks that need to address specially using React since the algorithm itself is based on refining the heuristics in order to make things happen faster.
In newer versions of reconciliation React uses web workers making the web UI DOM updates backed by a parallel DOM-diffing computation set that happens in a separate thread results in much more efficiency and performance improvements.