Detailed explanation of DOM DIFF algorithm in react application

Preface

For those of us who are engaged in front-end development, the two most popular front-end frameworks are undoubtedly React and Vue. I believe everyone is very familiar with these two frameworks. However, these two frameworks have all abandoned the use of traditional DOM technology and adopted the JS-based Virtual DOM technology, which can also be called virtual DOM. So, what exactly is Virtual DOM? What is the reason why both of the two popular frameworks use Virtual DOM? Next, let me, a front-end developer, explain to you the awesomeness of the DOM DIFF algorithm.

What is Virtual DOM?

As the name suggests, Virtual DOM is a virtual DOM. Its characteristic is to use Javascript to simulate the DOM structure and compare the changes of DOM in the JS layer. The specific operations are as follows:

// Ordinary HTML DOM structure <ul class="list">
   <li class="item">wjy</li>
   <li class="item">Yi Yang Qianxi</li>
</ul>

// Mapped virtual DOM
{
   tag:'ul',
   props:{
       class:'list'
   },
   children: [
       {
           tag:'li',
           props:{
               class:'item'
           },
           children: ['Yi Yang Qianxi']
       }
   ]
}

Some friends may be a little confused. Isn’t the ordinary HTML DOM structure bad? It is easy to understand and the code is more concise. Why do we need to use nested recursive virtual DOM? In fact, this is related to the fact that ordinary DOM consumes a lot of performance in the process of re-rendering. DOM operations seem simple, but in fact, the efficiency is quite low. This is because if it is in the real DOM that needs to be modified frequently, the Virtual DOM that looks more complicated and uses JS structure will be more efficient.

Reasons to use Virtual DOM

DOM rendering page operation process

• When the browser gets the corresponding HTML file from the server through the domain name, the browser will first build the DOM tree and CSSOM tree. Regarding the concept of tree, students who have studied data structures and algorithms may be impressed by the concept of tree nodes.
• In HTML DOM, everything is a node, and DOM is HTML viewed as a node tree, and each node has a corresponding hierarchical relationship. The DOM node tree corresponds to the tags in HTML one by one, forming the DOM tree
• HTML File

• HTML DOM Tree

Same. In a CSS document, all elements are nodes, corresponding one-to-one to the tags in HTML, forming the CSSOM tree as shown below:

warn! If JS-related content is encountered during the construction of the DOM tree, the construction of the DOM tree will stop immediately. This is because JS can operate on DOM nodes. In order to prevent JS from affecting the completed DOM, the browser will prevent the construction of the DOM tree to save resources.

As the DOM tree and CSSOM tree are continuously constructed, the rendering tree is also gradually formed. The browser will perform web page layout and drawing processes based on the constructed rendering tree, and continuously build web pages. The specific operation flow chart is as follows:

Generally speaking, for routine operations of page rendering, we usually operate DOM, modify and reset innerHTML to complete page rendering. Each time a DOM update operation is performed, the rendering process will be performed again, and this process includes redrawing and rearranging the page.

Advantages of Virtual DOM

However, for large-scale page projects or web pages with multiple tags and attributes, conventional DOM operations are too time-consuming. Each simple modification requires the redrawing and rearrangement of a large number of DOM nodes, which greatly reduces the efficiency of page rendering. Therefore, when front-end developers are at a loss in the face of DOM bottlenecks, Virtual DOM shows its great superiority as a lightweight JavaScript object and successfully wins the favor of front-end developers.

When the page is re-rendered, Virtual DOM performs DOM diff calculation and comparison twice and finds the difference. It only needs to modify the different parts of the DOM tree. It can also be understood that Virtual DOM is a middleware. First, JS is used to modify Virtual DOM. After comparing the differences, all changes are added to the real DOM of the page. Therefore, the biggest advantage of Virtual DOM is that it does not need to rebuild and create DOM after comparison like native DOM, because this is very performance-consuming and costly for the operation of large projects. It can be seen that no matter what the size of the web page is, abandoning traditional DOM and adopting Virtual DOM is undoubtedly a very efficient and excellent choice.

How to represent DOM with virtual DOM

First, create a new dom diff project in vscode, initialize the project, and install the corresponding components

