React and Vue Diff algorithm analysis and comparison

React diff algorithm

Only peer nodes are compared, not reused if DOM nodes move across hierarchies
Use key to build a map of the old node, and delete it from the map after reuse
lastPlacedIndexRepresents the index of the last node not to be moved
The principle of movement is to move as little as possible, if there must be one to move, the new status of the higher motionless, the new status of the lower move

Compare the order

1. If the node corresponding to the key can be found, then compare the type. If the type is different, delete the old node and create a new one.
LastPlacedIndex <= oldIndex does not need to be moved, otherwise it needs to be moved and updated

Change the execution order of A, B, C, D, E, F to A, C, E, B, G

lastPlacedIndex = 0
A exists in the map and is in the same position. Multiplexing nodes update attributes
C Compare lastPlacedIndex < oldIndex, lastPlacedIndex = 2
E compare lastPlacedIndex < oldIndex, lastPlacedIndex = 4
B: lastPlacedIndex > oldIndex
G is not found in map, need to create and insert
Mark the remaining elements D F in the map as deleted

Change the dom order: delete first, then update and move, and finally insert

const EFFECT_TYPE = {
  UPDATE: 2./ / update
  INSERT: 4./ / insert
  INSERT_UPDATE: 6.// Insert and update
  DELETE: 8./ / delete
};

const oldNodes = [{ key: "A" }, { key: "B" }, { key: "C" }, { key: "D" }];

const newNodes = [
  { key: "D" },
  { key: "A" },
  { key: "F" },
  { key: "G" },
  { key: "B"},];* A B C D becomes * D A F G B *1 A B D *2. B D A *3. D A B *4. D A F B *5. D A F G B */

