First, Diff algorithm

The Diff algorithm of Vue is an efficient algorithm to compare tree nodes of the same layer, which avoids layer by layer traversal of the tree and reduces time complexity

The characteristics of

  1. Peer comparison, not cross-level, breadth-first traversal
  2. Diff refers to the two sides of the cycle coming closer to the center

Second, Vue Diff algorithm

The core of Vue’s virtual DOM diff lies in the patch process, and the core algorithm adopts the double-pointer algorithm.

2.1 Mark the start and end positions of the old and new VNodes

let oldStartIndex = 0;
let oldEndIndex = oldChildren.length-1;
let oldStartVnode = oldChildren[0];
let oldEndVnode = oldChildren[oldEndIndex];

let newStartIndex = 0;
let newEndIndex = newChildren.length-1;
let newStartVnode = newChildren[0];
let newEndVnode = newChildren[newEndIndex];
Copy the code

2.2 Mark the node position and cycle the node

  • If the current oldStartVnode and newStartVnode nodes are the same, the new node is directly used to reuse the old node to reuse patchVnode. Update oldStartVnode, newStartVnode, oldStartIndex++, and newStartIndex++;
  • If the current oldEndVnode and newEndVnode nodes are the same, the new node is directly used to reuse the old node, and the patchVnode is reused to update oldEndVnode, newEndVnode, oldEndIndex– and newEndIndex–.
  • If the current oldStartVnode and newEndVnode nodes are the same, the new node is directly used to reuse the old node, and then the patchVnode is moved to oldEndVnode. Update oldStartVnode, newEndVnode, oldStartIndex++, and newEndIndex–
  • If the current oldEndVnode and newStartVnode nodes are the same, the new node is directly used to reuse the old node for patchVnode reuse. Update oldStartVnode, newStartVnode, oldEndIndex–, and newStartIndex++;
  • If the preceding procedure is not met, perform key comparison. If the conditions are met, patchVnode is made and the DOM is moved to the front of oldStartVnode. If not found, recreate

2.3 Recursive processing

Vue Diff diagram

  • Step 1: Create four Pointers: start pointer and end pointer for the old VNode and start pointer and end pointer for the new VNode
  • Step 2: Compare the start pointer of the old VNode with the start pointer of the new VNode, namely, A and E, to find that the node is not the same
  • Step 3: Compare the end pointer of the old VNode with the end pointer of the new VNode, that is, D and F, which are still different nodes
  • Step 4: Compare the start pointer of the old VNode with the end pointer of the new VNode, that is, A and F, which are not the same node
  • Step 5: Compare the end pointer of the old VNode and the start pointer of the new VNode, E and D, which are not the same node
  • Step 6: Through the above four comparison methods are not the same node, the following in the old VNode node to find whether the same node with E node
  • Step 7: If there is no E node in the old VNode, a new E node is inserted in front of the old VNode
  • Step 8: After the operation of the first node is completed, the pointer moves back, continue to compare, repeat steps 2 to 7, the result is: add/delete/move
  • Step 9: When the same node is found, the patchVnode method is used to conduct a more detailed Diff algorithm for the two nodes

disadvantages

The DOM diff of vue2 was completely rewritten because of the performance cost of manipulating the DOM while diff was being performed. There will be an article on the principle of Vue3DOM Diff later

conclusion

Each Diff calls the updateChildren method to compare, and so on, until all the children of the old VNode are compared to the new VNode. It’s a deep recursive traversal that also manipulates the DOM on the side.