How React's Fiber Architecture and Diff Algorithm Turn O(n³) Tree Comparisons Into 16ms Slices

Deep Understanding of React Core: Fiber Mechanism and Diff Algorithm

Preface

As the mainstream framework for modern frontend development, React's efficient performance relies on two core mechanisms: Fiber architecture and Diff algorithm. This article will start from the underlying principles and help you thoroughly understand what these two are and how they work together.

After reading this article you will gain:

Understanding the design intent of Virtual DOM
Thoroughly grasping why Fiber architecture emerged and what problems it solves
Mastering the three-layer strategy and core logic of the Diff algorithm
Understanding the relationship between the event loop and React scheduling

1. Everything Starts with Virtual DOM

1.1 What is Virtual DOM?

After Babel transpilation, JSX becomes React.createElement calls:

// What you write
const App = (
  <div className="container">
    <h1>Hello</h1>
  </div>
);

// After Babel transpilation
const App = React.createElement(
  'div',
  { className: 'container' },
  React.createElement('h1', null, 'Hello')
);

createElement ultimately returns a plain JavaScript object, which is a Virtual DOM node:

{
  type: 'div',
  props: {
    className: 'container',
    children: [
      {
        type: 'h1',
        props: {
          children: [
            {
              type: 'TEXT_ELEMENT',
              props: { nodeValue: 'Hello', children: [] }
            }
          ]
        }
      }
    ]
  }
}

1.2 Why Do We Need Virtual DOM?

The core reason can be summed up in one sentence: Manipulating the real DOM is too expensive.

Real DOM nodes are associated with a large number of properties behind the scenes, and every modification can trigger browser repaints and reflows. Virtual DOM, on the other hand, is just a lightweight JS object, making creation and comparison extremely cheap.

The entire workflow:

You change data (setState) 
  → React generates a new VDOM object (JS object, very low cost)
  → React compares old and new VDOM, only updating changed nodes (Diff algorithm)
  → React maps the differences to the real DOM (batch updates, reducing repaints and reflows)

Developers only need to focus on data logic; React handles all DOM additions, deletions, and modifications for you.

2. Why Did Fiber Emerge? — The Crisis of Stack Reconciler

2.1 The Original Recursive Approach

React's early reconciler was called Stack Reconciler, and its core logic was very simple: perform a recursive traversal of the Virtual DOM tree, comparing and updating as it went.

function reconcile(parentDOM, oldVDOM, newVDOM) {
  if (oldVDOM == null) {
    // Add new node
    parentDOM.appendChild(createDOM(newVDOM));
  } else if (newVDOM == null) {
    // Delete node
    parentDOM.removeChild(oldVDOM.dom);
  } else if (oldVDOM.type !== newVDOM.type) {
    // Replace node
    parentDOM.replaceChild(createDOM(newVDOM), oldVDOM.dom);
  } else {
    // Recursively compare child nodes...
  }
}

2.2 The Fatal Flaw of Recursion

This recursive approach has two major problems:

Problem	Impact
Uninterruptible	Once reconciliation starts, it must recursively traverse the entire tree before stopping
Long-term main thread occupation	JS is single-threaded; occupying the main thread continuously blocks user interactions, animations, and scrolling

Imagine this scenario: a complex SPA page with a VDOM tree of thousands of nodes. When you trigger a setState, React needs to recursively traverse these thousands of nodes for comparison — this process can take tens or even hundreds of milliseconds. During this time:

User clicks a button → frozen, unresponsive
Page animations, scrolling → dropped frames, stuttering
Typing in an input field → noticeable delay

This is the performance bottleneck caused by the uninterruptible nature of Stack Reconciler.

2.3 Review of Browser Rendering Mechanism

To understand Fiber's solution, let's first review how many tasks the browser's main thread has to handle:

Browser Main Thread Task List:
├── Parse HTML → Generate DOM tree
├── Calculate CSS → Generate CSSOM tree
├── Combine → Generate Render Tree
├── Layout → Calculate node positions and dimensions
├── Paint → Draw pixels onto the screen
├── Execute JavaScript
└── Respond to various events (clicks, scrolls, input...)

All tasks are queued for execution on the same main thread. If JS execution takes too long, the subsequent rendering tasks have to wait → what the user sees is stuttering.

3. Fiber Mechanism: Interruptible Rendering

3.1 Core Idea

The core idea of Fiber architecture can be summed up in eight words: Task sharding, interruptible and resumable.

Instead of traversing the entire VDOM tree in one go, break the whole tree into small Units of Work, processing only one unit at a time, and yield main thread control back to the browser after processing. If the browser is free, continue to the next unit; if the browser needs to handle higher-priority tasks (like user clicks), interrupt first.

// Pseudocode: Fiber core loop
let nextUnitOfWork = null;

