3 Key Steps of Diffing Algorithm in React for Efficiently Updating the Real DOM
Tags: react, frontend, javascript
Published: 2024-05-01 14:10:57

Ever wondered how React's diffing algorithm manages to efficiently update the real DOM ?

React's diffing algorithm is a crucial mechanism that efficiently updates the real DOM based on changes in the virtual DOM. It plays a significant role in React's performance optimization by minimizing the number of DOM manipulations required.

Here are the 3 key steps.

## 1. Virtual Dom Generation

- After a state or prop change, React creates a new virtual DOM tree that reflects the updated UI state.
- Virtual DOM is a lightweight in-memory representation of the UI.

## 2. Recursive Comparison

- React's diffing algorithm recursively compares the root nodes of the previous and new virtual DOM trees.
- It employs a heuristic approach with the following key principles:
    - **Element Type:** If elements have different types (e.g., `div` vs. `span`), they are considered entirely different and replaced.
    - **Key Prop:** If elements have the same type and a `key` prop, React assumes their order and identity are significant. It rearranges or replaces elements based on key changes.
    - **Text Content:** If elements have the same type and no `key` prop, React compares their text content. If different, the element's text is updated.
    - **Attributes:** If elements have the same type and content, React compares their attributes. If any attributes differ, the corresponding DOM element's attributes are updated.

## 3. DOM Reconciliation

- Based on the diffing results, React determines the minimal set of DOM operations needed to bring the actual DOM in sync with the virtual DOM.
- This might involve:
    - Inserting new DOM nodes.
    - Updating existing DOM nodes (e.g., text content, attributes).
    - Removing DOM nodes that are no longer present in the virtual DOM.

## Time and Space Complexity

### Naive Approach

- In worst case, comparing two trees has a time complexity of O(n^3), where n is the number of nodes.
- This can be computationally expensive for large trees.

### React's Heuristic Approach:

- To achieve efficient diffing, React employs a heuristic approach that leverages the following optimizations:
    - **Key Prop:** React uses the `key` prop to uniquely identify nodes across different renders. This allows the algorithm to track node movements and updates more efficiently.
    - **Structural Assumptions:** React assumes that elements of different types will produce different trees, reducing the need for extensive comparisons.
    - **Depth-First Traversal:** React traverses the trees in a depth-first manner, focusing on the first child node before moving to siblings. This helps in early detection of changes and potential optimizations.
- Through these optimizations, React's diffing algorithm achieves a time complexity of O(n) in most practical scenarios, making it significantly faster than the naive approach.
- The space complexity of React's diffing algorithm is generally O(n), as it requires memory to store the virtual DOM trees and the diffing results.

## Example

Consider the following simple React component:

```jsx
function MyComponent() {
  const [count, setCount] = useState(0);

  return (
    <div>
      <p>You clicked {count} times</p>
      <button onClick={() => setCount(count + 1)}>Click me</button>
    </div>
  );
}

```

When the `count` state changes, React creates a new virtual DOM with the updated value. The diffing algorithm then compares the virtual DOM with the real DOM:

1. **Root Comparison:** Both roots are `div` elements, so the comparison moves to the child elements.
2. **Recursive Comparison:**
    - The `p` elements are compared. The text content has changed, so the real DOM element is updated.
    - The `button` elements are compared. They are the same type, so their props are compared. The `onClick` handler is the same, so no change is needed.

As a result, only the text content of the `p` element is updated in the real DOM, minimizing unnecessary DOM manipulations.

### **Key Points:**

- The diffing algorithm is essential for React's efficient DOM updates.
- It minimizes the number of DOM manipulations, leading to better performance and responsiveness.
- React uses heuristics and optimizations to achieve near-linear time complexity.
- The time complexity is typically O(n).
- Understanding the diffing algorithm can help you write React components that are more performant and efficient.