preface

Those of you who have used Vue and React will be familiar with the virtual Dom and diff algorithms, which play an important role. React is only a superficial study, so this article mainly introduces Vue and takes you step by step to understand it.

Virtual DOM

What is the virtual DOM?

The Virtual DOM (Virtual DOM), also known as the Virtual node, is used to simulate nodes in the real DOM with JS objects. The object contains the structure and attributes of the real DOM and is used to compare the differences between the Virtual DOM and the real DOM, so as to achieve the purpose of optimizing performance by local rendering.

Real element nodes:

<div id="wrap">
    <p class="title">Hello world!</p>
</div>
Copy the code

VNode:

{
    tag:'div'.attrs: {id:'wrap'
    },
    children:[
        {
            tag:'p'.text:'Hello world! '.attrs: {class:'title',}}]}Copy the code

Why use the virtual DOM?

The React and Vue frameworks use the virtual DOM. Good question! Let’s take care of your little friend’s doubts.

When we first started working with JS/JQuery, it was inevitable that there would be a lot of DOM manipulation, and DOM changes would cause backflow or redraw, which would degrade page rendering performance. So how can you reduce manipulation of the DOM? At this time, the virtual DOM application was born, so the main purpose of the virtual DOM is to reduce the frequent DOM manipulation caused by backflow redraw caused by performance problems!

What does the virtual DOM do?

  1. Good compatibility. Since a Vnode is essentially a JS object, it can be manipulated regardless of Node or browser environment.
  2. Reduced manipulation of the Dom. Data and state changes in the page are compared through Vnode, and DOM only needs to be updated after comparison, which does not need frequent operation and improves page performance.

What is the difference between the virtual DOM and the real DOM?

Speaking of which, what is the difference between the virtual DOM and the real DOM? The summary is as follows:

  • The virtual DOM does not backflow and redraw;
  • The backflow redraw caused by frequent manipulation of the real DOM results in poor performance;
  • The virtual DOM is frequently modified, and then the difference is compared and the real DOM is modified at one time. Finally, the performance loss caused by multiple backflow redrawing in the real DOM is reduced.
  • The virtual DOM effectively reduces the redrawing and typesetting of a large area. Because it is compared with the real DOM, the different parts are updated, so only partial rendering is performed.
Total loss = real DOM + (multi-node) backflow/redraw;// Calculate the cost of using the real DOMTotal loss = virtual DOM addition, deletion, and modification + (Diff contrast) real DOM differentiation addition, deletion, and modification + (fewer nodes) backflow/redraw;// Calculate the cost of using the virtual DOM
Copy the code

As you can see, these are all around frequent manipulation of the real DOM causing backflow redraw, resulting in a loss of page performance. The framework does not have to use the virtual DOM, however, but the key is to see if frequent manipulation can cause extensive DOM manipulation.

So what exactly does the virtual DOM do to reduce frequent DOM manipulation on a page? So you have to understand DOM Diff algorithms.

The DIFF algorithm

How does VUE update views when data changes? In fact, it is very simple. At first, the virtual DOM will be generated according to the real DOM. When the data of a node of the virtual DOM changes, a new Vnode will be generated.

The diff process is to call the patch function, compare the old and new nodes, and patch the real DOM while doing the comparison.

Control vue source code to parse, posted the core code, aimed at a simple and clear story clearly, otherwise small editor looked at their head big O(∩_∩)O

patch

So how does patch work?

// Patch function oldVnode: old node vnode: new node
function patch (oldVnode, vnode) {...if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)    // If the new node is the same as the old node, then compare the child node with patchVnode
    } else {
        /* ----- Otherwise, the new node directly replaces the old node ----- */
        const oEl = oldVnode.el // The real element node corresponding to the current oldVnode
        let parentEle = api.parentNode(oEl)  / / the parent element
        createEle(vnode)  // Generate new elements based on Vnode
        if(parentEle ! = =null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // Add the new element to the parent element
            api.removeChild(parentEle, oldVnode.el)  // Remove the old element node
            oldVnode = null}}...return vnode
}

