React is a UI library used by millions, and they have good reasons to. React was first to achieve truly reactive way of developing user interfaces, which works on every platform imaginable. But few know, that without the React Reconciliation Algorithm, none of this would be possible.

What is so hard about drawing some buttons?

While developing with React, it is easy to forget (or not know at all) the imperative way of creating and managing the UI. As an analogy, React lets you “describe” the interface you want, while native libraries and frameworks have to “build” it, using primitives. So, while for you it looks like 1 return statement, in native code translates to hundreds of objects, assignments, and expressions.

So, updating a native (both DOM or Platform) interface is not an easy process. But, thankfully, we do not have to do it often. Most of the time, your app does not change the UI structure entirely on every render. Often, a button changes its color, or a label gets updated text. On the few occasions when everything changes (navigating to another screen), we will just have to deal with it. But how does React know what is the most efficient change to the underlying interface? The Reconciliation algorithm.

You might be familiar with a data structure called tree. Even if you are not, you work with it on a daily basis. A tree is a collection of nodes (components). Every node can have children, which are themselves nodes. Basically, the JSX and HTML both can be described as trees.

The Reconciliation algorithm, then, compares two trees and returns a set of operations to update the second tree so that it matches the first one. In the computer science world, this is called the Tree Distance Problem. Of course, it has a few general solutions, but their complexity is O(n^3), which is completely inappropriate for user interfaces. In order to make it faster, the React team had to make some tradeoffs.

How does the Reconciliation algorithm solve the problem?

Recall that the algorithm is optimized for user interfaces and the assumptions about user interfaces that we made earlier. These were the foundations of the Reconciliation algorithm. Deriving from the assumptions, the algorithm takes these actions:

1. If a node had changed its type (H1 -> MARKUEE or View -> Text), the old one is dismissed and the new one is recursively rendered from scratch.
2. If 2 nodes in both trees have equal key props, they are the same node and is reused without creating a new one.

Using these as axioms, you can easily derive the rest of the algorithm. If nodes are different, the old one is dismissed and a new one is created from scratch. If nodes are the same, the algorithm will compare its props, make necessary changes to them, and continue on to child nodes recursively.

Reconciliation algorithm’s shortcomings

Since these are tradeoffs, they bring some unwanted results along. Consider a list of items. It may have hundreds of nodes of the same type, which can be edited and rearranged. The if we were to rearrange them, the Reconciliation algorithm will have no idea which ones are which in 2 trees, causing a full rerender. This is where key comes into play. If you assign a unique key to every list item, the algorithm will easily match them between trees and have no problems whatsoever. This is also the reason why you must never use array index or a random number as a key. If you use index and the items are rearranged, their indexes will change. The algorithm will match the nodes in a wrong way and your UI will behave completely unpredictable. If you use random numbers that are generated on every render nothing will break, but it would be extremely inefficient as every node will be recreated from scratch on every render.

Closing notes

Thank you for reading, I hope you enjoyed this article. The React Concurrent Mode will introduce some changes to how React handles UI, so stay tuned for updates!

Resources

• react-reconciler package
• Tree edit distance problem