This article is free translation and collation, if misleading, please give up reading. The original
preface
This article explores the work loop in The React Reconciler’s new implementation -Fiber. In the text, we compare and explain the difference between the Browser’s Call Stack and the React Fiber architecture’s own stack.
The body of the
In order to educate myself and give back to the community, I spent a lot of time practicing reverse engineering of Web technologies and writing articles documenting my findings. Over the past year, I have focused on Angular source code, publishing the largest number of articles about Angular on the web – angular-in-depth. Now, it’s time to dive into React. Change Detection is an area I specialize in at Angular. I hope that with enough patience and lots of debugging, I can reach the same professional level in React as soon as possible.
In React, the change detection mechanism is often referred to as “reconciliation” or “rendering.” Fiber is the latest implementation of reconciliation. At the bottom of the Fiber architecture, it gives us the ability to implement all sorts of interesting features. Examples include “non-blocking rendering”, “Priority based update strategy” and “pre-rendeing content in the background”. These features are collectively referred to as time slicing in Concurrent React Philosophy.
In addition to solving practical problems for application developers, the internal implementation of these mechanisms is also very attractive from an engineering perspective. Within the source code, there is a wealth of knowledge that can help you become a better developer.
Today, if you Google React Fiber, you’ll see a ton of articles about it. Among them, except for a high-quality Notes by Andrew Clark article, the quality of the other articles is…… You know. In this article, I will quote some of the arguments from this note. I’ll explain some of the most important concepts in Fiber architecture in more detail. Once you’ve read and understood this article, you’ll be in a good position to follow an excellent talk from ReactConf 2017 Lin Clark. This is a speech you need to see and hear. But it would be much better if you took the time to study the source code and come back to this talk.
This article was the first in my “Inside XXX” series. I believe I understand about 70% of the implementation details inside Fiber. In the meantime, I plan to write three articles on reconciliation and rendering.
Now, let’s begin our journey of discovery.
context
Fiber architecture has two main phases:
Reconciliation/Render and Commit phases. In most of the source code, the reconciliation stage is referred to as the Render stage. It is in the Render phase that React iterates through the component tree and does the following:
- Update the state and props,
- Call the lifecycle function,
- Get children from the component (by calling the Render method),
- Compare the children that you get with the children that came before
- Finally, figure out what DOM operations need to be performed.
In the Fiber architecture, all of these activities are called “work.” What kind of work a Fiberr node needs to do depends on what type of React Element it corresponds to. For example, for a class component, React needs to do the work of instantiating the component. Functional Component has no such work to do. If you’re interested, here are all the types of work you want to see. These activities are what Andrew talks about in his notes:
When dealing with UIs, the problem is that if too much work is executed all at once, It can cause animations to drop frames…
“All at once”? Well, basically React iterates through a tree of components synchronously, performing specific actions on each component. What’s the problem with that? In practice, this approach can result in application logic code taking longer than the available 16 milliseconds to execute. This will cause frames to drop in the interface rendering, resulting in the appearance of a lag.
So, can this problem be solved?
Newer browsers (and React Native) implement APIs that help address this exact problem…
The new API he’s talking about is the global function requestIdleCallback. This global function queues up a function and then calls it during the browser’s idle time. Here is an example in use:
requestIdleCallback((deadline)=>{
console.log(deadline.timeRemaining(), deadline.didTimeout)
});
Copy the codeIf I type the code above on the Chrome console and execute it. So, we see that the console prints 49.9 false. The result is basically telling me that you have 49.9 milliseconds of private time to do your own thing. False is telling me that you haven’t used up the time I’ve allocated to you. If I run out of time, deadline. DidTimeout will be true. Keep reminding yourself that the timeRemaining field values will change as the browser runs. Therefore, we should always check the value of this field.
RequestIdleCallback is actually quite limited and does not execute frequently enough to create a smooth interface rendering experience. So the React team had to implement its own version.
Now, assuming we put all the work we need to do on the React component into the performWork function and use requestIdleCallback to schedule the function, our implementation code would look something like this:
requestIdleCallback((deadline) => {
// while we have time, perform work for a part of the components tree
while ((deadline.timeRemaining() > 0 || !deadline.didTimeout) && nextComponent) {
nextComponent = performWork(nextComponent);
}
});
Copy the codeWe perform work on the components one by one, and then, one by one, after processing the current component, return the introduction of the next component, and continue processing. By rights, this implementation should be feasible. But there’s a problem. You can’t synchronously traverse the entire tree of components like previous implementations of the Reconciliation algorithm. That’s what Andrew’s notes are about:
in order to use those APIs, you need a way to break rendering work into incremental units
To solve this problem, React had to re-implement the algorithm used to traverse the component tree. Change it from synchronous recursive mode, which relies on the browser’s native Call stack, to asynchronous mode with linked lists and Pointers. Andrew had this to say about this:
If you rely solely on the browser’s native Call stack, the Call Stack will execute our code until it empties itself….. Wouldn’t it be great if we could manually and arbitrarily interrupt the Call Stack and manipulate every frame of the Call Stack? And that’s what React Fiber is all about. React Fiber is a reimplementation of stack, specifically for the React component. You can think of a single Fiber node as a virtual stack frame.
And what Andrew said is exactly what I’m going to explain.
The thing about stack
I assume that you are familiar with the concept of “Call Stack.” It’s what you see in the debug panel when the browser developer breaks. Here’s a quote and illustration from Wikipedia:
In computer science, a Call stack is a stack structure that stores information about subroutines currently being executed by a computer program…… The main reason to use the Call Stack is to keep a pointer to who should be given control of the program after the current subroutine completes execution….. A Call Stack consists of multiple stack frames. Each stack frame corresponds to a subroutine call. As a stack frame, this subroutine should not be terminated by a return statement at this point. For example, we have a subroutine called DrawLine running. This subroutine is called by another subroutine called DrawSquare, so the top layout of the call stack should look like this:
Why is stack related to React?
In the section above, we mentioned that React iterates through the entire component tree during the Reconciliation/Render phase and performs specific work for each component. In previous implementations of the Reconciler, React used a synchronous recursive mode. This mode relies on the browser’s native Call Stack. This official document explains the process and talks a lot about recursion:
By default, when recursing on the children of a DOM node, React just iterates over both lists of children at the same time and generates a mutation whenever there’s a difference.
If you think about it, you know that each recursive call adds a stack frame to the Call stack. In this case, the whole recursive process behaves so synchronously (too synchronously, in a way, blocking the Call Stack). To dig deeper into the Call Stack, check out my list: What exactly is an Event Loop?) . Suppose we have the following component tree:
We use an object with a Render method to represent each node. You can also think of this object as an instance of a component;
const a1 = {name: 'a1'};
const b1 = {name: 'b1'};
const b2 = {name: 'b2'};
const b3 = {name: 'b3'};
const c1 = {name: 'c1'};
const c2 = {name: 'c2'};
const d1 = {name: 'd1'};
const d2 = {name: 'd2'};
a1.render = () => [b1, b2, b3];
b1.render = () => [];
b2.render = () => [c1];
b3.render = () => [c2];
c1.render = () => [d1, d2];
c2.render = () => [];
d1.render = () => [];
d2.render = () => [];
Copy the codeReact requires iterating through the entire tree, doing some work for each component. For simplicity, we define the work that the component needs to do as “print the name of the component and return children.” The next section describes how we do this recursively.
Recursive traversal
The function responsible for iterating through the component tree is called walk. Its concrete implementation is as follows:
function walk(instance) {
doWork(instance);
const children = instance.render();
children.forEach(walk);
}
function doWork(o) {
console.log(o.name);
}
walk(a1);
Copy the codeExecute the above code and you should see the following output:
a1, b1, b2, c1, d1, d2, b3, c2
Copy the codeIf you feel like you don’t know enough about recursion, feel free to read my article on recursion in depth.
Using recursion here is a good intuition, and it also lends itself well to component tree traversal. However, we also discovered its limitations. The biggest one is that we can’t split work into incremental units. We cannot suspend execution of a particular component of Work and then resume it later. In recursive mode, React can only iterate until all components have been processed and the Call stack is empty (this is called a “one pass”).
So here’s the problem. How does React implement an algorithm that traverses the component tree without using recursive patterns? The answer is that it uses a singly-linked-list tree traversal. This makes it possible to iterate over pauses and stop the stack from growing.
Single linked list traversal
I’m glad I found an overview of the algorithm summarized by Sebastian Markbage here. To implement this algorithm, we need a data structure linked by three fields:
- Child – Points to the first child
- Sibling – Points to the first sibling node
- Return – Refers to parent (formerly owner concept)
In the context of React’s new reconciliation algorithm, the data structure with these three fields is called a “Fiber node.” At the bottom, it represents a React element that has work to execute. For more on that, see my next article.
The following diagram illustrates the hierarchy of nodes in linked-List and the relationships that exist between them:
Let’s define our own fiber node constructor:
class Node { constructor(instance) { this.instance = instance; this.child = null; this.sibling = null; this.return = null; }}Copy the codeLet’s implement another one that links together the children returned from the render method of the component instance, making them functions of linked-List. This function takes a parent Fiber node and an array of component instances as input, and returns a reference to the first child of the parent Fiber Node:
function link(parent, elements) {
if (elements === null) elements = [];
parent.child = elements.reduceRight((previous, current) => {
const node = new Node(current);
node.return = parent;
node.sibling = previous;
return node;
}, null);
return parent.child;
}
Copy the codeThis function starts from the reciprocal (note that it uses the reduceRight method) and iterates through each element of the set, linking them into a linked-list. Finally, return the reference to the first Child Fiber node of the Parent Fiber node. The following code demonstrates the use of this function:
const children = [{name: 'b1'}, {name: 'b2'}];
const parent = new Node({name: 'a1'});
const child = link(parent, children);
// the following two statements are true
console.log(child.instance.name === 'b1');
console.log(child.sibling.instance === children[1]);
Copy the codeWe also need to implement a helper function to perform specific work on the Fiber node. In this example, the work simply prints out the name of the component instance. In addition to performing work, the helper function also gets the latest children list of the component and links them together:
function doWork(node) {
console.log(node.instance.name);
const children = node.instance.render();
return link(node, children);
}
Copy the codeOkay, everything is ready except the east wind. Now, let’s implement a specific traversal algorithm. This is a depth-first algorithm implementation. Here is the implementation code with some comments:
// You can say it is a fiber node or it is a fiber node treefunction walk(o) {
let root = o;
let current = o;
while (true) {
// perform work for a node, retrieve & link the children
let child = doWork(current);
// if there is a child, set it as the current active node
if (child) {
current = child;
continue; } / /if we have returned to the top, exit the function
if (current === root) {
return;
}
// keep going up until we find the sibling
while(! current.sibling) { //if we have returned to the top, exit the function
if(! current.return || current.return === root) {return; } / /setthe parent as the current active node current = current.return; } / /if found, setthe sibling as the current active node current = current.sibling; }}Copy the codeAlthough the implementation code above is not particularly hard to understand. But I think you’d better play with it so you can understand it better. Do it here. The central idea of this implementation is to keep a reference to the fiber node currently being processed, and keep revising the reference as depth-first traverses down until the traversal reaches the leaf node of the tree branch. Once that’s done, we use the return field to layer by layer back to the parent Fiber node.
If we were to look at the call Stack implementation at this point, we would see something like this:
As you can see, the stack doesn’t increase in height as we traverse. But if we make a breakpoint in the doWork function and print out the name of the component instance node, we will see something like this:
The resulting animation looks a lot like the browser’s Call Stack (except that the bottom of the call stack is at the bottom and this is at the top). With this algorithm implementation, we can nicely replace the browser’s Call Stack with our own stack. This is one of the things That Andrew talks about in his notes:
Fiber is re-implementation of the stack, specialized for React components. You can think of a single fiber as a virtual stack frame.
We can now save a reference to a Fiber node that acts as the top frame of the stack by constantly switching its orientation
In one case point to its Child Fiber node, in another case point to its Sibling Fiber node, in another case point to its return/ Parent Fiber node
To control our “call Stack” :
function walk(o) {
let root = o;
let current = o;
while (true) {... current = child; . current = current.return; . current = current.sibling; }}Copy the codeTherefore, we can pause and resume execution at will during traversal. This is a prerequisite for being able to use the new requestIdleCallbackAPI.
React work loop
React implements work loop.
function workLoop(isYieldy) {
if(! isYieldy) { // Flush work without yieldingwhile (nextUnitOfWork !== null) {
nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
}
} else {
// Flush asynchronous work until the deadline runs out of time.
while (nextUnitOfWork !== null && !shouldYield()) {
nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
}
}
}
Copy the codeAs you can see, the implementation in React is very similar to the algorithm implementation we mentioned above. It also holds a fiber node reference via the nextUnitOfWork variable.
React’s walk loop algorithm synchronously traverses the component tree and performs some work on each fiber node (nextUnitOfWork). The synchronous approach tends to occur in so-called “interactive update” scenarios [caused by UI events (click, input, etc.)]. In addition to synchronous mode, walk loop can also be performed asynchronously. During traversal, the algorithm checks whether there is currently available time before each fiber node related work is performed. The shouldYield function returns the result based on the variables deadlinedidex and Deadline. The values of these two variables will be updated as React works on fiber nodes.
For more details on peformUnitOfWork, check out this article: In-depth Reconciliation Algorithm for the React Fiber architecture.