preface

Hello everyone, my name is Lin Sanxin. In daily interviews, Diff algorithm is a difficult obstacle to overcome. In the most popular words, it has always been the purpose of my writing articles to talk about the most difficult knowledge points. Lets Go

What is the virtual DOM

Before we talk about the Diff algorithm, let me tell you a little bit about the virtual DOM. This is conducive to the further understanding of Diff algorithm.

The virtual DOM is an object. What kind of object is it? An object that represents the real DOM, remember that. For an example, look at the following real DOM:

<ul id="list">
    <li class="item">Ha ha</li>
    <li class="item">Ha ha</li>
    <li class="item">Hey hey</li>
</ul>
Copy the code

The corresponding virtual DOM is:

let oldVDOM = { // Old virtual DOM
        tagName: 'ul'./ / tag name
        props: { // Tag attributes
            id: 'list'
        },
        children: [ // Label the child node
            {
                tagName: 'li'.props: { class: 'item' }, children: ['ha ha'] {},tagName: 'li'.props: { class: 'item' }, children: ['呵呵'] {},tagName: 'li'.props: { class: 'item' }, children: ['hey']},]}Copy the code

At this point, I modify the text of an li tag:

<ul id="list">
    <li class="item">Ha ha</li>
    <li class="item">Ha ha</li>
    <li class="item">Lin Sanxin ha ha ha ha ha</li> / / modify
</ul>
Copy the code

The new virtual DOM generated at this time is:

let newVDOM = { // New virtual DOM
        tagName: 'ul'./ / tag name
        props: { // Tag attributes
            id: 'list'
        },
        children: [ // Label the child node
            {
                tagName: 'li'.props: { class: 'item' }, children: ['ha ha'] {},tagName: 'li'.props: { class: 'item' }, children: ['呵呵'] {},tagName: 'li'.props: { class: 'item' }, children: ['Lin Sanxin ha ha ha ha ha']},]}Copy the code

This is what we usually call the old and new virtual DOM. At this time, the new virtual DOM is the latest state of data. So if we directly use the new virtual DOM to render the real DOM, is the efficiency really higher than that of directly operating the real DOM? It certainly won’t. Here’s a look:

From the figure above, we can see that the second method is definitely faster, because the first method has a virtual DOM step in between, so the statement that the virtual DOM is faster than the real DOM is actually wrong, or it is not rigorous. So what’s the right way to say it? The performance of the virtual DOM algorithm when operating the real DOM is higher than that when directly operating the real DOM. Virtual DOM and virtual DOM algorithm are two concepts. Virtual DOM algorithm = Virtual DOM + Diff algorithm

What is the Diff algorithm

Above we said virtual DOM, also know that only the virtual DOM + Diff algorithm can really improve the performance, that tells the virtual DOM, we will talk about the Diff algorithm, or the above example (this picture is compressed a little small, you can open to see, relatively clear) :

In the figure above, there is only one li tag that changes the text, the rest is unchanged, so it is not necessary to update all the nodes, just update the Li tag, and Diff algorithm is the algorithm to find out the Li tag.

Conclusion: Diff algorithm is a comparison algorithm. Compare the old virtual DOM and the new virtual DOM, compare which virtual node has changed, find out this virtual node, and only update the real node corresponding to this virtual node without updating other nodes whose data has not changed, so as to realize accurate update of the real DOM and improve efficiency.

Loss calculation using virtual DOM algorithm: Total loss = virtual DOM increment, deletion and alteration + (related to the efficiency of Diff algorithm) increment, deletion and alteration of real DOM difference + (fewer nodes) typesetting and redrawing

Direct operation of real DOM loss calculation: total loss = real DOM complete add, delete, and change + (possibly many nodes) typesetting and redrawing

Principle of Diff algorithm

Diff comparison with the same layer

When comparing the old and new virtual DOM, the Diff algorithm only compares at the same level, not across levels. So Diff algorithm is: breadth first algorithm. Time complexity :O(n)

Diff Comparison process

When the data changes, the setter is triggered and all subscribers Watcher is notified via dep. notify, who then call the patch method to patch the real DOM and update the corresponding view. For those who don’t know much about this step, look at the Vue source code series I wrote before

NewVnode and oldVnode: New and old virtual nodes in the same layer

Patch method

The function of this method is to compare whether the virtual nodes in the current layer are labels of the same type (the same type standard, described below) :

  • If yes, go aheadPatchVnode methodMake deep comparisons
  • No: No comparison is necessary. Replace the whole node withNew virtual node

