Like React, Vue also has its own diff algorithm, patch, when dealing with virtual DOM updates.

What is a patch

When Vue renders DOM through VNode nodes, it does not update DOM nodes through the current VNode node, but compares the old and new two VNode nodes through patch algorithm, and then finds out the different attributes or nodes through the comparison results to make them more detailed as needed. Obviously, PATCH can reduce unnecessary overhead and improve performance.

In the process of patch, the following things are accomplished:

  • Create the nodes that need to be added
  • Remove deprecated nodes
  • Moves or modifies the node that needs to be updated

Patch optimization for VUE3 — PatchFlag

PatchFlag optimization for patch was mentioned in many UUE3 lectures, so I paid special attention to it when I read the source code. So what exactly is patchFlag for?

For example, when two nodes are of the same type, although the two nodes are of the same type, the attributes of the new node may also change. Therefore, we need to traverse the attributes of the node in order to effectively judge whether it needs to be updated.

Let’s look at the following elements:

<div id="bar" :class="foo">Hello World</div>

For such a div element, it is clear from a front-end engineer’s point of view that id=”bar” and children as text types are static attributes that will not change, and it is only important to see if the class changes. Now VUE3 uses patchFlag to do this. After the AST tree is generated, each node is traversed through the converter and patchFlag is applied according to the characteristics of the node. In the process of patch, only class is processed, not the full comparison. This reduces the number of times the props need to be iterated, resulting in improved performance.

How does PATCH work

After explaining the role of patch, the author will take you to look at the implementation of the source code of patch. The source code of patch is located in the file @runtime-core/ SRC /renderer.ts. Since the code length in this file is very long, the author will omit the unnecessary code and only focus on the main logic when explaining the code.

This is because the author hopes that what you can gain from reading this article is the logical summary of patch process, and just notice the key logic. Not everyone needs to read the source code, and posted part of the key code, is hoping to have students interested, want to read the source code can have a code snippet reference.