function workLoop(deadline) {
  // Is there idle time left in the current frame?
  while (nextUnitOfWork && deadline.timeRemaining() > 0) {
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
  }
  
  if (nextUnitOfWork) {
    // Work remaining, continue in the next frame
    requestIdleCallback(workLoop);
  } else {
    // All work complete, commit updates to DOM
    commitRoot();
  }
}

requestIdleCallback(workLoop);

requestIdleCallback is a browser-provided API that calls the callback we pass in when the browser is idle. React uses this mechanism to achieve Time Slicing.

3.2 Fiber Node: A Brand New Unit of Work

In Fiber architecture, each component corresponds to a Fiber node, which is an enhanced VDOM node:

// Fiber node structure (simplified)
{
  // ========== Node Basic Information ==========
  type: 'div',            // Node type (DOM tag / function component / class component)
  props: { ... },         // Node properties, including children
  
  // ========== Association Information ==========
  dom: domNode,           // Corresponding real DOM

  // ========== Tree Structure Links ==========
  return: parentFiber,    // Parent node
  child: firstChildFiber, // First child node
  sibling: nextSibling,   // Next sibling node

  // ========== Side Effects ==========
  effectTag: 'PLACEMENT | UPDATE | DELETION', // Mark operation type
  
  // ========== Scheduling Related ==========
  alternate: oldFiber,    // Points to the Fiber from the previous render (double buffering mechanism)
}

The key lies in those three pointers child, sibling, return — they transform a tree structure into a linked list structure, allowing traversal to be "paused" and "resumed".

         div (parent)
         /   |   \
        /    |    \
     h1 -- p -- span   (sibling chain: h1.sibling → p.sibling → span)
    /        |
  text     text

Traversal order (depth-first):
div → h1 → text → p → text → span → back to div → end

Traversal rules:

If there is a child node → enter child
If there is no child node → find sibling
If there is no child node and no next sibling → go back to return (uncle node)

The advantage of this linked list traversal method is: at any point when paused, the nextUnitOfWork pointer clearly points to the next node to be processed, and when resumed, it continues directly from the pointer position.

3.3 Double Buffering Mechanism

Another clever design of Fiber architecture: Draw completely, then swap.

Work process:
┌─────────────────────────────────┐
│  current Fiber Tree (currently displayed on screen) │
└─────────────────────────────────┘
              ↓
┌─────────────────────────────────────────┐
│  workInProgress Fiber Tree (new tree being built) │
│  - Each node points back to the old tree's corresponding node via alternate    │
│  - Compare old and new, mark effectTag (add/update/delete)       │
│  - Commit all at once after build is complete                   │
└─────────────────────────────────────────┘
              ↓
     commitRoot()  →  Update DOM all at once

This ensures:

The build process does not affect the current display: users always see the current tree
Atomicity: either all updates are applied, or none are (no half-finished state)

3.4 Interruptible ≠ Interrupt Anytime

Fiber's commit phase is uninterruptible because DOM updates must ensure consistency. The entire process is divided into two phases:

Phase	Interruptible?	What it does
Render / Reconciliation	✅ Interruptible	Traverse Fiber tree, compare old and new, mark effectTag
Commit	❌ Uninterruptible	Apply marked changes to the real DOM all at once

4. Diff Algorithm: How to Smartly Compare Old and New VDOM?

The goal of the Diff algorithm is to find the minimum difference between two VDOM trees and then update the DOM with the minimum cost.

4.1 Theoretical Basis

A complete comparison of two trees is an O(n³) problem — if done by brute force, 1000 nodes would mean 1 billion operations, completely infeasible.

React made three key assumptions based on real-world frontend scenarios, reducing the complexity to O(n):

Assumption	Strategy
Elements of different types produce different trees	Tree Diff: Cross-level movement is extremely rare; if types differ, destroy and rebuild directly
Identify node stability via `key`	Element Diff: Reuse nodes via key to avoid destruction and recreation
Elements of the same type have similar structure	Component Diff: Reuse components of the same type, directly replace different types

4.2 Tree Diff: Compare by Layer

React does not perform cross-level node comparison, only compares nodes at the same level:

Old tree:               New tree:
  div                  div
  ├── A      →        ├── B        (A → B: different types, delete A, create B)
  └── B               └── C        (B → C: different types, delete B, create C)

What if the entire subtree of A is moved to another position?
React's handling:
  Old position: delete A and its entire subtree
  New position: recreate A and its entire subtree

Why not compare across layers? Because in actual development, cross-level DOM movement is extremely rare. To reduce complexity by over 90%, this trade-off is very worthwhile.

4.3 Component Diff: Same Type Reuse, Different Type Rebuild

// Different types → rebuild directly
<div>
  <MyComponent />     →  <OtherComponent />
</div>
// Result: unmount MyComponent, mount OtherComponent

// Same type → reuse, only update props
<div>
  <MyComponent title="A" />  →  <MyComponent title="B" />