Take a look at the patch core principle code

function patch(oldVnode, newVnode) {
  // Compare whether a node is a type
  if (sameVnode(oldVnode, newVnode)) {
    // Yes: continue the deep comparison
    patchVnode(oldVnode, newVnode)
  } else {
    / / no
    const oldEl = oldVnode.el // The real DOM node of the old virtual node
    const parentEle = api.parentNode(oldEl) // Get the parent node
    createEle(newVnode) // Create the real DOM node corresponding to the new virtual node
    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
      // Set null to free memory
      oldVnode = null}}return newVnode
}
Copy the code

SameVnode method

The key step for patch is to determine whether the nodes are of the same type by using sameVnode method. Then, the problem arises: how can a node be considered as a node of the same type? What are the criteria for this type?

Let’s take a look at the core principles of the sameVnode method code

function sameVnode(oldVnode, newVnode) {
  return (
    oldVnode.key === newVnode.key && // Whether the key values are the same
    oldVnode.tagName === newVnode.tagName && // Whether the tag names are the same
    oldVnode.isComment === newVnode.isComment && // Whether all are comment nodes
    isDef(oldVnode.data) === isDef(newVnode.data) && // Whether data is defined
    sameInputType(oldVnode, newVnode) // When the tag is input, the type must be the same)}Copy the code

PatchVnode method

This function does the following:

  • Find the correspondingReal DOM, known as theel
  • judgenewVnodeandoldVnodeDoes it point to the same object? If so, then directlyreturn
  • If they both have text nodes and are not equal, thenelThe text node is set tonewVnodeText node of.
  • ifoldVnodeStudent: Has child nodes andnewVnodeIf no, delete itelThe child nodes of the
  • ifoldVnodeThere are no child nodesnewVnodeYes, it willnewVnodeThe child node is added toel
  • If both have child nodes, executeupdateChildrenFunction to compare child nodes. This step is important
function patchVnode(oldVnode, newVnode) {
  const el = newVnode.el = oldVnode.el // Get the real DOM object
  // Get the array of child nodes of the old and new virtual nodes
  const oldCh = oldVnode.children, newCh = newVnode.children
  // If the new and old virtual nodes are the same object, then terminate
  if (oldVnode === newVnode) return
  // If the old and new virtual nodes are text nodes and the text is different
  if(oldVnode.text ! = =null&& newVnode.text ! = =null&& oldVnode.text ! == newVnode.text) {// Update the real DOM text directly to the new virtual node text
    api.setTextContent(el, newVnode.text)
  } else {
    / / otherwise

    if(oldCh && newCh && oldCh ! == newCh) {// Both the old and new virtual nodes have different child nodes

      // Compare the child nodes and update them
      updateChildren(el, oldCh, newCh)
    } else if (newCh) {
      // The new virtual node has children; the old virtual node does not

      // Create a child node of the new virtual node and update it to the real DOM
      createEle(newVnode)
    } else if (oldCh) {
      // The old virtual node has children, the new virtual node does not

      // Delete the corresponding child node from the real DOM
      api.removeChild(el)
    }
  }
}
Copy the code

The other points are easy to understand, so let’s talk about updateChildren in detail

UpdateChildren method

This is the most important method in patchVnode. The comparison of the child nodes of the new and old virtual nodes takes place in the updateChildren method. Next, it will be combined with some diagrams for better understanding

What is a comparison? The new set of child nodes and the old set of child nodes each have two first and last Pointers. For example:

<ul>
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>After modifying the data<ul>
    <li>b</li>
    <li>c</li>
    <li>e</li>
    <li>a</li>
</ul>

Copy the code

So the set of new and old child nodes and their first and last Pointers are:

They then compare each other, and there are five comparisons:

  • 1.OldS and newS,useSameVnode methodTo compare,sameVnode(oldS, newS)
  • 2,OldS and newEuseSameVnode methodTo compare,sameVnode(oldS, newE)
  • 3,OldE and newSuseSameVnode methodTo compare,sameVnode(oldE, newS)
  • 4,OldE and newEuseSameVnode methodTo compare,sameVnode(oldE, newE)
  • 5, if the above logic is not matched, then all the old child nodekeyMake one that maps to the old node indexkey -> indexWatch and then use newvnode 的 keyTo find out where in the old nodes can be reused.

Let’s analyze the comparison process using the above code as an example

Before analyzing, please keep in mind that the final rendering results are based on newVDOM, which explains why the nodes need to be moved to the corresponding position of newVDOM

  • The first step
oldS = a, oldE = c
newS = b, newE = a
Copy the code

OldS and newE are equal, we need to move the node A to newE’s position, the end, and oldS++, newE–

  • The second step
oldS = b, oldE = c
newS = b, newE = e
Copy the code

Comparison result: oldS and newS are equal, and node B needs to be moved to the position corresponding to newS, while oldS++,newS++

  • The third step
oldS = c, oldE = c
newS = c, newE = e
Copy the code

Comparison result: oldS,oldE and newS are equal, and node C needs to be moved to the position corresponding to newS, while oldS++,oldE–,newS++

  • The fourth step

OldS > oldE, oldCh completes traversal first, while newCh does not, indicating that newCh is more than oldCh, so the extra nodes need to be inserted into the corresponding position on the real DOM

  • To consider

I’m going to leave you with a question. In the example above, newCh has more nodes than oldCh. If oldCh has more nodes than newCh, newCh will finish the loop first, and oldCh will have more nodes. As a result, oldCh will delete the old nodes in the real DOM. You can think about it, you can simulate it, you can draw it, like I did, to reinforce that.

Attached is the core principles of updateChildren code

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0, newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx
  let idxInOld
  let elmToMove
  let before
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    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]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode)
      api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode)
      api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // Compare with key
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // Generate index table with key
      }
      idxInOld = oldKeyToIdx[newStartVnode.key]
      if(! idxInOld) { api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el) newStartVnode = newCh[++newStartIdx] }else {
        elmToMove = oldCh[idxInOld]
        if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el) }else {
          patchVnode(elmToMove, newStartVnode)
          oldCh[idxInOld] = null
          api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }
  if (oldStartIdx > oldEndIdx) {
    before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].el
    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}
