Vue series: Virtual DOM and diff algorithm

Virtual DOM

DOM manipulation is very performance expensive, and when manipulating the DOM, Reflow and Repaint the DOM and re-render the DOM, as you can see in my previous article —- browser rendering process

Vue and React are data-driven views that only add, delete, or modify data. How does the framework control DOM manipulation?

React and VUE use virtual DOM (VDOM) to solve this problem. The main principle is as follows: Use JS to simulate DOM structure, transfer DOM calculation to JS calculation, use diff algorithm to calculate the smallest changes, and then operate DOM based on the changes to reduce computation.

For example: using javascript objects to represent HTML tree structures:

Below we through snabbDOM this VDOM library source code to learn vDOM and DIFF algorithm, Vue is a reference to its implementation of VDOM and DIFF

First look at the official example

import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule, // attaches event listeners
]);

const container = document.getElementById("container");
const vnode = h("div#container.two.classes", { on: { click: someFn } }, [
  h("span", { style: { fontWeight: "bold"}},"This is bold"),
  " and this is just normal text",
  h("a", { props: { href: "/foo"}},"I'll take you places!"),]);// Patch into empty DOM element -- This modifies the DOM as a side effect
patch(container, vnode);

const newVnode = h(
  "div#container.two.classes",
  { on: { click: anotherEventHandler } },
  [
    h(
      "span",
      { style: { fontWeight: "normal".fontStyle: "italic"}},"This is now italic type"
    ),
    " and this is still just normal text",
    h("a", { props: { href: "/bar"}},"I'll take you places!"),]);// Second ` patch ` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
Copy the code

There are two key functions:

hThe function returns a vNode, which is a virtual DOM structure represented by a JS object. acceptsel(selector),data(JS description of DOM),children(The child vNode element of the virtual DOM)
patchThe vNode () function is used to render the VNode as a real DOM and mount it to the page, and to re-render the DOM using the diff algorithm to compare the differences between the two VNodes.

The vNode structure is as follows:

Conclusion:

DOM manipulation is very performance-intensive because of redrawing by reflux
Vue and React are data-driven views. They use JS to simulate the DOM structure (VNode) and transfer DOM calculation to JS calculation. Diff algorithm is used to compare the old and new VNodes to calculate the smallest changes.
Snabbdom in the libraryhThe function generates a vnode,patchFunction to render the DOM and update the DOM using the diff algorithm

The diff algorithm

An overview of the

The process of comparing the diff of two old and new VNodes is mainly done inpatchDelta function,

If two trees are normally compared, first, tree1 is traversed. Second, traverse tree2; Third, sort, three times, so the time of the tree diff is O (n^3). Let’s say there are 1000 DOM nodes, 100 million computations, and the algorithm is not available

The diff algorithm in the framework is optimized as follows:

Compare only the same level, not across levels
If the tag is not the same, delete it and rebuild it. (If the tag is not the same, but the child elements under the tag are the same, we will delete it as long as the tag is not the same, because the complexity of depth comparison is too high.)
If the tag and key are the same, they are considered the same node and are not compared in depth

Optimization time complexity to O (n)

Next, read the core functions of the source code to understand the general flow of diff

Generate vnode

The h function in the h.ts file is used to generate vNode, let’s take a look at the source code

//h.ts.export function h (sel: any, b? :any, c? :any) :VNode {
  var data: VNodeData = {}, children: any.text: any.i: number; .// Ignore details
  / / return vnode
  return vnode(sel, data, children, text, undefined);
};
export default h;
Copy the code

Then look at the vnode function:

export function vnode (sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined) :VNode {
  let key = data === undefined ? undefined : data.key;
  // Returns the virtual DOM of a JS object structure
  return { sel, data, children, text, elm, key };
}
Copy the code

Returns a virtual DOM (vNode) of the JS object structure.
children 和 textCan’t coexist, either in plain text or child elements
elmThis is the DOM element that vNode corresponds to
keyIs equivalent tov-forThe inside of thekeyWe use itv-forYou need to add them manually

`patch`function

The patch function is returned by init (snabbdom.ts)

The analysis is as follows:

return function patch (oldVnode: VNode | Element, vnode: VNode) :VNode {
  let i: number.elm: Node, parent: Node;
  constinsertedVnodeQueue: VNodeQueue = []; .// The first argument is not vnode
  if(! isVnode(oldVnode)) {// Create an empty vNode associated with the DOM element
    oldVnode = emptyNodeAt(oldVnode);
  }

  // Same vnode (key and SEL are equal)
  if (sameVnode(oldVnode, vnode)) {
    / / vnode contrast
    patchVnode(oldVnode, vnode, insertedVnodeQueue);
  
  // Different vnodes, delete directly rebuild
  } else{ elm = oldVnode.elm! ; parent = api.parentNode(elm);/ / reconstruction
    createElm(vnode, insertedVnodeQueue);

    if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}...// Don't look at the rest of the code
  return vnode;
};
Copy the code

