Core Concepts of Vue's Diff Algorithm

When component state changes, Vue leverages Virtual DOM and an optimized diff algorithm to minimize the number of DOM operations, improving overall application performance.

The diff algorithm is the core of any Virtual DOM implementation. Its primary job is to compare differences between the old and new Virtual DOM trees, then apply only the detected changes to the real DOM tree. Vue's diff algorithm is built around two core assumptions:

1. The main performence bottleneck of DOM operations in web apps comes from repaints and reflows triggered by DOM access and modification.
2. Adjacent DOM nodes almost always share the same parent element, so batching changes to the parent reduces the total number of DOM operations needed.

Based on these assumptions, Vue's diff algorithm follows this core workflow:

1. First compare the two root nodes. If they are different node types, replace the entire old root with the new root directly.
2. If the root nodes are the same type, move on to compare their child nodes, using an optimized double-ended comparison strategy. By comparing from both the head and tail of the old and new child node lists at the same time, this strategy maximizes reuse of existing DOM nodes and cuts down on unnecessary operations.
3. If one of the node lists is fully processed while the other still has remaining unmatched nodes, add all remaining nodes to the real DOM in a single batch operation.

To further optimize node matching, Vue requires developers to add a key attribute to dynamic list nodes. The key lets the diff algorithm correctly identify which nodes are stable and can be reused, avoiding unnecessary node re-creation.

A simple example to demonstrate diff behavior:

<div id="demo-app">
  <ul>
    <li v-for="item in itemList">{{ item }}</li>
  </ul>
  <button @click="addItem">Add New Item</button>
</div>

We initialize an empty list and a method to add new entries:

new Vue({
  el: '#demo-app',
  data: {
    itemList: []
  },
  methods: {
    addItem() {
      this.itemList.push(`Item ${this.itemList.length + 1}`);
    }
  }
})

After adding two items, the old Virtual DOM structure looks like this:

{
  type: 'div',
  children: [
    {
      type: 'ul',
      children: [
        { type: 'li', text: 'Item 1' },
        { type: 'li', text: 'Item 2' }
      ]
    },
    { type: 'button', text: 'Add New Item' }
  ]
}

When we click the buttton to add a third item, the new Virtual DOM becomes:

{
  type: 'div',
  children: [
    {
      type: 'ul',
      children: [
        { type: 'li', text: 'Item 1' },
        { type: 'li', text: 'Item 2' },
        { type: 'li', text: 'Item 3' }
      ]
    },
    { type: 'button', text: 'Add New Item' }
  ]
}

The diff algorithm first confirms the root nodes match, then compares child nodes. It detects that the first two list nodes are identical between the old and new trees, reuses the existing real DOM nodes for these entries, and only creates and inserts one new node for the third item.

Double-Ended Comparison Explained

Vue's double-ended comparison is an optimized approach over the traditional top-down single-ended diff algorithm, designed to handle large Virtual DOM trees more efficiently. Traditional diff algorithms traverse the tree from root down, comparing every node one by one even when most nodes are unchanged, leading to unnecessary performance overhead for large trees.

Double-ended comparison solves this by starting comparisons from both the head and tail of the old and new child node lists simultaneously. This lets the algorithm quickly find matching reusable nodes and avoid unnecessary comparisons on unchanged sections. The algorithm follows these core steps:

1. Start comparing nodes from the head of both the old and new node lists
2. If no match is found at the current head position, shift to comparing nodes from the tail of both lists
3. If no match is found at the current tail position, narrow down the range of nodes that require full matching
4. Once the change range is confirmed, apply all required updates to the real DOM.

For example, when adding a fourth item to our list, the new VDOM has an extra node at the tail of the child list:

{
  type: 'div',
  children: [
    {
      type: 'ul',
      children: [
        { type: 'li', text: 'Item 1' },
        { type: 'li', text: 'Item 2' },
        { type: 'li', text: 'Item 3' },
        { type: 'li', text: 'Item 4' }
      ]
    },
    { type: 'button', text: 'Add New Item' }
  ]
}

Double-ended comparison will first match all existing nodes starting from the head, quickly identify the new extra node at the tail, and insert it with minimal extra comparison work. Through this optimized strategy, Vue can handle large Virtual DOM structures much more efficiently with out sacrificing performance.