preface

It has been more than a year since the release of VUe3 version, and VUe3 has begun to become stable. This chapter will make a shallow analysis of THE DIff algorithm of VUe3

React versus Vue2 diff defects

react: Core diff compares the old and new nodes from the head until the first node that cannot be matched jumps out, which is recorded as lastplaceIndex. Then, it compares the remaining set of new nodes with the remaining set of old nodes, and compares the oldIndex of the old node to determine the location. The React Diff algorithm has some performance defects. The React Diff algorithm will sacrifice some performance when the React operation is moved.

Vue2. X: Vue2. X learned the experience of React and adopted the comparison method named dual-end queue, which effectively solved the performance defects left by React. But vue2

  1. Not so sensitive to add and delete operations
  2. A maximum of five comparisons on the same node are required each time

Vue3 — inferno

Vue3 adopts the DIff algorithm implemented in Inferno. The following is a comparison diagram of the DIFF algorithm

The data comes from JS-Framework-benchmark. Here we introduce its principle

An obvious example

exp1:

  var text1 = 'text'
  var text2 = 'text'
Copy the code

Text1 === text2, we don’t need to do anything else, we can reuse it all

exp2:

  var text1 = 'I love React very much'
  var text2 = 'I love Vue very much'
Copy the code

It can be found that the difference between React and Vue is only in the characters, and the rest can be reused

exp3:

  var text1 = 'I love martin'
  var text2 = 'I love martin too'
Copy the code

By comparison, we can find that the difference between the two is that text2 has too, and the rest can be reused. Therefore, we only need to add too to the old node in specific operation

exp4:

  var text1 = 'I love martin too'
  var text2 = 'I love martin'
Copy the code

After comparison, we can find that the difference between the two is that text1 has too. We only need to delete too at the end of the old node

Through the above example, we can find that this method can quickly master the operation of adding and deleting. For these operations, we can completely avoid calling patch method again, thus improving the performance to a higher level

Same prefix and suffix

From the above example we can extract the basic operation steps

  1. Search for all similarities between the old and new nodes from the head until the first different node is encountered or the string is traversed, at which point j is the current index and j is the first different node index
  2. Find all similarities between the old and new nodes in reverse order starting from the tail until the first different node is encountered or less than j, at which point the new node newEnd and the old prevEnd are recorded as the first different node index
  3. Compare j with newEnd and prevEnd
A. J > prevEnd and j <= newEnd; b. J > prevEnd and j <= newEnd; b. J > prevEnd and j <= newEnd; C. J < prevEnd and j < newEnd, indicating that the new node has been traversed and the old node has not been traversed, indicating that all values from j to prevEnd need to be deleted. At this point, the core diff algorithm (explained in a moment) will be entered. D. j > newEnd and j > prevEnd indicate that the new and old nodes have been traversed and do not need to be recreatedCopy the code

Core diff – Determine if there are moving nodes and how

As with React and Vue2. X, there are two things we need to do to determine whether the old and new nodes move:

  1. Determine if there is movement
  2. How do moving nodes move

According to point C above, we will enter the core Diff algorithm talk is cheap show me code:

  const source = []
  const keyIndexMap = new Map(a)let uid = 0
  function sureIsMove(nChildren, oChildren) {
    let moved = false
    let lastPlaceIndex = 0
    
    for (let i = 0; i < nChildren.length; i++) {
      constkey = nChildren[i].data? .key || uid++ source[i] = -1
      keyIndexMap[key] = i
    }
    
    for (let i = 0; i < oChildren.length; i++) {
      const oldNode = oChildren[i]
      constkey = oldNode.data? .keyconst index = keyIndex.get(key)
      
      if (~index) { // Abstract leakage
        source[index] = i
        
        if (index < lastPlaceIndex) {
          moved = true
        } else {
          lastPlaceIndex = index
        }
      }
    }
    
    return moved
  }
  
  function moveNode() {
    const moved = sureIsMove.apply(null.arguments)
    const lisSource = lis(source)
    if(version) {let x = nChildren.length - 1
      let y = lisSource.length - 1
      let end = nextEnd + 1 // nextEnd is the index of the first different value obtained from the end of the previous step
      for (; x >= 0; x--) {
        if (source[x] === -1) { // Add a node
          const node = nChildren[x].tag
          const el = docuement.createElement(node)
          ......
          const oldEl = nChildren[--end].el
          const container = oldEl.parentNode
          container.insertBefore(el, oldEl)
        } else if(x ! == y) {/ / to move
          const el = nChildren[x].el
          ......
          const oldEl = nChildren[--end].el
          const container = oldEl.parentNode
          container.insertBefore(el, oldEl)
        } else {
          y--
        }
      }
    }
  }
