Why does React Fiber use linked lists to design component trees

background

Fiber architecture has two main phases, Reconciliation and COMMIT. The coordination stage is often called the rendering stage. This happens:

1. Update the state and props
2. Call life cycle
3. Retrieves the child
4. Compare the difference with the previous child
5. Update the DOM

These are called the internal activities of Fiber.

If React traverses the entire component tree synchronously, too many updates can take longer than 16ms to execute, resulting in visual lag.

requestIdleCallback

The requestIdleCallback will execute the callback when the browser is idle. Check out my previous post on requestIdleCallback for more information

But the React team had to implement their own version of requestIdleCallback because it wasn’t implemented frequently enough to render the UI smoothly

Assuming React performs updates in performWork and uses requestIdleCallback, the code might look something like this

requestIdleCallback((deadline) = > {
    while ((deadline.timeRemaining() > 0|| deadline.didTimeout) && nextComponent) { nextComponent = performWork(nextComponent); }});Copy the code

We perform work on one component and then return to the next component to be processed. We cannot process the entire tree of components synchronously as before. To solve this problem React had to move from a synchronous recursive model that relied on stacks to an asynchronous model with linked lists and Pointers.

If you rely solely on the call stack, each update will work until the stack is empty. It would be nice if you could interrupt the call stack at any time and manipulate the stack frame manually. That’s the purpose of Fiber, which is a reimplementation of the stack, specifically for React

StackFrame stack frame

Each call to a function maintains a separate stack frame on the Call stack. Each independent stack frame generally includes:

What is a stack

In data structures, a stack is a linear table that limits insert or delete operations to the end of the table. A stack is a data structure that stores data according to the principle of last in, first out. The data entered first is pushed to the bottom of the stack, and the last data is placed at the top of the stack. When data needs to be read, the data will be ejected from the top of the stack.

What is a stack frame

Each call to a function maintains a separate stack frame on the Call stack. Each individual stack frame contains:

1. The return address and arguments of the function
2. Temporary variables: Includes non-static local variables of a function and other temporary variables automatically generated by the compiler
3. The context of the function call
4. The stack extends from the high address to the low address, and the stack frame of a function is bounded by two registers, EBP and ESP. Ebp points to the bottom of the current stack frame, esp always points to the top of the stack frame; The EBP register is also called a Frame Pointer. The ESP register is also called a Stack Pointer.

The stack and the React

The React coordination phase, which relies on the built-in recursive model, is described in the official coordination documentation

React recurses to the child elements of a DOM node. React iterates through lists of both child elements at the same time. When a difference occurs, a mutation is generated.

Suppose we have the following component tree:

Our simplest virtual DOM represents this component tree

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 code

Recursively traverses the component tree

function walk(instance) {
    doWork(instance);
    const children = instance.render();
    children.forEach(walk);
}

function doWork(o) {
    console.log(o.name);
}

// a1, b1, b2, c1, d1, d2, b3, c2
walk(a1)
Copy the code

Recursively walking through a tree of components is straightforward, but it has limitations in that it cannot pause work on a particular component. With this approach, React keeps iterating until all components are processed and the stack is empty.

So how does the Fiber architecture traverse the tree without recursion? React uses a single-linked list tree. You can pause traversal at any time

List tree traversal

See here for the main points of the list tree traversal algorithm

If a list tree is to be traversed, each node of the tree must contain the following three attributes:

1. Child, reference to the first child
2. Sibling, the first sibling reference
3. Return, the parent reference

In the React coordination algorithm, nodes with these fields are called fibers. The figure below is a single list tree.

Let’s first define the node’s constructor

class Node {
    constructor(instance) {
        this.instance = instance;
        this.child = null;
        this.sibling = null;
        this.return = null; }}Copy the code

We need a function to link the parent node to the child node. The first child of the link function parent. Returns null if there are no child nodes.

function link(parent, elements) {
    // Returns an empty array if there are no children
    if (elements === null) elements = [];

    parent.child = elements.reduceRight((previous, current) = > {
        // Create a child node
        const node = new Node(current);
        // Set a reference to the parent node
        node.return = parent;
        // Sets the sibling reference, first iteration previous is null
        node.sibling = previous;
        return node;
    }, null);

    return parent.child;
}
Copy the code

Create a single-linked list tree

const children = [{name: 'b1'}, {name: 'b2'}];
const parent = new Node({name: 'a1'});
const child = link(parent, children);
Copy the code

Once created, the single-linked list should look like the following:

// true
console.log(parent.child.instance.name === 'b1');
// true
console.log(child.sibling.instance.name === 'b2');
// true
console.log(child.sibling.sibling === null);
Copy the code

Walk through the list tree

Start by creating a utility function that prints the traversal and links the parent and child nodes

