The topic
React has greatly improved the efficiency of our page builds by introducing the concept of the Virtual DOM, which greatly avoids invalid DOM manipulation. But how effectively you compare the old and new Virtual DOM to find the real DOM changes also determines page performance. React uses its special diff algorithm to solve this problem. The combination of Virtual DOM and React DIff greatly ensures React performance and has a good reputation in the industry. React didn’t create the Diff algorithm. React was just an optimization of the DIff algorithm. However, the optimization brought a huge performance improvement to React, which made people admire the wisdom of the creators of React. Let’s explore the React diff algorithm.
Traditional DIff algorithm
At the beginning of the article, we mentioned that the React DIff algorithm brought great performance improvement to React, while the previous React DIff algorithm was optimized on the traditional DIff algorithm. Let’s first look at what a traditional diff algorithm looks like.
The traditional DIFF algorithm compares nodes in turn through cyclic recursion, which is inefficient and achieves O(n^3) in algorithm complexity, where N is the total number of nodes in the tree. Specifically how to calculate it, you can check an answer on Zhihu.
React diff goes from O(n^3) to O(n). How do I calculate O(n^3) and O(n)?
How scary is O(n^3)? This means that if you want to show 1000 nodes, you have to perform billions of comparisons in turn, an exponential performance cost that is too high for a front-end rendering scene. React’s diff algorithm goes from O(n^3) to O(n). How big is the improvement from O(n^3) to O(n)? Let’s just look at a picture.
As you can see from the graph above, the improvements made by the React Diff algorithm are enormous. Let’s look at another picture:
The React principle of the diff
As mentioned above, the time complexity of the traditional DIFF algorithm is O(n^3), where N is the total number of nodes in the tree. With the increase of n, the time consumed by diFF will show explosive growth. React uses its special diff algorithm to jump from O(n^3) to O(n). It does this by using three deceptically simple diff strategies:
- The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored.
- Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree structures.
- For a set of child nodes at the same level, they can be distinguished by unique ids.
On the basis of the above three strategies, React optimizes the corresponding Tree Diff, Component Diff, and Element Diff algorithms respectively, greatly improving the efficiency of DIff.
tree diff
Based on strategy 1, React optimizes the algorithm of trees in a simple and straightforward way, that is, the trees are compared at different levels. Two trees will only compare nodes at the same level.
Since DOM node movement across hierarchies is negligible, React only compares DOM nodes of the same hierarchy, that is, all children of the same parent node. When a node is found to no longer exist, the node and its children are removed completely and are not used for further comparison. This allows you to compare the entire DOM tree with only one walk through the tree.
The premise of Strategy 1 is that there are very few trans-hierarchical operations of DOM nodes in the Web UI, but it does not deny the existence of trans-hierarchical operations of DOM nodes. Then, how does React deal with such operations?
It can be seen that when A node is moved across the hierarchy, the imaginary move operation does not occur, but the whole tree with A as the root node is recreated. This is an operation that affects React performance, so it is not recommended to operate across DOM nodes.
When developing components, maintaining a stable DOM structure can help improve performance. For example, you can hide or show nodes through CSS without actually removing or adding DOM nodes.
component diff
React builds applications based on components and uses a concise and efficient strategy for comparing components.
- If it is a component of the same type, continue to compare the Virtual DOM tree using the same policy.
- If not, the component is judged to be a dirty Component and all child nodes under the entire component are replaced.
- Knowing that it is possible for components of the same type to have no change in their Virtual DOM can save a lot of diff time. Therefore, React allows the user to use shouldComponentUpdate() to determine if the component needs diff, but shouldComponentUpdate fails if the forceUpdate method is called.
Let’s take a look at the following example:
element diff
When nodes are at the same level, diff provides three node operations: INSERT_MARKUP, MOVE_EXISTING, and REMOVE_NODE.
- INSERT_MARKUP: The new component type is not in the old collection; that is, the new node needs to be inserted.
- MOVE_EXISTING: old collection of new component types, and the element is updatable type, generateComponentChildren has called receiveComponent, this kind of circumstance prevChild = nextChild, You need to move it around, and you can reuse the old DOM node.
- REMOVE_NODE: An old component type that exists in the new collection but cannot be reused or updated directly due to its different elements. If the old component is not in the new collection, it needs to be deleted.
The old set contains nodes A, B, C and D, while the updated new set contains nodes B, A, D and C. At this time, the new and old sets are diff differentiated comparison, and B! =A, create and insert B into new set, delete old set A; Similarly, create and insert A, D, and C, and delete B, C, and D.
We found that these nodes were all the same with only their positions changed, but complicated and inefficient deletion and creation operations needed to be carried out. In fact, it was only necessary to move the positions of these nodes. React proposes an optimization strategy to address this problem: It allows developers to add unique keys to subnodes of the same hierarchy. Although it is only a small change, the performance has undergone a dramatic change! Let’s take a look at how react Diff works when this strategy is applied.
Can be accurately found the old and new by key nodes in the collection are the same, so the need for the node to delete and create, only need to move the location of the nodes in the old collection, update for the new collection of node position, at this point the React the diff results as follows: B, D, don’t do any operation, A and C for mobile operation.
The specific process is shown in a table:
| index | node | oldIndex | maxIndex | operation |
|---|---|---|---|---|
| 0 | B | 1 | 0 | OldIndex (1)>maxIndex(0),maxIndex=oldIndex,maxIndex becomes 1 |
| 1 | A | 0 | 1 | OldIndex (0)<maxIndex(1), node A moves to index(1) |
| 2 | D | 3 | 1 | OldIndex (3)>maxIndex(1),maxIndex=oldIndex,maxIndex becomes 3 |
| 3 | C | 2 | 3 | OldIndex (2)<maxIndex(3), node C moves to the position of index(3) |
- Index: Traversal index of the new collection.
- OldIndex: Index of the current node in the old collection.
- MaxIndex: The maximum subscript value of the node visited by the new collection in the old collection.
Only oldIndex and maxIndex are compared in the action column:
- When oldIndex>maxIndex, the value of oldIndex is assigned to maxIndex
- When oldIndex=maxIndex, no operation is performed
- When oldIndex
The above example only shows that the nodes in the old and new collections are the same nodes. If the new collection has new nodes and the old collection has nodes that need to be deleted, how does the diff compare and contrast?
| index | node | oldIndex | maxIndex | operation |
|---|---|---|---|---|
| 0 | B | 1 | 0 | OldIndex (1)>maxIndex(0), maxIndex=oldIndex, maxIndex becomes 1 |
| 1 | E | – | 1 | OldIndex does not exist, add E to index(1) |
| 2 | C | 2 | 1 | OldIndex (2)>maxIndex(1),maxIndex=oldIndex,maxIndex becomes 2 |
| 3 | A | 0 | 2 | OldIndex (0)<maxIndex(2), node A moves to index(3) |
Note: At last, the old set needs to be iterated to find out the nodes that are not in the new set. At this time, such node D is found, so node D is deleted and the diff operation is completed.
In the same operation column, only oldIndex and maxIndex are compared, but oldIndex may not exist:
- OldIndex exist
- When oldIndex>maxIndex, the value of oldIndex is assigned to maxIndex
- When oldIndex=maxIndex, no operation is performed
- When oldIndex
- OldIndex does not exist
- Add the current node to the index position
- Add the current node to the index position
Of course, this diff is not perfect. Let’s take a look at this situation:
During development, minimize operations like moving the last node to the head of the list. When the number of nodes is too large or update operations are too frequent, React rendering performance will be affected to some extent.
React can accurately determine whether a node exists in a new set due to the presence of a key, which greatly improves diff efficiency. When rendering a list, react will warn the developer to add a key if the list does not add a key. But does it have to be better with a key than without it? Let’s look at another example:
Now I have a set [1,2,3,4,5] rendered as follows: < div > 1 < / div > < div > 2 < / div > < div > 3 < / div > < div > 4 < / div > < div > 5 < / div > -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- now we're going to disrupt this collection order into,3,2,5,4 [1]. 1. Add key <div key='1'>1</div> <div key='1'>1</div>
<div key='2'>2</div> <div key='3'>3</div>
<div key='3'>3</div> ========> <div key='2'>2</div>
<div key='4'>4</div> <div key='5'>5</div>
<div key='5'>5</div> <div key='4'>4</div> action: move node 2 to subscript 2 and node 4 to subscript 4. 2. Do not add key < div > 1 < / div > < div > 1 < / div > < div > 2 < / div > < div > 3 < / div > < div > 3 < / div > = = = = = = = = > < div > 2 < / div > < div > 4 < / div > < div > 5 < / div > < div > 5 < / div > < div > 4 < / div > operation: modify the first to fifth nodes the innerText -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- if we are to add or delete operation to the collection,3,2,5,6 [1]. 1. Add key <div key='1'>1</div> <div key='1'>1</div>
<div key='2'>2</div> <div key='3'>3</div>
<div key='3'>3</div> ========> <div key='2'>2</div>
<div key='4'>4</div> <div key='5'>5</div>
<div key='5'>5</div> <div key='6'>6</div> Operation: move node 2 to subscript 2, add node 6 to subscript 4, delete node 4. 2. Do not add key < div > 1 < / div > < div > 1 < / div > < div > 2 < / div > < div > 3 < / div > < div > 3 < / div > = = = = = = = = > < div > 2 < / div > < div > 4 < / div > < div > 5 < / div > < div > 5 < / div > < div > 6 < / div > operation: modify the first to fifth nodes the innerText -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- through the two example above we find that: Because dom node movement is expensive, performance is better without a key than with a key.Copy the codeThrough the above example, we find that although adding key improves diff efficiency, it does not necessarily improve page performance. So let’s take note of this:
For simple list page rendering, performance is better without keys than with keys
Based on the above situation, we finally summarize the function of key:
- Determine exactly whether the current node is in the old collection
- Greatly reduce the number of traversals
The application practice
Example code address: github.com/ruichengpin…
The specified area of the page is refreshed
import React from 'react';
import {connect} from 'react-redux';
let oldAuthType = ' '; @connect(state=>state.user) class Page1 extends React.PureComponent{state={loading:true
}
loadMainDataThis.setstate ({loading:true
});
const timer = setTimeout(()=>{
this.setState({
loading:false}); clearTimeout(timer); }, 2000); }componentDidUpdate(){ const {authType} = this.props; // Determine whether the current user's identity has changedif(authType! ==oldAuthType){// Store new user id oldAuthType=authType; // Reload data this.loadmainData (); }}componentDidMount(){
oldAuthType=this.props.authType;
this.loadMainData();
}
render(){
const {loading} = this.state;
return(<h2>{' page 1${loading? 'Loading... ':' load done '}`}</h2>
)
}
}
export default Page1;
Copy the codeIt seemed like we could accomplish this by just adding a single piece of code, but when we had dozens of pages, this approach became too limited. Is there a good way to implement this requirement? React Diff is a simple way to implement react Diff. For this requirement, you actually want the current component to be destroyed and rebuilt. How do you get it destroyed and rebuilt? From the summary above I found two situations where you can destroy and rebuild components.
- When the component type changes
- When the key changes then we’re going to combine these two characteristics and do it in two ways.
The first is to introduce a loading component. If loading is set to true, the loading component will be displayed. The identity switch is complete, loading changes to false, and children is displayed.
<div className="g-main">{loading? <Loading/>:children}</div>Copy the codeSecond: add a key value in the refresh area, the user identity changes, the key value will change.
<div className="g-main" key={authType}>{children}</div>
Copy the codeIn terms of the choice between the first and the second, I suggest the following:
If you need to request a server, use the first one, because the requesting server will have a certain waiting time. Adding a loading component can make users feel and experience better. If you don’t need to request the server, choose the second option because it is simpler and more practical.
Easier to listen for props changes
import React from 'react';
import {Card} from 'antd';
import Filter from './components/filter';
import Teacher from './components/teacher';
export default class Demo2 extends React.PureComponent{
state={
filters:{
name:undefined,
height:undefined,
age:undefined
}
}
handleFilterChange=(filters)=>{
this.setState({
filters
});
}
render(){
const {filters} = this.state;
return<Card> {/* Filter */} <Filter onChange={this.handleFilterChange}/> {/* query list */} <Teacher filters={filters}/> </Card>}}Copy the codeNow we are facing the problem of how to listen for changes in the filters in the component Teacher. Since the filters are a reference type, listening for changes becomes a bit complicated. Fortunately, LoDash provides a tool method to compare two objects, which makes it easy. But if you add additional props to Teacher later, when you need to listen for changes in multiple props, your code becomes more difficult to maintain. In view of this problem, we can still achieve the key value, when each search, generate a key, then the Teacher component will be reloaded. The code is as follows:
import React from 'react';
import {Card} from 'antd';
import Filter from './components/filter';
import Teacher from './components/teacher';
export default class Demo2 extends React.PureComponent{
state={
filters:{
name:undefined,
height:undefined,
age:undefined
},
tableKey:this.createTableKey()
}
createTableKey() {returnMath.random().toString(36).substring(7); } handleFilterChange = (filters) = > {enclosing setState ({filters, / / to regenerate tableKey tableKey: enclosing createTableKey ()}); }render(){
const {filters,tableKey} = this.state;
return<Card> {/* Filter */} <Filter onChange={this.handleFilterChange}/> {/* query list */} <Teacher key={tableKey} filters={filters}/> </Card> } }Copy the codeEven if we add new props to Teacher in the later stage, there is no problem, just splicing key:
<Teacher key={`${tableKey}-${prop1}-${prop2}`} filters={filters} prop1={prop1} prop2={prop2}/>
Copy the codeThe Link in the React-router is faulty. Procedure
import React from 'react';
import {Card,Spin,Divider,Row,Col} from 'antd';
import {Link} from 'react-router-dom';
const bookList = [{
bookId:'1',
bookName:Romance of The Three Kingdoms,
author:'Luo Guanzhong'
},{
bookId:'2',
bookName:'Water Margin',
author:'Nai am'
}]
export default class Demo3 extends React.PureComponent{
state={
bookList:[],
bookId:' ',
loading:true
}
loadBookList(bookId){
this.setState({
loading:true
});
const timer = setTimeout(()=>{
this.setState({
loading:false, bookId, bookList }); clearTimeout(timer); }, 2000); }componentDidMount(){
const {match} = this.props;
const {params} = match;
const {bookId} = params;
this.loadBookList(bookId);
}
render(){
const {bookList,bookId,loading} = this.state;
const selectedBook = bookList.find((book)=>book.bookId===bookId);
return <Card>
<Spin spinning={loading}>
{
selectedBook&&(<div>
<img width="120" src={`/static/images/book_cover_${bookId}.jpeg '}/> <h4> title: {selectedBook?The '-'}</h4> <div> selectedBook.author:The '-'}</div>
</div>)
}
<Divider orientation="left"> Link book </Divider> <Row> {booklist.filter ((book)=> book.bookid! ==bookId).map((book)=>{ const {bookId,bookName} = book;return <Col span={6}>
<img width="120" src={`/static/images/book_cover_${bookId}.jpeg`}/>
<h4><Link to={`/demo3/${bookId}`}>{bookName}</Link></h4>
</Col>
})
}
</Row>
</Spin>
</Card>
}
}
Copy the codeBy demonstrating the GIF, we can see that the address bar has changed, but not as we expected to go through the process of requesting data for componentDidMount, indicating that our component has not been destroyed and rebuilt. To fix this you can listen for changes at componentDidUpdate:
componentDidUpdate(){
const {match} = this.props;
const {params} = match;
const {bookId} = params;
if(bookId!==this.state.bookId){
this.loadBookList(bookId);
}
}
Copy the codeAs mentioned earlier, if multiple props need to be monitored in the later stage, it will be troublesome to maintain in the later stage. On the home page, we can wrap the page as a BookDetail component, wrap another layer around it, and add a key to the BookDetail as follows:
import React from 'react';
import BookDetail from './bookDetail';
export default class Demo3 extends React.PureComponent{
render(){
const {match} = this.props;
const {params} = match;
const {bookId} = params;
return <BookDetail key={bookId} bookId={bookId}/>
}
}
Copy the codeThe advantage of this is that our code structure is clearer, and it is easier to expand new functions later.
Conclusion:
- React is efficient thanks to its Virtual DOM+React Diff system. The DIff algorithm isn’t original to React. React is just an optimization of the traditional DIff algorithm. But because of its optimization, the time complexity of the DIff algorithm is suddenly reduced from O(n^3) to O(n).
- React Diff’s three strategies:
- The movement of DOM nodes across hierarchies in the Web UI is minimal and can be ignored.
- Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree structures.
- For a set of child nodes at the same level, they can be distinguished by unique ids.
- When developing components, maintaining a stable DOM structure can help improve performance.
- During development, minimize operations like moving the last node to the head of the list.
- Keys are there to improve diff efficiency, but not necessarily performance. Keep in mind that simple list rendering works better without keys than with keys.
- Know how to use react Diff features to solve a number of problems in our actual development.