React Internals - Reconciliation algorithm until React 15

The previous article in the series is a prerequisite to understanding this one. It introduces you to terms and concepts that will be used extensively in this article. I will also link to further reading resources, React docs and sources for writing this article. I will try to keep jargon on the minimum and provide with meanings of terms wherever possible

Review

Reconciliation

The diffing algorithm that React uses to determine which parts of the tree have changed

DOM

The DOM or Document Object Model is a tree data structure that is used
by the browser. It is a representation of the UI in the form of a tree data structure.

The Recursive Nature Of The Diffing Algorithm

At any time, you can think of the render() function with a return value of a tree of React elements

var elementTree = render(a);

For example. Take a look at this component:

class HashSign extends React.Component {
    render() {
        return <span>#</span>
    }
}

class HashTag extends React.Component {
    render() {
        return (
            <div className="row">
                <HashSign/>
                <b>React</b>
            </div>
        )
    }
}

When React starts rendering the UI, first HashTag component's render function is called. Then a recursive call to the render functions of HashSign and the b tag is done. This results in the following tree of elements (Lists of elements are stored as Linked Lists):

{
    type: "div",
    className: "row",
    props: {
        children: [
            {
                type: "span",
                children: "#"
            },
            {
                type: "b",
                children: "React"
            }
        ]
    }
}

When the props or state changes, React needs to update the Real DOM. On the next update, the render() function generates a different tree of React elements.

Now, React needs to figure out what has changed and find the minimum number of changes to transform the old tree into the new one.

A naive implementation of this transformation would have a complexity in order of O(n³) but React implements a heuristic O(n) algorithm based on two assumptions:

Two elements having different type props will product different trees. React will not attempt to diff the two trees and will rather replace the old tree completely
key props given components are stable, predictable and unique. React uses these keys to diff lists (hence the key related warnings in the console when rendering a list)

A **heuristic* technique or a heuristic is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, short-term goal or approximation. - Wikipedia*

Note: I have explained the type prop for elements in the previous article

The Diffing Algorithm Itself

When React starts diffing the two trees, it starts comparing the trees from the root element. There can be a few possibilities:

1. Elements have different types

If the type property of the root elements don't match, React will tear down the old subtree and build the new one from scratch. When the old subtree gets destroyed, the old DOM nodes have to be removed from the DOM. When building the new subtree, new elements are inserted into the DOM. Any state associated with the old subtree is lost.

Any elements associated with the root will also get unmounted and also have their state destroyed. For example

<div>
    <p>Hello World!</p>
</div>

<span>
    <p>Hello World!</p>
</span>

This will destroy the old instance of the p tag and create a new one

2. Elements have same type

When comparing two React DOM elements that have the same type, React looks at the attributes of the element and only updates the changed attributes. For example

<div className="before" title="stuff" />

<div className="after" title="stuff" />

React will only modify the className on the underlying DOM node

3. Elements in lists

React iterates over elements in both lists simultaneously and makes changes wherever necessary. This approach works when an element is added to the end of the list. For example:

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

Here, React first compares the first elements in both the lists. Sees that there are no changes and moves on to the second element. It then compares the second element in both the lists and sees that there are no changes to be made. Then it sees that an element is inserted in the new list, and makes the required change.

This approach can result in poor performance if an element is inserted at the start of the list. For example:

<ul>
  <li>Mumbai</li>
  <li>Banglore</li>
</ul>

<ul>
  <li>Hyderabad</li>
  <li>Mumbai</li>
  <li>Banglore</li>
</ul>

React first compares Mumbai and Hyderabad and since the inner text has changed, it destroys the old list and creates a new list from scratch.

This is where the key prop becomes the saviour.

<ul>
  <li key="2018">Mumbai</li>
  <li key="2019">Banglore</li>
</ul>

<ul>
  <li key="2017">Hyderabad</li>
  <li key="2018">Mumbai</li>
  <li key="2019">Banglore</li>
</ul>

When elements have keys, React uses the keys to match elements in the old tree with the new one. It understands that Hyderabad has been inserted into the list and the other two elements have just been moved.

The Problem With This Approach

The above algorithm is purely recursive. Any update results in the subtree being rerendered immediately when setState is called. This approach has a limitation:

Not all updates are equal

An update to the user interface should be given more priority than say, a data store change. Otherwise, the UI might feel slow to use.

Most apps will have a rather large element tree and an update of one of the higher elements in the tree will cause the entire subtree to rerender. If this subtree is large, then it might cause a drop in the frame rate.

Most computers now have a refresh rate higher than 60Hz which means that the screen refreshes at least 60 times every second. This gives React 1/60 = 16.67ms. In this limited amount of time, React has to diff the two subtrees and apply the changes in the Real DOM (which is a slow task). Also, the browser has to do other work as well at the same time. If this time budget is exhausted, there will be a drop in the frames and the screen will feel jittery.

To fix this, the React team rewrote the reconciliation algorithm from scratch and found an intuitive way of updating the elements. The new algorithm is called Fiber and has been in use since React 16. I will cover Fiber in the next article in the series.

Wrapping Up

We saw how the reconciliation algorithm in use until React 15 renders elements recursively. We also saw the limitations of the algorithm.

In the next article in this series, I will cover the Fiber reconciliation engine. Fiber was first introduced in React 16. I will also cover how it enables the incremental rendering of the virtual DOM.

References

In the next article in this series, I will cover the new reconciliation engine used by React 16. Follow me on Dev or subscribe to my newsletter to get updated

I am also on Twitter If you wanna have a chat