A, the opening

Let’s start with a simple and common example:

<ul id='list'>
  <li class='item'>1</li>
  <li class='item'>2</li>
  <li class='item'>3</li>
</ul>
Copy the code

React list (1, 2, 3, 4, 5, 6, 7) Method 1: removeChild() clears the list and appendChild() adds 4 elements (nodeValue/textContent) Use innerHtml to override the entire list directly

The above three methods all use native DOM apis and can achieve results, but there are performance differences. The reasons can vary, depending on the element type, the length of the list, and even the browser version (the evil Internet Explorer). Therefore, different DOM manipulation methods should be used flexibly according to the current environment, but this undoubtedly increases the difficulty of development and prevents engineers from focusing on the current business.

React is much easier. We don’t have to worry about DOM manipulation, just store the data in state and map generates the JSX code in the render function. React decides how to manipulate the DOM, thanks to the virtual DOM and diff algorithms.

What is the virtual DOM?

The virtual DOM is a tree structure that uses javascript objects to represent the real DOM. In the real DOM, a normal div would be complicated to print:

const tree = {
  tagName: 'ul'.// Node label name
  props: {       // A DOM property that uses an object to store key-value pairs
    id: 'list'
  },
  children: [    // Children of this node
    {tagName: 'li'.props: {class: 'item'}, children: ['1'] {},tagName: 'li'.props: {class: 'item'}, children: ['2'] {},tagName: 'li'.props: {class: 'item'}, children: ['3']},]}Copy the code

The virtual DOM retains only some of the basic properties of real DOM nodes, and the hierarchical relationship between nodes. It acts as a layer of “cache” between javascript and DOM, similar to CPU and hard disk: hard disk reads and writes are slow compared to cheap memory.

What is Diff algorithm?

React requires two virtual DOM trees to be maintained at the same time: one representing the current DOM structure and the other generated when React state changes are about to be re-rendered. React compares the differences between the two trees to determine if and how the DOM structure needs to be modified. This algorithm is called the Diff algorithm.

There are some general solutions to this algorithmic problem, which generate the minimum operand to convert one tree to another. However, even in the most cutting-edge algorithms, the complexity of the algorithm is O(n 3), where n is the number of elements in the tree. If the algorithm was used in React, the amount of computation required to show 1000 elements would be on the order of a billion. The cost is simply too high. React proposed a set of O(n) heuristic algorithm based on the following two assumptions:

  1. Two different types of elements produce different trees;
  2. Developers can usekey propTo indicate which child elements are stable in different renders;

Some people say that virtual DOM is fast, and this is also in comparison. The maintenance of the virtual DOM tree and the computation of the Diff algorithm simplify DOM operations and save a lot of time compared to MVVM changing the mode of the entire DOM tree. However, it is still faster to manipulate the DOM directly compared to the native JS development model, because the developer knows exactly what part of the DOM structure should be changed (provided the developer understands the most basic DOM optimization methods).

Fourth, the specific process of Diff algorithm

Diff algorithm will perform depth-first traversal of the old and new trees to avoid complete comparison between the two trees, so the algorithm complexity can reach O(n). Then generate a unique flag for each node:

During the traversal, the old and new trees are compared each time a node is traversed, and only elements of the same level are compared:

That is, only the parts of the graph connected by dotted lines are compared and the differences are recorded. The types of possible differences are as follows:

1. Different types of elements

For example, when an element changes from to , from

to

, or from


2. Elements of the same type

<div className="before" title="stuff" />

<div className="after" title="stuff" />
Copy the code

When comparing two elements of the same type, React preserves the current DOM node and child nodes and only compares and updates the changed attributes. By comparing the two elements, React knows that it only needs to change the className attribute on the DOM element. Namely, removeAttribute() -> setAttribute() or setAttribute().

React does something special for style changes:

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} / >Copy the code

By comparing the two elements, React knows that it only needs to change the color style on the DOM element, not the fontWeight.

If is the React component, when a component updates, component instance remains the same, and update the component state, call the instance componentWillReceiveProps () and componentWillUpdate () method. Next, the render() method is called, and the diff algorithm recurses over the previous result as well as the new one.

3. Text nodes

<div>text 1</div>
<div>text 2</div>
Copy the code

React modifies the nodeValue/textContent when the text node is changed.

4. Move, delete, or add a child node

By default, React iterates through lists of both child elements while recursively iterating through the child elements of a DOM node. When a difference occurs, a mutation is generated.

When adding an element at the end of the child element list, the change overhead is lower. Such as:

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>
Copy the code

By comparison, there is no difference between the first two elements, just insert a

  • third

    • at the end.

    If implemented simply, inserting at the head of a list can have a performance impact, such as:

    <ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>
Copy the code

    According to the algorithm rules mentioned above,

  • Duke

    • and

  • Villanova

    • cannot be retained and are regarded as different parts, thus the change cost will be high.

    Five, the Keys

    To address these issues, React supports the key attribute. When a child element has a key, React uses the key to match the child element of the original tree with the child element of the latest tree. The following example makes a previously inefficient conversion efficient after adding a key:

    <ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>
Copy the code

    The Diff algorithm learns by comparison that the element with key ‘2014’ is new, and the element with key ‘2015’ and ‘2016’ is just moved, so insertBefore() can be called to insert the node.

    Key generation notes:

    • keyYou should be unique in a list, but you don’t need to be globally unique.
    • keyShould have stability, a node in the determinationkeyIt should not be changed after thatkey(Unless you want it re-rendered). unstablekey(as inrender()Through theMath.random()Generated) causes many component instances and DOM nodes to be unnecessarily recreated, which can lead to performance degradation and loss of state in child components.
    • You can use the subscript of an element in an array askey. This strategy works well when elements are not reordered, but diff slows down once the order changes.

    Component state may encounter some problems when subscription-based components are reordered. Because component instances decide whether to update and reuse based on their key, if the key is a subscript, the order in which changes are made changes the current key, causing states of uncontrolled components (such as input fields) to tamper with each other and change unpredictably.

    Six, summarized

    1. React and Vue both implement virtual DOM and DIff algorithms to encapsulate the PART of DOM manipulation, allowing developers to focus on business implementation and improve DOM performance as much as possible while ensuring development efficiency.
    2. keyThe use of array subscripts is performance-dependentkey, but in the form of id, or array subscript +id/name.

    Reference article:

    In-depth analysis: How to implement a Virtual DOM algorithm

    Coordination – the React. Js