The first time you post an article the format may be a little bad but also the manuscript research Finally you get something after reading it

Diff algorithm: For update components, it compares the current component with the Fiber node corresponding to the last update of the component, and generates a new Fiber node from the comparison result.

! To prevent confusion, emphasize

A DOM node may have as many as four nodes associated with it at any one time.

1. The current Fiber. If the DOM node is already on the page, current Fiber represents the corresponding Fiber node of the DOM node. - 2. WorkInProgress Fiber. If the DOM node will be rendered to the page in this update, workInProgress Fiber represents the corresponding Fiber node of the DOM node. - 3.DOM node itself. - 4.JSX objects. The JSX object contains information describing the DOM node that is returned by the Render method of the ClassComponent or called in the FunctionComponent.Copy the code
The diff algorithm essentially compares 1 and 4 to produce 2.Copy the code

Diff bottlenecks and React

The Diff operation itself also causes performance loss. As mentioned in the React document, even the most advanced algorithm that completely compares two trees is O(n 3) in complexity, where n is the number of elements in the tree. If the algorithm was used in React, the amount of computation required to show 1000 elements would be on the order of a billion. The cost is simply too high.Copy the code

To reduce algorithm complexity, React diff presets three limits:

1. Diff sibling elements. React does not attempt to reuse a DOM node if it crosses the hierarchy in two updates. 2. Different types of elements produce different trees. If the element changes from div to P, React destroys the div and its descendants and creates a new p and its descendants. 3. Key prop can be used to indicate which child elements are stable in different renders.Copy the code

So let’s see how Diff is implemented

Diff can be divided into two types according to the number of nodes at the same level:

1. If the newChild type is Object, number, or String, there is only one node - 2 at the same level. When newChild is Array, there are multiple nodes at the same levelCopy the code

Single node diff

In the case of the type Object, it goes into this function reconcileSingleElementCopy the code

This function does the following:Copy the code

Let's look at how the second step of determining whether a DOM node can be reused is implemented.Copy the code

React checks whether the key is the same. If the key is the same, the type is the same. A DOM node can be reused only when both keys are the same.

Here’s one detail to note:

1. When the child! == null and the key is the same and the type is different execute deleteRemainingChildren to delete both child and its sibling fiber. 2. When the child! If the key is not null, only the child flag is removed.Copy the code

Example: there are three Li’s on the current page, we need to delete all of them and insert a p.

Since there is only one P in this update, the Diff belonging to a single node will follow the code logic described above.

Explanation:

The previous three fibers are iterated in reconcileSingleElement (the corresponding DOM is three Li) to find out whether the UPDATED P can reuse one of the DOM from the previous three fibers. When the key is the same and the type is different, it means that we have found the fiber corresponding to the updated P, but the TYPE of P is different from that of Li, so it cannot be reused. Since the only possibility is no longer reusable, the rest of the fiber has no chance, so all need to be marked and deleted. If the key is different, the fiber cannot be p multiplexed, and the brother fiber has not been traversed. So just mark the fiber deletion.Copy the code

Exercises:

1. Default key = null; , so the key before and after the update is the same as null, but the type before the update is div, and the type after the update is P. If the type changes, it cannot be reused. Problem 2: The key changes before and after the update, do not need to determine the type, cannot reuse. Problem 3: The key does not change before and after the update, but the type changes. Problem 4: The key and type are unchanged before and after the update, and can be reused. Children change, and the DOM child element needs to be updated.Copy the code

Multi-node diff

Diff of multiple nodes of the same class must fall into one or more of the following three situations.

  • Case 1: Node updates

  • Case 2: A node is added or reduced

  • Case 3: Node position changes

Notice that the diff algorithm can't use double pointer optimization and when we do array problems, we often use double Pointers to traverse both the head and the tail of an array to make it more efficient, but that's not the case here.Copy the code
Although the JSX object newChildren updated this time is in the form of an array, what is compared with each component in newChildren is that fiber nodes at the same level of Current Fiber are single linked lists formed by sibling pointer links. That is, newChildren[0] is compared with Fiber and newChildren[1] is compared with fiber.sibling.Copy the code
So you can't use two-pointer optimization.Copy the code

For the above reasons, the overall logic of the Diff algorithm goes through two rounds of traversal:

1. First traversal: Process the updated node. 2. Second round of traversal: Process the remaining nodes that are not updatedCopy the code

First traversal:

The steps of the first round of traversal are as follows:

Let I = 0 to traverse newChildren and compare newChildren[I] with oldFiber to determine whether DOM nodes are reusable. If reusable, I ++, continue to compare newChildren[I] with oldFiber.sibling, and continue to traverse if reusable. If not reusable, immediately jump out of the entire traversal, the first traversal end. If newChildren is traversed (i.e. I === newchildren.length-1) or oldFiber is traversed (i.e. Oldfiber.sibling === null), the first round of traversal is completed. The traversal shown in 3 above has not been completed by newChildren, nor has oldFiber.Copy the code

Example:

The first two nodes can be reused. The type of the node traversed to key === 2 is found to be changed and cannot be reused. At this point, oldFiber is left with key === 2 untraversed, newChildren is left with key === 2 and key === 3 untraversed. The traversal of 4 above may be completed by newChildren, or oldFiber, or both.Copy the code

Example:

With the results of the first iteration, we begin the second iteration.

First round traversal :(4 cases)

- 1. NewChildren and oldFiber are traversed at the same time. That is the ideal situation: only components are updated. At this point the Diff ends.Copy the code
- 2. NewChildren is not traversed, oldFiber traverses existing DOM nodes, and then there are new nodes added. This means that new nodes are inserted for this update and we just need to iterate over the remaining newChildren to mark Placement for the generated workInProgress fiber.Copy the code