If it is the same vnode (check method iskey 和 selAll equal), executepatchvNodeDelta function, and let’s go ahead and compare
Different Vnodes, delete directly rebuild

SameVnode has the following functions:

function sameVnode (vnode1: VNode, vnode2: VNode) :boolean {
  // Key and sel are equal
  // undefined === undefined // true
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}
Copy the code

If there is no key (not v-for), then compare the sel selectors of two vnodes to determine whether they are the sameVnode. If there is a key, compare the sel and key together

Conclusion:

First executionpatch ， patch(container, vnode);Create an empty VNode, associate the dom passed in, make both parameters passed in vNodes, and then execute the following logic
If the vNodes have the same tag (SEL) and key, the vNodes are considered to be the same. performpatchVnodeMethods.
If the tag (SEL) is different for different VNodes, delete the tag and rebuild it without further comparison

`patchVnode`function

In the patch function above, if the two VNodes are the same, the patchVnode method is executed to compare the vNodes.

The process of patchVnode is as follows

function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {

  // Set vnode.elem, the new vNode may not have elm, so assign the old one to it to know which real DOM element needs to be updated
  constelm = vnode.elm = oldVnode.elm! ;/ / the old children
  let oldCh = oldVnode.children as VNode[];
  / / new children
  let ch = vnode.children as VNode[];

  if (oldVnode === vnode) return;


  // vnode.text === undefined (vnode.children)
  if (isUndef(vnode.text)) {
    // There are children in both old and new
    if (isDef(oldCh) && isDef(ch)) {
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);// New children have, old children do not (old text has)
    } else if (isDef(ch)) {
      / / clear the text
      if (isDef(oldVnode.text)) api.setTextContent(elm, ' ');
      / / add the children
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    // Old child does, new child does not
    } else if (isDef(oldCh)) {
      / / remove the children
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    / / the old text
    } else if (isDef(oldVnode.text)) {
      api.setTextContent(elm, ' ');
    }

  // else : vnode.text ! == undefined (vnode.children have no value)
  } else if(oldVnode.text ! == vnode.text) {// Remove old children
    if (isDef(oldCh)) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    }
    // Set the new text
    api.setTextContent(elm, vnode.text!);
  }
}
Copy the code

Conclusion:

If the new VNode has onechildren, there is notext （ vnode.text === undefined （ text 和 childrenCannot coexist)) :
- If there are both old and new VNodeschildren, the callupdateChildren()Method, and then continue to update
- If the newchildrenYes, the oldchildrenIf no, calladdVnodes()Method, put the newchildrenAdded to theelmOn,
- If the newchildrenNo, the oldchildrenIf yes, callremoveVnodes()Method to remove the old vNodechildren
- There’s only one thing left. Old and newchildren, old VNodes havetextThe new VNode does nottextThen take itelm 的 textSet to null
If the new VNode does notchildrenonlytext, (vnode.text ! == undefined （ vnode.childrenNo value), and old and newtextNot the same (oldVnode.text ! == vnode.text) to remove the old vNodechildrenTo replace with that of the new VNodetext

If both vNodes have children, the updateChildren() method needs to be called. The update method is more complicated. The rest of the vNodes simply call the DOM API to add and remove DOM elements. Now let’s talk about the update dren() method

`updateChildren`function

Update Dren is complex, so you can just understand the process. Passed the element elm, old children, new chlidren

The caption above represents vNodekeyIt is a combination of tag (SEL) and vNode.

The process is shown above

Principle:

In view of the old and newchLet’s define four indexes,oldStartIdx ， oldEndIdx ， newStartIdx ， newEndIdxIn the loop, IDX will accumulate or decrease, startIdx will accumulate, endIdx will decrease, in the process, the Pointers will slowly move towards the middle, when the Pointers overlap, indicating that the traversal is finished, the loop is finished.

The specific comparison process in each cycle is:

Execute if one of the following four conditions is the same: start vs. start, end vs. end, or end vs. startpatchVnode()Function, performs a recursive comparison, and the pointer accumulates or decays and moves to the middle. In the next cycle, the pointer points to the next onechildren
If none of the above four cases are present, the new node will be taken firstkeyCan be corresponding to a node in oldChkey 。
- If it doesn’t match, the node is new, just insert it somewhere new.
- If it does, you have to judgeselIs it equal, ifselIt’s not equal, so it still doesn’t match, which means that the node is new, so I’ll insert a new node somewhere.
- ifselEqual,keyEqual, then continue to execute on the same two nodespatchVnodeMethod, recursive comparison.

