React Fiber单向链表架构

hushicai commented 5 years ago

原文地址：The how and why on React’s usage of linked list in Fiber to walk the component’s tree

在处理UI时，如果一次执行太多工作，可能会导致动画丢帧。

基本上，如果React要同步遍历整个组件树，并为每个组件执行任务，它可能会运行超过16毫秒，这将导致不顺畅的视觉效果。

较新的浏览器（和React Native）实现了有助于解决这个问题的API：requestIdleCallback，可用于对函数进行排队，这些函数会在浏览器空闲时被调用：

requestIdleCallback((deadline)=>{
    console.log(deadline.timeRemaining(), deadline.didTimeout)
});

如果我现在打开控制台并执行上面的代码，Chrome会打印49.9和false，它基本上告诉我，我有49.9ms去做我需要做的任何工作，并且我还没有用完所有分配的时间，否则deadline.didTimeout将会是true。

请记住timeRemaining可能在浏览器被分配某些工作后立即更改，因此应该不断检查。

但requestIdleCallback 实际上有点过于严格，并且执行频次不足以实现流畅的UI渲染，因此React团队必须实现自己的版本。

现在，如果我们将React对组件执行的所有活动放入函数performWork, 并使用requestIdleCallback来安排工作，我们的代码可能如下所示：

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

我们对一个组件执行工作，然后返回要处理的下一个组件。

这是可以做到的，但前提是我们不能同步地处理整个组件树。

因此，我们需要一种方法将渲染工作分解为增量单元。

为了解决这个问题，React必须重新实现遍历树的算法，从依赖于内置堆栈的同步递归模型，变为具有链表和指针的异步模型。

递归遍历

walk(a1);

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

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

递归方法直观，非常适合遍历树。

但是正如我们发现的，它有局限性：最大的一点就是我们无法分解工作为增量单元。

我们不能暂停特定组件的工作并在稍后恢复。

通过这种方法，React只能不断迭代直到它处理完所有组件，并且堆栈为空。

链表遍历

Sebastian Markbåge在Fiber Principles: Contributing To Fiber概括了该算法的要点。

要实现该算法，我们需要一个包含3个字段的数据结构：

child — 第一个子节点的引用
sibling — 第一个兄弟节点的引用
return — 父节点的引用

在React新的协调算法的上下文中，包含这些字段的数据结构称为Fiber。

下图展示了通过链表链接的对象的层级结构和它们之间的连接类型：

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

    while (true) {
        let child = doWork(current);

        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;
    }
}

它看起来像浏览器中的一个调用堆栈。

我们现在通过保持对current节点（充当顶部堆栈帧）的引用来控制堆栈：

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

    while (true) {
            ...

            current = child;
            ...

            current = current.return;
            ...

            current = current.sibling;
    }
}

我们可以随时停止遍历并稍后恢复。

bigggge commented 4 years ago

Fiber 有 child sibling return 三个节点，为什么说是“单向”链表？

hushicai commented 4 years ago

Fiber 有 child sibling return 三个节点，为什么说是“单向”链表？

child、return是用来构建“树”，“sibling”用来构建同级元素的“单向”链表，通过遍历这个“单向”链表来 dom diff。

lilywang711 commented 3 years ago

“我们可以随时停止遍历并稍后恢复。”

这个要怎么做到呢，如何停止、如何恢复

hushicai commented 3 years ago

“我们可以随时停止遍历并稍后恢复。”

这个要怎么做到呢，如何停止、如何恢复

循环完全由程序负责了，当然可以根据各种条件，随时跳出循环，并择机恢复。

lilywang711 commented 3 years ago

好的，理解了，那我觉得跳出循环简单，但要恢复的实现应该比较麻烦 😂

hushicai commented 3 years ago

好的，理解了，那我觉得跳出循环简单，但要恢复的实现应该比较麻烦 😂

恢复也不麻烦，重新进入循环就好了，不过需要在循环外保存上次退出时的状态。

hushicai / hushicai.github.io

React Fiber单向链表架构 #41

递归遍历

链表遍历