This post is published simultaneously on my personal blog: zhengyQ. club

Writing in the front

In React, the combination of Virtual Dom and Diff greatly improves rendering efficiency. The diff algorithm has changed from O(n^3) complexity to O(n) complexity

Virtual DOM and Diff

What is the virtual DOM?

The Virtual DOM is a programming concept. In this concept, the UI is held in memory in an idealized, or “virtual,” representation. In React, the result of render execution is not a real DOM node, but a lightweight JavaScript object. Like this:

<div class="box"> <span>hello world! </span> </div>Copy the code

The above code translates to this virtual DOM structure

{
    tag: "div",
    props: {
        class: "box"
    },
    children: [{
        tag: "span",
        props: {},
        children: ["hello world!"]]}}Copy the code

What is the Diff algorithm?

The diff algorithm compares the old and new virtual DOM, records the changes between them, and then updates the changes to the view. In fact, the previous diff algorithm, by recursing each node in a loop and then comparing, is O(n^3) complexity, n is the total number of nodes in the tree, so the performance is very poor.

The principle of dom – the diff

The DIff algorithm will compare the Virtual DOM before and after, so as to obtain patches. Patches can then be compared with the old Virtual DOM, and the new Virtual DOM can be obtained by applying the new Virtual DOM to the places where it needs to be updated. There is a very intuitive diagram on the Internet for your reference

To explain this picture: At this time, we delete the last P node and son2 node to obtain a new virtual DOM. The new VDOM will be compared with the old VDOM to obtain the Pathes object. After that, the old real DOM will be operated to obtain the new DOM.

Diff’s strategies

  • The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored.

  • Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree structures.

  • For a set of child nodes at the same level, they can be distinguished by unique ids.

React optimizes the tree Diff, Component Diff, and Element Diff algorithms based on the above three strategies.

tree diff

The first strategy, based on the react only carries on the comparison to the same level of node, the following figure, only to the DOM node in the box the same color comparison, when found the node does not exist, will delete the whole node and its children, not to compare, so you only need to traverse a, can finish comparing the DOM tree

What happens if DOM nodes are moved across hierarchies?

React simply takes into account the position changes of nodes at the same level. For nodes at different levels, only create and delete operations are performed. If A is completely moved under D and the root node finds that A is missing from the child node, it destroys A. Then D finds that it has an extra child node, and creates a new child node (including its own child node) as its child node. React diff is executed in this order: craete a -> create B -> create c -> delete A. When nodes are moved across hierarchies, they are not moved, but created and deleted. React does not recommend this operation because it affects React performance. When developing components, maintaining a stable DOM structure can help improve performance

component diff

React’s strategy for comparing components is also simple and efficient

  • If it is a component of the same type, continue to compare the virtual DOM tree using the same policy

  • If not, the component is judged to be a dirty Component and all child nodes under the entire component are replaced

  • React allows users to shouldComponentUpdate() to determine if the component needs to be diff, since it is possible for components of the same type to have their Virtual DOM unchanged

For example, when componentD is changed to componentG, react will determine that D and G are not components of the same type, even though the compoent structure is similar. Instead, it will delete D and recreate G and its child nodes. React performance is affected

element diff

React Diff provides three node operations when nodes are at the same level: insert, move, and delete

  • Insert: The new Component type is not in the old collection -> the new node needs to be inserted

  • Mobile: In old collection with new type component, and the element type can be updated, generateComponentChildren has called receiveComponent, this case prevChild = nextChild, you need to do mobile operating, You can reuse previous DOM nodes

  • Delete: The old component type is present in the new collection, but the corresponding element is different and cannot be reused or updated. It needs to be deleted, or the old Component is not in the new collection

For example, 🌰 : look at the following figure, the old set contains nodes A, B, C and D, and the updated set contains nodes B, A, D and C. At this time, the difference comparison between the new and old sets is conducted, and it is found that B is not equal to A, so B is created and inserted into the new set, and the old set A is deleted, and so on… React proposes an optimization strategy that allows developers to add unique keys to the same group of sub-nodes at the same level.

