Understanding React - Part 3. Exploring the React Reconciler and the Diff Algorithm

September 22

# Tech

# Front-End

# React

Introduction

In the last post, we introduced the work loop mechanism in React, explaining how React traverses the Fiber tree to create and update the UI. During the "begin work" phase, React performs two crucial tasks: it computes the latest state and reconciles the children. Since the reconciliation of children is a key part of React’s performance, we will explore this process in more detail in this post. Let's dive into how React reconciles children efficiently.

How React Determines Operations for Child Nodes

In the "begin work" phase, when traversing each fiber, React computes the latest state for the current fiber and schedules work for its children, including creating, updating, or deleting child nodes. But how does React decide which operation to perform on each child node? Should it create, update, or delete a node? And how can it efficiently update multiple child nodes?

This is where React's "alternate" architecture comes into play.

Recognizing and Executing Creation Operations

React identifies two cases where it needs to create new child nodes:

1. The current node doesn’t exist: This means the node did not exist in the previous render cycle, such as during the initial mounting of the application. In this case, React must create all child nodes under this fiber.
2. The current node’s child property is empty: This means the node existed in the previous render, but there were no child nodes at that time. For instance, conditional rendering in JSX may result in newly added child nodes, which React will need to create.

Recognizing Update and Delete Operations

Identifying which child nodes should be updated or deleted is slightly more complex. In a large React application, there may be thousands of fiber nodes. To improve performance, React tries to reuse existing nodes whenever possible. But how does it determine whether a node can be reused or should be recreated?

React uses two key properties to decide whether a fiber node can be reused: type and key. A node can only be reused if both properties are identical.

• Type: This property represents the type of the fiber node. For example, for a function component, the type stores the function reference for that component. For host components (such as DOM elements), the type stores a unique string identifier (e.g., "div" for a <div> element). If the types of two fiber nodes match, React assumes that their structure and UI logic are identical.
• Key: This property is the unique identifier that differentiates a fiber node from its siblings. It plays an essential role when rendering multiple child elements. If a list of elements all share the same type, React needs the key to distinguish between them and avoid state and prop mismatches. That’s why React encourages us to provide a unique key when rendering arrays of elements.

React Diff Algorithm: Handling Child Node Updates

GitHub code reference: ReactChildFiber.ts

Now that React can determine whether nodes can be reused based on type and key, why is updating and deleting child nodes still considered complex? This complexity arises when elements in a list change their order, making a one-to-one comparison inefficient.

Consider the following example: suppose we have a list of elements [<div key="A" />,<div key="B" />, <div key="C" />], and we update it to [<div key="A" />, <div key="C" />, <div key="B" />]. If React simply compared the nodes in order, it would only reuse the "A" element, forcing "B" and "C" to be recreated. But since "B" and "C" have merely switched places, React can still reuse them.

To handle such cases, React employs a specialized algorithm called the React Diff Algorithm, which breaks down the comparison into several steps:

1. Head-to-head comparison: React starts by comparing elements from the beginning of both the old and new arrays, reusing nodes wherever possible.
2. Delete remaining old nodes: If React reaches the end of the new array but there are still nodes left in the old array, these old nodes are deleted.
3. Create remaining new nodes: If React reaches the end of the old array but there are still nodes left in the new array, these new nodes are created.
4. Diff remaining nodes: If both the old and new arrays have remaining nodes, React diff’s them by trying to find reusable nodes in the old array:
   • If no match is found, React creates a new node.
   • If a match is found, React checks whether it needs to reposition the node.

Let’s illustrate this with a few examples.

Case 1: Appending or Deleting Children

In simple cases like appending or deleting children at the end of the array, React performs a straightforward comparison from the beginning of the arrays (step 1), followed by the addition or deletion of nodes (steps 2 and 3).

append or delete children in reconciliation of children

Case 2: Reordering Children

Now, let's look at a case where the order of children changes. In this case, React will first compare the elements from the beginning, reusing nodes A and B. After that, React starts the diffing process for the remaining nodes.

When React encounters node D, it finds that a matching node D' exists in the old array, meaning D can be reused. React then places node D after B and updates its position in the old array with a variable called lastPlacedIndex.

Next, React processes node E, which can also be reused, and since its index in the old array is greater than lastPlacedIndex, React knows it doesn't need to move. React updates lastPlacedIndex again.

Finally, when React encounters node C, it finds that it can be reused. However, C's index in the old array is less than lastPlacedIndex, meaning C must be moved to a new position. React flags this change and updates the DOM accordingly.

move children in reconciliation of children

React Diff Trade-offs

The React Diff Algorithm solves the problem of efficiently comparing arrays of elements by optimizing for head-to-head reuse and handling reordering. However, it has its limitations. For instance, React can only detect if an element has moved to the right, which isn't always the most efficient strategy.

In some cases, like the example below, React performs three swap operations when it detects that elements C, D, and E have moved to the right. But if we consider it from the opposite perspective, only element F moved to the left, requiring just one swap.

fallback of the React diff algorithm

This is a trade-off React makes to maintain simplicity and performance. React avoids using more complex algorithms for comparing arrays during reconciliation to maintain performance and responsiveness. While advanced algorithms could minimize DOM updates, they tend to have higher computational costs, slowing down the UI, especially in large applications. React’s Diff Algorithm strikes a balance, offering linear performance (O(n)) optimized for common cases like adding, removing, or reordering elements. This ensures a predictable developer experience and smooth user interactions, even on resource-constrained devices, without introducing excessive complexity or memory overhead.

Conclusion

In this post, we explored how React reconciles children efficiently by leveraging its diff algorithm. We learned that React determines whether to create, update, or delete nodes based on their type and key, and handles child updates through an optimized algorithm that balances reuse and performance. Although React's diff algorithm has some limitations, it provides a highly performant way to reconcile the UI in most cases.