Author: Baidu Takeout Cheng Yajie Li Xianlu Peipeng reprint please indicate the sourceCopy the codeorigin
In the process of front-end development, the factor that has the biggest impact on performance is DOM rearrangement and redrawing. React, as the front-end framework leader, adopts the Virtual DOM idea in order to effectively solve the problem of DOM update overhead, which not only improves the efficiency of DOM operation, but also promotes the formation and improvement of data-driven component development. Once used to data-driven development, and then asked us to use explicit DOM operation development, the degree of sadism is no different from the Spring Festival home tickets sold out, can only travel long agonizing.
The main idea of VirtualDOM is to simulate the tree structure of DOM and create node data to save mapping DOM information in memory. When view update is needed due to interaction and other factors, the node data should be diff to get the difference results, and then the DOM should be updated in batches at one time. It’s like in memory to create a parallel world, the browser DOM tree of each node and attribute data in the parallel world there is another version of the virtual DOM tree, and all the update logic complex twists and turns in the parallel world VirtualDOM processing is completed, will eventually update results only sent to the browser DOM tree, This avoids the burden of redundant and trivial DOM tree operations, thus effectively improving performance.
If you’re already a project veteran with Vue or React, this article will give you a look at how these front-end frameworks work for view updates, and give you some insight into VirtualDOM’s core algorithms, even if you haven’t yet taken advantage of these data-driven tools. You’ll also learn how some of the current front-end frameworks have had a dramatic impact on development patterns. At the same time, this article is also a summary of our relevant knowledge learning, inevitable mistakes, welcome to corrections, and look forward to greatly our guidance.
The Diff efficiency debate
VirtualDOM is an important optimization scheme for THE PERFORMANCE bottleneck of DOM rearrangement and redrawing under the componentization development scenario of React. Its most valuable core function is how to identify and save the difference between the old and new node data structures, that is, diFF algorithm. There is no doubt that the complexity and efficiency of diFF algorithm are the key factors that determine the performance improvement effect of VirtualDOM. Therefore, after the VirtualDOM scheme was proposed, improved algorithms for DIff continuously emerged in the community. To quote the classic introduction of Situ Zhengmei:
At first, the classical dept-first traversal DFS algorithm, whose complexity is O(n^3), has high diff cost. Then cito. Js comes out, which has a significant impact on all future virtual DOM algorithms. It uses the algorithm of comparing both ends at the same time to pull diff speed up to several levels. This is followed by Kivi.js, which proposes two optimization schemes based on cito.js, using key to realize movement tracking and the application of key-based editing length distance algorithm (algorithm complexity is O(n^2)). However, such diff algorithm is too complex, so snabbdom, a newcomer, simplifies Kivi.js by removing the edit length and distance algorithm and adjusting the comparison algorithm on both ends. There is a slight loss of speed, but readability is greatly improved. After that, the famous vue2.0 integrated the entire snabbdom library.
Therefore, the current mainstream Diff algorithms of VirtualDOM tend to be consistent. In terms of the main diff ideas, snabbDOM and React reconilation methods are basically the same.
Diff Main strategy
- Diff (level by level)
Since the data structure of DIff is the node data of simulated tree hierarchy with DOM rendering as the target, and the DOM hierarchy is rarely updated due to interaction in WebUI, the Diff strategy of VirtualDOM is to diff the new node tree and the old node tree according to the hierarchy to obtain the difference. Instead of the traditional search by depth traversal, this improved scheme obtained by bold assumptions not only meets the needs of the actual scene, but also greatly reduces the complexity of the algorithm, from O(n^3) to O(n).
- Diff by type
Whether the node data in VirtualDOM corresponds to a native DOM node or a component in VUE or React, the structure of sub-tree nodes of different types of nodes often differs significantly, so the input cost to output ratio of diff on sub-tree of different types of nodes will be very high. To improve diff efficiency, VirtualDOM diff only the same node of the same type. When the type of the new node changes, a new type of VirtualDOM is created to replace the old node without subtree comparison.
- List the diff
When the diff node is at the same level, the new node is updated through three node operations: Insert, move and delete, and provide the user with the way to set the key attribute to adjust the default sorting mode of DIFF update. In the list DIff without key value, only the comparison, update, insert and delete of each element can be carried out in order. In the case of a large amount of data, diFF is inefficient. If you can focus on diFF based on the set key identifier, you can quickly identify changes between old and new lists and improve diFF efficiency.
Different implementation modes of the Virtual DOM
Based on the above three DIFF principles, we are free to choose the specific Virtual DOM solution, and even do the diFF practice ourselves. Until then, Let’s start by reconciling the two Virtual DOM implementations in Vue (SnabbDOM) and React (Reconcile).
The vnode snabbdom
Among many VirtuaDOM implementation solutions, SNABbDOM stands out for its efficient implementation, small volume and flexible scalability. Its core code is only 300 lines +, but it has been applied to vUE and other lightweight front-end frameworks as the main function of VirtualDOM implementation.
A demo created using snabbdom looks like this:
import snabbdom from 'snabbdom';
import h from 'snabbdom/h';
const patch = snabbdom.init([
require('snabbdom/modules/class'), // makes it easy to toggle classes
require('snabbdom/modules/props'), / /for setting properties on DOM elements
require('snabbdom/modules/style'), // handles styling on elements with support for animations
require('snabbdom/modules/eventlisteners'), // attaches event listeners
]);
var vnode = h('div', {style: {fontWeight: 'bold'}}, 'Hello world');
patch(document.getElementById('placeholder'), vnode)
Copy the codeSnabbdom provides h function as the main function to create VirtualDOM. The three parameters accepted by H function reveal the three cores concerned in diFF algorithm: node type, attribute data and child node object. Patch method is the diff core function used to create the initial DOM node and update VirtualDOM.
function view(name) {
return h('div', [
h('input', {
props: { type: 'text', placeholder: 'Type a your name' },
on : { input: update }
}),
h('hr'),
h('div'.'Hello ' + name)
]);
}
var oldVnode = document.getElementById('placeholder');
function update(event) {
const newVnode = view(event.target.value);
oldVnode = patch(oldVnode, newVnode);
}
oldVnode = patch(oldVnode, view(' '));
Copy the codeThis is a typical app that triggers VirtualDOM updates via input events. In the h function, not only data attributes can be saved for VirtualDOM, but also event callback function can be set, in which relevant event attributes can be obtained and processed, such as the Event object in the Update callback. Create a new vnode by capturing the event, diff with the oldVnode, and finally update the current oldVnode, and show the update result to the user. The workflow is as follows:
The core patch function in snabbDOM source code clearly reflects VirtualDOM’s diFF by type and diff by list strategy: If the old and new nodes of patch are not the same node judged by sameVnode, the new node will be created and inserted and the old node will be deleted. SameVnode is based on whether the two nodes have the same key identifier and whether the incoming selector string with node type and other information is the same:
function sameVnode(vnode1, vnode2) {
return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}
Copy the codeThe implementation process of the main function patchVnode to perform the new and old diff on the same node is as follows, where oldCh and ch are to save the old current node and the new node to be updated:
// The new text does not existif (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); } // The old child does not exist, the new one existselse if(isDef(ch)) {// Old text existsif (isDef(oldVnode.text))
api.setTextContent(elm, ' '); AddVnodes (elm, null, ch, 0, ch.leng-1, insertedVnodeQueue); } // The new child does not exist, the old one doeselse if(isDef(oldCh)) { removeVnodes(elm, oldCh, 0, oldCh.length - 1); } // The new child does not exist; the old text doeselse if (isDef(oldVnode.text)) {
api.setTextContent(elm, ' ');
}
Copy the code- Diff the children of the node further if the new node is likely to be a complex node rather than a text node: First, determine whether the children of the new node are added or deleted as a whole. If so, batch update is performed. When both the new and old nodes contain the children list, updateChildren processing is performed
- If the old and new nodes are both text nodes and the two are different, only the text update is sufficient
The core diff method of updateChildren is described as follows. OldCh is used as the current VirtualDOM state, and oldCh is updated with the changes of newCh to obtain the new VirtualDOM state. Compare the startIndex and endIndex of the new and old nodes at the same time. This will get the diff result faster than the one-way sequential comparison.
- When the corresponding startVnode and endVnode of the new and old nodes are the same, the comparison continues, and the positions of startVnode and endVnode move to the middle one bit each.
- When oldStartVnode and newEndVnode are found to be the same, that is, oldStartVnode becomes the new end node, oldStartVnode is inserted into the following position of oldEndVnode
- When oldEndVnode and newStartVnode are the same, that is oldEndVnode becomes the new header node, oldEndVnode is inserted into the position before oldStartVnode
- If oldCh does not contain the current node in newCh, insert the new node in front of oldStartVnode, and map the node to see if there is a matching node in other locations. If there is a matching node, update the old node. Then insert it before the current oldStartVnode.
- At the end of this round of comparison, there are two cases. When oldStartIdx > oldEndIdx, oldCh has been traversed. AddVnodes is used to insert before positions of the parent nodes in batches. Before is often null. AddVnodes calls insertBefore to manipulate the DOM node. Let’s look at the insertBefore documentation: ParentElement. InsertBefore (newElement referenceElement) if referenceElement null newElement will be inserted into the child node to the end of the. If the newElement is already in the DOM tree, it is first removed from the DOM tree. So before is null, and newElement will be inserted at the end of the child node.
- If newStartIdx > newEndIdx, then newCh first iterates through the first comparison. The vnodes between oldStartIdx and oldEndIdx in oldCh need to be removed. Call removeVnodes to remove them from the DOM.
The React of reconcilation
In react history, the process for diff is reconcilation. When you call setState in a component, React reconcilates the component node as dirty, reconciles it, and gets a reconstructed subtree called virtual-DOM. Re-render the dirty nodes at the end of the workflow. If you setState on the root node of the component, the entire component tree Virtual DOM is recreated, but since this is not directly manipulating the real DOM, the actual impact is still limited.
In the React16 rewrite, the most important change was to change the core architecture to an asynchronous rendering architecture code-named Fiber. In essence, a Fiber is a POJO object, and a React Element can correspond to one or more Fiber nodes. The Fiber contains all the attribute data needed to work with the DOM node and React component. Therefore, although there is no clear concept of Virtual DOM in React code, the functions and mechanisms of Virtual DOM are fully completed through the design of Fiber.
In addition to assuming the role of Virtual DOM, Fiber is really designed to be a lightweight execution thread executed at the front end. It shares the same address space as ordinary threads, but can be scheduled by React’s own Fiber system to realize subdivision of rendering tasks, and can be timed, interrupted, and restarted. A powerful rendering task control mechanism for scheduling collaborative multitasking.
To get to the point, although the Fiber asynchronous rendering mechanism almost rewrote the whole reconcilable process, we can see from the analysis of the source code that the idea of reconciling nodes is basically the same as before version 16:
In version 16.3.1 of React, FiberNode will be created in the process of page initialization and render running, and the child node and siblings attribute are used to store the child node and sibling node respectively, and the return attribute is used to mark the parent node for easy traversal and modification. When a Fiber is updated, it will clone a new Fiber (called alternate) from the original Fiber (we call current). The side effect of two Fiber diff releases is recorded on alternate. So an update component will have at most two fibers corresponding to it, and alternate will replace the previous current node as the new current node after the update.
Skip the complicated process of building Fiber and look directly at the internal mechanism for updating a component. When setState is called in the component, the updateQueue property is first set on the component’s corresponding Fiber node to store the update in a queue. And then we’re going to go through the Fiber tree from the top, and we’re going to look for the Fiber node that needs to be updated, and we’re going to see if that node has an update in its updateQueue, and if so, we’re going to run the shouldUpdateComponent function that we know, If shouldUpdateComponent returns true, then execute componentWillUpdate and decide which way to update based on the type of the node. In this case, run the reconcile mechanism to diff. Run the componentDidUpdate function in lifeCycle after diff is complete.
const shouldUpdate = checkShouldComponentUpdate(
workInProgress,
oldProps,
newProps,
oldState,
newState,
newContext,
);
ifThis is to support react-lifecycles-compat compatible components // using the new API should not call non-secure lifecycle hooksif (
!hasNewLifecycles &&
(typeof instance.UNSAFE_componentWillUpdate === 'function' ||
typeof instance.componentWillUpdate === 'function') {// Start componentWillUpdate phase startPhaseTimer(workInProgress,'componentWillUpdate'); // Execute the componentWillUpdate hook on the component instanceif (typeof instance.componentWillUpdate === 'function') {
instance.componentWillUpdate(newProps, newState, newContext);
}
if (typeof instance.UNSAFE_componentWillUpdate === 'function') { instance.UNSAFE_componentWillUpdate(newProps, newState, newContext); } // Finish timing componentWillUpdate phase stopPhaseTimer(); } // Tag the current working Fiber, and then execute the componentDidUpdate hookif (typeof instance.componentDidUpdate === 'function') {
workInProgress.effectTag |= Update;
}
if (typeof instance.getSnapshotBeforeUpdate === 'function') { workInProgress.effectTag |= Snapshot; }}elseIf the current node is being updated, the componentDidUpdate hook should be executed even if the update is terminatedif (typeof instance.componentDidUpdate === 'function') {
if( oldProps ! == current.memoizedProps || oldState ! == current.memoizedState ) { workInProgress.effectTag |= Update; }}if (typeof instance.getSnapshotBeforeUpdate === 'function') {
if( oldProps ! == current.memoizedProps || oldState ! == current.memoizedState ) { workInProgress.effectTag |= Snapshot; }}Copy the codeAfter we setState in the component, React will treat it as a dirty node. After the event stream is over, React will find the dirty component node and diff it. It’s worth noting that while rerender builds a new Virtual DOM tree, it doesn’t touch the real DOM. Instead of creating a new Fiber tree, alternate and current properties are set for each Fiber node to store alternate and current versions of the node, respectively, and a new Fiber node is generated for update after the tree is traversed to find the dirty nodes:
As described in the React official document, when a node needs to be updated (shouldComponentUpdate), the next step is to apply the Reconcile process and the Reconcile process to its child nodes. Here we can determine whether to update the logic by writing the override shouldComponentUpdate function in the component:
ReconcileChildFiber function reconcileChildFiber is the core source code of reconcileChildFiber process, and the main implementation methods are as follows: The reconcileChildrenArray process varies according to the type of incoming components, with the most complex reconcileChildrenArray being invoked for an incoming subcomponent array. ReconcileChildrenArray starts to compare old and new child node array reconcilechildarray in index order by default. Since the Fiber node itself does not have a backward pointer, React currently does not adopt the algorithm of comparing both ends simultaneously. In other words, each sibling Fiber node at the same level can only point to the next node. Therefore, normally react will just call updateSlot to update the new Fiber data directly to the old Fiber’s location according to its type.
In the sequential comparison, if no unequal key values are found by using updateSlot, the old node will be replaced with the new node. After the first round of traversal is completed, the remaining old nodes will be deleted in batch if the new node has been traversed. If the old node has been traversed, there are still new nodes left. Are the ends of bulk insert the new node, if found in the first round of the traversal key values are not equal, directly out of the above steps, according to the key value to traverse the update, and then remove is not the above situation the elements involved, thus it can be seen in the component list structure, add the key value is to boost the diff algorithm efficiency.
Here’s the source code for reconcileChildrenArray:
// React uses flow for type checkingfunction reconcileChildrenArray(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChildren: Array<*>,
expirationTime: ExpirationTime,
): Fiber | null {
let resultingFirstChild: Fiber | null = null;
let previousNewFiber: Fiber | null = null;
let oldFiber = currentFirstChild;
let lastPlacedIndex = 0;
let newIdx = 0;
let nextOldFiber = null;
for(; oldFiber ! == null && newIdx < newChildren.length; NewIdx++) {// there is no simultaneous comparison on both ends, which is limited to the unidirectional structure of the Fiber listif (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else{nextOldFiber = oldfiber.sibling; } // try to update the old node with a newFiberreturnFiber, oldFiber, newChildren[newIdx], expirationTime, ); // If the key values are not equal during the traversal, the first round of traversal is skippedif (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
if (shouldTrackSideEffects) {
if(oldFiber && newFiber. Alternate === null) {// if (oldFiber && newFiber.returnFiber, oldFiber); } } lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // Record the last updated child nodeif (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
if(newIdx === newchildren.length) {// we have traversed all the new nodes, delete the remaining old nodesreturnFiber, oldFiber);
return resultingFirstChild;
}
if(oldFiber === null) {// Insert the remaining nodes in order if the old nodes are traversed firstfor (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(
returnFiber,
newChildren[newIdx],
expirationTime,
);
if(! newFiber) {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;
}
returnresultingFirstChild; Const existingChildren = mapRemainingChildren(); // mapRemainingChildren();returnFiber, oldFiber); Use map to find nodes that need to be saved or deletedfor(; newIdx < newChildren.length; Const newFiber = updateFromMap(existingChildren,returnFiber,
newIdx,
newChildren[newIdx],
expirationTime,
);
if (newFiber) {
if (shouldTrackSideEffects) {
if(newFiber.alternate ! == null) {// The new Fiber is also a worker thread, but if the current instance already exists, we can reuse the Fiber. // We will delete the new Fiber from the list. Existingchildren.delete (newfiber.key === null? NewIdx: newfiber.key,); LastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}ifExistingchildren.foreach (child => deleteChild())returnFiber, child)); } // Finally return the first node in the list of Fiber subnodesreturn resultingFirstChild;
}
Copy the codeConclusion:
The design of VirtualDOM is an effective solution to improve front-end rendering performance, and therefore provides the basis for data-driven front-end framework tools, which can liberate us from the tedious operation of DOM. Different VirtualDOM schemes are basically based on three DIFF principles in terms of DIFF. The specific DIFF process selects the diFF implementation considering the data structure, algorithm efficiency, component life cycle and design in its own running context. For example, snABbDOM’s updateChildren implementation above uses the update strategy of simultaneous comparison on both ends and moving according to the position order, while React is limited by the one-way structure of Fiber and is updated by direct replacement in order. However, the React optimized component design and the Fiber worker threading mechanism provide efficiency gains in terms of overall rendering performance, while both provide a way to improve diff strategies based on key values.
The design of VirtualDOM has a profound influence. This paper only introduces the ideas in VirtualDOM and the implementation of DIff in detail. In addition, there are still many different concrete implementation ways to explore such as how to create a VirtualDOM tree and how to patch update diff results. And React16’s Fiber mechanic is a step forward in asynchronous rendering, which is worth keeping an eye on.
Refer to the reading
Diff algorithm class:
Snabbdom source
React-less Virtual DOM with Snabbdom :functions everywhere!
Snabbdom source code parsing, teach you to achieve a streamlined Virtual DOM library
The React ‘s diff algorithm
Snabbdom – a Virtual DOM Focusing on Simplicity – Interview with Simon Friis Vindum
How to develop Qunar Mini React
Fiber is introduced class
React Fiber Architecture
How to understand React Fiber architecture?
React 16 Fiber
How React Fiber can make your web and mobile apps smoother and more responsive
What is the React Fiber engine?