[Vue] Diff algorithm

Virtual DOM

1. What is the virtual DOM? (Virtual DOM hereinafter referred to as VDOM)
   • Vdom is an object, a tree, that describes the structure of the DOM in an object
   • A DOM tag is described with an attribute
   • A property describes a property on the DOM
   • Use an attribute to describe a child node in the DOM. The child node should be an array, and the element is a VDOM

   const vdom = {
       tag: 'div'.attr: {
           class: 'xx'
       },
       text: 'Div text'
       children: [
           tag: 'input'.attr: {
               value: 3}}]Copy the code

   • So how to render the virtual DOM into the real DOM is essentially a tree traversal, and then call the corresponding browser API to create the node, set its attributes to the node, and add child nodes.

   

What is a diff?

1. Comparing two virtual DOM trees (VDOM) is essentially a comparison of two objects and two trees. When views are updated in a responsive manner, the overhead of DOM manipulation is minimized, so we don’t need to update the entire view completely, but only the parts where they differ

Warm up algorithm

1. If A sorted array A is scrambled into array B, how do I locate the elements in array A in array B
   • A:[1, 2, 3, 4, 5, 6]
   • B:[2, 5, 1, 3, 6, 4]
   • The problem is simple enough that two for loops can solve it:

   for(let i = 0; i < A.length; i++){
       for(let j = 0; j < B.length; j++){
           if(A[i] = B[j]) return j
       }
   }
   Copy the code

   • Why talk about this problem, because this is the “core” of the DIff algorithm, the processing of the other parts of the DIFF can be considered optimization on top of this

How diff

1. In the first step, the diff of the old and new vNodes starts from the root div node. At this point, it is easy to update the attributes, events, styles, etc. of the div according to the VNode of the old and new vNodes

2. The second step is to compare the children under the root div and update the children, which is the red box in the diagram. This part of the comparison is the most troublesome – the biggest problem is how to find which two children in the two child array are the same child node. Because a node may be added to the child node of the new VNode, a node may be deleted, or the node may be inserted before a node, the situation is complicated – in all cases, it must be possible to find which child node of the new VNode corresponds to the old VNode. Is it possible to solve this problem using the algorithm above

3. Step 3: Find the child node A of the new VNode corresponding to the child node of the old VNode using the solution of the algorithm problem above, then update the events and attributes of the child node A in the way of the first step, and then continue to update the child node of the child node A…

   

4. The child node is updated and optimized

   • The update of the node in the second step above is a cycle of n square time complexity, and we want to optimize it into an algorithm of N time complexity
   • This is a summary of several DOM variations (here are just a few common ones)
     1. New child nodes are not added, deleted or moved, but some child nodes themselves change
        • Old Vnode:[1, 2, 3, 4, 5]
        • New Vnode:[1, 2, 3, 4, 5]
     2. The new child node deletes a DOM
        • Old Vnode:[1, 2, 3, 4, 5]
        • New Vnode:[1, 2, 3, 4]
     3. The new child node adds a DOM
        • Old Vnode:[1, 2, 3, 4, 5]
        • New Vnode:[6]
     4. The new child node flips
        • Old Vnode:[1, 2, 3, 4, 5]
        • New Vnode:,4,3,2,1 [5]
   • It is found that the changes of sub-nodes in most cases are consistent with the above situation. In the rare cases where the order of the new child nodes is completely out of order, an N2n ^2n2 time-complexity loop is required to ensure that the same VNode is found.
   • So how to optimize for the above special cases?
     • For the first three cases, it is ok to traverse the child nodes of the new Vnode directly, because the same positions of the old and new child nodes are one-to-one. In the case of 2 or 3, the remaining DOM can be added or removed after the array is traversed, and the details are fine.
     • In the fourth case, I simply iterate over the new Vnode and discover that the new child node 5 and the old child node 1 are different VNodes. If the new child node 5 and the old child node 1 are found to be different from the same VNode, we do not start from the head of the old VNode to determine whether the new child node 5 and the end of the old child node array 5 are the same VNode. If the new child node 5 and the end of the old child node array 5 are found to be the same VNode, we can go down again.
   • After summing up the squid, it is found that the following four ways to determine whether the VNode of the child node is the same VNode can greatly reduce the probability of traversal times
     

     For the sake of illustration, we use A to represent the old child node array and B to represent the new child node array

     1. Check whether the first node of A is the same node as the first node of B

     2. If not, check whether the last node of A is the same node as the last node of B

     3. If not, proceed to determine whether the first node of A is the same node as the last node of B

     4. If not, proceed to determine whether the last node of A is the same node as the first node of B

     5. If the above four methods cannot be matched, there is no other way but to use violence to match the nodes of A one by one with the nodes of B and find the nodes of B corresponding to the nodes in A

   • This optimization algorithm can simply be called a head – tail comparison shrinkage algorithm, vivid

