Writing is not easy, without the permission of the author forbid to reprint in any form! If you think the article is good, welcome to follow, like and share!
Vue advanced Diff algorithm in detail
I. Virtual DOM
What is the virtual DOM?
Virtual DOM abstracts the structure and information of the real DOM tree and simulates the tree structure in the form of objects, as follows:
True DOM.
<div>
<p>Hello World</p>
</div>
Copy the codeThe corresponding virtual DOM is:
let vnode = {
tag: 'div'.children:[ {tag:'p'.text:'Hello World'}}]Copy the codeWhy do you need a virtual DOM?
Real DOM rendering will have some overhead. If real DOM rendering is performed every time data is modified, it will cause DOM tree redrawing and rearrangement, and the performance cost is very high. Is it possible to modify only a small part of the data without rendering the whole DOM? Virtual DOM and Diff algorithms can be implemented.
How?
- First, generate a virtual DOM tree based on the real DOM
- When a DOM node’s data changes, a new Vnode is generated
- Compare the new Vnode with the old oldVnode
- Patch the real DOM, create Vnode, remove oldVnode and so on through patch function
What’s the difference?
- Real DOM operations are modified one attribute at a time, which is costly.
- The virtual DOM directly modifies the entire DOM node and then replaces the real DOM
What else is good?
Vue’s virtual DOM data update mechanism is asynchronous update queue. Instead of updating DOM immediately after data changes, it is promoted to an asynchronous data update queue for unified update. Want to get the updated DOM information right away? There’s an API called Vue.Nexttick
2. Diff algorithm
Traditional Diff algorithm
Every node in the two trees is traversed, and every two nodes are compared.
For example, a-> E, a-> D, a-> B, a-> C, a->a
- The time to complete the traversal is O(n^2).
- After you compare the differences, you have to calculate the minimum conversion, and the complexity is O(n^3).
Vue optimized Diff algorithm
Vue’s Diff algorithm only compares elements of the same level, and does not compare across levels
Realization of Diff algorithm in Vue
Vnode classification
- EmptyVNode: Comment node with no content
- TextVNode: text node
- ElementVNode: Common element node
- ComponentVNode: Component node
- CloneVNode: A cloned node can be any of the preceding types, the only difference being that the isbiology attribute is true
The Patch function
The patch function receives the following parameters:
- OldVnode: Indicates an old virtual node
- Vnode: indicates a new virtual node
- Hydrating: Whether to mix with the real DOM
- RemoveOnly: Indicates a special flag for the Transition-group
The processing process is divided into the following steps:
- If vnode does not exist and oldVnode exists, remove the oldVnode
- If vNode exists but oldVnode does not exist, create a Vnode
- Vnode and oldVnode exist
- If vNode and oldVnode are the same node (use the sameVnode function to compare for details), use patchVnode to perform follow-up comparison
- If vnode and oldVnode are not the same node, then a new element based on vnode is created and mounted to the oldVnode parent element. If the component root node is replaced, iterate to update the parent node element. Then remove the old node. If oldVnode is a server rendering element node, you need to use the function hydrate to map the virtual DOM to the real DOM
The source code is below, with comments written for easy reading
return function patch(oldVnode, vnode, hydrating, removeOnly) {
// If vNode does not exist but oldVnode does exist, remove oldVnode
if (isUndef(vnode)) {
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
// Create vNode if oldVnode does not exist but vNode does
if (isUndef(oldVnode)) {
isInitialPatch = true
createElm(vnode, insertedVnodeQueue)
} else {
// In the remaining case, both vnode and oldVnode exist
// Check whether it is a real DOM element
const isRealElement = isDef(oldVnode.nodeType)
if(! isRealElement && sameVnode(oldVnode, vnode)) {// If vnode and oldVnode are the same (sameVnode)
// Use the patchVnode function to perform the follow-up comparison.
patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
} else {
// Vnode and oldVnode are not the same case
if (isRealElement) {
// If real nodes exist, the data-server-render attribute exists
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
// Hydrating is true when the old Vnode is a server rendering element
oldVnode.removeAttribute(SSR_ATTR)
hydrating = true
}
We need to use the hydrate function to map the virtual DOM to the real DOM
if (isTrue(hydrating)) {
// Need to merge into the real DOM
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
// Call the insert hook
invokeInsertHook(vnode, insertedVnodeQueue, true)
return oldVnode
} else if(process.env.NODE_ENV ! = ='production') {
warn(
'The client-side rendered virtual DOM tree is not matching ' +
'server-rendered content. This is likely caused by incorrect ' +
'HTML markup, for example nesting block-level elements inside ' +
'<p>, or missing <tbody>. Bailing hydration and performing ' +
'full client-side render.')}}// If the element is not rendered by the server or fails to merge into the real DOM, create an empty Vnode node to replace it
oldVnode = emptyNodeAt(oldVnode)
}
// Obtain the parent oldVnode
const oldElm = oldVnode.elm
const parentElm = nodeOps.parentNode(oldElm)
// Create a real DOM node from the vnode and mount it to the parent node of oldVnode
createElm(
vnode,
insertedVnodeQueue,
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
// If the component root node is replaced, iterate to update the parent Element
if (isDef(vnode.parent)) {
let ancestor = vnode.parent
const patchable = isPatchable(vnode)
while (ancestor) {
for (let i = 0; i < cbs.destroy.length; ++i) {
cbs.destroy[i](ancestor)
}
ancestor.elm = vnode.elm
if (patchable) {
for (let i = 0; i < cbs.create.length; ++i) {
cbs.create[i](emptyNode, ancestor)
}
/ / # 6513
// invoke insert hooks that may have been merged by create hooks.
// e.g. for directives that uses the "inserted" hook.
const insert = ancestor.data.hook.insert
if (insert.merged) {
// start at index 1 to avoid re-invoking component mounted hook
for (let i = 1; i < insert.fns.length; i++) {
insert.fns[i]()
}
}
} else {
registerRef(ancestor)
}
ancestor = ancestor.parent
}
}
// Destroy the old node
if (isDef(parentElm)) {
// Remove the old node
removeVnodes(parentElm, [oldVnode], 0.0)}else if (isDef(oldVnode.tag)) {
// Call the destroy hook
invokeDestroyHook(oldVnode)
}
}
}
// Call the insert hook and return the node
invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
return vnode.elm
}
Copy the codeSameVnode function
How does Vue determine whether it is the same node? The process is as follows:
- Check whether the Key values are the same
- Whether the values of tag are the same
- IsComment, don’t worry too much about that.
- data
- SameInputType () is used to determine the input items of the form: the input is the same but the type inside is different
It can be seen from here that key can assist diff algorithm, which can quickly locate whether it is the same element, and must ensure the uniqueness.
If you use index as the key, the key changes every time you change the order, making this judgment invalid and reducing the efficiency of Diff.
Therefore, using good key is also a way to optimize Vue performance.
- The source code is as follows:
function sameVnode(a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
a.asyncFactory === b.asyncFactory &&
isUndef(b.asyncFactory.error)
)
)
)
}
Copy the codePatchVnode function
Prerequisites Vnode and oldVnode are the same node
Execution process:
- If oldVnode and vnode references are the same, return is considered unchanged
- If oldVnode’s isAsyncPlaceholder property is true, skip checking for asynchronous components and return
- If oldVnode and vnode are static nodes and have the same key, and vnode is a clone or v-once command control node, only need to copy oldvNode. elm and oldvNode. child to vnode, there is no other operation, return
- If the vNode is not a text section or comment node
- If both vNode and oldVnode have children and the children are inconsistent, updateChildren is called to update the children
- If only vNodes have child nodes, call addVnodes to create the child nodes
- If only oldVnode has children, then call removeVnodes to remove all of them
- If the vnode text is undefined, clear the vnode.elm text
- If vNode is a text node but has different text content than oldVnode, just update the text.
The source code is below, with comments written for easy reading
function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {
// If the old and new references are the same, return directly.
if (oldVnode === vnode) {
return
}
const elm = vnode.elm = oldVnode.elm
// Skip checking asynchronous components if oldVnode's isAsyncPlaceholder property is true
if (isTrue(oldVnode.isAsyncPlaceholder)) {
if (isDef(vnode.asyncFactory.resolved)) {
hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
} else {
vnode.isAsyncPlaceholder = true
}
return
}
// If both new and old nodes are static nodes, vNode keys are the same
// The new Vnode is cloned or the new Vnode has the V-once property
// Assign and return. The componentInstance of vNode remains the same
if (isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
) {
vnode.componentInstance = oldVnode.componentInstance
return
}
let i
const data = vnode.data
// Execute the data.hook.prepatch hook
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
i(oldVnode, vnode)
}
// Get the list of child elements
const oldCh = oldVnode.children
const ch = vnode.children
if (isDef(data) && isPatchable(vnode)) {
// Iterate calls the cbs.update hook function to update all properties of oldVnode
// Includes attrs, class, domProps, events, style, ref, and directives
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
// Execute the data.hook. Update hook
if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
}
// The Vnode's text option is undefined
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
// The children of the new and old nodes are different, so execute the updateChildren method
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) {
// oldVnode children The addVnodes method does not exist
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) {
// The removeVnodes method does not exist for vnode
removeVnodes(elm, oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) {
// Delete the text from the old node.
nodeOps.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// New and old nodes have different text content, update the text
nodeOps.setTextContent(elm, vnode.text)
}
if (isDef(data)) {
// Execute the data.hook.postpatch hook, and the patch is complete
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}
Copy the codeUpdateChildren function
Important!!
Prerequisite: Vnode and oldVnode have unequal children
The overall implementation idea is as follows:
-
The vnode header compares the oldVnode header
-
Vnode tail compares oldVnode tail
-
The vnode header compares the oldVnode tail
-
The vnode tail compares with the oldVnode head
- As long as one situation is met, operation such as patch, moving node and moving subscript is carried out
-
I’m going to find another node in oldChild that has the same key as newStart
-
Can’t find it, create a new one.
-
Find, get this node, and determine if it is the same node as newStartVnode
- If it is the same node, patch and insert the node before oldStart, and the newStart subscript continues to move
- If it is not the same node, you need to execute createElm to create a new element
-
Why is there a head to tail, tail to tail operation?
- Reverse operation can be detected quickly to speed up diFF efficiency.
The source code is commented as follows:
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
// Define variables
let oldStartIdx = 0 // The old node Child header subscript
let newStartIdx = 0 // New node Child header subscript
let oldEndIdx = oldCh.length - 1 // The old node Child subscript
let oldStartVnode = oldCh[0] // The old Child header node
let oldEndVnode = oldCh[oldEndIdx] // The old Child endpoint
let newEndIdx = newCh.length - 1 // New node Child subscript
let newStartVnode = newCh[0] // New node Child header node
let newEndVnode = newCh[newEndIdx] // The new node Child tail node
let oldKeyToIdx, idxInOld, vnodeToMove, refElm
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
constcanMove = ! removeOnlyif(process.env.NODE_ENV ! = ='production') {
checkDuplicateKeys(newCh)
}
// Define the loop
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// Detection exists
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
// If the old Child header is the same as the new Child header
} else if (sameVnode(oldStartVnode, newStartVnode)) {
/ / patch
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
// Patch After moving the node, continue to compare the next node
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
// If the old Child tail and the new Child tail are the same node
} else if (sameVnode(oldEndVnode, newEndVnode)) {
/ / patch
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
// Patch After moving the node, continue to compare the next node
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
// If the old Child header and the new Child tail are the same node
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
/ / patch
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// Put oldStart after oldEnd
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// Patch After moving the node, continue to compare the next node
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
// If the old Child tail and the new Child header are the same node
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
/ / patch
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// Put oldEnd before oldStart
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
// Patch After moving the node, continue to compare the next node
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// If there is no same Key, execute the createElm method to create the element
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key) ?
oldKeyToIdx[newStartVnode.key] :
findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
// If both nodes have the same Key, determine whether they are sameNode
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
// If it is the same node, patch and insert oldStart before oldStart, newStart subscript continues to move
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// If the node is not the same, run createElm to create a new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
// oldStartIdx > oldEndIdx = newEndIdx; // oldChild = oldChild
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
// If newStartIdx > newEndIdx indicates that newChild has traversed first, remove the nodes that oldChild has not traversed
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codeFour,
- Proper use of keys allows for fast sameVnode comparisons and accelerated Diff efficiency, which can be used as a point of performance optimization.
- DIff only does peer comparisons, using the sameVnode function, where the text node directly replaces the text content.
- The Diff of the list of child elements is compared head to head, tail to tail, and head to tail until the list of child elements of the two elements has been traversed.
- AddVnode/removeVnode
The original link: Vue Diff algorithm explanation | step in learning notes
Continue to share technical blog posts, follow wechat public account 👇🏻
