The effect of diff
In React, the diff algorithm needs to work with the virtual DOM to be truly powerful. React uses the DIff algorithm to calculate the parts of the virtual DOM that actually change and only perform DOM operations on those parts, thus avoiding extensive page updates and rendering and reducing performance overhead.
The React diff algorithm
In the traditional DIff algorithm, the complexity will reach O(n^3). For example, if our page has 1000 elements, we need to compare 1 billion times, which is very inefficient and cannot meet the efficiency required by front-end rendering. To solve this problem, React defines three policies that allow comparisons to be performed only once through the tree, reducing complexity to O(n) :
- Tree diff: When two trees are compared, only nodes at the same level are compared, and cross-level operations are ignored
- Component diff: When comparing two components, it first determines whether they are of the same type. If they are different, the component is destroyed and a new component is inserted without further comparison.
- Element diff: For a group of nodes at the same level, unique keys are used to distinguish whether they need to be created, removed, or moved.
Source structure
The entry function of the Diff is reconcileChildren:
export function reconcileChildren(
current: Fiber | null,
workInProgress: Fiber,
nextChildren: any,
renderLanes: Lanes,
) {
if (current === null) {
// current === null; call mountChildFibers to create Fiber based on the child element
workInProgress.child = mountChildFibers(
workInProgress,
null,
nextChildren,
renderLanes,
);
} else {
// Compare current tree and workInProgress tree with diff algorithm to find the difference part
workInProgress.child = reconcileChildFibers(
workInProgress, // Fiber node in workInProgress
current.child, // Child node of the current Fiber node in the current tree
nextChildren, // React Element with the latest data
renderLanes, // A set of rendered Lane priorities); }}Copy the codeIf the Fiber node in the workInProgress tree is null, the Fiber node in the workInProgress tree does not exist. If the Fiber node is null, the Fiber node in the workInProgress tree does not exist. Then call the mountChildFibers function to build the workInprogress tree from the React Elements generated by calling the Render function. If the reconcileChildFibers function is called, the reconcileChildFibers function is then called to compare the Current tree and the workInProgress tree with the Diff algorithm to find out the differences and update the reconcileChildFibers.
The Diff algorithm compares the process in the reconcileChildFibers function, and we take a look at the source code:
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any,
lanes: Lanes,
) :Fiber | null {
// Process a single node
if (typeof newChild === 'object'&& newChild ! = =null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
case REACT_PORTAL_TYPE:
...
case REACT_LAZY_TYPE:
...
}
// Process multiple nodes at the same level
if (isArray(newChild)) {
returnreconcileChildrenArray( returnFiber, currentFirstChild, newChild, lanes, ); }... }... }Copy the codeThe render function generates the React Element to determine whether it is a single node or multiple nodes.
A single node
The diff process for individual nodes is mainly in the reconcileSingleElement function, and let’s first look at how individual nodes diff:
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement,
lanes: Lanes,
) :Fiber {
const key = element.key; // Get the key attribute on the React Element
let child = currentFirstChild; // Fiber node in the current tree
while(child ! = =null) {
// The current tree is already rendered on the screen
// Compare the Fiber key on the current tree with the key on the React element.
// If not, add the Fiber object in the current tree to the deletions property of the parent Fiber
// Add the delete flag to the Flags collection, and then create a new Fiber node based on the newly created React Element
// In the commit phase, the Fiber object added to the deletions property will be removed according to the flags collection.
// Remove the old DOM node corresponding to the Fiber object, including all its children, and insert the new node into the page
// If it is equal, then fiber is reused as opposed to fiber on the current tree, and the pendingProps property on fiber is updated with the latest props
// Dom nodes are updated during the COMMIT phase
if (child.key === key) {
const elementType = element.type;
if (elementType === REACT_FRAGMENT_TYPE) {
if (child.tag === Fragment) {
deleteRemainingChildren(returnFiber, child.sibling);
constexisting = useFiber(child, element.props.children); existing.return = returnFiber; .returnexisting; }}else {
Compare the elementType attribute of the Fiber node in the current tree with the type attribute of the newly generated React Element to determine whether the type is the same
// If not, add the Fiber object in the current tree to the deletions property of the parent Fiber
// Add the delete flag to the Flags collection, and then create a new Fiber node based on the newly created React Element
// In the commit phase, the Fiber object added to the deletions property will be removed according to the flags collection.
// Remove the old DOM node corresponding to the Fiber object, including all its children, and insert the new node into the page
// If it is equal, then fiber is reused as opposed to fiber on the current tree, and the pendingProps property on fiber is updated with the latest props
// Dom nodes are updated during the COMMIT phase
if (
child.elementType === elementType ||
(__DEV__
? isCompatibleFamilyForHotReloading(child, element)
: false) ||
(enableLazyElements &&
typeof elementType === 'object'&& elementType ! = =null &&
elementType.$$typeof === REACT_LAZY_TYPE &&
resolveLazy(elementType) === child.type)
) {
deleteRemainingChildren(returnFiber, child.sibling);
// Reuse the fiber corresponding to the current tree and update the pendingProps property on fiber with the latest props
const existing = useFiber(child, element.props);
existing.ref = coerceRef(returnFiber, child, element);
existing.return = returnFiber;
returnexisting; }}// Didn't match.
deleteRemainingChildren(returnFiber, child);
break;
} else {
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// When the key or type is not equal, a new Fiber node is created based on the newly created React Element.const created = createFiberFromElement(element, returnFiber.mode, lanes);
created.ref = coerceRef(returnFiber, currentFirstChild, element);
created.return = returnFiber;
return created;
}
Copy the codeGet the React Element key from the Fiber node in the current tree and compare it with the React Element key.
- The key is not equal: is invoked
deleteChildThe Fiber () function adds the Fiber object to the parent Fiber’s deletions property, and adds a delete flag to the flags collection. At the commit stage, the dom corresponding to the Fiber added to the deletions collection and all its children are deleted.
function deleteChild(returnFiber: Fiber, childToDelete: Fiber) :void {
const deletions = returnFiber.deletions;
if (deletions === null) {
returnFiber.deletions = [childToDelete];
returnFiber.flags |= ChildDeletion;
} else{ deletions.push(childToDelete); }}Copy the codeThen create a new Fiber node based on the newly created React Element.
- The key is equal: compares the elementType attribute of the Fiber node in the current tree with the Type attribute of the React element.Check whether the types are the same:The same typeWill call
useFiberThe React Element function reuses the old Fiber node and updates the pendingProps property of the Fiber node with the props on the React Element. It also updates the properties of the node and adds the node to the workInProgress tree.Different types ofIs calleddeleteRemainingChildrenThe Fiber () function adds the Fiber object to the parent Fiber’s deletions property and adds a delete flag to the flags collection. At the commit stage, the dom of the Fiber added to the deletions collection and all its children will be deleted. Finally, create a new Fiber node based on the newly created React Element.
summary
The comparison of individual nodes, which can be components or HTML tags, starts with a key attribute, usually not an element in the list, we don’t add keys, so the key value is null. During the comparison, the key value is null, so the type is directly compared to check whether the type is the same. If the type is the same, the old node is updated and reused, if the type is different, the old node and all its children are removed, and a new node is created based on the React Element to insert.
Multiple nodes
After analyzing each reconcileChildrenArray, we turn to the diff for the reconcileChildrenArray function:
function reconcileChildrenArray(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChildren: Array<*>,
lanes: Lanes,
) :Fiber | null {
let resultingFirstChild: Fiber | null = null; // The list updates the first Fiber node of the property with React Element data
let previousNewFiber: Fiber | null = null; // The last updated Fiber node is used to associate siblings in the list
let oldFiber = currentFirstChild; // First Fiber node in the list in the current tree
let lastPlacedIndex = 0; // The index of the position moved by the last element
let newIdx = 0; // Iterate through the React Element tree subscript
let nextOldFiber = null; // current Sibling node of the element in the list in the tree
// The purpose of this for loop is to weed out unchanged nodes and update and reuse them
// When oldFiber is null, the loop is broken, and a new Fiber is created and inserted into the end, without any comparison with other nodes
// When a new node is inserted in the middle, newFiber is null, then the loop is broken, and the node position needs to be moved to sort
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
nextOldFiber = oldFiber.sibling;
}
// If the old Fiber key is the same as the React Element key, the React Element's data will be used to update the Fiber node's properties
// if not, null is returned
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// If the element's key attribute changes, it is not an update scenario and the for loop is broken
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) { deleteChild(returnFiber, oldFiber); }}// Assign newIdx to the Fiber node's index property in the workInProgress tree, representing the current element's position in the list (subscript)
// Check whether the Index of the element in the current tree is less than that of the lastPlacedIndex
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
// Associate the updated sibling Fiber nodes
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
// New child nodes have been traversed. If there are any remaining nodes in the current tree, delete all the nodes in the workInProgress tree
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
// Create a new node without comparing it with the old node
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
// TODO: Move out of the loop. This only happens for the first run.
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// Add uncompared elements from the list in the current tree to the Map object
// The following for loop fetches the old Fiber and React Element in the Map based on the key
// If the React Element type is the same, update the Fiber property. If the React Element type is different, create a new Fiber and insert it
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// The node moves
for (; newIdx < newChildren.length; newIdx++) {
// Select the old Fiber and React Element from the Map according to the key
// If the type is the same, update the Fiber node with the React Element data for reuse. If the type is different, create a new Fiber node based on the React Element data for insertion
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if(newFiber ! = =null) {
if (shouldTrackSideEffects) {
// newFiber. Alternate is not null, indicating that the node is reused, and the reused node in existingChildren needs to be deleted
// The remaining nodes in existingChildren need to be deleted after traversal
if(newFiber.alternate ! = =null) {
// When the updateFromMap method is called, the corresponding Fiber is fetched according to the key
// After calling updateFromMap, the Fiber value of the key was reused, so we need to delete the value of the key used in the Map
existingChildren.delete(
newFiber.key === null? newIdx : newFiber.key, ); }}// Assign newIdx to the Fiber node's index property in the workInProgress tree, representing the current element's position in the list (subscript)
// Check whether the Index of the element in the current tree is less than that of the lastPlacedIndex
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}// Node deletion
if (shouldTrackSideEffects) {
// The remaining Fiber in existingChildren represents the element in the current tree, but not in the workInProgress tree
// Add the remaining fibers to the parent Fiber node's deletions property and add a delete flag to the Flags collection. These elements will be removed during the COMMIT phase
existingChildren.forEach(child= > deleteChild(returnFiber, child));
}
// Returns the first node in the list
return resultingFirstChild;
}
Copy the codeBelow, we analyze the multi-node DIff algorithm by taking examples.
Adding child Nodes
Assuming we have rendered the interface now, the corresponding current tree looks like this:
Now that an update is done, the React Element tree generated by calling the Render method looks like this:
A new element with key E is added at the end of the list.
The reconcileChildrenArray function is called with the following arguments:
returnFiber: Fiber object corresponding to node A in the workInProgress treecurrentFirstChild: Fiber object corresponding to the first element B in the list in the current treenewChildrenThe React Element tree generated by calling the Render method, as shown in the previous figure.lanes: Set of priorities of tasks that need to be updated
As can be seen in the reconcileChildrenArray function, the first child in the list (B) was first assigned to oldFiber, which initialized newIdx to 0 and nextOldFiber to NULL, using newIdx as the index for the for loop, Iterate over newChildren. During the traverse, the updateSlot function is called to determine whether the Fiber node in the current tree is the same as the key attribute and type on the React element. / / React Element props update Fiber properties on the current tree; / / Reuse old Fiber properties on the React Element tree; / / Return null if the properties are not equal to the old Fiber properties on the current tree:
function updateSlot(
returnFiber: Fiber,
oldFiber: Fiber | null,
newChild: any,
lanes: Lanes,
) :Fiber | null {
constkey = oldFiber ! = =null ? oldFiber.key : null; .if (typeof newChild === 'object'&& newChild ! = =null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE: {
// Check whether the key is equal
if (newChild.key === key) {
// Create a new Fiber based on the React Element
return updateElement(returnFiber, oldFiber, newChild, lanes);
} else {
return null; }}case REACT_PORTAL_TYPE: {
...
}
caseREACT_LAZY_TYPE: { ... }}... }Copy the codeIf the B node in the current tree has the same key attribute and type as the B node in the React element tree, the old Fiber node is returned and the placeChild function is called. This function determines whether the current node needs to be moved:
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number { newFiber.index = newIndex; .const current = newFiber.alternate;
// Check whether the Fiber node in the workInProgress tree has a corresponding Fiber node in the current tree
// If so, the index of the old and new Fiber will be compared to determine whether it needs to be moved
// If current is null, there is no corresponding Fiber in the current tree. This Fiber is newly added and needs to be inserted
if(current ! = =null) {
const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
// This is a move.
newFiber.flags |= Placement;
return lastPlacedIndex;
} else {
// This item can stay in place.
returnoldIndex; }}else {
// This is an insertion.
newFiber.flags |= Placement;
returnlastPlacedIndex; }}Copy the codeIn this function, the index attribute of the Fiber node in the current tree, that is, its position in the list, is compared with the lastPlacedIndex. At this time, the lastPlacedIndex is 0, and the position of the B node in the current tree is also 0, so the position remains unchanged. The node is moved to the right only if its position in the current tree is less than lastPlacedIndex.
After B is compared, D and C are compared in turn. Since D and C have not changed, the process is the same as B.
When D starts the comparison, its sibling node is obtained and assigned to nextOldFiber. Since D is the last node in the current tree, null is assigned to nextOldFiber:
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else{ nextOldFiber = oldFiber.sibling; }... oldFiber = nextOldFiber; }Copy the codeWhen D completes the comparison, nextOldFiber is assigned to oldFiber. When E is traversed and oldFiber is null, the cycle is terminated. At this time, the index newIdx is the subscript of D: 2:
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
...
}
Copy the codeAt this point, the newly generated Reat element has not been traversed, there is still an E, will enter the node’s new code:
// Create a new node without comparing it with the old node
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
Copy the codeIf oldFiber is null, enter the for loop and call createChild. This creates a new Fiber based on the React Element. Then call placeChild. Since newFiber is newly created, current is null, and the insert flag needs to be added to perform the insert operation:
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number {...const current = newFiber.alternate;
// Check whether the Fiber node in the workInProgress tree has a corresponding Fiber node in the current tree
// If so, the index of the old and new Fiber will be compared to determine whether it needs to be moved
// If current is null, there is no corresponding Fiber in the current tree. This Fiber is newly added and needs to be inserted
if(current ! = =null) {... }else {
// Add the insert identifier
newFiber.flags |= Placement;
returnlastPlacedIndex; }}Copy the codeFinally, return resultingFirstChild, which is the first child in the list after comparison, and add it to the WorkInProgress tree to form a new WorkInProgress tree.
In this process, React uses diff lookup to update and reuse nodes with the same key and type (B, C and D), and creates and inserts different nodes.
Deleting child Nodes
In this example, we removed the C.
Contrast B is the same process as above, and the end result is also reused.
When D is used for comparison, updateSlot is called with the following arguments:
const newFiber = updateSlot(
returnFiber, // A
oldFiber, // C
newChildren[newIdx], // D
lanes,
);
Copy the codeD is compared with C, the key is different, updateSlot returns null, and then breaks out of the current for loop, oldFiber is the corresponding Fiber node of C, newIdx is 1, and mapRemainingChildren function is called, Add nodes C and D in the list of current tree that have not been compared to the Map object: existingChildren:
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
function mapRemainingChildren(returnFiber: Fiber, currentFirstChild: Fiber,) :Map<string | number.Fiber> {
const existingChildren: Map<string | number, Fiber> = new Map(a);let existingChild = currentFirstChild;
while(existingChild ! = =null) {
if(existingChild.key ! = =null) {
existingChildren.set(existingChild.key, existingChild);
} else {
existingChildren.set(existingChild.index, existingChild);
}
existingChild = existingChild.sibling;
}
return existingChildren;
}
Copy the codeThe React Element tree is iterated with newIdx:
// The node moves
for (; newIdx < newChildren.length; newIdx++) {
// Select the old Fiber and React Element from the Map according to the key
// If the type is the same, update the Fiber node with the React Element data for reuse. If the type is different, create a new Fiber node based on the React Element data for insertion
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if(newFiber ! = =null) {
if (shouldTrackSideEffects) {
// newFiber. Alternate is not null, indicating that the node is reused, and the reused node in existingChildren needs to be deleted
// The remaining nodes in existingChildren need to be deleted after traversal
if(newFiber.alternate ! = =null) {
// When the updateFromMap method is called, the corresponding Fiber is fetched according to the key
// After calling updateFromMap, the Fiber value of the key was reused, so we need to delete the value of the key used in the Map
existingChildren.delete(
newFiber.key === null? newIdx : newFiber.key, ); }}// Assign newIdx to the Fiber node's index property in the workInProgress tree, representing the current element's position in the list (subscript)
// Check whether the Index of the element in the current tree is less than that of the lastPlacedIndex
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}Copy the codeEnter the for loop, newIdx = 1, and call updateFromMap:
const newFiber = updateFromMap(
existingChildren, // Map: {C: FiberC, D: FiberD}
returnFiber, // A
newIdx, / / 1
newChildren[newIdx], // React element D
lanes,
);
function updateFromMap(
existingChildren: Map<string | number, Fiber>,
returnFiber: Fiber,
newIdx: number,
newChild: any,
lanes: Lanes,
) :Fiber | null {...if (typeof newChild === 'object'&& newChild ! = =null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE: {
// Select the old Fiber and React Element from the Map according to the key
// If the type is the same, update the Fiber node with the React Element data for reuse. If the type is different, create a new Fiber node based on the React Element data for insertion
const matchedFiber =
existingChildren.get(
newChild.key === null ? newIdx : newChild.key,
) || null;
return updateElement(returnFiber, matchedFiber, newChild, lanes);
}
case REACT_PORTAL_TYPE: {
...
caseREACT_LAZY_TYPE: ... }... }Copy the codeIf the types are the same, use the React Element data to update the properties on the Fiber node for reuse. The React Element data creates a new Fiber return.
Since D exists in existingChildren and the type does not change, the old Fiber will be reused.
When the updateFromMap call is complete, newFiber is determined to be reused, if it is, then its alternate property is definitely not null, and reused Fiber in existingChildren is removed. That’s going to delete D from existingChildren.
Then call placeChild:
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
Copy the codeNewFiber is the Fiber object in the current tree, lastPlacedIndex is the position of B: 0, newIdx is: 1:
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number {
// Give the current position to newFiber
newFiber.index = newIndex;
const current = newFiber.alternate;
// Check whether the Fiber node in the workInProgress tree has a corresponding Fiber node in the current tree
// If so, the index of the old and new Fiber will be compared to determine whether it needs to be moved
// If current is null, there is no corresponding Fiber in the current tree. This Fiber is newly added and needs to be inserted
if(current ! = =null) {
const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
// This is a move.
newFiber.flags |= Placement;
return lastPlacedIndex;
} else {
// This item can stay in place.
returnoldIndex; }}else{... }}Copy the codeCurrent is not null because D is re-used, and then the position of D in the curren tree: 2 is assigned to oldIndex, which says that lastPlacedIndex is the position of B: 0. OldIndex is greater than lastPlacedIndex, and does not need to be moved.
After the placeChild call completes, at this point, the new child node has been traversed.
There is still a C left in existingChildren, and Fiber is left in existingChildren at the end, indicating that the node exists in the current tree but does not existin the workInProgress tree, which needs to be deleted. The remaining fibers are added to the parent Fiber node’s deletions property by calling the deleteChild function and adding a delete flag to the Flags collection. These nodes are removed during the COMMIT phase.
Move child node
In this example, we move C after D.
Firstly, B nodes in the two trees are compared. The key and type are the same, and B is reused.
Then compare D with C and find different keys, jump out of the first loop and add the uncompleted comparison node to existingChildren: C, D.
Then enter the second loop, call updateFromMap, extract the Old Fiber from existingChildren based on the key of D in the React Element tree, Then, the type of old Fiber D is compared with that of D in React Element, and it is found to be the same. Reuse old Fiber D and delete D from existingChildren after reuse.
The placeChild method is then called to move the position:
lastPlacedIndex = placeChild(
newFiber, // The D node is reused as old fiber
lastPlacedIndex, / / 0
newIdx / / 1
);
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number { newFiber.index = newIndex; .const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
// This is a move.
newFiber.flags |= Placement;
return lastPlacedIndex;
} else {
// This item can stay in place.
returnoldIndex; }... }Copy the codeThe index of old Fiber D is current, the position in the tree is 2, lastPlacedIndex is 0, oldIndex is greater than lastPlacedIndex, no move.
Compare C with D, call updateFromMap, extract old Fiber from existingChildren according to the key of D in the React Element tree, and compare the type of old Fiber C with the type of D in the React Element. Old Fiber C was reused, and C was deleted from existingChildren after the reuse.
Call placeChild, old Fiber C’s index is current 1 on the tree, lastPlacedIndex is 2, oldIndex is less than lastPlacedIndex, move to the right.
Why is it moving to the right? You can see the first line of code in placeChild:
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number { newFiber.index = newIndex; . }Copy the codeThe current newIndex is assigned to the index attribute of Fiber C, which is 2. The index of fiber C in the current tree is 1. Move fiber C one bit to the right and add 1 to index, which becomes 2.
From above, we can see that the key to moving a node is this code in the placeChild function:
const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
newFiber.flags |= Placement;
return lastPlacedIndex;
} else {
return oldIndex;
}
Copy the codeWhat if we move D to the first place?
For the first traversal comparison, newIndex is 0, D is 2 in the current tree, and lastPlacedIndex is 0. Since oldIndex is greater than lastPlacedIndex, D does not move, and index is assigned 0. Returns oldIndex assigned to lastPlacedIndex as 2.
In the second traversal comparison, newIndex is 1, B’s position in the current tree is 0, and lastPlacedIndex is 2. Since oldIndex is less than lastPlacedIndex, B moves to the right and index is assigned to 1. Return lastPlacedIndex as 2.
On the third iteration, newIndex is 2, C is 1 in the current tree, and lastPlacedIndex is 2. Since oldIndex is less than lastPlacedIndex, C moves to the right, and index is assigned to 2. Return lastPlacedIndex as 2.
You can see that if YOU move D to the first place, B and C move to the right
Once there are too many nodes, this incurs a high performance overhead, so we try to avoid moving the tail nodes forward.
conclusion
- React Diff Uses three strategies to reduce the complexity of the traditional diff algorithm from O(n^3) to O(n).
- Tree diff: When two trees are compared, only nodes at the same layer are compared and operations across layers are ignored.
- Component diff: When comparing two components, only the types are compared. If the types are different, no further comparison is made. The old component and its children are destroyed and the new component is created and inserted.
- Element diff: For a group of nodes at the same level, unique keys are used to distinguish them.
- Whether a node is a single node or multiple nodes, the key value is compared first and then the type is compared to determine whether the node needs to be reused or created.
- As for the function of the key attribute, we can see that each traversal will first compare the key value. Through the key, we can quickly find the changed nodes and operate on these nodes.
- During development, we try not to move the tail nodes forward to reduce the performance overhead.