</div>
// Result: component instance retained, only triggers componentWillReceiveProps → render

4.4 Element Diff: Same-Level Child Node Comparison (Core Difficulty)

This is the most ingenious part of the Diff algorithm, and also the most error-prone part.

Without key:

Old: A B C D
New: B A D C

React compares position by position:
  Position 0: A vs B → different types → delete A, insert B
  Position 1: B vs A → different types → delete B, insert A
  Position 2: C vs D → different types → delete C, insert D
  Position 3: D vs C → different types → delete D, insert C

Result: 4 deletions + 4 insertions = 8 DOM operations
Just a change in order, but it's a full rebuild 😱

With key:

Old: {key:'A'} {key:'B'} {key:'C'} {key:'D'}
New: {key:'B'} {key:'A'} {key:'D'} {key:'C'}

React matches using key:
  1. Traverse new array, find nodes with the same key in the old array
  2. key:'B' was at position 1 in old array → just move to position 0
  3. key:'A' was at position 0 in old array → just move to position 1
  4. key:'D' was at position 2 in old array → just move to position 2
  5. key:'C' was at position 3 in old array → just move to position 3

Result: 4 move operations, 0 destructions and recreations!

This is why React consistently emphasizes not to use index as key:

// ❌ Wrong: using index as key
{list.map((item, index) => <Item key={index} data={item} />)}

// When you insert an item at the head of the list:
// Old: key:0=A, key:1=B, key:2=C
// New: key:0=D, key:1=A, key:2=B, key:3=C
// 
// React comparison:
//   key:0: A vs D → different types, destroy and rebuild (actually just position changed)
//   key:1: B vs A → different types, destroy and rebuild
//   key:2: C vs B → different types, destroy and rebuild
//   key:3: - vs C → add new
// Just inserting one item turned into destroying and rebuilding everything!

// ✅ Correct: using unique id as key
{list.map(item => <Item key={item.id} data={item} />)}

4.5 Overall Flow of the Diff Algorithm

beginWork(fiber):
  1. Compare if fiber.type is the same as the old node
     ├── Different types → mark DELETION + PLACEMENT (skip diff)
     └── Same type → enter diff
        ├── Is DOM element → diffProps (compare properties)
        │    ├── New/changed properties → UPDATE
        │    └── Deleted properties → remove
        └── Is component → render component, get new child elements
            └── reconcileChildren(fiber, newChildren)
                ├── Traverse newChildren
                ├── Match with oldChildren via key
                ├── Mark PLACEMENT / DELETION / UPDATE
                └── Build new Fiber child linked list

5. Fiber + Diff: A Match Made in Heaven

Let's string together the complete journey of a setState:

1. setState triggers
        ↓
2. Create Update object, put into the Fiber's updateQueue
        ↓
3. Starting from the Fiber that triggered the update, go up to find root
        ↓
4. Enter Render phase starting from root (interruptible)
    │
    ├── beginWork: Traverse each Fiber node
    │   ├── Compare old and new props → Diff Props
    │   ├── Compare old and new child nodes → Diff Children
    │   └── Generate effectTag marks (PLACEMENT / UPDATE / DELETION)
    │
    └── completeWork: Build effectList (side effect linked list)
        │
5. Commit phase (uninterruptible)
    ├── before mutation: execute getSnapshotBeforeUpdate
    ├── mutation: operate on real DOM according to effectTag
    └── layout: execute componentDidMount / componentDidUpdate / useEffect
        ↓
6. User sees the updated page

Core relationship summary:

Fiber (Architecture) + Diff (Algorithm) = Reconciliation

Fiber answers "when to do it": sharding, scheduling, interruptible
Diff  answers "what to do": find the minimum change set
The reconciler merges them together to achieve efficient, non-blocking UI updates

6. Summary

Concept	Core Role	One-Sentence Summary
Virtual DOM	JS object simulating DOM	Makes DOM operations cheap
Fiber Architecture	Time slicing + linked list traversal	Makes the rendering process interruptible, resumable, and schedulable
Diff Algorithm	Tree + Component + Element three-layer strategy	Finds the minimum update set at O(n) cost
Event Loop	Macro task / Micro task mechanism	Fiber uses idle time to execute low-priority tasks

Understanding React is understanding the design philosophy of modern frontend frameworks:

With limited resources (single thread), through ingenious architectural design (Fiber) and algorithm optimization (Diff), achieve a smooth user experience. React does not pursue doing everything at once, but accumulates small gains — each frame only does a little, but ultimately converges into a complete, smooth UI.

Comments

Top 1 from juejin.cn, machine-translated. The original thread is authoritative.

一路上__有你

This explanation is problematic. If you simply add one array element, it won't destroy and rebuild; it will just reuse key=0 and change the props. Also, React doesn't recommend using index as key not because all components get destroyed and rebuilt, but because React will incorrectly reuse existing Fibers, causing component instances and state to bind to the wrong data.