web front-end diff algorithm in depth a little?

A student asked: can you go into detail about the diff algorithm.

In detail, please read this article, and if you have any questions, please leave a comment to discuss.

Because the diff algorithm is a key core point in vue2.x, vue3.x, and react, understanding the diff algorithm helps you understand the nature of each framework.

When we talk about the diff algorithm, we have to talk about Virtual Dom, because the two are closely related.

For example:

Wait

Let's start with virtual Dom, which is a DOM implemented through JS emulation, and then the hard part is how to determine the difference between the old object and the new one.

Dom is a multinomial tree structure, so if you need to completely compare the differences between two trees, the algorithm has a time complexity of O(n ^ 3), which is hard to accept, especially if n is large, so the React team optimized the algorithm to achieve a complexity of O(n) to compare the differences.

The key to implementing O(n) complexity is to only compare nodes in the same tier, not across tiers, given that it's rare to move DOM elements across tiers in the real world.

The virtual DOM diff algorithm is divided into 2 steps:

In the actual diff algorithm comparison, there are 5 main rules for node comparison

Part of the source code /vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/ core/vdom/patch.js#L501 as follows:

In the reconcileChildren function's entries

The two bodies of diff are: oldFiber (current.child) and newChildren (nextChildren, the new ReactElement), which are two different data structures.

Some of the source code

Often manual optimization of dom will indeed be more efficient than virtual dom. There is no problem with manual optimization of simple dom structures, but when the page structure is very large and complex, manual optimization will take a lot of time and is not very maintainable, and it is not guaranteed that everyone will have the ability to optimize manually. Thus, the virtual dom solution was born.

virtual dom is a solution that "addresses the performance impact of too many operational domes".

virtual dom is often not the optimal operation, but it is universal, striking a balance between efficiency and maintainability.

What virutal dom means:

The diff for vue2.x is in the patch.js file, and the algorithm is derived from snabbdom, with O(n) complexity. Understanding the diff process allows us to use the framework more efficiently. react's diff is actually pretty much the same as vue's.

The diff for vue2.x is located in the patch.js file.

The big thing is that comparisons are only done at the same level, not across levels.

Before and after comparing: you might expect to move directly after

which is optimal.

But the actual diff operation is:

The diff algorithm is also used in vue, and it's important to understand how Vue works. With this question, we can get a good handle on where the diff algorithm is in the whole compilation process, what part of it, what operations it does, and then what is the output after using the diff algorithm?

Explanation:

The mount function gets the template and then goes to the compileToFunctions function.

The compileToFunctions function compiles the template into a render function. First, it reads the cache, and if there is no cache, it calls the compile method to get the render function as a string, and then generates the render function as a new Function.

The compile function compiles the template into a string form of the render function. We'll focus on render later

Once we're done generating the render method, we go to mount to do the DOM update. The core logic of this method is as follows:

The compile mentioned above compiles the template into a string for the render function. The core code is as follows:

The compile function has three main steps:

Outputs a function containing

The parse function: its main function is to parse the template string into an AST (Abstract Syntax Tree). The parse function converts the structures in the template (directives, attributes, tags) into ASTs and stores them in an ASTElement, which is then parsed to produce an AST.

The optimize function (src/compiler/optomizer.js): The main function is to convert the template string into an AST (abstract syntax tree). The main function is to tag static nodes. This is done later in the patch process by comparing the old and new VNode tree structures. Nodes marked as static are simply ignored in the diff algorithm and are not compared in detail.

The generate function (src/compiler/codegen/index.js): its main function is to generate a string for the render function based on the AST structure.

The genElement function (src/compiler/codgen/index.js) calls different methods based on the properties of the AST to generate a string to return.

In summary:

The three core steps in the compile function are introduced.

The patch function is the diff function that compares the old and the new VNode, which is designed to optimize the dom, and to minimize the manipulation of the dom through algorithms. The diff algorithm is derived from snabbdom, which is the core of the VDOM idea. snabbdom's algorithm is optimized for the goal of having fewer nodes added or removed across levels of DOM manipulation, and it will only do this at the same level, not across levels of comparison.

In summary:

This optimization, combined with the Diff algorithm, improves performance by determining the type of a VNode at creation and using bitwise operations to determine the type of a VNode during mount/patch.

Take a look at the vue3.x source code: /vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js

A comparison of the oldFiber and the new The comparison of the oldFiber with the new ReactElement node generates new fiber nodes, tagged with an effectTag, which are attached to the workInProgress tree as new WIP nodes. The structure of the tree is thus defined bit by bit, and the new workInProgress node is almost finalized. After diff, the beginWork node of the workInProgress node is complete, and the completeWork phase follows.

snabbdom algorithm: /snabbdom/snabbdom

Position: a virtual DOM library focused on simplicity, modularity, power, and performance.

The type of Vnode defined in snabbdom (/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/vnode.ts#L12)

The address of the init function:

The address of the init function.

/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/init.ts#L63

The init() function takes an array of modules and an optional domApi object as arguments. It returns a function, the patch() function.

The interface to the domApi object contains many methods for DOM manipulation.

Source:

/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/init.ts#L367

Source:

/snabbdom/ snabbdom/blob/blob/patch() function. snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/h.ts#L33

The h() function takes a variety of arguments, one of which must be the sel parameter, and serves to mount the contents of the node into that container and return a new VNode.

Instead of the full snabbdom algorithm, in vue2.x there are some modifications and optimizations based on the vue scenario, mainly in the judging key and diff sections.

1. In snabbdom, the key and sel are used to determine if the node is the same, so in vue, some additional judgments are added to satisfy the key equivalence and at the same time will determine if the tag name is the same, if it is a comment node, if it is an asynchronous node, or if it is the same type when it is an input, etc.

/vue2.x is not a full snabbdom algorithm.

/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js#L35

2. diff, patchVnode is a function that compares the changes to the template, which may use diff or update directly. use diff or update directly.

/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js#L404