// Check whether the two nodes are the same node
function sameVnode (a, b) {
    return (
	    a.key === b.key &&  / / key values
	    a.tag === b.tag &&  / / tag name
	    a.isComment === b.isComment &&  // Whether it is a comment node
	    // Whether data is defined, data contains some specific information, such as onclick, style
	    isDef(a.data) === isDef(b.data) &&  
	    sameInputType(a, b) // When the tag is , the type must be the same)}Copy the code

As can be seen from the above, the patch function determines whether the new and old nodes are the same node:

  • If the node is the same, run patchVnode to compare the child nodes.

  • If the node is not the same, the new node directly replaces the old node.

What if they are not the same node, but their children are the same? OMG, remember: Diff is a peer comparison, there is no cross-level comparison! Just to be brief, React is the same way. They compare nodes in the same layer.

patchVnode

Since the patchVnode method is used, it indicates that the old and new nodes are the same node, so what does this method do?

function patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el           // Find the corresponding real DOM
    let i, oldCh = oldVnode.children, ch = vnode.children     
    if (oldVnode === vnode) return         // If the new and old nodes are the same, return directly
    if(oldVnode.text ! = =null&& vnode.text ! = =null&& oldVnode.text ! == vnode.text) {// If both new and old nodes have text nodes and are not equal, the text node of the new node replaces the text node of the old node
        api.setTextContent(el, vnode.text)  
    }else {
        updateEle(el, vnode, oldVnode)
        if(oldCh && ch && oldCh ! == ch) {// If both the old and new nodes have children, run updateChildren to compare the children.
            updateChildren(el, oldCh, ch)
        }else if (ch){
            // If the new node has children and the old node has none, add the children of the new node to the old node
            createEle(vnode)
        }else if (oldCh){
            // If the new node has no children and the old node has children, delete the children of the old node
            api.removeChildren(el)
        }
    }
}
Copy the code

If the two nodes are different, replace the old node with the new one.

If two nodes are the same,

  • The new and old nodes are returned directly.
  • The old node has children, but the new node does not. Delete the children of the old node.
  • The old node has no children, but the new node has children: the children of the new node append directly to the old node.
  • Both have only text nodes: replace the old text node with the text node of the new node;
  • Both have child nodes: updateChildren

The most complex case is when both the old and new nodes have children. This method is at the heart of the Diff algorithm to handle this problem.

updateChildren

Because there’s so much code, here’s an overview. The core of the updateChildren method:

  1. Extract the child nodes of the old node: the new node node CH and the old node node oldCh;
  2. Ch and oldCh set the StartIdx (pointing to the head) and EndIdx (pointing to the tail) variables, respectively, and compare them in pairs (according to the sameNode method). There are four ways to compare. If none of the four methods are successful, the comparison is performed by key if the key is set. In the comparison process, StartIdx ++, endIdx–, the comparison ends once StartIdx > endIdx indicates that at least one ch or oldCh has been traversed.

The following is combined with the figure to understand:

The first step:

oldStartIdx = A , oldEndIdx = C;
newStartIdx = A , newEndIdx = D;
Copy the code

At this point oldStartIdx and newStarIdx match, so put A node in the DOM in the first position. At this point, A is already in the first position, so no processing is done.

The second step:

oldStartIdx = B , oldEndIdx = C;
newStartIdx = C , oldEndIdx = D;
Copy the code

When oldEndIdx and newStartIdx match, the original C node is moved after A, and the actual DOM order is A, C, and B.

Step 3:

oldStartIdx = C , oldEndIdx = C;
newStartIdx = B , newEndIdx = D;
oldStartIdx++,oldEndIdx--;
oldStartIdx > oldEndIdx
Copy the code

At this point, the traversal is complete and oldCh has been traversed. Then, insert the remaining CH nodes into the real DOM according to their index.

Therefore, there are two conditions for the end of judgment in the matching process:

  • OldStartIdx > oldEndIdx indicates that oldCh is traversed first. If ch has any remaining nodes, add them to the real DOM according to the corresponding index.
  • NewStartIdx > newEndIdx indicates that ch is traversed first, so redundant nodes should be deleted in the real DOM;

In this example, the new node is traversed first and the redundant node is deleted:

Finally, if the conditions are met after these sub-nodes sameVnode, patchVnode is continued to be executed, layer by layer recursion, until the comparison between oldVnode and all sub-nodes in Vnode is completed, all patches are completed, and then updated to the view.

conclusion

Dom diff algorithm time complexity is O (n^3), if used in the framework will be poor performance. The DIff algorithm used by Vue, with o(n) time complexity, simplifies many operations.

Finally, remember the whole Diff process with a picture, hope you can learn something!

eggs

React is just a quick primer, so here’s a quick comparison:

React render mechanism: React uses the virtual DOM. When each property and state changes, the render function returns a different element tree, compares the difference between the returned element tree and the last rendered tree, updates the difference, and finally renders the real DOM.

2. Diff is always a peer comparison. If the node type is different, replace the old node with the new one. If the nodes are of the same type, compare their children, and so on. The key bound to an element is usually used to compare nodes, so it must be unique. Array subscripts are generally not used as the key, because the index will change when the array element changes.

3. The whole process of rendering includes updating and converting the virtual DOM to the real DOM, so the whole process is reconciled. And the core of this process is mainly diff algorithm, using the life cycle shouldComponentUpdate function.