preface

Speaking of vUE source code in the interview, will generally pull the DIFF algorithm, and the DIFF and on the Internet legend, said to improve the page update performance, let’s see what’s going on

Traditional DIff algorithm

Back in the days of Jquery, I was told that frequent manipulation of the DOM was a performance drain, and that we could improve efficiency by replacing the entire DOM with innerHTML after splicing together HTML fragments.

So I’ve been asking myself why diff can improve performance by comparing nodes and reusing nodes, but wouldn’t it be more efficient to just replace the entire innerHTML?

With doubt on the Internet to consult some articles, the feeling seems to be understood

First, the cost of creating a complete node object is very high, because DOM nodes are very complex objects

const elm = document.createElement('div')

for(let propName in elm) {
    console.log(propName)
}
Copy the code

So even if we replace the entire DOM with innerHTML in the browser, the browser will reuse it by comparing different nodes.

The comparison algorithm involves the pound-for-pound comparison of each old and new node, and its complexity is O(n^2). After the comparison, the minimum transformation method has to be calculated, so the combined complexity is O(n^3). We call this the traditional DIff algorithm

React diff goes from O(n^3) to O(n). How do I calculate O(n^3) and O(n)?

Framework layer diff algorithm principle

Compared with the traditional DIFF algorithm, the framework layer diFF has a major premise

The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored

So the core of DIFF is that it only compares nodes in the same layer, ignoring the reuse of nodes across layers

As shown in the figure above, only nodes with the same parent are compared for reusability.

It is worth noting that nodes of the same layer are not compared in pairs, but in a certain order, or judged by the key attribute. Therefore, new nodes only need to be traversed once, so the complexity of the algorithm is reduced to O(n).

Look at diff through vue source code

In fact, the principle of diff algorithm is so simple, nothing more than recursion and traversal nodes to compare node reuse. But in vUE source code, how to achieve it? Together to see

Virtual Dom

First, understand that a VUE maintains a VNode object corresponding to the DOM node

For example,

<div key="1">123</div>
Copy the code

There will be a VNode object corresponding to this in the VUE, and we have listed several key attributes

{
  elm: el, // Corresponds to the actual DOM node
  tag: 'div'.key: 1.text: '123'.children: []}Copy the code

The children array of VNode corresponds to the VNode object of the child node, so the MAPPING between VNode and the real DOM tree is carried out in VUE, which is also called virtual tree.

It’s because of the virtual tree, when the data is updated. We can compare the difference between the VNode built with new data and the oldVnode built with old data to achieve surgical precision update.

And our algorithm for comparing differences is diff. Diff is used to compare the differences of virtual trees, and the differences are updated to the corresponding real DOM nodes by means of patch.

The patch function

The patch function is the entry function of the DIFF process

It receives two input parameters, namely vnode and oldVnode, and diff analysis is performed on the virtual node

function patch (oldVnode, vnode) {
  // some code
  if (sameVnode(oldVnode, vnode)) {
    // patch existing root node
    patchVnode(oldVnode, vnode)
  } else {
    // replacing existing element
    const oldElm = oldVnode.elm
    const parentElm = nodeOps.parentNode(oldElm)

    // create new node
    createElm(
      vnode,
      null,
      parentElm,
      nodeOps.nextSibling(oldElm)
    )

    // destroy old node
    if (isDef(parentElm)) {
      removeVnodes([oldVnode], 0.0)}}return vnode.elm
}
Copy the code

The logic of patch function is relatively simple

  1. Check whether the node can be reused. If yes, patch the node

  2. The node cannot be reused. Create a new node and insert it before the old node and delete the old node

As can be seen, if the node is not reusable, directly create a new node to replace, the old child node will not consider reuse. This is the assumption that corresponds to diff, that the DOM node movement across hierarchies in the Web UI is so minimal that it can be ignored

How does the sameVnode function evaluate reusability

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 code

This section of vue complete source code involves more variables, we only need to understand roughly through the tag key inputType to determine the line. In other words, when the tag key inputType is exactly the same, we assume that the node is reusable.

PatchVnode function

Next, how do you patch reusable nodes

function patchVnode(oldVnode, vnode) {
  // some code
  if (oldVnode === vnode) {
    return;
  }

  const elm = (vnode.elm = oldVnode.elm);
  const oldCh = oldVnode.children;
  const ch = vnode.children;
  
  // Non-text node
  if (isUndef(vnode.text)) {
    // Both old and new nodes have children
    if (isDef(oldCh) && isDef(ch)) {
      // Peer comparison of child nodes
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch); }else if (isDef(ch)) {
      // Only new elements have child nodes
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1.null);
      // Only old elements have child nodes
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // Empty the text
      nodeOps.setTextContent(elm, "");
    }
  // Update the text node
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }
}
Copy the code

The logic of patchVnode function is not complicated, so let’s analyze it

  1. Find the corresponding DOM node elm and assign it to vnode.elm

  2. Determine the new node type (vnode.text). If it is a text node, update elm text

  3. Under the non-text node, determine the child nodes of the old and new nodes

  4. If both the old and new nodes have children, go to the layer comparison process updateChildren of the children

  5. If only the new node has child nodes, use addVnodes to add child nodes to ELM (delete text first).

  6. If only the old node has child nodes, use removeVnodes to remove them

  7. If there is no child node, check whether the old data has a text node, if so, empty