const patch: PatchFn = ( n1, n2, container, anchor = null, parentComponent = null, parentSuspense = null, isSVG = false, SrotscopeIDS = null, Optimized = false) => {// Patching & Not the same type of VNode, then unload if (n1 &&! isSameVNodeType(n1, n2)) { anchor = getNextHostNode(n1) unmount(n1, parentComponent, parentSuspense, N1 = null} // PatchFlag is a BAIL type, If (n2. PatchFlag === PatchFlags.BAIL) {Optimized = false n2. DynamicChildren = null} const {type, REF, ShapeFlag} = n2 switch (type) {// case Text: // Processtext (n1, n2, container, anchor) break case Comment: // comment type processCommentNode(n1, n2, container, anchor) break case Static: // StaticNode type if (n1 == null) {mountStaticNode(n2, container, anchor, isSVG)} break case Fragment: // Fragment type processFragment(/* ignore parameter */) break default: If (shapeFlag & shapeFlags.element) {// Element type processElement(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, Optimized)} else if (ShapeFlag & ShapeFlags.ponent) {// Component type ProcessComponent (/* Ignore parameters */)} else if (ShapeFlag & ShapeFlags. Teleport) {// Teleport type; (type as typeof teleportImpl).process(/* ignore parameter */)}}}

Let’s look at the above source code of 👆 patch function with the author. Let’s start from the input reference: n1 and n2 are the two nodes to be compared, n1 is the old node, and n2 is the new node. The container is the container for the new node, and the anchor is an anchor point that identifies which node to refer to when adding, deleting, or moving new and old nodes. Optimized parameter is an indicator of whether optimization mode is on or not. Other parameters will not be introduced, we do not care about.

When we look at the first if condition, the old node is unloaded from the tree when it exists and the old node is not of the same type. This is the first logic of patch that we can summarize: when two nodes have different types, the old node will be unloaded directly.

The second if branch condition is that if the value of patchFlag on the new node is BAIL, the optimization mode will be turned off. This is the first time we’ve encountered patchFlag in the source code, but without going into too much detail here, let’s move on.

Next, the patch function will judge the node type through the switch case and perform different operations for different node types.

Let’s use the ELEMENT type as an example, because HTML elements are the types we spend most of our time with. In the top source code, when a case goes to the default branch, At this time, it is determined that the current VNode is an element type through bit-and-operation of ShapeFlag, and then processElement is called to continue the process of patch, and the parameters in patch function are passed to the past. The author follows the processElement function to continue the analysis.

The Patch process of the element — ProcessElement

The code logic of processElement itself is very simple, which can be summed up in one sentence: if there is an old node, continue to compare the old and new nodes through patch; otherwise, mount the new node directly. The source is as follows:

const processElement = ( n1: VNode | null, n2: VNode, container: RendererElement, anchor: RendererNode | null, parentComponent: ComponentInternalInstance | null, parentSuspense: SuspenseBoundary | null, isSVG: boolean, slotScopeIds: string[] | null, optimized: Boolean) => {// if (n1 == null) {mountElement(n2, container, } else {patchElement(n1, n2, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } }

When the old node does not exist, it is easier to mount it directly. Therefore, in order to reflect the process of patch, the author assumes that both the old and the new nodes exist and continues the analysis along the PATCHELEMENT.

Compare the child node — patchElement

During the element type patch process, VUE3 first extracts the props declaration for the old and new nodes, because the props need to be patched later.

Several hooks are fired before the comparison begins, such as the VNode’s own hooks: onvNodeBeforeUpdate, and beforeUpdate for directives bound on elements.

if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
  invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
}
if (dirs) {
  invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate')
}

Update the attributes

After that, the props are compared, and if the element is patchFlag at this point, the on-demand comparison is done with patchFlag, otherwise the full diff elements are compared.

If (patchFlag > 0) {if (patchFlag & patchFlags.full_props) {// If the props for the element contain dynamic keys, Patchprops (EL, N2, oldProps, newProps, parentComponent, parentSuspense, isSVG ) } else { if (patchFlag & PatchFlags.CLASS) { if (oldProps.class ! == newProps.class) { hostPatchProp(el, 'class', null, newProps.class, isSVG) } } if (patchFlag & PatchFlags.STYLE) { hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG) } if (patchFlag & PatchFlags.PROPS) { const propsToUpdate = n2.dynamicProps! for (let i = 0; i < propsToUpdate.length; i++) { const key = propsToUpdate[i] const prev = oldProps[key] const next = newProps[key] if ( next ! == prev || (hostForcePatchProp && hostForcePatchProp(el, key)) ) { hostPatchProp( el, key, prev, next, isSVG, n1.children as VNode[], parentComponent, parentSuspense, unmountChildren ) } } } } if (patchFlag & PatchFlags.TEXT) { if (n1.children ! == n2.children) { hostSetElementText(el, n2.children as string) } } } else if (! optimized && dynamicChildren == null) { patchProps( el, n2, oldProps, newProps, parentComponent, parentSuspense, isSVG ) }

Let’s go through the branching conditions at the top and see what patchFlag does at this point.

  • When patchFlag is FULL_PROPS, this means that the elements may contain dynamic keys and that full props diff is required.
  • When patchFlag is CLASS, when the classes of the old and new nodes are inconsistent, the CLASS will be patched. When the CLASS attributes of the old and new nodes are exactly the same, no operation is required. This Flag is added when the element has a dynamic class binding.
  • When patchFlag is STYLE, the STYLE is updated, which happens for each patch, and the Flag is added when there is a dynamic STYLE binding.

  • When patchFlag is PROPS, note that this Flag is added when the element has dynamic properties or ATTRS bindings. Unlike class and style, these dynamic prop or ATTRS keys are saved for faster iteration.

    • The PROPS comparison will extract the dynamic properties of the new node and traversal all the keys in this property. When the old and new properties do not agree, or the key needs to be forcefully updated, hostPatchProp will be called to update the property.
  • When patchFlag is TEXT, HostSetElementText is called to update if the TEXT of the child nodes in the old and new nodes changes. This flag is added when the child nodes of an element contain only dynamic text.

At this point, the branching judgment ends when the element has patchFlag. From these branching judgments, we can feel the efforts made by patchFlag to improve the speed of patch algorithm.

The branch goes to the last else, and if the optimization flag does not exist and the dynamic child node does not exist, then diff the props directly, using the patchProps function.

For props, this is the end of the page. We won’t cover the specific function calls inside the branch.

Update the child node — patchChildren

Next comes the most important part of updating the child nodes. During the patch process of the element, it will determine whether there is a dynamic child node. If so, patchBlockChildren will be called to update only the dynamic child node; otherwise, patchChildren will be called to update the full amount of child nodes.

Here we’ll look at the general case: patchChildren.

When updating children, we first use patchFlag’s ability to classify children and make different processing. In order to avoid a large amount of source code, I will summarize the logic of patchChildren function, and then we will focus on the common parts.

  • Judging according to patchFlag:

    • If patchFlag is a Fragment: KEYED_FRAGMENT with a key value, then patchKeyedChildren is called to continue processing the child nodes.
    • If patchFlag is a Fragment with no key set: UNKEYED_FRAGMENT, then patchunkeyedChildren is called to process the child nodes with no key.

  • Determine by shapeFlag (element type flag) :

    • If the new child node is of text type and the old child node is of array type, the children of the old node are unloaded directly.

      • If the old and new node types are the same, the text of the new child node is updated directly.

    • If the old child node type is array type

      • If the new child node is also of array type, patchKeyedChildren is called for the full diff.
      • If the new child node is not of array type, then there is no new child node and you can simply unload the old node from the tree.
    • If the old child node is a text type, you can simply set the text of the element as an empty string, since you’ve already determined whether the new child node is a text type at the beginning.
    • If the new child node is of type array, but the old child node is not of type array, then mount the new child node in the tree and perform mount operation.

This is the complete logic of patchChildren. The most complicated logic here is to call patchKeyedChildren to perform a complete comparison between the two arrays when both the old and new children are of array type.

Update policy for child nodes

How to do the diff algorithm efficiently, the most important performance bottleneck is how to compare the child nodes in the tree more quickly to find out what specific operations need to be done. If the comparison is conducted according to normal thinking, then the time complexity is at least O(n^3), then the tree with 1000 child nodes needs at least 1 billion comparisons. There is no doubt that this operation is very expensive. In this case, how to implement an algorithm with time complexity of O(n) is a problem that must be considered by the front-end framework. Like React, there are keys in Vue to help identify child nodes and help the framework identify and compare child nodes more efficiently.

Child node optimization strategy of VUE2

When I was reading the book Vue.js, the author Liu Bowen summed up the sub-node optimization strategies of Vue2 into four categories:

  • New before and old before
  • New queen and old queen
  • New after and old before
  • New before and after

Note that the new front refers to the node with the new child index at the front, the new after refers to the node with the new child index at the end, and the old refers to the old child.

At that time, after reading the book, I found that such a summary was very appropriate and easy to remember, and also helped me to read the source code of VUE2 more easily and easily. Therefore, I still planned to use such a name to describe the update strategy of VUE3’s child nodes.

The child nodes of Vue3 are updated

For the sake of fluency and being able to see the code for reference, I will break the patchKeyedChildren function into logical points, and paste the source code and corresponding images at the pace we describe.

const patchKeyedChildren = ( c1: VNode[], c2: VNodeArrayChildren, container: RendererElement, parentAnchor: RendererNode | null, parentComponent: ComponentInternalInstance | null, parentSuspense: SuspenseBoundary | null, isSVG: boolean, slotScopeIds: string[] | null, optimized: boolean ) => { let i = 0 const l2 = c2.length let e1 = c1.length - 1 // prev ending index let e2 = l2 - 1 // next ending Index /* ignores subsequent logic */}

First, let’s look at the signature part of the function of patchKeyedChildren. C1 and C2 in the function parameters represent the old child node and the new child node respectively.

The function starts by declaring four variables:

  • The index I = 0 of the child node is traversed
  • New child node length: L2
  • The last index of the old child node: e1
  • The last index of the new child: e2

With these four declared variables in mind, let’s look at the first comparison strategy for word child nodes in VUE3.

New before and old before

The C1 and C2 nodes on the same row are two new and old child nodes to be compared. The comparison child node starts from the starting index of the two children nodes:

When I = 0, the 0th index is compared and it is found that node A of C1 and node A of C2 are elements of the same type. Then patch operation will be carried out on the old and new node A. Patch here can recursively visit all child nodes under node A. Increment index I after patch is completed.

Continuing the comparison, it is found that B node of C1 and B node of C2 are elements of the same type. I index is increased after patch recursion on B node as before.

When comparing the third child node, it will be found that the C node of C1 and the D node of C2 are not of the same type, so the break breaks out of the comparison cycle between the new and the old, so the comparison between the new and the old ends.

At this point, the first two nodes of C1 and C2’s children have been compared. The comparison process in the source code looks like this:

while (i <= e1 && i <= e2) { const n1 = c1[i] const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : NormalizevNode (c2[I])) if (isSamevNodeType (n1, n2)) {patch(n1, n2, container, null, ParentComponent, ParentSuspense, ISSvg, Slotscopeids, Optimized)} else {// If N1 and N2 are not of the same type, // increment I ++}

New queen and old queen

After the comparison between the new and the old is completed, the comparison will start in accordance with the optimization strategy in VUE2.

Let’s see the new and old examples of pictures, I believe that after the introduction of the new and old, we have been able to understand the new and old after the comparison of ideas.

The elements are compared from the very end through the previously declared end indexes of the new and old child nodes, e1 and e2.

According to the comparison in the figure, the logic is as follows:

  • From the end, C1 is node C, while C2 is also node C, and the two nodes are of the same type. The patch comparison is started. When the patch is completed, the index -1 at the end of the old and new child nodes is obtained.
  • The second comparison shows that the end of C1 is B node, and the end of C2 is B node with the same type. Patch is conducted, and then the tail index is decreased.
  • The third comparison is made. The end node of C1 is A, and the end node of C2 is E. The type is different, and the break breaks out of the comparison cycle between the new and the old.

The following is the new and old after the comparison source:

while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : NormalizevNode (c2[e2])) if (isSamevNodeType (n1, n2)) {patch(n1, n2, container, null, ParentComponent, ParentSuspense, ISSvg, Slotscopeids, Optimized)} else {// If N1 and N2 are not of the same type, // After patch operation is completed, the tail index decreases e1-- e2--}.

New child nodes in regular order are mounted

When we finish the comparison of the first two rounds, we can often find some elements that exist in the new child node but not in the old child node on the regular sequence number, so we need to insert these new child nodes.

As shown in the figure, after the comparison between the new child and the old child is completed, the index I at this time has increased beyond the length of C1 child node, at this time I = 2, and I is less than or equal to the length of C2 child node, so it can be determined that there are still nodes in the new child node that have not been traversed, and the old child node has been traversed completely. So insert all the child nodes that have not been traversed.

For this diagram, the C node should be inserted.

The source code for this mount process is as follows, refer to the comments in the source code:

If (I <= e2) {const nextPos = e2 + 1 // const anchor = nextPos < L2 ? (c2[nextPos] as VNode).el : ParentAnchor // While (I <= e2) {// The first parameter is NULL when patch(NULL, (c2[I] = Optimized? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) i++ } } }

Excess nodes are removed in a regular order

The corresponding mount logic above is to remove the redundant old child nodes.

When the new child node has been traversed completely, if there are still elements of the old child node that have not been traversed at this time, it can be determined that the remaining old child nodes are no longer needed, so the remaining old child nodes can be removed directly.

As can be seen from the figure, after the comparison between C1 and C2 is completed, node A is still left in the old child node C1, and there is no node to be compared in the new node, so node A can be removed directly.

The corresponding logic in the source code is also simple:

If (I <= e1) {if (I <= e1) {if (I <= e1) {if (I <= e1) {if (I <= e1) {if (I <= e1) {if (I <= e1) {if (I <= e1) { Suspense, true) // increment index i++}}

Child node comparison of unknown order

After the above ideal-case processing is complete, we are left with scenarios where we cannot determine the location of elements.

Let’s take a look at the figure first. We can see that there are more elements mounted in both the old and new child nodes. When we compare the new and old child nodes, there are still nodes in the middle that are in uncertain order. CDE in the old child node, EDCH in the new child node.

As a bystander, we know that we need to move the CDE and insert the H node. Let’s take a look at how Patch accomplishes this task:

  • Declare two variables S1 and S2, and assign the preorder index I to S1 and S2. S1 and S2 represent the starting indexes of the new and old child nodes, respectively.

  • With S2 as the starting node and E2 as the ending condition, the new child node is traversed. The key of the new child node neutron node is used as the key and the index I is used as the value to generate a Map object to store the original index.

    • Duplicate keys found during update XXX, Make sure keys are unique If Duplicate keys are found during update XXX, a warning is issued to all Vue developers.
    Const s1 = I // const s2 = I // const s2 = I // const keytonewIndexMap for the new child: Map<string | number, number> = new Map() for (i = s2; i <= e2; i++) { const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])) if (nextChild.key ! = null) {// Warning if it is a DEV environment and the KeytonewIndexMap already has the key value of the current node. if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) { warn( `Duplicate keys found during update:`, JSON. Stringify (nextChild.key), 'Make sure keys are unique.')} // Save the map with the key of the new child node and the index as the value. keyToNewIndexMap.set(nextChild.key, i) } }
  • Declare the variable toBePatched, and calculate how many nodes need toBePatched. The variable patched = 0 is declared to record the number of nodes of patch.

  • Declare an array of NewIndexTooldIndexMap, which is used to determine the maximum increment subsequence. The size of the NewIndexTooldIndexMap array is the length of TobePatched, and all elements in the array are initialized to 0.

    • NewIndexTooldIndexMap with the form Map
      ,>
    • Note that the oldIndex stored inside is indexed with offset +1.
    • OldIndex = 0 is a special value indicating that there is no corresponding old child in the new child node.

  • Traversing the old child node marks the currently traversed child node as prevChild.

    • If patched is greater than or equal to toBePatched, it means that all nodes that need toBePatched have been compared, then the remaining prevChild can be removed.
    • Otherwise declare the variable newIndex.
    • If the prevChild key is not empty, then take the prevChild key from the KeyToIndexMap and assign the value to newIndex.
    • If newIndex has no value, then there is no corresponding old child in the new child node, and the old prevChild child is removed.
    • Otherwise, save the new index in NewIndexTooldIndexMap, mark the farthest position of the current index movement or add a movement mark, and compare the patch of the old and new child nodes.
    • After patch is completed, the patched count is incremented.

The code for the above logic is as follows:

/** * /** * /** * /** * /** * /** * /** * / */ let j let patched = 0 const toBePatched = e2 - s2 + 1 let moved = false // Use to trace if any node moved let // const NewIndexTooldIndexMap = new Array(TobePatched) for (I = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0 for (i = s1; i <= e1; I ++) {const prevChild = C1 [I] if (patched >= toBePatched) {// All new nodes are patched Unmount (PrevChild, ParentComponent, ParentSuspense, True) Continue} let newIndex if (PrevChild. Key! = null) {newIndex = KeytonewIndexMap.get (prevChild. Key)} else {// For nodes where the key is not found, /* Ignore logic */} // If the old child node is not matched to the corresponding new child node, If (newIndex === undefined) {unmount(prevChild, parentComponent, parentSuspense, } else {newIndexTooldIndexMap [newIndex-s2] = I + 1 // newIndexTooldIndexMap [newIndex-s2] = I + 1 // newIndexMap [newIndexTooldIndexMap] = I + 1 // Is greater than the furthest moved index, If (newIndex >= MaxNewIndexsOfR) {maxNewIndexsOfR = newIndex} else {// Otherwise mark Moved to True Moved = True} // Patch (prevChild, C2 [newIndex] as VNode, container, null, parentComponent, parentSuspense, isSVG, Slotscopeids, Optimized) // Increase patched count after patch completion. patched++ } }

In after traversing the old child nodes, we have removed the unnecessary old child nodes, and is still present in the new node to the corresponding old child nodes are compared, and the patch then we need to traverse the new child node, only from the back forward traversal needs to be part of the patch, the purpose is to insert for the new child node, Move the child nodes that need to be moved at the same level. The logic is described as follows:

  • If there is a moved flag, find the longest increasing subsequence from the NewIndexTooldIndexMap and assign j to the last index of the longest increasing subsequence array.
  • Traversing the new child node from back to front allows us to determine the location of the anchor element.
  • Declaration newIndex = s2 + I, that is, the last node to be patched.
  • Gets the anchor element.
  • If the node needs to be patched, the value of I index in the NewIndexTooldIndexMap is 0. Remember I mentioned earlier that 0 is a special value that means the node has no corresponding node in the old child node. So for elements that don’t have corresponding nodes, we insert them.

  • If there is a corresponding index in the NewIndexTooldIndexMap, but the moved flag exists, that means the node may have moved and you should proceed.

    • If j < 0, all nodes in the longest increasing subsequence have been processed. Or when the index I is not equal to the value corresponding to the index j in the longest growing subsequence, it indicates that the node is not in a relatively stable position, so a move operation is needed.
    • If the above conditions are met, the j index decreases and the node is not processed.

The above logic code is as follows:

/ * * * movement and mount * / / / when the nodes are mobile, create the longest increasing subsequence const increasingNewIndexSequence = version? getSequence(newIndexToOldIndexMap) : EMPTY_ARR j = increasingNewIndexSequence length - 1 / / in order to convenient for anchor, choose from the traversal for forward (I = toBePatched - 1; i >= 0; i--) { const nextIndex = s2 + i const nextChild = c2[nextIndex] as VNode const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : ParentAnchor if (NewIndexTooldIndexMap [I] === 0) {parentAnchor if (NewIndexTooldIndexMap [I] === 0) {parentAnchor if (NewIndexTooldIndexMap [I] === 0) { Then add node patch(NULL, NextChild, Container, Anchor, ParentComponent, ParentSuspense, ISSvg, Slosscopeids, Optimized)} else if (version) {/ / if it is not a stable sequence, or the current node is not increasing subsequence, need to move the if (j < 0 | | I! == increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) } else { j-- } } }

This is the end of the update of the child node that has a key value. Following the author’s review, I believe that it is very easy to understand the source code of the child node update if you can carefully combine the source code with the logic.

conclusion

In this paper, the author introduced the role of patch and explained the performance optimization of VUE3 by accelerating the speed through patchFlag when updating nodes.

After that, the author explained the process of patch function, and took ELEMENT type as an example to follow the process of calling the function until the update of child nodes was introduced.

In the update of child nodes, we compare the different update strategies of VUE2 and VUE3, and explain in detail how VUE3 compares child nodes with a key value.

I can summarize the child node update of VUE3 in five steps:

1, before the new and before the old comparison.

2. Comparison between the new and the old.

3. New operations for regular sequences.

4. Removal of conventional sequences.

5. Processing of unknown order.

5.1 KeytonewIndexMap to establish keys and indexes on new child nodes: KeytonewIndexMap. 5.2 Traverse old child nodes. Patch the old nodes that can be matched, and remove the old child nodes that do not exist. 5.3 Move or add new child nodes.

The above 5 points is a very important child node update process in VUE3, if you think the article is too long to see friends can also be directly read the summary.

Finally, if this article can help you understand the patch process and child node update strategy in VUE3, I hope you can give this article a favorite ❤️. If you want to keep up with the following articles, you can also follow my account or follow my GitHub. Thank you again for your lovely reading.