5. Note that the diff algorithm starts with four numeric variables that point to the subscripts of the beginning and end nodes of the old and new child nodes. Define four object variables that point to the start and end nodes of the old and new child nodes. The reason for doing this is that each time he finds the corresponding VNode, the start and end nodes of the new and old child nodes shrink to the middle. You don’t need to start all over again because you’ve already done it. The source code is as follows:

   

   • The general process is as follows

   

conclusion

1. Priority is given to determine whether the first and the last four cases can be matched. If not, the cycle of n2N ^2n2 is used to match
2. In this optimization, the best case is n, and the worst case is N2 +4nn^2+4nn2+4n, also n2n^2n2
3. The core of diff algorithm is the traversal of two arrays, but it is optimized on this basis, so that the actual time complexity of DIff is close to N in most cases
4. So the diff algorithm is actually not that scary. Other posts are not going to talk about the core of the DIFF, they’re going to talk about the optimization part of the diFF first, they’re going to talk about a bunch of variables, OldStartVnode old VNode start node, oldEndVnode old VNode tail node, newStartVnode new VNode start node… It’s spinning people around.

Diff triggers the process

1. Diff triggers in two ways:
   • The first is the first diff when a Vue instance is initialized
   • The second type is reactive update-time diff, where data.setter is an object-defineProperty proxy for an Object property that is triggered when the data is changed

   

2. Note that the _update method for updating views is also responsive and requires collecting dependencies, and you can simply think of Vue’s view updates as a computed. It is separate from Computed and Watcher on Vue, and note that Computed and Watcher responsiveness has nothing to do with view updates. Views update only if they actually use values in computed and data, and the values change. Adding a reactive update to _upodate is done in the mountComponent.

thinking

1. Why do I need to check whether the VNode is the same by tag and key
   

   You should not think of this as a necessary key, but rather why the author of the Diff thought of an extra key to identify the same VNode.

   • First of all, the author of Diff must have considered the feasibility of other schemes at the beginning, so whether the two Vnodes are the same VNode has the following schemes:
     • If the reference is the same, it is the same VNode. However, if you change the new VNode, the old VNode will also change, so the old VNode and the new VNode must be different references, i.e. two unrelated objects. This will not work
     • A comparison of two objects, deep traversal to see if they all have the same properties. First of all, performance is poor, and it is normal to add and delete DOM attributes on the same DOM, so this scheme is not suitable for many cases.
   • It is impossible to be 100% sure that two VNodes are the same VNode, mainly because the new VNode can change at will with respect to the old VNode.
   • That’s why early diff writers used the less-than-perfect way of identifying the same VNode with tags and extra defined keys
     • This is why we add an extra key to the for loop. When we first started using the React framework, we probably wondered why we needed a key property that wasn’t relevant to development.
     • Why not perfect? If the index of the for loop is used as the key value, the second child node B of the old VNode and the second child node C of the new VNode are considered to be the same VNode during patch even though they are not actually the same VNode

     

2. Why diff? What does diff do
   • A backflow redraw that mimics the browser DOM
   • Improve development efficiency
     • Improve the development efficiency of the framework, Vue this part of the code is the squid sucked on the basis of Snabbdom transformation, EMMM, advanced copy and paste engineering [head]
     • It also increased our development efficiency because we didn’t have to manipulate the DOM manually
   • Cross-platform and compatibility
     • Vdom is essentially a JS object, or ECMAScript object, which is platform-independent, whereas the real DOM is platform-dependent

     Js includes ECMAScript, Window, and Document. ECMAScript is standards-compliant, while Window and Document objects may be slightly different for different platforms. Vdom does not need to render into real DOM, does not need to call platform-related window and document to achieve high cross-platform compatibility

   • As for the argument that performance can be improved, I prefer to guarantee a lower limit of performance. My view is as follows:
     • In fact, it is widely believed on the Internet that it can speed up the rendering speed, but there is no advantage in the actual speed, because vDOM rendering into the real DOM actually also needs to call the browser’s native API createElement, Append, insertBefore
     • Theoretically, the efficiency of wrapped code should be greater than or equal to that of unwrapped code. Why? Because the encapsulated code to consider a variety of cases fault tolerance, reference language encapsulation.