This is the 24th day of my participation in the August More Text Challenge

📢 Hello everyone, I am Xiao Cheng, a prospective sophomore front-end enthusiast

📢 this article will try to explain the Diff algorithm

📢 May you be true to yourself and love life

preface

The DIff algorithm is an optimization algorithm used by React to improve rendering performance. It plays an important role in React and not only React, but also in Vue. There seems to be no difference between the diff algorithm. In the recent React learning, I learned the DIff algorithm. I felt that the content in the video was a little shallow and the diFF algorithm was not in-depth enough, so I wanted to have an in-depth understanding of the following DIFF algorithm. So IN the nuggets, Zhihu, CSDN and other platforms, I read a lot of blogs, they are very good, but unfortunately I can not understand, WWWW. So this article is just a little understanding of their own diff algorithm, there are any problems or mistakes, we must point out!

What is the virtual DOM?

Before we talk about diff algorithms, we need to understand the virtual DOM. It is a programming concept in which a virtual representation is held in memory. In React, the result of render execution is not a real DOM node, but a JavaScript object

The virtual DOM only preserves some basic properties of real DOM nodes, and the hierarchical relationship between nodes. It is like a layer of “cache” built between JavaScript and DOM.

<div class="hello">
    <span>hello world!</span>
</div>
Copy the code

The above code will be converted into a virtual DOM structure

{
    tag: "div",
    props: {
        class: "hello"
    },
    children: [{
        tag: "span",
        props: {},
        children: ["hello world!"]]}}Copy the code

There are three attributes required for a node: tag, props, and children

  • Tag specifies the element’s valueThe labelType, such as”li.div“
  • Props specifies attributes on the element, such asclass ，style, custom attributes
  • Children specifies whether the element has child nodes, passed in as an array

The JSX code we wrote in Render is a virtual DOM structure.

What is the Diff algorithm?

In fact, when I first learned React, many people probably heard that React is very efficient and performs well, which is actually due to the perfect combination of diff algorithm and Virturl DOM.

My naive self would have thought at first

React just introduced someone else’s diff algorithm. How good is it?

But when I looked through a lot of data, the one that was mentioned the most was a “traditional diff algorithm.”

The React optimization for the DIff algorithm is what we should learn

React optimised O(n) from O(n3n^3n3)

Rough execution process diagram

So how does React work?

Three strategies

To reduce the complexity to O(n), React optimized the algorithm based on these three policies

  1. The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored.
  2. Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree structures.
  3. For a set of child nodes at the same level, they can be distinguished by unique ids.

React optimizes tree Diff, Component Diff, and Element Diff for these three policies

Tree diff

The first thing you do is you compare the old and the new DOM trees, and by comparison you mean a hierarchical comparison. In addition, DOM nodes are rarely moved across hierarchies, so they are ignored. React uses updataDepth to control the hierarchy of the virtual DOM tree. Only nodes in the same layer are compared. In this figure, only DOM nodes in the same color box are compared. Such as:

When the node is found to disappear by comparison, the node and its child nodes will be completely deleted without further comparison. In this way, the comparison of the whole DOM tree can be completed only by traversing the tree once

There is another point of concern here: DOM nodes move across hierarchies

Why is this question raised? In the deletion principle above, we find that when a node does not exist, it will be deleted. If I just transpose it, will it also delete the whole node and its children?

In this picture, we need to do something like this, and you’d think it would just move like this

But in reality, that’s not the case. React simply changes the position of nodes at the same level. For nodes at different levels, only create and delete operations are required. When B is found to be missing, B is destroyed.

React does not recommend cross-level DOM node operations

component diff

At the component level, optimizations have also been made

  • If it is the same type of component, the virtual DOM tree is compared according to the original policy
  • If not, the component is denoted asdirty componentTo replace all child nodes under the entire component

Meanwhile, for components of the same type, there may be no change in their Virtual DOM. Knowing this can save a lot of time for diff operation. React therefore allows users to determine whether the component needs diff analysis via shouldComponentUpdate()

In general, if two components have similar structures but are identified as different types of components, they are not compared but simply removed

element diff

Element Diff is a strategy for all nodes in the same hierarchy. When nodes are at the same level, diff provides three node operations: insert, move, and delete

When we want to do the transformation shown in the figure, it is very difficult because in the process of comparing old and new nodes, we find that each node has to be deleted and recreated, but this is just a reorder, which is very unfriendly to performance. Hence the optimization strategy proposed in React:

Allows the addition of a unique value key to distinguish nodes

The introduction of key optimization strategy has made a dramatic change in performance

So what does key do?

When a key attribute is added to a node at the same level, the position changes. React Diff compares old and new nodes. If the same key is found, the nodes are moved instead of being deleted and created

So how exactly does key work?

First, React only allows nodes to move right

So for the transformation in the figure above, only A, C moves are made

Only the nodes that move need to be updated, and the nodes that do not move need not be updated

Why can’t index be the key?

In React, if the key is the same as the index, the last item in the array may be moved forward. If the key is the same as the deleted node, it will be treated as the same component. But the two components are different, which will cause trouble. For example, the serial number does not correspond to the text

So you have to make sure that the key is unique

advice

React already does a lot for us, but we need to pay attention to the rest for better performance

There are three strategies to note

Tree Diff recommends that when developing components, care be taken to keep the DOM structure stable

Component Diff suggests using shouldComponentUpdate() to reduce unwanted updates

Element Diff suggests reducing the last node move to the head, so that all previous nodes need to move

The resources

React Diff algorithm strategy and implementation

The React diff algorithm

React virtual DOM, Diff algorithm and Key mechanism

The diff algorithm is a bit more difficult to implement by hand, but we’ll talk about it after React

Thank you very much for reading, welcome to put forward your opinion, if you have any questions, please point out, thank you! 🎈