Copy the code

Do the key in the index

When rendering a v-for loop, why not use index as the key of the loop?

Let’s take an example where I have the initial data on the left, and then I insert a new data in front of the data, which becomes the list on the right

<ul>                      <ul>
    <li key="0">a</li>        <li key="0">Lin three heart</li>
    <li key="1">b</li>        <li key="1">a</li>
    <li key="2">c</li>        <li key="2">b</li>
                              <li key="3">c</li>
</ul>                     </ul>

Copy the code

Supposedly, the ideal outcome is to insert a new node with a Li tag and leave everything else untouched, ensuring the most efficient DOM manipulation. But if we use index as the key here, is that really what we want? Without further ado, try this:

<ul>
   <li v-for="(item, index) in list" :key="index">{{ item.title }}</li>
</ul>
<button @click="add">increase</button>

list: [
        { title: "a".id: "100" },
        { title: "b".id: "101" },
        { title: "c".id: "102"},]add() {
      this.list.unshift({ title: "Three hearts of Lin".id: "99" });
    }
Copy the code

When we click on the button, we can see that, instead of the expected result, all the Li tags are updated

Why is that? Again, let’s try to figure it out

The a, B, c li tags are all reused, because they haven’t changed at all, but a new li tag has been added

But as we said before, in the process of diff on the child nodes, the sameNode of the old first node is compared to the new first node, and this step hits the logic, because now the key of the old first node and the new first node are both 0. Similarly, the sameNode with key 1 and key 2 also hits the logic. As a result, nodes with the same key will be updated by patchVnode, but the existing C node is regarded as a new node because there is no node with key 4 before. So it is funny that the index is used as the key, and the new C node is actually the existing C node. Therefore, the patchVnode text was updated for the first three, and the last one was added, which explains why all li tags were updated.

So what can we do about it? All we need to do is use a unique value for the key

<ul>
   <li v-for="item in list" :key="item.id">{{ item.title }}</li>
</ul>
Copy the code

Now let’s see what happens

Why do we use ID as key to achieve our ideal effect? Because in this way, the keys of nodes A, B and C will always be the same before and after the update. Moreover, since the contents of nodes A, B and C have not changed, even after the implementation of patchVnode, It also does not perform complex update operations, which saves performance. The lin-core node, since there is no node corresponding to its key before the update, is added to the real DOM as a new node.

conclusion

Hopefully this will help those of you who have been wondering about virtual DOM and Diff algorithms

If you think this article has helped you in any way, please give it a like

Welcome to point out my mistakes, I will timely change drops

Study group please click here, study together, fish together!!