Home >Web Front-end >Vue.js >Quickly understand the Vue2 diff algorithm (detailed graphic explanation)
The diff algorithm is an efficient algorithm that compares tree nodes at the same level, avoiding the need to search and traverse the tree layer by layer. So how much do you know about the diff algorithm? The following article will give you an in-depth analysis of the diff algorithm of vue2. I hope it will be helpful to you!
I have been looking at the source code of Vue 2 for a long time. From using flow to now using TypeScript, I will open its source code and take a look every time, but every time I only saw the data initialization part, which is the stage of beforeMount
, about how to generate VNode (Visual Dom Node, which can also be directly called vdom) and how to compare VNode (diff) when updating components ) has never been carefully studied. I only know that the double-ended diff algorithm is used. As for how this double-ended starts and ends, I have never seen it, so I took the opportunity to write an article to study it carefully this time. If the content is wrong, I hope you can help me point it out. Thank you very much~
In my understanding, diff refers to differences
, that is, calculating the difference between old and new content; the diff algorithm in Vue quickly compares the old and new content through a simple and efficient method The difference between VNode node arrays is to update page content with minimal dom operations. [Related recommendations: vuejs video tutorial, web front-end development]
There are two necessary prerequisites here:
The comparison is the VNode array
There are two sets of old and new VNode arrays at the same time
So it generally only occurs when data updates Execute when the page content needs to be updated, that is, renderWatcher.run()
.
As mentioned above, what is compared in diff is VNode, not the real dom node. I believe that why VNode is used? Most people compare It’s clear, let me just briefly explain it, right?~
There are roughly two reasons for using VNode in Vue:
VNode is designed as a framework designer according to the framework requirements. The JavaScript object itself has simpler properties than the real DOM node, and there is no need to perform DOM query during operation, which can greatly optimize the performance consumption during calculation
This link from VNode to the real DOM The rendering process can be processed differently according to different platforms (web, WeChat applet) to generate real dom elements adapted to each platform
During the diff process, the old and new node data will be traversed. In comparison, using VNode can bring great performance improvements.
In the web page, the real dom nodes exist in the form of tree, and the root nodes are all
, in order to ensure that the virtual node is consistent with the real dom node, VNode also uses a tree structure.
If all VNode nodes need to be compared when the component is updated, both the old and new sets of nodes need to be deeply traversed and compared, which will cause a lot of performance overhead; therefore, by default in Vue Comparison of nodes at the same level, that is, if the levels of the old and new VNode trees are different, the content of the extra levels will be directly created or discarded, and only the diff operation will be performed at the same level.
Generally speaking, diff operations generally occur in v-for
loops or v-if/v-else
, component
and the like. Dynamically generate node objects (static nodes generally do not change, and comparison is very fast), and this process is to update the dom, so in the source code, the method name corresponding to this process is updateChildren
, located in src/core/vdom/patch.ts
. As shown below:
Here is a review of the creation and update process of Vue component instances:
First of all
beforeCreate
to thecreated
stage, mainly processing data and status as well as some basic events and methodsThen,
$mount(vm .$options.el)
method enters the creation and mounting phase ofVnode
and dom, that is, betweenbeforeMount
andmounted
(when the component is updated Similar to here)The
$mount
on the prototype will be rewritten inplatforms/web/runtime-with-compiler.ts
, and the original implementation is inplatforms/web/runtime/index.ts
; in the original implementation method, it actually calls themountComponent
method to executerender
; and inweb
Theruntime-with-compiler
below adds the template string compilation module, which will perform thetemplate
inoptions
Once parsed and compiled, converted into a function bound tooptions.render
mountComponent
inside the function defines rendering MethodupdateComponent = () => (vm._update(vm._render())
, instantiates awatcher
instance withbefore
configuration (i.e.renderWatcher
), by defining thewatch
observation object as the just-definedupdateComponent
method to perform the first component rendering and trigger dependency collection , wherebefore
The configuration only configures the method to trigger thebeforeMount/beforeUpdate
hook function; this is why the real dom node cannot be obtained in thebeforeMount
stage and thebeforeUpdate
stage The reason is that the old dom node
_update
method is defined in the same file asmountComponent
, and its core is reading The$el
(old dom node) and_vnode
(old VNode) in the component instance are compared with thevnode
generated by the_render()
function.patch
Operation
patch
The function first compares to see if it has an old node. If not, it must be a new one. Component, create and render directly; if there is an old node, compare the old and new nodes throughpatchVnode
, And if the old and new nodes are consistent and both havechildren
child nodes, Then enter the core logic ofdiff
-updateChildren
Child node comparison update, this method is also what we often call thediff
algorithm
Since we are comparing the old and new VNode arrays, there must first be a comparison judgment method: sameNode (a, b)
, method of adding nodesaddVnodes
, method of removing nodesremoveVnodes
, of course, even after sameNode
determines that the VNode is consistent , patchVnode
will still be used to deeply compare the contents of a single new and old VNode to confirm whether the internal data needs to be updated.
This method has one purpose: Compare whether the old and new nodes are the same.
In this method, the first thing to compare is whether the key
of a and b are the same. This is why Vue notes v-for, v-if, Dynamic nodes such as v-else
must set key
to identify the uniqueness of the node. If key
exists and is the same, you only need to compare whether the internal changes have occurred. Under normal circumstances It can reduce a lot of DOM operations; if it is not set, the corresponding node elements will be directly destroyed and rebuilt.
Then it will compare whether it is an asynchronous component, and here it will compare whether their constructors are consistent.
Then you will enter two different situations for comparison:
undefined
The overall process of the function is as follows
As the name suggests, add new VNode nodes.
This function receives 6 parameters: parentElm
The parent element of the current node array, refElm
The element at the specified position, vnodes
New Virtual node array, startIdx
The starting position of the inserted element of the new node array, endIdx
The end index of the inserted element of the new node array, insertedVnodeQueue
The virtual node that needs to be inserted Node queue.
The internal function will traverse the vnodes
array starting from startIdx
until the endIdx
position , and then call createElm
Create and insert the elements corresponding to vnodes[idx]
before refElm
in turn.
Of course, there may be Component
components in this vnodes[idx]
, and createComponent
will also be called to create the corresponding Component instance.
Because the entire
VNode
and dom are both a tree structure, so after comparison at the same level, it is necessary to process the deeper VNode under the current level. and dom processing.
Contrary to addVnodes
, this method is used to remove VNode nodes.
Since this method only removes, it only requires three parameters: vnodes
Old virtual node array, startIdx
Start index, endIdx
End index.
The internal function will traverse the vnodes
array starting from startIdx
until the endIdx
position , if vnodes[idx ]
If it is not undefined
, it will be processed according to the tag
attribute:
recursively process the contents of
vnodes[idx], trigger remove hooks and destroy hooks
does not exist
tag, you can directly remove the node from the dom
In this method, it mainly contains nine
main parameter judgments, and corresponds to different processing logic:The old and new VNodes are congruent, It means there is no change,
If the new VNode has real dom binding, and the node set that needs to be updated is an array, copy the current The VNode goes to the specified position of the collection
hydrate The function converts the new VNode into a real dom for rendering; in both cases, exits the function
key are equal, or if the node is not updated if isOnce is specified, the component instance of the old node will be directly
reused and
exit the function
prepatch hook function, execute
prepatch(oldVnode, vnode) Notifies the node to enter the comparison phase. Generally, this step will configure performance optimization
update hook function configured in the
cbs callback function object and the
update## configured in data
#Hook function
If there are both old and new nodes children
child node, enter the
If the old node has no child nodes, directly create a new child node corresponding to the VNode
If the new node has no child nodes, remove the old VNode child nodes
finally calls the
of the new node to notify the node that the update is completeSimply put,
. And The comparison and update of child node arrays is the core logic of diff, and it is also one of the questions often mentioned during interviews.
Next, let’s enter the analysis of the updateChildren method~
##updateChildren
diff core analysis
Comparing the difference in elements of two object arrays based on the new array
What are the methods? through violent means to find the order and difference of each element in the array, which is simple diff algorithm
.That is, traverses the new node array, traverses the old node array again in each cycle to compare whether the two nodes are consistent, and determines whether the new node is added, removed or moved by comparing the results , The entire process requires m*n comparisons, so the default time complexity is On.
This comparison method is very performance consuming during a large number of node updates, so Vue 2 has optimized it and changed it to Double-ended comparison algorithm
, which is Double-ended diff
.
As the name suggests, Double-ended is starting from both ends and traversing to the middle for comparison algorithm.
In double-ended diff
, there are five comparison situations:
The old and new headers are equal
The old and new tails are equal
The old head is equal to the new tail
The old tail is equal to the new head
The four are not equal to each other
Among them, the first four are ideal situations, while the fifth is The most complex comparison situation.
Judge equality, that is,
sameVnode(a, b)
is equal totrue
Below we use a preset situation to Perform analysis.
In order to try to demonstrate the above five situations at the same time, I preset the following new and old node arrays:
oldChildren
, including a total of 7 nodes from 1 to 7newChildren
, There are also 7 nodes, but compared to the old node, there is one less vnode 3
and one more vnode 8
Before comparing, you first need toDefine the double-ended index of two sets of nodes :
let oldStartIdx = 0 let oldEndIdx = oldCh.length - 1 let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx] let newStartIdx = 0 let newEndIdx = newCh.length - 1 let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx]
Copied source code, where
oldCh
isoldChildren
in the figure,newCh
isnewChildren
Then, we define the stop condition for the traversal comparison operation:
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)
stop here The condition is As soon as either the traversal of the old or new node array ends, the traversal will stop immediately.
The node status at this time is as follows:
In order to ensure the old and new The node array will not perform invalid comparison during comparison, and will first exclude the data where the beginning part and end part of the old node array are continuous and the value is
Undefined.
if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx] } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx]
Of course this is not the case in our example and can be ignored.
At this time, it is equivalent to the two starting indexes of the old and new node arrays. The node pointed to isBasically consistent, then patchVnode will be called at this time to perform deep comparison and dom update of the two vnodes, and
the two starting indexes will be moved backward . That is:
if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode( oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx ) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] }The node and index changes at this time are as shown in the figure: ##4. The old tail is equal to the new tail
. At this time, patchVnode is also called to compare the sum of the two tail nodes. Update the dom and move the two end indices forward
. if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
The node and index changes at this time are as shown in the figure:
. Call patchVnode to perform the same on the two nodes. deal with. But the difference from the above two is that in this case, the
, so it will end at patchVnode Then reinsert the
old head node through nodeOps.insertBefore
to after the current old tail node . Then,
forward.
You may have a question when you see this, why is theold node arraymoved here? This is because there is an attribute elm in the vnode node. , will point to the actual dom node corresponding to the vnode, so moving the old node array here is actually
moving the actual dom node sequence
on the side; and note that this is the current tail node, when the index changes Afterwards, this is not necessarily the end of the old node array.
即:
if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode( oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx ) canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] }
此时状态如下:
这里与上面的 旧头等于新尾 类似,一样要涉及到节点对比和移动,只是调整的索引不同。此时 旧节点的 末尾索引 前移、新节点的 起始索引 后移,当然了,这里的 dom 移动对应的 vnode 操作是 将旧节点数组的末尾索引对应的 vnode 插入到旧节点数组 起始索引对应的 vnode 之前。
if (sameVnode(oldEndVnode, newStartVnode)) { patchVnode( oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx ) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] }
此时状态如下:
在以上情况都处理之后,就来到了四个节点互相都不相等的情况,这种情况也是 最复杂的情况。
当经过了上面几种处理之后,此时的 索引与对应的 vnode 状态如下:
可以看到四个索引对应的 vnode 分别是:vnode 3、vnode 5、 vnode 4、vnode 8,这几个肯定是不一样的。
此时也就意味着 双端对比结束。
后面的节点对比则是 将旧节点数组剩余的 vnode (oldStartIdx
到 oldEndIdx
之间的节点)进行一次遍历,生成由 vnode.key
作为键,idx
索引作为值的对象 oldKeyToIdx
,然后 遍历新节点数组的剩余 vnode(newStartIdx
到 newEndIdx
之间的节点),根据新的节点的 key
在 oldKeyToIdx
进行查找。此时的每个新节点的查找结果只有两种情况:
找到了对应的索引,那么会通过 sameVNode
对两个节点进行对比:
patchVnode
进行深层对比和 dom 更新,将 oldKeyToIdx
中对应的索引 idxInOld
对应的节点插入到 oldStartIdx
对应的 vnode 之前;并且,这里会将 旧节点数组中 idxInOld
对应的元素设置为 undefined
createElm
重新创建一个新的 dom 节点并将 新的 vnode 插入到对应的位置
没有找到对应的索引,则直接 createElm
创建新的 dom 节点并将新的 vnode 插入到对应位置
注:这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中
idxInOld
中的元素置为undefined
。
最后,会将 新节点数组的 起始索引 向后移动。
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 { vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode( vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx ) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ) } else { // same key but different element. treat as new element createElm( newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx ) } } newStartVnode = newCh[++newStartIdx] }
大致逻辑如下图:
经过上面的处理之后,根据判断条件也不难看出,遍历结束之后 新旧节点数组都刚好没有剩余元素 是很难出现的,当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点相同时才会发生,只要有一个节点发生改变或者顺序发生大幅调整,最后 都会有一个节点数组起始索引和末尾索引无法闭合。
那么此时就需要对剩余元素进行处理:
即:
Vue 2 的 diff 算法相对于简单 diff 算法来说,通过 双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作,新旧数组均只需要进行一次遍历即可将所有节点进行对比。
The double-end comparison will perform four comparisons and moves respectively, and the performance is not the optimal solution, so Vue 3 introduced the Longest Increasing Subsequence method to replace the double-end comparison. , while the rest still uses space expansion to reduce time complexity by converting it into an index map, thereby further improving computing performance.
Of course, the real dom node of elm corresponding to vnode is not given in the figure of this article. The mobile relationship between the two may cause misunderstandings. It is recommended to read it together with "Vue.js Design and Implementation".
The overall process is as follows:
(Learning video sharing: vuejs introductory tutorial, Programming Basic video)
The above is the detailed content of Quickly understand the Vue2 diff algorithm (detailed graphic explanation). For more information, please follow other related articles on the PHP Chinese website!