scenario

The structural differences of the two trees were calculated and converted

In this paper, n refers to the number of nodes

Traditional Diff algorithm

Solution: Iterate over each node

Traditional diff

As shown above, node A of the left tree is compared as follows:

A -> E, A -> D, A -> B, A -> C, A -> A

Then other nodes B, C, D and E of the left tree are compared with each node of the right tree, and the algorithm complexity can reach O(n^2).

After finding the difference, we also need to calculate the minimum transformation mode, the principle of which I did not look carefully, and finally achieved the algorithm complexity is O(n^3).

It takes O(n²) complexity to compare all the nodes in the two trees one by one. During the comparison process, it is found that the old node is not found in the new tree, so it needs to delete the old node. The time complexity of deleting a node in a tree (finding a suitable node to be placed at the deleted location) is O(n), and the time complexity of adding a new node is also O(n). Combined, the complexity of the two trees is O(n³).

Optimized Diff algorithm

The diff algorithm of the virtual DOM of Vue and React is roughly the same, and its core is based on two simple assumptions:

  1. Two identical components produce a similar DOM structure, and different components produce different DOM structures
  2. A group of nodes at the same level that can be distinguished by a unique ID

The (optimized) Diff three-point strategy:

  • The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored.
  • Two components of the same type will generate similar tree structures, and two components of different types will generate different tree structures.
  • For a set of self nodes at the same level, they can be distinguished by unique ids.

That is, comparisons are made only at the same level, not across levels

React optimizes Diff algorithm

React performs the following algorithm optimization based on the above optimized DIFF three-point strategy

  • tree diff
  • component diff
  • element diff
tree diff

React performs a hierarchical comparison of tree algorithms. React uses updateDepth to level the Virtual Dom tree. Only nodes in the same color box are compared, that is, all children of the same parent node. If a node does not exist, both the node and its children are deleted. This is done by traversing the DOM tree once, completing the comparison of the entire DOM tree

Hierarchical comparison IMG

If it is a move across hierarchies, see figure

Operate img across hierarchies

When the root node finds that A has disappeared, it deletes A and its children. When A node A is found on D, A node (including its children) is created as A child node

Therefore, when moving across hierarchies, React does not simply move, but deletes and creates, which affects React performance. So try to avoid cross-level operations. (for example: controlling display to show and hide without actually adding and removing dom)

component diff
  • If it is a component of the same type, compare it directly to the Virtual Dom Tree
  • If the component is not of the same type, all the children of the component are directly replaced
  • If the type is the same, but maybe the virtual DOM hasn’t changed, we can use shouldComponentUpdate() to determine if we need to diff

component vs img

If component D and component G, if the type is different but the structure is similar. In this case, react will delete D and create G because the type is different. So we can use shouldComponentUpdate() to return false without diff.

There is a new life cycle for Act15, 16

So: Component diff is optimized using shouldComponentUpdate()

element diff

Element Diff involves three operations: insert, move, and delete

Img without key

React compares the old set with the new set and finds that B in the new set is not equal to A in the old set, so A is deleted and B is created, and so on until D in the old set is deleted and C in the new set is created. =

React allows you to add keys to differentiate between these and render performance bottlenecks

Img using key

React first iterates through the new set, for(name in nextChildren), uses the unique key to determine whether the old set has the same node, if not, creates the node, if (preChild === nextChild) moves the node

Before moving, the position of the node in the new set will be compared with that in the old set lastIndex. If (child._mountIndex < lastIndex) moves the node, otherwise the move will not be carried out. This is a sequential movement optimization. Move only if the position in the new set is less than that in the old set.

If there is no node in the new set but in the old set during the traversal, the operation will be deleted

So: Element Diff is diff optimized with unique keys.

Summary: 1. Minimize cross-level operations in React. ShouldComponentUpdate () can be used to avoid repeating renders in React. 3. Add unique keys to reduce unnecessary rerendering

Vue optimization Diff

Vue2.0 adds the Virtual DOM and shares the same diff optimization principles as React

The difference is that diff calls the patch function to modify the real DOM just like patching

  • patchVnode
  • updateChildren

UpdateChildren is the core process of Vue DIff, which can be summarized as follows: oldCh and newCh each have two starting and ending variables, StartIdx and EndIdx. Their two variables are compared with each other in four ways. If none of the four comparisons match, if the key is set, the comparison will be performed with the key. During the comparison, the variable will be moved to the middle, and the comparison will end as soon as StartIdx>EndIdx indicates that at least one of oldCh and newCh has been traversed

Vue 2.x vs Vue 3.x

The core Diff algorithm of Vue2 adopts the algorithm of double-end comparison, which starts from the two ends of the old and new children, finds the reusable node with the help of key value, and then carries out relevant operations. Compared with the React Diff algorithm, it can reduce the number of nodes to be moved, reduce unnecessary performance loss, and be more elegant

Vue3. X draws on ivI algorithm and Inferno algorithm. The type of VNode is determined when VNode is created, and the bit operation is used to determine the type of a VNode in the process of mount/patch. On this basis, combined with the core Diff algorithm, the performance is improved compared with Vue2. The actual implementation can be combined with Vue3. X source code to see

The algorithm also uses the idea of dynamic programming to solve the longest recursive subsequence

Finally, I hope you can realize your dream as soon as possible!!

Welcome to exchange ~

  • Wechat official account: Mr. Lian has cat disease
  • Wechat id: Wanderlian
  • Nuggets: Obsidian
  • Personal blog: lianpf.github. IO /