function doWork(node) {
    console.log(node.instance.name);
    const children = node.instance.render();
    return link(node, children);
}
Copy the code

Next we start to implement the single list tree traversal algorithm, the algorithm is depth-first implementation. Let’s start by creating some nodes

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 code

function walk(o) {
    / / the root node
    let root = o;
    // Pointer to the node currently traversed
    let current = o;

    while (true) {
        // With doWork, connect the root and child nodes and return the first child of the root node
        let child = doWork(current);

        // 1. If there is a child node, point the current pointer to the child node and enter the next loop (because it is the preferred depth)
        // 2. If there is no child node, skip it
        if (child) {
            current = child;
            continue;
        }

        // If the current pointer is equal to the root node, the traversal ends
        if (current === root) {
            return;
        }

        // If there are no brothers, enter the while loop
        while(! current.sibling) {// If the current pointer is equal to the root node, the traversal ends
            if(! current.return || current.return === root) {return;
            }

            // If there are no children and no siblings, return the parent node
            current = current.return;
        }

        // If there are sibling nodes, set the current pointer to sibling nodes and proceed to the next iteration
        current = current.sibling;
    }
}

walk(new Node(a1))
Copy the code

Summarize the idea of walk

1. Get the first child node from root
2. If root has child nodes, set the current pointer to the first child node and proceed to the next iteration. (Depth-first traversal)
3. If root’s first child has no children, it tries to get its first sibling.
4. If there are siblings, set the current pointer to the first child, and then the sibling enters the depth-first traversal.
5. If there are no siblings, the parent is returned. Finally, the traversal is finished

The node traversal process is shown as follows:

We now keep the reference to the current stack frame, so we can stop and resume traversal at any time

function walk(o) {
    let root = o;
    let current = o;

    while (true) {... current = child; . current = current.return; . current = current.sibling; }}Copy the code

🚀 🚀 🚀 there are no examples in the original text here. I would like to implement an example here to show how Fiber interrupts traversal and then resumes traversal using the browser’s requestIdleCallback API

// Use sleep to simulate rendering time
function sleep (ms = 100) {
    let sleepSwitch = true
    let s = Date.now()
    while (sleepSwitch) {
        if (Date.now() - s > ms) {
            sleepSwitch = false}}}class Node {
    constructor(instance) {
        this.instance = instance;
        this.child = null;
        this.sibling = null;
        this.return = null; }}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;
}

/ / the node
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 = () = > {
    sleep(60)
    return [b1, b2, b3]
};
b1.render = () = > {
    return[]}. b2.render =() = > {
    sleep(20)
    return [c1]
};
b3.render = () = > {
    sleep(20)
    return [c2]
};
c1.render = () = > {
    sleep(40)
    return [d1, d2]
};
c2.render = () = > [];
d1.render = () = > [];
d2.render = () = > [];

const root = new Node(a1);
// Always keep a reference to the current node
let current = root;
// Whether the rendering is complete
let isRendered = false;

const rIcb = (deadline) = > {
    if (deadline.timeRemaining() > 20) {
        walk(current, deadline)
    } else{ requestIdleCallback(rIcb); }}function doWork(node, deadline) {
    if (deadline.timeRemaining() > 20) {
        console.log(node.instance.name);
        const children = node.instance.render();
        return link(node, children);
    } else{ requestIdleCallback(rIcb); }}function walk(o, deadline) {
    while (true) {
        let child = doWork(current, deadline);
        if (child) {
            current = child;
            continue;
        }
        if (current === root) {
            return;
        }
        while(! current.sibling) {if(! current.return || current.return === root) {return;
            }
            current = current.return;
        }
        current = current.sibling;
    }
}

requestIdleCallback(rIcb);
Copy the code

Running results:

As you can see from the example above, we just need to get a reference to the current heap frame to pause and then resume traversal

React and work loops

This is the code for the work loop in React, with the nextUnitOfWork variable as the top stack frame, keeping a reference to the current Fiber node.

function workLoop(isYieldy) {
    if(! isYieldy) {while(nextUnitOfWork ! = =null) { nextUnitOfWork = performUnitOfWork(nextUnitOfWork); }}else {
        while(nextUnitOfWork ! = =null&&! shouldYield()) { nextUnitOfWork = performUnitOfWork(nextUnitOfWork); }}}Copy the code

The React algorithm can traverse the component tree either synchronously or asynchronously to check if there is any time left after executing Fiber’s internal activity. Whether you need to wait for an idle time to execute the task. The function shouldYield returns the result based on the deadlineDidExpire and Deadline variables, which are constantly updated when React works for the Fiber node.

reference

• The how and why on React’s usage of linked list in Fiber to walk the component’s tree
• The Stack Frame (Stack Frame)