AddVnodes and removeVnodes update elm nodes directly. This is a simple process to patch elm nodes using data (vnode oldVnode).

It’s worth noting that the sibling comparison updateChildren for the children is involved, so let’s see how it works, that is, how it flows further from the parent node to the child node comparison.

updateChildren

The child node comparison process is a little more complicated, because it involves determining whether there are reusable nodes at the same layer, based on the key attribute. Or in some other order?

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
  let 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, idxInOld, vnodeToMove, refElm;

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    } 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)) {
      // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode);
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      );
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      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,
          null,
          parentElm,
          oldStartVnode.elm
        );
      } else {
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          );
        } else {
          // same key but different element. treat as new elementcreateElm(newStartVnode, insertedVnodeQueue, parentElm); } } newStartVnode = newCh[++newStartIdx]; }}if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1])?null
      : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
  } else if(newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx); }}Copy the code

At first glance, the code looks pretty long, but there are actually multiple if-elseif sorting processes, and trust me, the code looks long but still simple

I recommend drawing a graph like I did before analyzing, because there are a lot of variables at the front of the code

So first of all we’ll call startIdx endIdx left pointer, right pointer, startVnode, endVnode we’ll call them left node, right node, and all of a sudden the variables are a lot clearer

All right, let’s start analyzing the logic

  1. Loop over if the left pointer is less than or equal to the right pointer

  2. If the old node boundary is null, move the pointer inward

  3. Determine whether the left node can be reused, patch the node (recursively call patchVnode, the same below), and move the pointer to the right

  4. Otherwise, check whether the right node can be reused. If yes, patch the node and move the pointer to the left

  5. Otherwise, determine whether the new right node and the old left node can be reused, patch the node if yes, move the old left node to the front of the old right node, and then move the pointer inward (the process of moving will eliminate the old right node).

  6. Similarly, judge the new left node and the old right node, and perform similar operations

  7. When none of the above conditions can be reused, the next step is to use key to determine whether it can be reused

First, the createKeyToOldIdx function is used to get the mapping of the old node index to the key property. The data structure is

{
  keyIdx: oldChIdx
}
Copy the code

Then assign the idxInOld variable to the old node index corresponding to the key of the new left node

idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
Copy the code

The findIdxInOld function returns the first old node that can be reused when the new node does not have a key

function findIdxInOld (node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i]
    // Return the first old node that can be reused (the old node key must also be null)
    if (isDef(c) && sameVnode(node, c)) return i
  }
}
Copy the code

If no node index is found for which the key can be reused, a new node is created and moved to the front of the old left node (oldStartvNode.elm)

if (isUndef(idxInOld)) {
  // New element
  createElm(
    newStartVnode,
    null,
    parentElm,
    oldStartVnode.elm
  );
}
Copy the code

If the old node corresponding to the key is found, sameVnode is used to determine whether it is really reusable. If it is not reusable, a new node is created. Make sure that the old node corresponding to the key is reusable, patch the old node, set the array element of the old node to NULL (which is why it is null in the first step), and move the old node before the old left node (oldStartvNode.elm)

vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
  patchVnode(vnodeToMove, newStartVnode);
  oldCh[idxInOld] = undefined;
  nodeOps.insertBefore(
    parentElm,
    vnodeToMove.elm,
    oldStartVnode.elm
  );
} else {
  // same key but different element. treat as new element
  createElm(newStartVnode, insertedVnodeQueue, parentElm);
}
Copy the code

Finally, complete the logic of this step and move the pointer inward

newStartVnode = newCh[++newStartIdx];
Copy the code

  1. After executing the above sequence, jump out of the loop

  2. If old nodes have been traversed, new nodes are added in batches

if (oldStartIdx > oldEndIdx) {
  refElm = isUndef(newCh[newEndIdx + 1])?null
    : newCh[newEndIdx + 1].elm;
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
}
Copy the code
  1. If new nodes have been traversed, delete existing nodes in batches
if (newStartIdx > newEndIdx) {
  removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
Copy the code

At this point, the logic of update Hildren is finished. The difficulty lies in the classification judgment, and the essence lies in the movement of pointer (index).

Tips: The insertBefore method can move the node, it will delete the original node, you can see the description of MDN

For example

Let’s take a look

We assume that all nodes have corresponding key attributes (values and letters)

  1. Compare the left node A === A reusable, move the pointer to the right

  1. The comparison node B === B is reusable, and the pointer is moved inward before B is moved to D

  1. C cannot find the reusable node and creates a new node before D while moving the pointer

  1. If the loop condition is not met, the loop is broken

  2. Delete oldStartIdx oldEndIdx from oldStartIdx

conclusion

The principle of Diff is actually quite simple, it is the same layer comparison reusability. However, the logic of how to compare the reusability of nodes of the same layer is still quite numerous, so we need to simplify the complexity and understand it naturally. There may be some errors in the above analysis, you are welcome to point them out. Happy New Year everyone!

reference

  • Understand the React: Diff algorithm

  • Explain the DIff algorithm of VUE

Welcome to the front food birds together fish paddling ~ 516913974