关于javascript:React-Fiber为什么使用链表来设计组件树

背景介绍

Fiber架构次要有两个阶段, reconciliation(协调)和commit(提交)。协调阶段通常称为渲染阶段。此时会产生：

更新state和props
调用生命周期
检索子级
比拟和之前子级的区别
更新DOM

这些被称为Fiber的外部流动。

如果React同步遍历整个组件树，一次的更新操作过多，执行的工夫可能会超过16ms以上, 会导致视觉上的卡顿。

requestIdleCallback

requestIdleCallback会在浏览器闲暇的时候，执行callback。无关requestIdleCallback的内容能够查看我之前写的文章详解 requestIdleCallback

然而因为requestIdleCallback的执行频率不足以晦涩的出现UI, React团队不得不实现本人的版本

咱们假设React执行更新的操作都在performWork中，并且应用requestIdleCallback，代码可能会如下所示

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

咱们在一个组件上执行工作，而后返回下一个要解决的组件。咱们不能像之前一样同步解决整个组件树。要解决此问题React必须从依赖堆栈的同步递归模型迁徙到具备链表和指针的异步模型。

如果仅依附调用堆栈，每次更新都会工作到堆栈被清空为止。如果能够随时中断调用堆栈，手动操作栈帧，会更好。这就是Fiber的目标，Fiber是堆栈的从新实现，专门用于React

StackFrame 栈帧

每一次函数的调用,都会在调用栈(call stack)上保护一个独立的栈帧(stack frame).每个独立的栈帧个别包含:

什么是栈

在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它依照后进先出的准则存储数据，先进入的数据被压入栈底，最初的数据在栈顶，须要读数据的时候从栈顶开始弹出数据。

什么是栈帧

每一次函数的调用,都会在调用栈(call stack)上保护一个独立的栈帧(stack frame).每个独立的栈帧蕴含：

函数的返回地址和参数
长期变量: 包含函数的非动态局部变量以及编译器主动生成的其余长期变量
函数调用的上下文
栈是从高地址向低地址延长,一个函数的栈帧用ebp和esp这两个寄存器来划定范畴。ebp指向以后的栈帧的底部, esp始终指向栈帧的顶部;ebp寄存器又被称为帧指针(Frame Pointer);esp寄存器又被称为栈指针(Stack Pointer);

堆栈与React

React的协调阶段，之前应用了依赖于内置递归模型, 对于协调官网文档形容了此过程

React递归DOM节点的子元素时，React会同时遍历两个子元素的列表；当产生差别时，生成一个 mutation。

假如咱们有如下的组件树：

咱们最简洁的虚构DOM，示意这个组件树

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 = () => [];

递归遍历组件树

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)

递归遍历组件树的办法很间接，然而它有局限性，它无奈在特定的组件上暂停工作。如果通过这种办法，React会始终放弃迭代，直到解决完所有组件并且堆栈为空为止。

那么Fiber架构是如何做到不须要递归而遍历树的呢？React应用了单链表树。能够随时暂停遍历

链表树遍历

对于链表树遍历算法的要点请看这里

如果须要实现链表树的遍历，链表树的每个节点须要蕴含上面三个属性：

child, 第一个子级的援用
sibling, 第一个同级的援用
return，父级的援用

在React新的协调算法中，领有这些字段的的节点被成为Fiber。下图是一个单链表树。

首先定义下节点的构造函数

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

咱们须要一个函数，链接父节点和子节点。link函数函数parent的第一个子节点。如果没有子节点返回null
.

function link(parent, elements) {
    // 如果没有子节点返回空数组
    if (elements === null) elements = [];

    parent.child = elements.reduceRight((previous, current) => {
        // 创立子节点
        const node = new Node(current);
        // 设置父节点的援用
        node.return = parent;
        // 设置同级的援用，第一次迭代previous是null
        node.sibling = previous;
        return node;
    }, null);

    return parent.child;
}

创立单链表树

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

创立实现，单链表的构造应该如下图所示：

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

遍历链表树

首先创立一个工具函数，能够打印遍历的过程，还能够链接父节点和子节点

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

接下来咱们开始实现单链表树遍历算法，算法是深度优先的实现。咱们首先创立一些节点

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 = () => [];

function walk(o) {
    // 根节点
    let root = o;
    // 指针，以后遍历到的节点
    let current = o;

    while (true) {
        // 应用doWork，连贯根节点和子节点，并返回根节点的第一个子节点
        let child = doWork(current);

        // 1. 如果有子节点，将以后的指针指向子节点，并进入下一个循环（因为是优先深度）
        // 2. 如果没有子节点，略过
        if (child) {
            current = child;
            continue;
        }

        // 如果以后指针等于根节点，完结遍历
        if (current === root) {
            return;
        }

        // 如果没有兄弟，进入while循环
        while (!current.sibling) {

            // 如果以后指针等于根节点，完结遍历
            if (!current.return || current.return === root) {
                return;
            }

            // 如果没有子节点，并且没有兄弟节点，返回父级的节点
            current = current.return;
        }

        // 如果有兄弟节点，将以后指针设置为兄弟节点，进入下一次迭代
        current = current.sibling;
    }
}

walk(new Node(a1))

总结下walk的思路

从根节点root获取第一个子节点
如果root有子节点，将以后指针设置为第一个子节点，并进入下一次迭代。（深度优先遍历）
如果root的第一个子节点，没有子节点，则尝试获取它的第一个兄弟节点。
如果有兄弟节点，将以后指针设置为第一个子节点，而后兄弟节点进入深度优先遍历。
如果没有兄弟节点，则返回父节点。最初完结遍历

节点遍历的过程如下图：

咱们当初保留对以后堆栈帧的援用，就能够随时进行遍历而后再复原遍历

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

    while (true) {
            ...

            current = child;
            ...
            
            current = current.return;
            ...

            current = current.sibling;
    }
}

???? ???? ???? 原文在这里没有举例子阐明，我想在这里实现一个例子，来阐明fiber如何中断遍历，而后复原遍历的, 应用了浏览器的requestIdleCallback API

// 应用sleep模仿渲染的消耗工夫
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;
}

// 节点
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);
// 始终放弃对以后节点的援用
let current = root;
// 是否渲染实现
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);

运行后果：

从下面的例子能够看出，咱们只须要拿到以后堆帧的援用，就能够暂停遍历，随后复原遍历

React和工作循环

这是React中工作循环的代码，nextUnitOfWork变量作为顶部栈帧，保留对以后Fiber节点的援用。

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

React中的算法，既能够同步遍历组件树，也能够异步遍历组件树，查看在执行Fiber外部流动后后是否还剩下工夫。是否须要等到一次闲暇工夫执行工作。函数shouldYield返回基于deadlineDidExpire和deadline变量的后果，这些变量在React为Fiber节点执行工作时不停的更新。

参考

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

关于javascript:React-Fiber为什么使用链表来设计组件树

背景介绍

requestIdleCallback

StackFrame 栈帧

什么是栈

什么是栈帧

堆栈与React

递归遍历组件树

链表树遍历

遍历链表树

React和工作循环

参考

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于javascript:React-Fiber为什么使用链表来设计组件树

背景介绍

requestIdleCallback

StackFrame 栈帧

什么是栈

什么是栈帧

堆栈与React

递归遍历组件树

链表树遍历

遍历链表树

React和工作循环

参考

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复