Since it is a DOM tree, when converting HTML into a DOM tree, a recursive form is used. First, create the node, then set the attributes, and then set the child nodes.

<ul class="list">
    <li class="item">wjy</li>
    <li class="item">Yi Yang Qianxi</li>
</ul> 

// DOM tree expression conversion form let virtualDOM = createElement('ul', {
  class:'list',
}, [
  createElement('li',{
    class:'item'
  },['wjy']),
  createElement('li',{
    class:'item'
  },['Yi Yang Qianxi']),
])

Then, create a new element.js file to output it externally and complete the page rendering

// Construct a virtual DOM node through the Element constructor class Element {
    constructor(type,props,children){
        this.type = type;
        this.props = props;
        this.children =children;
    }
}
// 
const createElement = (type,props,children) => { 
  return new Element(type,props,children);
}

// Render the page and convert Virtual Dom into real DOM
const render = (domObj) => {  
    let el = document.createElement(domObj.type);
    for(let key in domObj.props){
        setAttr(el,key,domObj.props[key]);
    }
    domObj.children.forEach(child => {
        child = (child instanceof Element)
        ? render(child)
        : document.createTextNode(child);
        el.appendChild(child);

    })
    return el;
}

function setAttr(node,key,value){
    switch(key){
        case 'value':
            if(node.tagName.toLowerCase() === 'input' || 
            node.tagName.toLowerCase() === 'textarea'
            ){
                node.value = value;
            }else{
                node.setAttribute(key,value)
            }
            break;
            case 'style':
            // node.setAttribute('style',value)
            node.style.cssText = value;
            break;
            default:
                node.setAttribute(key,value)
            break;
    }
}

// Mount the real DOM to the specified root node const renderDOM = (el,target) => {
    target.appendChild(el);
}

//Export to the outside world
    createElement,
    render,
    renderDOM
}

Get the real DOM on the console

Page rendering successful! 😃

DOM DIFF algorithm

After the user changes the interactive page operation, the nodes on the virtual DOM tree will change, but the real nodes will not change at this time. In order to synchronize the changes with the real page, we will use the DOM DIFF algorithm to find the difference between the two trees, and then generate a difference patch object, and then apply the difference patch object to the real DOM node, thus completing the rendering and update of the page.

The time complexity of the traditional Diff algorithm reaches O(n^3). If the purpose of refreshing the entire page every time is to be achieved, this exponentially growing performance overhead cannot meet the performance requirements. Therefore, Facebook engineers optimized this and reduced the complexity of the Diff algorithm to O(n) by formulating a diff strategy.

Diff strategy

• There are very few cross-level operations on DOM nodes, so they can be ignored.
• Two components of the same class will produce similar tree structures, and two components of different classes will produce different tree structures.
• A group of child nodes at the same level, they can be distinguished by uuid
  

Diff granularity

Due to the different granularity of DIFF, the DIFF algorithm is executed in the following order:

• Tree DIFF
  
• Component DIFF
• Element DIFF
  

Patching

We compare the two virtual DOMs through depth-first traversal according to the diff strategy and the comparison algorithm in react diff. If there are differences, the operations corresponding to the index values ​​of the traversed nodes are stored, also known as patch objects.

Then the real DOM is traversed again in depth first, and the index in the patch object will correspond to the DOM, and we have completed the DOM update operation.

Conclusion In the Internet environment, refreshing interactive pages at any time is our routine operation when surfing the Internet. However, this simple operation is the result of multiple algorithm optimizations. The underlying principle of DOM DIFF is quite complicated. If you are interested, you can search for relevant literature by yourself. Because this article is just a superficial analysis, too many aspects will not be elaborated. If there are any errors or omissions in this article, you are welcome to correct them! Humbly accept all reasonable criticism! 😉

If this article helps you understand the DOM diff algorithm, I hope you can give me a thumbs up. I am a newbie in front-end development. Every thumbs up is my motivation to move forward. I will continue to update the blog of Nuggets.

The above is a detailed explanation of the DOM DIFF algorithm in react applications. For more information about the DOM DIFF algorithm in react applications, please pay attention to other related articles on 123WORDPRESS.COM!