The Diff algorithm

Diff algorithm is the difference search algorithm.

Vue’s DIff policy

  • The traditional time complexity of calculating the difference between two trees is O(n^3), which obviously costs a lot (each node of the old tree traverses the node of the new tree until the corresponding node of the new tree is found. So the process is O(n^2), and then after finding the difference, calculate the shortest change distance and then change the node, which is O(n^3).
  • Vue uses the same layer comparison of nodes in the tree, so the time complexity is O(n), which is relatively efficient

What strategy is the Vue Diff algorithm based on

  • The movement of DOM nodes across hierarchies in Web UI is extremely rare and can be ignored (tree-diff)
  • Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree nodes (Component diff).
  • For a group of children at the same level, they can be distinguished by unique ids (element-diff)

The reason and purpose of Vue Diff algorithm

Vue Diff algorithm is the product of virtual DOM introduced in VUE2, which is designed to calculate the minimum changes that need to be changed by comparing the old and new nodes. Core idea: reuse old nodes as much as possible

Vue2 diff process

New and old nodes are different

  • Create a new node and insert it into the DOM with the current old node in mind
  • Delete old nodes

The new and old nodes are the same

  • Returns if the two nodes are referenced identically
  • The interior is filled with new and old text nodes updating the content of text nodes
  • Only new nodes have child nodes removed and old nodes add content in batches
  • Only the old ones have children removed in batches
  • Both have child nodes and execute differentlyupdateChildrenUpdate child nodes

updateChildren

According to the habit of our daily operation of nodes, mobile addition and deletion, Vue2 compares the two child nodes using a double-terminal comparison method, and tries to reuse the old node as much as possible by comparing the old node in the position of the new node.

  • Head to tail to tail
  • Cross comparisons head to tail
  • New nodes are available to be added
  • Old nodes are available to be removed

The DIFF flow of Vue3

Different old and new nodes

  • Destroy old nodes
  • Mount different nodes according to the type of the new node

Processing components

  • Determine whether the child components need to be updated
  • Recursively execute subrenderers of subcomponents to update if needed
  • Otherwise, just update some vNode properties and let child component instances keep references to component VNodes

Processing elements

  • Update props
  • Update child nodes There are three types of child nodes plain text Vnode array and empty

The old node is plain text:

  • The new node is also a simple substitution
  • The new node is empty and deleted
  • The new node is a batch addition of Vnode arrays

The old node is empty:

  • If the new child node is plain text, add the new text node under the parent container of the old child node.
  • If the new child node is also empty, then nothing needs to be done, right
  • If the new child node is a vNode array, add more children to the parent container of the old child node.

The old child nodes are vNode arrays:

  • If the new child node is plain text, delete the old child node first, and then add the new text node under the parent container of the old child node.
  • If the new child node is empty, delete the old child node
  • If the new child node is also a VNode array, then you need to do the full diff of the old and new child nodes, which is the most complicated case, using the core diff algorithm internally

Both old and new nodes are arrays

The comparison between the old and new arrays is accomplished by updating, deleting, adding and removing nodes. The core of diff algorithm aims to complete the updating of child nodes at a low cost and solve the series of operations to generate DOM of new child nodes. Process:

  • Synchronous head node
  • Synchronous tail node
  • Add a new node. The new child node is free
  • Delete unnecessary nodes. The existing nodes are available
  • Processing unknown subsequences

Processing unknown subsequences

Sometimes we encounter complex unknown subsequence: for the operations of move, delete, add and update, the most complex is the move operation. The core of Vue for unknown subsequence is to find the minimum value that needs to be moved through the longest increasing subsequence.

Contrast old and new subsequence is needed in finding process, so we must traverse a sequence, if in the process of traversal sequence old need to determine whether a node in the new subsequence exist, this will require a double loop, and the complexity of the double loop is O (n2), in order to optimize this complexity, we can use a space in the thinking of time, index figure, Reduce the time complexity to O(n).

Build index map

  • Build the index graph in the new subsequence based on the key in the for loop
  • Then create a mapping between the old and new subsequence indexes to determine the longest increasing subsequence,
  • Then it traverses the old subsequence in positive order to see if it is in the index graph of the new subsequence. If it is no longer in the index, it will be deleted. If it is in the longest increasing subsequence, it does not need to move
  • Then, the new node is marked in the traversal process. For the identifier 0 that is not searched, the operation needs to be added