React: Diff algorithm

Where does the React diff algorithm evaluate?

The diff algorithm is calculated in render.

The React diff algorithm differs from the traditional diff algorithm:

let result = [];
// Compare leaf nodes
const diffLeafs = function (beforeLeaf, afterLeaf) {
    // Get the length of the larger node tree
    let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
    // loop over
    for (let i = 0; i < count; i++) {
        const beforeTag = beforeLeaf.children[i];
        const afterTag = afterLeaf.children[i];
        // Add the afterTag node
        if (beforeTag === undefined) {
            result.push({ type: "add".element: afterTag });
            // Delete the beforeTag node
        } else if (afterTag === undefined) {
            result.push({ type: "remove".element: beforeTag });
            // When the node name changes, delete the beforeTag node and add the afterTag node
        } else if(beforeTag.tagName ! == afterTag.tagName) { result.push({type: "remove".element: beforeTag });
            result.push({ type: "add".element: afterTag });
            // Change the node when the node is unchanged and the content is changed
        } else if(beforeTag.innerHTML ! == afterTag.innerHTML) {if (beforeTag.children.length === 0) {
                result.push({
                    type: "changed".beforeElement: beforeTag,
                    afterElement: afterTag,
                    html: afterTag.innerHTML
                });
            } else {
                // Recursive comparisondiffLeafs(beforeTag, afterTag); }}}return result;
}
Copy the code

React diff algorithm

The following describes the three strategies of the React Diff algorithm. (1) DOM nodes are rarely moved across hierarchies in the Web UI and can be ignored. (2) Two components with the same class will generate similar tree structures. (3) For a group of child nodes at the same level, they can be distinguished by unique IDS.

React optimizes tree Diff, Component Diff, and Element Diff for the above three policies. 2. The diff granularity

tree diff

React controls the Virtual DOM tree hierarchies and only compares DOM nodes of the same hierarchy, that is, all child nodes under the same parent element. When the node is found to be no longer existing, all child nodes under the node are deleted. No more comparisons. In this way, you only need to traverse the DOM tree once to complete the comparison of the entire tree. The complexity becomes O(n); Question: How does diff behave when our DOM nodes operate across hierarchies? When nodes move across hierarchies, they are deleted and recreated, which affects React performance. Therefore, it is not officially recommended to operate across hierarchies of DOM nodes.

component diff

React builds applications based on components and uses a concise and efficient strategy for comparing components. If it is a component of the same type, the Virtual DOM comparison is performed according to the original policy. If it is not a component of the same type, it is judged as a dirty Component and all child nodes under the entire component are replaced. If the components are of the same type, it is possible to go through a Virtual DOM comparison drop-down without changing. If we can know this exactly in advance, we can save a lot of diff time. As a result, React allows the user to determine if the component needs diff analysis via shouldComponentUpdate(). For example, when component D changes to component G, React will delete component D and recreate component G and its child nodes without comparing the structure of component D and G, even though the two components have similar structures. Although when two components are of different types but similar in structure, diff algorithm analysis will affect performance, after all, similar DOM trees exist in different types of components rarely occur in the actual development process, so it is difficult for such extreme factors to cause significant influence in the actual development process.

Element diff Provides three node operations when nodes are on the same level: INSERT_MARKUP, MOVE_EXISTING, and REMOVE_NODE.

INSERT_MARKUP: The new component type is not in the old collection, that is, the new node needs to be inserted.

MOVE_EXISTING: When an old collection has a new component type and element is an updatable type, you need to move it and reuse the old DOM node.

REMOVE_NODE: An old component type that exists in the new collection but cannot be reused or updated directly due to its different elements. If the old component is not in the new collection, it needs to be deleted.

Conclusion:

1. React converts O(N3) complexity problems into O(n) complexity problems by implementing a bold diff strategy; How does React convert an O(n3) complexity problem to O(n)?

   1. Do peer comparisons only
   2. React components of different classes are completely replaced as completely different DOM structures
   3. Key prop: Developers can hint that React is the same DOM structure by giving the Virtual DOM a unique key property, or treat React as a completely different DOM structure if the key value is different.

2. React optimizes the Tree Diff algorithm by adopting a hierarchical differentiation strategy.

3. React optimizes the Component diff algorithm by using the strategy of generating similar tree structures from the same class and different tree structures from different classes.

4. React optimizes the algorithm on Element Diff by setting a unique key policy.

5. It is recommended that when developing components, maintaining a stable DOM structure will help improve performance;

6. It is recommended to minimize operations like moving the last node to the head of the list during development. When the number of nodes is too large or update operations are too frequent, React rendering performance will be affected to some extent.