The case we described above is the case without A key. If there is A key (assuming that key is the name of each node in the figure above, for example, node A, which corresponds to key A), it will look like this:

Diff will use the key to discover that the nodes in the old and new sets are the same nodes, so there is no need to delete or create nodes. Instead, the nodes in the old set need to be moved to the nodes in the new set. React gives the diff result: B and D do nothing, while A and C move.

First to iterate over the new collection of nodes, through the only key to judge whether there is the same nodes from the set of new and old, if present, is for mobile operation, but before moving to the current node in the set of old position compared with lastIndex, if the location of the nodes of the current < lastIndex, mobile nodes is for operation, Otherwise, the operation is not performed. This is a kind of sequence optimization means, lastIndex has been updated, represent the old collection visited node in the right place (i.e., the location of the maximum), if the current access nodes from the set of new than lastIndex, explain the current access nodes in older collection node position than the last one, then the node will not affect the position of the other nodes, Therefore, there is no need to add to the difference queue, that is, no move operation is performed, only if the accessed node is smaller than lastIndex

_mountIndex is the current node location, and lastIndex is the reference location.

1. Take B from the new set, judge whether there is the same node in the old set, and judge whether the operation has been moved by comparing the node position. The position of B in the old set is _mountIndex=1, and lastIndex = 0. Child._mountIndex < lastIndex, so B is not moved. Prevchild._mountindex = math.max (prevchild._mountIndex, lastIndex), where prevchild.mountIndex indicates the position of B in the old set. PrevChild._mountIndex=nextIndex; prevChild._mountIndex=nextIndex; prevChild

2. Obtain A from the new set, judge that there is the same node A in the old set, and judge whether to move the node by comparing the position of the node. The position of A in the old set is A._mountIndex=0, and lastIndex=1, which meets the condition of child.mountIndex

Select D from the new set, judge whether there is the same node in the old set, and judge whether to move the node by comparing its position. D is in the old set d._mountIndex =3, and lastIndex=1, which does not meet the condition that child._mountIndex

4. The same is true for node C

What if the old and new sets are not just interchangeable? React Diff how to React diff? (The key of each node in the following figure is the corresponding node name)

1. Fetch B from the new set, judge whether there is the same node in the old set, find the position of B in the old set b. _mountIndex=1, and lastIndex=0, so no operation is performed on B; Update lastIndex=1, and update the position of B to b. _mountIndex=0 in the new set, nextIndex++ to enter the next node judgment

2. Take node E from the new set. Since there is no identical node in the old set, create a new node E; Update lastIndex=1, and update the position of E to the position in the new set, nextIndex++ to enter the judgment of the next node.

C._mountIndex=2, lastIndex=1, c. _mountIndex > lastIndex, so C is not moved. Update lastIndex=2, and update the position of C to the position in the new set, nextIndex++ to proceed to the judgment of the next node.

A._mountIndex=0, lastIndex=2, then A._mountIndex < lastIndex, move A. Update lastIndex=2, and update the position of A to the position in the new set, nextIndex++ to enter the judgment of the next node.

5. When the diff of all nodes in the new set is completed, the old set needs to be cycled finally to determine whether there are nodes that are not in the new set but still exist in the old set. Such node D is found, so node D is deleted and the diff is complete.

conclusion

React suggests adding unique keys for optimization based on diff’s strategy. There is a problem:

What’s wrong with using index as the key?

In React, if the key is the same as the index, the last item in the array may be moved forward. In react, if the key is the same, it is treated as the same component, but the two components are not. There will be some problems that we don’t want to see, so we have to consider the value of the key to determine

The last

This article describes the virtual DOM and diff algorithm in detail, we need to distinguish the key without key is how to compare, but also know why the time complexity has been greatly improved, etc. ~ if there is something wrong with the article, please also point out ~ we learn together, common progress ~ ~ ~

If you want to receive the article push faster, welcome to pay attention to my public number “Web front-end diary” ~

Refer to the article

  • React Diff – React Diff

  • React source code analysis and implementation (3) : implementation of DOM Diff