What is the Stack Reconciler process in React?

Nowadays the React 16 or 17 is the React the industry recognized “crispy Fried chicken”, compared with the React lackluster 15 seems to have had a washed-up stopping phase.

It’s heartbreaking that fewer and fewer people are willing to learn React 15 on their own. After all, a great man once said, “By looking at history as a mirror, one can see what happens and what happens.” Another great man once said that “learning requires a complete and necessary context” — if we don’t know how React 15 works, we won’t be able to grasp its limitations; Without a firm grasp of React 15’s limitations, we can’t fundamentally understand the design motivations behind the React 16 overhaul. Therefore, one must learn history well before following the trend of The Times.

In this section, you’ll take the first and most important step in learning the history of React 15: Understand the stack and stack algorithm.

Reconciliation process and Diff algorithm

Let’s take a look at the exact direction of the terms “harmonization” and “Diff.”

• The React website explains the concept of the virtual DOM as follows:

The Virtual DOM is a programming concept. In this concept, the UI is kept in memory in an idealized, or “virtual,” representation, synchronized with the “real” DOM through libraries such as ReactDOM. This process is called harmonization.

The main point of this article is to synchronize the virtual DOM with the “real” DOM through libraries such as ReactDOM, a process called harmonization.

In short: reconciliation refers to the process of mapping the virtual DOM to the real DOM. So, strictly speaking, the harmonic process cannot be equated with Diff. Reconciliation is the process of conformity, whereas Diff is the process of finding difference. It is only one step in the process of conformity.

This is illustrated by the React source code structure, which breaks it down into Core, Renderer, and Reconciler from large blocks. Including the Reconciler (harmonic) source is located in the SRC/renderers/Shared/stack/Reconciler this path, is the work done by a series of harmonic, including component mounted, unloading, update process, the update process involves calls to Diff algorithm.

So reconcile! But the general perception today is that when you talk about reconciliation, you’re really talking about Diff.

Such a recognition is reasonable, because Diff is indeed the most representative part of the reconciliation process: the reconciliation process can be divided into “stack reconciliation” represented by React 15 and “Fiber reconciliation” since React 16 according to the different implementation forms of Diff. During the actual interview, when the interviewer asks questions about the Reconciliation, it’s mostly to find out how well the candidate knows Diff. Thus, in this chapter, “stack harmonization” refers to the React 15 Diff algorithm.

2. Design idea of Diff strategy

Before explaining the specific logic of Diff algorithm, we should first grasp the design idea of Diff as a whole.

As mentioned earlier, the Diff algorithm is a process of “finding different”. In computer science, to find the difference between two tree structures, the traditional calculation method is to compare the tree nodes one by one through cyclic recursion, which is O (n^3) algorithm complexity. Although the algorithm itself has been continuously optimized by generations of programmers, O (n^3) is still a performance disaster for browsers with limited computing power.

Specifically, if there are 100 nodes on a page (which is not uncommon in real development), 100^3 works out to a hundred thousand operations, and that’s just the cost of one Diff; On a larger scale, maintaining 1000 nodes, the number of operations will jump to the order of a billion.

If you do algorithms a lot, you know that the ideal time complexity in OJ is usually O(1) or O(n). As complexity climbs to O(n^2), we instinctively look for performance optimizations, not to mention O(n^3), which we all hate! Therefore, the React team also summarized the following two rules based on some design-level derivations to establish the general premise for converting O (n^3) complexity to O (n) complexity:

• If two components are of the same type, they will have the same DOM tree structure;

• A set of child nodes at the same level can be uniquely identified by a key to maintain the stability of each node in different rendering processes.

• In addition to these two “hard and fast” rules, there is another rule that is closely related to practice, which provides inspiration for efficient Diff implementation of React: “There are not many cross-level operations between DOM nodes. Same-level operations are the mainstream.”

Here’s how React uses these three rules to create a high-performance Diff.

3, Grasp the three “points”, diagram the Diff logic

There have been many versions of the splitting and interpretation of Diff logic in the community, and different versions have different interpretation methods and perspectives. But at the end of the day, there are really three important points to grasp:

• The key point of Diff algorithm performance breakthrough lies in “hierarchical comparison”;

• Nodes of the same type are necessary to continue Diff;

• The key attribute is set to help us reuse as many nodes as possible within the same hierarchy.

Each of these three points echoes the three rules above, so let’s look at them one by one.

(1). The decisive idea for changing the time complexity level: hierarchical comparison

In combination with the rule that “there are not many cross-level operations between DOM nodes, and same-level operations are the mainstream”, the React Diff process directly abandons cross-level node comparison and only compares nodes at the same level, as shown in the figure below. In this way, the comparison of the entire tree can be done in a single walk from top to bottom, which is one of the most important designs for reducing the order of complexity.

It is important to note that although stack harmonization optimizes the traditional tree comparison algorithm for hierarchical comparison, the whole algorithm still operates in a recursive form, and hierarchical recursion is also recursive.