- 3. NewChildren traversal is completed, oldFiber traversal is not completed, which means that the number of nodes in this update is less than the previous one, and some nodes have been deleted. Therefore, it is necessary to traverse the remaining oldFiber and mark Deletion in turn.Copy the code

- 4. Neither newChildren nor oldFiber has been traversed, which means that some nodes have changed their positions in this update. Since some nodes have changed their positions, we can no longer use the position index I to compare the nodes before and after. So how can we match the same node in two updates? We need to use key. In order to quickly find oldFiber corresponding to key, we stored all unprocessed oldFiber into the Map with key as key and oldFiber as value.Copy the code

Next, the remaining newChildren are iterated and newChildren[I].key is used to find whether the oldFiber token node with the same key has moved in existingChildrenCopy the code

! Since our goal is to find moving nodes, we need to be clear: Does the node move against what reference?

Our reference point is the position index of the last reusable node in oldFiber (represented by the variable lastPlacedIndex).Copy the code
In this update, the nodes are in the order of newChildren. In traversing newChildren, each traversed reusable node must be the right-most reusable node of all the currently traversed reusable nodes that must be behind the lastPlacedIndex corresponding reusable node in this update. So we only need to compare whether the traversed reusable node is also behind the oldFiber corresponding to lastPlacedIndex in the last update to know whether the relative position of the two nodes has changed during the two updates. We use the variable oldIndex to represent the position index of the traversed reusable node in oldFiber. If oldIndex < lastPlacedIndex, this object needs to be moved to the right. If oldFiber >= lastPlacedIndex, lastPlacedIndex = oldFiber. If oldFiber >= lastPlacedIndex, lastPlacedIndex = oldFiber.Copy the code

Here are two demos to see the essence of the React team’s diff algorithm

demo1

// before abcd // after acdb

=== first round of traversal begins === =

A (after) vs a (before) key remains the same, reusable now a corresponds to oldFiber (before A) which is indexed 0 in the previous array (abCD) so lastPlacedIndex = 0;Copy the code

Continue the first walk…

LastPlacedIndex === 0; lastPlacedIndex === 0;Copy the code

=== End of the first round ===

=== second round of traversal begins === =

NewChildren === CDB, no need to delete the old node oldFiber === BCD, no need to insert the new node oldFiber === BCD, save the remaining oldFiber (BCD) as mapCopy the code

// Current oldFiber: BCD

// Current newChildren: CDB

Continue through the remaining newChildren

Key === c const oldIndex = c (before).index; OldIndex === 2; // Compare oldIndex with lastPlacedIndex; // Compare oldIndex with lastPlacedIndex; If oldIndex >= lastPlacedIndex indicates that the reusable node does not need to be moved and sets lastPlacedIndex = oldIndex; If oldIndex < lastplacedIndex the location index of the reusable node is smaller than the location index to be inserted in this update, it means that the node needs to be moved to the right. In this example, oldIndex 2 > lastplacedIndex 0, LastPlacedIndex = 2; The position of node C remains unchangedCopy the code

Continue through the remaining newChildren

// Current oldFiber: bd

// Current newChildren: db

Key === d const oldIndex = d (before).index; OldIndex 3 > lastPlacedIndex 2 // oldIndex 3 > lastPlacedIndex 2; The position of node D remains unchangedCopy the code

Continue through the remaining newChildren

// Current oldFiber: b

// Current newChildren: b

Key === b const oldIndex = b (before).index; OldIndex 1 < lastPlacedIndex 3 // The previous node was abcd, so b.index === 1 then b needs to move to the rightCopy the code

=== End of the second round ===

! Finally, none of the three acD nodes moved, and node B was marked as moved

demo2

/ / before the abcd

/ / after dabc

=== first round of traversal begins === =

D (after) vs A (before) key change, cannot reuse, jump out of traversalCopy the code

=== End of the first round ===

=== second round of traversal begins === =

NewChildren === dabc, no need to delete the old node oldFiber === abcd, no need to insert the new node oldFiber === ABCD, save the remaining oldFiber (ABCD) as map and continue traversing the remaining newChildrenCopy the code

// Current oldFiber: abcd

// Current newChildren dabc

Key === d const oldIndex = d (before).index; OldIndex === 3; D. index === 3 oldIndex = lastPlacedIndex; OldIndex 3 > lastPlacedIndex 0 then lastPlacedIndex = 3; The position of node D remains unchangedCopy the code

Continue through the remaining newChildren

// Current oldFiber: ABC

// Current newChildren ABC

Key === a const oldIndex = a (before).index; key === a const oldIndex = a (before).index; // if a.index === 0, then oldIndex === 0; Compare oldIndex with lastPlacedIndex; If oldIndex 0 < lastPlacedIndex 3, a needs to move to the rightCopy the code

Continue through the remaining newChildren

// Current oldFiber: BC

// Current newChildren BC

Key === b const oldIndex = b (before).index; // the previous node is abcd, so b.index === 1 oldIndex === 1; Compare oldIndex with lastPlacedIndex; If oldIndex 1 < lastPlacedIndex 3, node B needs to move to the rightCopy the code

Continue through the remaining newChildren

// Current oldFiber: c

// Current newChildren c

Key === c const oldIndex = c (before).index; // the previous node is abcd, so c.index === 2 oldIndex === 2; Compare oldIndex with lastPlacedIndex; If oldIndex 2 < lastPlacedIndex 3, c needs to move to the rightCopy the code

=== End of the second round ===

! As you can see, we think to go from ABcd to Dabc, we just move d to the front. ! But React actually leaves D unchanged, moving ABC after D, respectively.

Let’s use the old picture

Finally attached research manuscript we sweep the five blessings set ha ha