React is a UI library used by millions, and they have good reasons to. React was the first to achieve a truly reactive way of developing user interfaces that work 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?
When 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 it looks like one return statement to you, that translates to hundreds of objects, assignments, and expressions in native code.
Updating a native (both DOM or platform) interface is not an easy process. 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 the most efficient change to the underlying interface is?
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 that 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³), which is completely inappropriate for user interfaces. In order to make it faster, the React team had to make some trade-offs.
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:
If a node has changed its type (H1 -> MARKUEE or View -> Text), the old one is dismissed and the new one is recursively rendered from scratch.
If two nodes in both trees have equal key props, they are the same node and are 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.
The Reconciliation Algorithm’s Shortcomings
Since these are trade-offs, they bring some unwanted results along. Consider a list of items. It may have hundreds of nodes of the same type that can be edited and rearranged. If we were to rearrange them, the reconciliation algorithm will have no idea which ones are which in the two trees, causing a full re-render.
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 an array index or a random number as a key. If you use an 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 unpredictably. If you use random numbers that are generated on every render, nothing will break, but it will 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. React’s Concurrent Mode will introduce some changes to how React handles UI, so stay tuned for updates!
https://github.com/facebook/react/tree/master/packages/react-reconciler
Top comments (0)