function updateChildren （parentElm:Node.oldCh:VNode[].newCh:VNode[].insertedVnodeQueue:VNodeQueue){
  let oldStartIdx = 0, newStartIdx =0;letOldEndIdx = oldCh. length -1;let oldStartVnode = oldCh[0];letOldEndVnode = oldCh [oldEndIdx];letNewEndIdx = newCh. length -1;let newStartVnode = newCh[0];letNewEndVnode = newCh [newEndIdx];letOldKeyToIdx: KeyToIndexMap |undefined;letIdxInOld:number;letElmToMove: VNode;letBefore:any;while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if(oldStartVnode = =null) {oldStartVnode = oldCh[++oldStartIdx];// Vnode might have been moved left
    } else if(oldEndVnode = =null) {oldEndVnode = oldCh[--oldEndIdx]; }else if(newStartVnode = =null) {newStartVnode = newCh[++newStartIdx]; }else if(newEndVnode = =null) {newEndVnode = newCh[--newEndIdx];// Start vs. start
    } else if(sameVnode (oldStartVnode, newStartVnode)) {patchVnode (oldStartVnode, newStartVnode, insertedVnodeQueue); OldStartVnode = oldCh [+ + oldStartIdx]; NewStartVnode = newCh [+ + newStartIdx];// End and end comparisons
    } else ifPatchVnode (oldEndVnode, newEndVnode) {patchVnode (oldEndVnode, newEndVnode, insertedVnodeQueue); OldEndVnode = oldCh [-- oldEndIdx]; NewEndVnode = newCh [-- newEndIdx];// Start and end comparisons
    } else if(sameVnode (oldStartVnode, newEndVnode)) {// Vnode moved rightPatchVnode (oldStartVnode, newEndVnode, insertedVnodeQueue); API. InsertBefore (parentElm, oldStartVnode. elm! , the API. NextSibling (oldEndVnode. Elm!) ); OldStartVnode = oldCh [+ + oldStartIdx]; NewEndVnode = newCh [-- newEndIdx];// Compare the end and the beginning
    } else if(sameVnode (oldEndVnode, newStartVnode)) {// Vnode moved leftPatchVnode (oldEndVnode, newStartVnode, insertedVnodeQueue); API. InsertBefore (parentElm, oldEndVnode. elm! , oldStartVnode. Elm!) ; OldEndVnode = oldCh [-- oldEndIdx]; NewStartVnode = newCh [+ + newStartIdx];// None of the above four were hit
    } else {
      if(oldKeyToIdx = = =undefinedOldKeyToIdx = createKeyToOldIdx (oldCh, oldStartIdx, oldEndIdx); }// Get the new node key, can match the key of a node in oldChIdxInOld = oldKeyToIdx[newStartvNode.keyas string];// It doesn't match
      if(isUndef (idxInOld)) {// New elementAPI. InsertBefore (parentElm, createElm (newStartVnode, insertedVnodeQueue), oldStartVnode. Elm!) ; NewStartVnode = newCh [+ + newStartIdx];// It works
      } else {
        // The node corresponding to the keyElmToMove = oldCh [idxInOld];// sel equal (sameVnode condition)
        if(elmToMove. sel ! = = newStartVnode. Sel) {// New elementAPI. InsertBefore (parentElm, createElm (newStartVnode, insertedVnodeQueue), oldStartVnode. Elm!) ;// sel equal, key equal
        } elsePatchVnode (elmToMove, newStartVnode, insertedVnodeQueue); oldCh[idxInOld] =undefined as any; API. InsertBefore (parentElm, elmToMove. elm! , oldStartVnode. Elm!) ; } newStartVnode = newCh[++newStartIdx]; }}}if(oldStartIdx < = oldEndIdx | | newStartIdx < = newEndIdx) {if(oldStartIdx > oldEndIdx) {before = newCh[newEndIdx +1] = =null ？ null: newCh [newEndIdx +1]. Elm; AddVnodes (parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue); }else{removeVnodes (parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the code

Why does V-for use key

As you can see from the updateChildren function above, the key is a key condition for comparing whether the old and new vNodes are equal

According to the source can be known:

If no key is used and Diff finds that no key matches, it assumes that all nodes have been updated, and the algorithm destroys all vNodes and re-renders the new element.
If a key in the new node is detected to correspond to a key in the old node, such as swapping positions, there is no need to destroy and re-render, just swap positions. Improved performance

If the key uses a random number, it will not work, because when the random number is updated, it will become new, and all the keys will not correspond, so it will re-render as if there is no write

If the key uses the index of the array, if the original element changes from 1 to 0, then after diff, the problem will be that the algorithm will think that the two elements are not changed, and then it will not update

Vue series: Virtual DOM and diff algorithm

Virtual DOM

The diff algorithm

An overview of the

Generate vnode

patchfunction

patchVnodefunction

updateChildrenfunction

Why does V-for use key

Related Posts

Introduction to algorithms: time complexity and space complexity and their calculations

Micro channel small program tuning keyboard performance optimization

Design Tokens — Sparks of design and development

`patch`function

`patchVnode`function

`updateChildren`function