What if A cross-hierarchy node operation (such as moving A subtree with node B as the root from below node A to below node C, as shown in the figure below) actually happens? Unfortunately, as a “secondary contradiction”, React cannot determine the behavior of “move” in this case. It can only assume mechanically that the component moved out of the subtree layer disappears and the corresponding subtree needs to be destroyed. The layer that moves into the subtree adds a new component and needs to create a new subtree for it.

React also advises developers not to operate across hierarchies and to keep the DOM structure as stable as possible.

(2) “one size fits all” strategy to reduce recursion: consistency of types determines the necessity of recursion

Combined with the rule that “if two components belong to the same type, they will have the same DOM tree structure”, we cannot directly deduce that “different types of components have different DOM structure”, but in most cases, this conclusion is valid. After all, the probability of encountering two components with exactly the same DOM structure but not the same type in real development is really low.

According to the basic principle of “principal contradiction”, React believes that only components of the same type need to be further compared. If the two components participating in Diff are of different types, the comparison is simply abandoned and the old node is replaced in place, as shown in the figure below. React tries to Diff deeper into the DOM tree (or subtree) of the component only after confirming that the component type is the same.

In this way, redundant recursive operations in the Diff process can be greatly reduced.

(3). Use the React key attribute to remember nodes

Above, we mentioned that the key attribute can help maintain the stability of nodes. Where does this conclusion come from? First, React defines the key property:

Key is used to help React identify what has been changed, added, or removed. The key needs to be written inside the element rendered in an array and given a stable value. Stability is important here, because React triggers a rerendering of the UI if the key changes. This is a very useful feature.

It tries to solve the reuse problem of nodes at the same level. Before we start our analysis, let’s consider a situation, as shown in the figure below, based on our understanding of the Diff process so far:

In the figure, component A inserts A new node (C) between two child nodes (B and D) while keeping the type and other attributes unchanged. According to the known Diff principle, the Diff process between two trees should look like this:

• Firstly, the nodes located at the first layer are compared, and the node types of the two trees are found to be the same (both are A), so further Diff is performed.

• The first node to be compared is B. After comparison, it is found that both nodes in this position of the two trees are B. Then it continues to diff.

• The second position to be compared is D. After comparing D and C, the type before and after is found to be inconsistent, so D is directly deleted to reconstruct C.

• The third position to accept the comparison is E. After comparing E and D, the type before and after is found to be inconsistent, so E is directly deleted to rebuild D.

• The last one to accept the comparison is the E node in tree 2, which is empty in tree 1, which means that E in tree 2 is a new node, so a new E is added.

Here’s the weird thing: C, D, and E are all directly usable. It takes a long time to delete and rebuild things that can be done by adding a node, which is too complicated and unnecessary. And this operation is not quite the same as moving nodes across hierarchies, which is a low-frequency operation and can be almost completely avoided with reasonable best practices; However, the form of inserting nodes shown in the diagram is a very high frequency operation, which cannot be avoided. Frequent addition and removal of nodes will drag down performance, and this is where you need to reuse nodes using the key attribute.

The form of the key attribute is familiar to everyone. When a node is dynamically generated from an array, it is common to add a key attribute to each node (here is a code example) :

const todoItems = todos.map((todo) =>
  <li key={todo.id}>
    {todo.text}
  </li>
)
Copy the code

If you forget to write a key, React does not generate an error, but the console flag is red. It will give you a warning: “Please complete the key attribute for list elements.” This warning is common to reflect the importance of keys. In fact, when we don’t set the key, the Diff process is just as brutal as the one described above. However, once a key is installed, it acts as a token that helps React “remember” a node, allowing it to be traced in subsequent updates. For example, in the virtual DOM tree, if each child node at level 2 is given a key value, as shown in the following figure:

When C is inserted between B and D, React does not assume that C, D, and E slots need to be rebuilt — it identifies the ID of each node. Realize that D and E have not changed (D’s ID is still 1, E’s ID is still 2), but have simply been reordered. React can then easily reuse it to “trace” old nodes, move D and E to new locations, and complete the insertion of C. As a result, the operation cost of elements at the same level is greatly reduced.

[Note] : As a unique identifier of a node, ensure that the key is unique and stable before using it.

4, summarize

At this point, the core logic of Diff algorithm under stack harmonic mechanism has been learned. Once emphasized in front, principle! This is especially true when it comes to the Diff algorithm. The Diff algorithm has a long link to the source code. React 15 is a big version that can take days to read. But if really the logical points in the source code for extraction, digestion of them may be no more than a cup of tea time.

For React 15 Diff processes, it’s enough to understand the logic layer and grasp the “tree recursion” feature. React 16 is still the main focus of the discussion on the reconciliation process. Learn how to implement React 16 reconciliation in advance. This will be the focus of the next module.

Ending our discussion of Diff in the React 15 era, don’t forget that there’s another batch in the virtual DOM. “Batch” describes the “batch” mechanism, which, like Diff, can be triggered by setState in React. Next, dive into the setState workflow to explore a number of issues, including “batch updates.”

Learning the source (the article reprinted from) : kaiwu.lagou.com/course/cour…