Copy the code

Let’s walk through the code step by step

  1. First we create a source array that stores the location of the old set of nodes in the new node

    For example:

        oldChildren = [b, a, c]

        newChildren = [a, b, c]

        source = [1, 0, 2]

    We can find that the subscript of source is the subscript of newChildren, and then the subscript of oldCHildren corresponding to newChildren is the value in source.Source is a set of newChildren and oldChildren subscripts
  2. We created a keyIndexMap to store the dictionary table of newChildren. Key is the key value corresponding to the node, and value is the subscript corresponding to newChildren. The dictionary is stored to facilitate the later source collection as a performance optimization, space for time ~
  3. Start the first goal: React Diff determines whether to move or not. We prefetch a value of lastplaceIndex and use it to mark the latest index to which newChildren is moved. When traversing oldChildren, we will go to keyIndexMap to find the subscript value index (that is, the subscript value located in newChildren) of the corresponding key. If it is found, it means that the node can be reused. At this time, we will collect the subscript value corresponding to oldChildren and put it into the source. Then determine the size of index and lastPlaceIndex. If index < lastPlaceIndex, it has moved. If not, assign index to lastPlaceIndex.Why would you be able to determine if you're moving by doing that?We can see that oldChildren arePositive sequence traversal, if the location of the old node is further back but the newChildren location is further forward, it indicates that the location has been moved and the old node has been moved to the front
  4. Once we have determined whether to move, what we need to consider is how to move, so we need to extract the longest increasing subsequence from the source beforehand, okay

    What is the longest increasing subsequence:

      const source = [2, 3, 1, 5]

    The longest increasing subsequence is [2, 3, 5]

So we can think of the longest increasing subsequence as the longest sequence that hasn’t changed in order in newChildren, and we don’t do any movement on that sequence, and then the rest of the sequence has to be processed and once we know that, we start processing how to move, First we get the longest increasing subsequence in the source (note here that the lisSource we extract is a set of subscripts rather than a set of values), and then we analyze the movement logic:

First, we calculate the longest increasing subsequence lisSource according to source, then we reverse order through newChildren and take the last value of lisSource at the same time 1. Source [x] === -1 indicates that this value is a newly added value, so we need to add new processing. DomOM provides an API that uses the insertBefore method for this inserted value. InsertBefore takes three arguments: 1. ParentNode 2. Node 3. ReferrenceNode = nextEnd + 1; ReferrenceNode = nextEnd + 1 and nextEnd -= 1 2.x! The current node of the == y surface is not in the longest increasing subsequence, so to move it, we are traversing in reverse order, so we just need to place the value in front of nextEnd + 1. If x === y, then this node does not need to move, we just need to subtract y by oneCopy the code

So far, the general principle is basically finished, you can also try to write to see

reference

Hcysun. Me/vue – design /…

At the end

If you don’t understand, please add me on wechat: IAmFineThanksMartin. Let’s be a layback socializer

push

I am currently working in the background of netease Hangzhou Research Institute for Big data. There is a shortage of staff inside. If you are interested, please add me on wechat and come to the pig Factory to have a happy meal together!