function diff(oldNodes, newNodes) {
  let lastPlacedIndex = 0;
  const oldNodeMap = oldNodes.reduce((memo, v, i) = > {
    memo[v.key] = v;
    v.oldIndex = i;
    return memo;
  }, {});

  newNodes.forEach((newNode, newIndex) = > {
    const oldNode = oldNodeMap[newNode.key];
    if(! oldNode) {/ / couldn't find it
      newNode.effectTag = EFFECT_TYPE.INSERT;
      newNode.insertIndex = newIndex;
      return;
    }

    // Delete from map
    delete oldNodeMap[newNode.key];

    // Insert and update at different positions
    if (lastPlacedIndex <= oldNode.oldIndex) {
      // The index is greater than lastPlacedIndex
      newNode.effectTag = EFFECT_TYPE.UPDATE;
      lastPlacedIndex = oldNode.oldIndex;
    } else {
      // Index less than lastPlacedIndex needs to be movednewNode.effectTag = EFFECT_TYPE.INSERT_UPDATE; }});return Object.keys(oldNodeMap);
}

const deletions = diff(oldNodes, newNodes);

console.log("Delete node", deletions);

console.log(newNodes);
Copy the code

Vue diff algorithm

The DIff algorithm in VUE involves logic to manipulate the DOM, so use HTML for the demonstration

OldNodes represents the old list of virtual nodes, el- real DOM, tag- tag type
The domDiff method takes three arguments, el- the parent of the node to be compared, oldChildren- the old virtual DOM list, and newChildren- the new virtual DOM list
Node comparison in VUE uses double Pointers, traversing from both ends to the middle. When the Pointers cross, the comparison is completed
At the beginning of traversal, the comparison of head to head, tail to tail, head to tail and tail to head is carried out successively, which is also an optimization point of DIff algorithm in VUE
All of these are compared, and then compare the other nodes that do not move regularly

<! DOCTYPEhtml>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="Width = device - width, initial - scale = 1.0" />
    <title>Document</title>
  </head>
  <body>
    <ul id="container">
      <li id="domA">A</li>
      <li id="domB">B</li>
      <li id="domC">C</li>
      <li id="domD">D</li>
    </ul>
    <script>
      const oldNodes = [
        { key: "A".el: domA, tag: "li" },
        { key: "B".el: domB, tag: "li" },
        { key: "C".el: domC, tag: "li" },
        { key: "D".el: domD, tag: "li"},];const newNodes = [
        { key: "C".tag: "li" },
        { key: "A".tag: "li" },
        { key: "F".tag: "li" },
        { key: "G".tag: "li" },
        { key: "B".tag: "li"},];/** * see if the two nodes are the same, and compare the tags and keys *@param {*} newVnode
       * @param {*} oldVnode* /
      function isSameVnode(newVnode, oldVnode) {
        return newVnode.tag === oldVnode.tag && newVnode.key == oldVnode.key;
      }

      / * * * *@param {*} El Real DOM node *@param {*} OldChildren old virtual dom *@param {*} NewChildren New virtual DOM */
      function domDiff(el, oldChildren, newChildren) {
        // Old start index
        let oldStartIndex = 0;
        // The old start node
        let oldStartVnode = oldChildren[0];
        // Old end index
        let oldEndIndex = oldChildren.length - 1;
        // The old end node
        let oldEndVnode = oldChildren[oldEndIndex];
        
        // New start index
        let newStartIndex = 0;
        // New start node
        let newStartVnode = newChildren[0];
        // The new end index
        let newEndIndex = newChildren.length - 1;
        // The new end node
        let newEndVnode = newChildren[newEndIndex];
        
        // Construct a map based on the old node
        let oldNodeMap = oldChildren.reduce((memo, item, index) = > {
          // A: 0 Records the position
          memo[item.key] = index;
          return memo;
        }, {});

        // Double pointer comparison, from both ends to the middle, when the pointer is crossed, the comparison is complete
        while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
          // When the pointer moves, the element may have already been removed, so skip this item
          if(! oldStartVnode) { oldStartVnode = oldChildren[++oldStartIndex];console.log("1. OldStartVnode is empty");
          } else if(! oldEndVnode) { oldEndVnode = oldChildren[--oldEndIndex];console.log("2. OldEndVnode empty");
          } else if (isSameVnode(oldStartVnode, newStartVnode)) {
            console.log("3. Same head", newStartVnode.key);
            // Compare the header, if the same move the header pointer
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
          } else if (isSameVnode(oldEndVnode, newEndVnode)) {
            console.log("4. Same from end to end", newEndVnode.key);
            // Compare tail to tail, if same, move tail pointer
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
          } else if (isSameVnode(oldStartVnode, newEndVnode)) {
            console.log(
              '5. Same head and tail movement${oldStartVnode.key} 到 ${oldEndVnode.key}Before the next node of '
            );
            // end comparison
            // Move the real DOM of oldStartvNode. el to the end of the old node
            el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
            oldStartVnode = oldChildren[++oldStartIndex];
            newEndVnode = newChildren[--newEndIndex];
          } else if (isSameVnode(oldEndVnode, newStartVnode)) {
            // end to end comparison
            console.log(
              '6. Same movement of tail head${oldEndVnode.key} 到${oldStartVnode.key}Before `
            );
            el.insertBefore(oldEndVnode.el, oldStartVnode.el);
            oldEndVnode = oldChildren[--oldEndIndex];
            newStartVnode = newChildren[++newStartIndex];
          } else {
            // All the above are special cases
            // Head/tail/head/tail/head/tail/head/tail
            // Compare out of order
            let moveIndex = oldNodeMap[newStartVnode.key];
            if (moveIndex === undefined) {
              // Can not find index, is a new node, need to create
              el.insertBefore(createElm(newStartVnode), oldStartVnode.el);
              console.log('7. Create a new node${newStartVnode.key}Inserted into the${oldStartVnode.key}Before `);
            } else {
              / / found
              let moveVnode = oldChildren[moveIndex];
              el.insertBefore(moveVnode.el, oldStartVnode.el);
              // Mark the moved node as undefine
              oldChildren[moveIndex] = undefined;
              console.log(
                '8. Move the out-of-order node${moveVnode.key} 到 ${oldStartVnode.key}Before `); } newStartVnode = newChildren[++newStartIndex]; }}// Insert a new one
        if (newStartIndex <= newEndIndex) {
          / / reference
          let anchor =
            newChildren[newEndIndex + 1= = =null
              ? null
              : newChildren[newEndIndex + 1].el;
          for (let i = newStartIndex; i <= newEndIndex; i++) {
            console.log("Insert", newChildren[i].key); el.insertBefore(createElm(newChildren[i]), anchor); }}// The old one needs to be removed
        if (oldStartIndex <= oldEndIndex) {
          for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            let child = oldChildren[i];
            console.log("Delete", child.key); child && el.removeChild(child.el); }}}/** * Create a real DOM from the virtual DOM *@param {*} vnode
       * @returns* /
      function createElm(vnode) {
        let { tag, text, key } = vnode;

        if (typeof tag === "string") {
          vnode.el = document.createElement(tag);
          vnode.el.innerText = key;
        } else {
          vnode.el = document.createTextNode(text);
        }
        return vnode.el;
      }

      domDiff(container, oldNodes, newNodes);
    </script>
  </body>
</html>
Copy the code

The difference between

The same

Both groups of virtual DOM comparisons (Fiber vs. virtual DOM after React16.8)
Only the same nodes are compared, which simplifies the algorithm complexity
The old node will be reused only if the key and label type are the same
Before traversal, a map is constructed based on the old nodes for quick search by key

The difference between

React only records nodes that need to be modified during diff traversal, forming an Effect list. The actual DOM will be modified according to the Effect list. The actual DOM will be deleted first, then updated and moved, and finally inserted
Vue uses the real DOM for traversalinsertBeforeMethod, which modifies the real DOM, and finally deletes it
React uses a single pointer to traverse from left to right
Vue uses double Pointers to traverse from both ends to the middle
React’s virtual diff is relatively simple, with some optimization in VUE, which is relatively complex but more efficient

React and Vue Diff algorithm analysis and comparison

React diff algorithm

Compare the order

Change the execution order of A, B, C, D, E, F to A, C, E, B, G

Change the dom order: delete first, then update and move, and finally insert

Vue diff algorithm

The DIff algorithm in VUE involves logic to manipulate the DOM, so use HTML for the demonstration

The difference between

The same

The difference between

Related Posts

Vue2 – Global API source code analysis

The for loop can also iterate over the object hahaha~

Wechat applet how to modify the style of the child component in the parent component