What is the Diff algorithm (1)

For components that need to be updated, React compares the current component to Fiber rendered after the last update. This comparison uses the Diff algorithm. The Diff algorithm deals with the difference between the updated component and the existing component. The Diff algorithm generates some effectTags and React updates the new component based on those effectTags

Concepts related to the Diff algorithm

For an existing DOM node on a view, the following concepts are associated with it in the Diff algorithm

  • Current Fiber: indicates the Fiber description of the current DOM node
  • WorkInProgress Fiber: If the DOM node is to be rendered to the page in this update, the workInProgress Fiber is the corresponding Fiber node to the DOM node to be replaced. The updated DOM corresponds to Fiber, but is still in the Fiber node
  • DOM node: A node in a view that describes a page at a time
  • JSX objects: the result returned by the Render method of the ClassComponent, or the result of the FunctionComponent call; JSX objects are associated with DOM nodes and describe the response information of DOM nodes.

The Diff algorithm is the process of reconciling the JSX object and current Fiber and finally generating the workInprogress Fiber. This process is also the reconcile process. The workInprogress Fiber will be rendered into a new DOM. This is direct rendering.

Why — Why do I use Diff/Why do I need a particular Diff, and what are the disadvantages of other methods?

Diff algorithm is the process of comparing currentFiber tree and JSX object, and finally generating workInprogress tree, where JSX object is also equivalent to dom tree mapping

  • For an algorithm that completely compares two trees, the time complexity should reach O(N3)O(n^3)O(N3), which is too high and requires too much resources. Therefore, after summarizing common features, React decides to impose restrictions on comparison pairs to reduce the complexity. The comparison algorithm under these restrictions is the Diff algorithm.

How1 — What is the Diff algorithm/what are the limitations in the restricted algorithm

General principles

  1. Diff only sibling elements. If a DOM node crosses the hierarchy before and after the update, React will remove the old node tree at the corresponding location of the WIP Fiber tree and rebuild it at the new location
  2. Two elements of different types produce different trees. The DOM node has changed its label, corresponding to fiber, which is the type detected, for examplediv -> p, the entire subtree corresponding to div will be deleted first, and then a new P-tree will be added in the corresponding position
  3. Use key prop to indicate which elements will remain stable in different renders

understand

Q: First of all, we need to determine when the DOM node crosses the hierarchy. How can we tell if the two elements are the same before and after the update?

  • If there is a key and the key is unique, then we can use the key to determine which group of two nodes before and after the update
  • If you don’t have a key, then you do it by position, for examplediv > p a pTurned out to bediv > a p pIf there is no key flag, p will be deleted first and then a corresponding A will be generated. And then you delete a, and you get p

Q: Function of key

  • A miracle, no key, direct comparison with the level, once the type is not correct, directly delete all, reconstruction is good
  • If there is a key, then each node corresponding to JSX needs to traverse all nodes at the same level of current Fiber to find the node with the same key, and then see whether to delete or update it.

Q: Why does key not necessarily improve efficiency

  • Although the key can avoid location transfer updates, it is inefficient to use the delete new method to update
  • However, when there is a key, each node needs to traverse all nodes of the same level to find the corresponding node. This traverse process is a resource consumption. If it is a leaf node, deleting the newly added method will consume less resources than traversing and searching and updating.
  • React, of course, recommends using keys, because statistically, deleting a subtree of that size at one time is much more expensive than traversing the search.

How2 — How is Diff implemented

An overview of the

  • The Diff algorithm compares the CHILD of JSX node with fiber at the same level by means of DFS, and then returns the corresponding result
  • The child can be an object, a string, an array, and so on
  • There are two Diff algorithms: single-node Diff and multi-node Diff
  • A single node is a single child, in which case the child might be a string/number, which is the same as the document; If it’s an object, it’s a component, and then it’s categorized again
    • Processing of the REACT_ELEMENT_TYPE common component
    • The REACT_PORTAL_TYPE entry component comes out
    • REACT_LAZY_TYPE xxx
  • If a multinode child is an array or an array of classes, then a more complicated comparison method is required
function reconcileChildFibers(
    returnFiber, Fiber / / parent
    currentFirsetChild, // The first child of the current hierarchy,
    newChild, // A node of JSX corresponds to an object
) {
    / / if
    const isObject = typeof newChild === 'object'&& newChild ! = =null;

    if (isObject) {
        // The object type can be REACT_ELEMENT_TYPE or REACT_PORTAL_TYPE or REACT_LAZY_TYPE
        switch (newChild.$$typeof) {
            case REACT_ELEMENT_TYPE:
            //todo
            case REACT_PORTAL_TYPE:
            //todo
            case REACT_LAZY_TYPE:
            //todo}}// Use the single-node text diff algorithm
    if (typeof newChild === 'string' || typeof newChild === 'number') {
        // Calls the reconcileSingleTextNode to process text nodes
        return placeSingleChild(
            reconcileSingleTextNode(
                returnFiber,
                currentFirstChild,
                ' ' + newChild,
                lanes,
            ),
        );
    }

    / / array
    if (isArray(newChild)) {
        / / array
        return reconcileChildrenArray(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
        );
    }

    / / array
    if (getIteratorFn(newChild)) {
        // Interator, similar to array
        return reconcileChildrenIterator(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
        );
    }

    // In other cases, delete the node and add it directly
    return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the code

Implementation of each Diff algorithm

To be continued…

summary

  1. The Diff algorithm is sent in the Reconcile phase of React to compare and process the JSX object with the currentFiber corresponding to the DOM currently displayed in the reconcile phase.
  2. Due to the high complexity of complete comparison two-lesson tree and the consumption of resources, a restricted comparison processing method, namely Diff method, was designed based on unknown statistics
  3. The key is an important attribute in the Diff method that determines how nodes are handled in a multi-node Diff, but using a key does not necessarily optimize performance.
  4. Diff has three major specifications: same-level comparison, deletion of different types of nodes, and use of keys
  5. In the process of comparison, given JSX Child is an array of objects, while same-level Fiber is a chain structure, and the corresponding sibling fiber is linked through Sibling.

reference

React – Diff algorithm revealed