The Principles of Virtual DOM Diff Algorithm

Principles of Virtual DOM Diff Algorithm

The Virtual DOM diff algorithm is one of the core mechanisms of front-end frameworks. Its primary role is to efficiently compare the differences between the old and new Virtual DOM trees and calculate the minimal set of DOM operations needed for an update.

1. Why is a Diff Algorithm Needed?

  • Direct manipulation of the real DOM is very performance-intensive (reflow and repaint).
  • Regenerating the entire Virtual DOM tree when state changes is low-cost.
  • However, it is necessary to precisely identify the changed parts to avoid updating the real DOM in full.

2. Basic Principles of the Diff Algorithm

Same-Level Comparison Principle

  • Only compares nodes at the same level; does not track across different levels.
  • If node types differ, the entire subtree is destroyed and rebuilt.
  • This optimizes the time complexity from O(n³) to O(n).

Example:

// Old tree
<div>
  <span>Hello</span>
</div>

// New tree  
<section>  // Different type, the entire div subtree is destroyed
  <span>Hello</span>
</section>

3. Specific Process of Node Comparison

Step 1: Compare Node Types

  • If the tag names differ (div → span), replace the entire node directly.
  • If the tag names are the same, proceed to the attribute comparison stage.

Step 2: Compare Attributes

  • Traverse the old and new attribute sets to identify:
    • Attributes that need to be added
    • Attributes that need to be deleted
    • Attributes that need to be updated
  • Only update the changed attributes to avoid unnecessary operations.

Step 3: Compare Child Nodes (Core Challenge)
This is the most complex part of the diff algorithm. React employs a "key optimization" strategy:

Without keys (poorer performance):

  • Compare in order: old first vs new first, old second vs new second...
  • If positions change, it can lead to unnecessary rebuilds.

With keys (recommended practice):

  • Establish a correspondence between old and new nodes via keys.
  • Even if positions change, the same node can be correctly identified.
  • Update positions by moving rather than rebuilding nodes.

4. Specific Implementation Ideas of the Diff Algorithm

Dual-pointer Comparison Method:

  1. Set two pointers (head pointer, tail pointer) for both the old and new child node arrays.
  2. Prioritize comparisons: new head vs old head, new tail vs old tail (common cases).
  3. If no match is found, attempt to locate the new head node in the old array.
  4. If a reusable node is found, update by moving it rather than rebuilding.

5. Practical Application Example

// Old list
<ul>
  <li key="a">A</li>
  <li key="b">B</li> 
  <li key="c">C</li>
</ul>

// New list - order changed
<ul>
  <li key="c">C</li>
  <li key="a">A</li>
  <li key="b">B</li>
</ul>

Diff process:

  1. Identify that the node with key="c" has moved from the third position to the first.
  2. Update by moving the DOM node instead of recreating it.
  3. Significantly improves list rendering performance.

6. Summary of Key Points

  • The diff algorithm reduces complexity through hierarchical comparison.
  • The key attribute helps accurately identify node identity.
  • The goal is to minimize DOM operations and improve performance.
  • Understanding this principle helps in writing high-performance React/Vue code.

This mechanism enables modern front-end frameworks to efficiently handle complex UI updates and serves as the cornerstone of framework performance optimization.