What is the Virtual DOM
The Virtual DOM is an abstraction of the DOM, essentially a JavaScript object that is a more lightweight description of the DOM.
Why the Virtual DOM
Since we already have the DOM, why do we need an extra layer of abstraction?
First of all, we all know that on the front end performance optimization of a secret is to as little as possible to the DOM, operation is not only a DOM is relatively slow, but because of the frequent changes of DOM can cause the browser’s back or return to, the performance of all of these are killers, so we need a layer of abstraction, in the process of patch updates to the DOM, as far as possible one-time differences This ensures that DOM performance does not deteriorate.
Second, is a basic requirement of the modern front frame does not need to manually DOM, on the one hand because of manual DOM cannot guarantee program performance, collaboration projects if you don’t strict review, there may be a developer write performance low code, on the other hand, more important is to omit the manual DOM manipulation can greatly improve the development efficiency.
Finally, and the original purpose of Virtual DOM, is better cross-platform, for example, Node.js does not have DOM, if you want to achieve SSR(server-side rendering), then one way is to use Virtual DOM, because Virtual DOM itself is a JavaScript object.
Key elements of the Virtual DOM
Creation of the Virtual DOM
We already know that the Virtual DOM is an abstraction of the real DOM, and different abstractions can be made according to different requirements. For example, snabbdom.js is abstracted in this way.
Of course, since snabbdom.js is a production-oriented library, it does a lot of abstractions. We’ll use the simplest abstraction method because we understand it as a tutorial:
{
Type, // String, the DOM node type, such as 'div'
Data, // Object, including props, style, and other DOM node properties
Children // Array, child node
}
Once we have our abstract Virtual DOM construction figured out, we need a function to create the Virtual DOM.
/ * *
* generate vnode
* @param {String} type, such as 'div'
* @param {String} key Specifies the unique ID of a key Vnode
* @param {Object} data data, including attributes, events and so on
* @param {Array} children Child Vnode
* @param {String} text Text
* @param {Element} elm
* @return {Object} vnode
* /
function vnode(type, key, data, children, text, elm) {
const element = {
__type: VNODE_TYPE,
type, key, data, children, text, elm
}
return element
}
This function is simple: it takes a set of parameters and returns an object based on those parameters, which is an abstraction of the DOM.
Create a Virtual DOM Tree
We have already declared a vNode function to create a single Virtual DOM, but we know that the DOM is actually a Tree. What we need to do is to declare a function to create an abstraction of the DOM Tree — the Virtual DOM Tree.
function h(type, config, ... children) {
const props = {}
let key = null
// Get the key and fill the props object
if (config ! = null) {
if (hasValidKey(config)) {
key = '' + config.key
}
for (let propName in config) {
if (hasOwnProperty.call(config, propName) && ! RESERVED_PROPS[propName]) {
props[propName] = config[propName]
}
}
}
return vnode(
type,
key,
props,
flattenArray(children).map(c => {
return isPrimitive(c) ? vnode(undefined, undefined, undefined, undefined, c) : c
})
)
}
Virtual DOM updates
The Virtual DOM is ultimately a JavaScript object, and we need to find a way to map the Virtual DOM to the real DOM. That is, we need to declare a function that converts a VNode into a real DOM.
function createElm(vnode, insertedVnodeQueue) {
let data = vnode.data
let i
// omit the hook call
let children = vnode.children
let type = vnode.type
// generate the DOM according to type
/ / handle the comment
if (type === 'comment') {
if (vnode.text == null) {
vnode.text = ''
}
vnode.elm = api.createComment(vnode.text)
}
// Handle other types
else if (type) {
const elm = vnode.elm = data.ns
? api.createElementNS(data.ns, type)
: api.createElement(type)
// Call create hook
for (let i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode)
// Handle children and text separately.
Vnode children and text do not/should exist at the same time.
if (isArray(children)) {
// Recursive children to ensure that each vnode in the vNode tree has its own dom;
// Construct the DOM tree corresponding to the vNode tree.
children.forEach(ch => {
ch && api.appendChild(elm, createElm(ch, insertedVnodeQueue))
})
}
else if (isPrimitive(vnode.text)) {
api.appendChild(elm, api.createTextNode(vnode.text))
}
// Call create hook; Populate the insertedVnodeQueue for insert hooks.
i = vnode.data.hook
if (i) {
i.create && i.create(emptyNode, vnode)
i.insert && insertedVnodeQueue.push(vnode)
}
}
// handle text (the type of text is empty)
else {
vnode.elm = api.createTextNode(vnode.text)
}
return vnode.elm
}
The above functions are simple: generate the corresponding DOM based on type, and set the various properties defined in data to the DOM.
Virtual DOM diff
The diff of the Virtual DOM is the most difficult and core part of the entire Virtual DOM. The purpose of diFF is to compare the old and new Virtual DOM trees to find out the differences and update them.
It can be seen that diff is a key part that directly affects the performance of Virtual DOM.
In order to compare the differences of Virtual DOM Tree, the theoretical time complexity is as high as O(n^3), which is an extremely high time complexity. Obviously, choosing such an inefficient algorithm cannot meet our basic requirements for program performance.
Fortunately, DOM changes across hierarchies are rare in our actual development. DOM changes are usually hierarchical, so modern Virtual DOM libraries compare hierarchies only. In this case, our time complexity is O(n).
Then we need to implement a function to perform a specific diff operation. The core algorithm of the function updateChildren is as follows:
// Iterate over oldCh and newCh to compare and update
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
/ / 1 ⃣ ️ first check 4 kinds of circumstances, to ensure oldStart/oldEnd/newStart/newEnd
// If the vnodes on the left are empty, move the index right; if the vnodes on the right are empty, move the index left.
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
}
/ * *
* 2 ⃣ ️ then oldStartVnode/oldEndVnode newStartVnode/newEndVnode two comparison,
* Execute patch logic for the four cases with the same VNode.
* - If two vNodes with the same start or end are the same (cases 1 and 2),
* Update the dom attribute/children instead of moving the actual DOM.
* - If the start and end vnodes are the same (cases 3 and 4),
* That means the VNode has been moved, and we need to move the DOM as well.
* /
// 1. If oldStartVnode and newStartVnode are the same (with the same key), run patch
else if (isSameVnode(oldStartVnode, newStartVnode)) {
// No need to move the DOM
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
// 2. If oldEndVnode and newEndVnode are the same, run patch
else if (isSameVnode(oldEndVnode, newEndVnode)) {
// No need to move the DOM
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
// 3. If oldStartVnode and newEndVnode are the same, run patch
else if (isSameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
/ / to get the updated oldStartVnode/newEndVnode dom moves to the right, move to
// oldEndVnode corresponds to the right of the DOM. Why is it moving to the right?
// (1) oldStartVnode is the same as newEndVnode.
// (2) If the while loop is just beginning, then it is reasonable to move to the right of oldendvNode. elm.
// (3) If the loop is not just beginning, since the comparison is from both ends to the middle, then the DOM position at both ends is already
Oldendvnode. elm is the correct location;
// (4) Remember, oldVnode and vnode are the same patch, and oldVnode corresponds to its own DOM
// Always existing, vnode dom does not exist, directly reuse oldVnode corresponding DOM.
api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
// 4. If oldEndVnode and newStartVnode are the same, run patch
else if (isSameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// Here is the left-shifted updated DOM for the same reason as the right-shifted above.
api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
// 3 one last case: 4 Vnodes are different, so we need to
Create key --> index map from oldCh array.
// 2. Process only newStartVnode (simplify logic, we will eventually process all vNodes with loops),
// Get index from map with its key;
// 3. If index exists, then there is a corresponding old vnode, patch.
// 4. If index does not exist, newStartVnode is a new vnode
// Create the corresponding DOM and insert it.
else {
// If oldKeyToIdx does not exist, create the vNode key of old Children to index
// map, so that we can get the subscript via key later.
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// Try to get the subscript with newStartVnode's key
idxInOld = oldKeyToIdx[newStartVnode.key]
// If the subscript does not exist, newStartVnode is a new Vnode.
if (idxInOld == null) {
// Then create a DOM for newStartVnode and insert it in front of oldStartvNode.elm.
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
}
// VNodes with the same key exist in old children.
else {
elmToMove = oldCh[idxInOld]
// If the type is different, you have no choice but to create a new DOM;
if (elmToMove.type ! == newStartVnode.type) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
}
// If the type is the same (and the key is the same), it indicates the same VNode. Run patch.
else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
// After the loop above is complete (there are two loop conditions), process possible unprocessed VNodes.
// If there is an unprocessed (oldStartIdx > oldEndIdx) in new vNodes
// Old vNodes are processed first.)
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}
// Conversely, if old VNodes have unprocessed dom, remove the excess DOM.
else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
We can assume that there are two arrays, the old Vnode array and the new Vnode array, and that there are four variables that act as Pointers to the beginning and end of each array.
Repeat the process until the head pointer of either array exceeds the tail pointer and the loop ends:
-
Head comparison: Compare the heads of two arrays. If found, patch the new node to the old node and move the head pointer back
-
End to end comparison: compare the ends of two arrays. If found, patch the new node to the old node and move the end pointer forward
-
Comparison of the old tail and the new head: cross-compare the old tail and the new head. If it is found, patch the new node to the old node, and the old tail pointer moves forward and the new head pointer moves back
-
Comparison of old head and new tail: cross-compare the old head and new tail. If the old head and new tail are found, patch the new node to the old node, and move the new tail pointer forward and the old head pointer backward
-
Use key comparison: use the key of the node corresponding to the new pointer to find the corresponding node in the old array. There are three cases here. When there is no corresponding key, create a new node; if there is a key and it is the same node, patch the new node to the old node; if there is a key but not the same node, create a new node
We assume we have two arrays, old and new:
-
Old array: [1, 2, 3, 4, 5]
-
New array: [1, 4, 6, 1000, 100, 5]
First, we do a header comparison. Both the old and new arrays have 1 heads, so we move the pointer to the head of both arrays back.
We continue the first comparison, but 2! == 4 causes the comparison to fail, I enter tail to tail comparison,5 === 5, then the tail pointer can move forward.
Now enter a new loop, head contrast 2! == 4, tail to tail comparison of 4! == 100. At this point, cross comparison is performed. The old tail and the new head are compared first, that is, 4 === 4, the old tail moves forward and the new head moves backward.
And then you go into a new cycle, and the head compares 2! == 6, tail to tail comparison 3! == 100, cross contrast 2! 3 = 100! = 6, all the four comparison methods do not meet the requirement. If you need to compare by key at this time, then move the new head pointer back
The loop continues until the head pointer of any array exceeds the tail pointer, and the loop ends.
At the end of the loop, there may be uniterated conditions in both arrays:
-
First compare the pointer to the beginning and end of the old array. If the old array is traversed, add the missing node to the new array
Adding a Missing Node
-
Then compare the pointer to the beginning and end of the new array. If the new array has been traversed, delete the missing node from the old array
Delete redundant nodes
Optimization of Virtual DOM
In the last section, our Virtual DOM implementation referred to the implementation of snabbdom.js. Of course, vue.js also referred to the implementation of snabbdom.js. We omitted a lot of code related to edge state and SVG, and only implemented the core part.
Snabbdom.js has been the mainstream Virtual DOM implementation in the community,vue 2.0 stage and Snabbdom.js have adopted the “double end comparison algorithm” explained above, so are there any optimization schemes to make it faster?
In fact, there are faster algorithms in the community, such as Inferno. Js, which is the fastest React-like framework (although inferno. Js is not only strong because of the algorithm, but its diff algorithm is the fastest), and Vue 3.0 will be optimized using inferno.
We can wait for the release of Vue 3.0 to find out. For specific optimization ideas, we can first refer to the principle overview of DIFF algorithm. One of the core ideas is to use the idea of LIS(longest increasing subsequence) to do dynamic programming and find the minimum number of moves.
For example, in the following two arrays, the React algorithm moves a, B, and C to their corresponding positions + 1, while Inferno. Js moves D directly to the front of the array.
* A: [a b c d]
* B: [d a b c]
Copy the codeReference article:
-
Overview of diff algorithm principle
-
snabbdom
-
Parse snabbDOM source code
-
nerv
