【JS】React Fiber为什么使用链表来设计组件树

React Fiber为什么使用链表来设计组件树

张越发布于 今天 09:45

背景介绍

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

  1. 更新state和props
  2. 调用生命周期
  3. 检索子级
  4. 比较和之前子级的区别
  5. 更新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必须从依赖堆栈的同步递归模型迁移到具有链表和指针的异步模型。

StackFrame 栈帧

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

什么是栈

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

什么是栈帧

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

  1. 函数的返回地址和参数
  2. 临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量
  3. 函数调用的上下文
  4. 栈是从高地址向低地址延伸,一个函数的栈帧用ebp和esp这两个寄存器来划定范围。ebp指向当前的栈帧的底部, esp始终指向栈帧的顶部;ebp寄存器又被称为帧指针(Frame Pointer);esp寄存器又被称为栈指针(Stack Pointer);

【JS】React Fiber为什么使用链表来设计组件树

堆栈与React

React的协调阶段,之前使用了依赖于内置递归模型, 关于协调官方文档描述了此过程

假设我们有如下的组件树:

【JS】React Fiber为什么使用链表来设计组件树

我们最简洁的虚拟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会一直保持迭代,直到处理完所有组件并且堆栈为空为止。

链表树遍历

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

如果需要实现链表树的遍历,链表树的每个节点需要包含下面三个属性:

  1. child, 第一个子级的引用
  2. sibling, 第一个同级的引用
  3. return, 父级的引用

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

【JS】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);

创建完成,单链表的结构应该如下图所示:

【JS】React Fiber为什么使用链表来设计组件树

// 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的思路

  1. 从根节点root获取第一个子节点
  2. 如果root有子节点,将当前指针设置为第一个子节点,并进入下一次迭代。(深度优先遍历)
  3. 如果root的第一个子节点,没有子节点,则尝试获取它的第一个兄弟节点。
  4. 如果有兄弟节点,将当前指针设置为第一个子节点,然后兄弟节点进入深度优先遍历。
  5. 如果没有兄弟节点,则返回父节点。最后结束遍历

节点遍历的过程如下图:

【JS】React Fiber为什么使用链表来设计组件树

我们现在保留对当前堆栈帧的引用,就可以随时停止遍历然后再恢复遍历

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

运行结果:

【JS】React Fiber为什么使用链表来设计组件树

从上面的例子可以看出,我们只需要拿到当前堆帧的引用,就可以暂停遍历,随后恢复遍历

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.js

阅读 44发布于 今天 09:45

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

avatar

张越

想去字节跳动,qq:1025873823

394 声望

178 粉丝

0 条评论

得票时间

avatar

张越

想去字节跳动,qq:1025873823

394 声望

178 粉丝

宣传栏

背景介绍

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

  1. 更新state和props
  2. 调用生命周期
  3. 检索子级
  4. 比较和之前子级的区别
  5. 更新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必须从依赖堆栈的同步递归模型迁移到具有链表和指针的异步模型。

StackFrame 栈帧

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

什么是栈

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

什么是栈帧

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

  1. 函数的返回地址和参数
  2. 临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量
  3. 函数调用的上下文
  4. 栈是从高地址向低地址延伸,一个函数的栈帧用ebp和esp这两个寄存器来划定范围。ebp指向当前的栈帧的底部, esp始终指向栈帧的顶部;ebp寄存器又被称为帧指针(Frame Pointer);esp寄存器又被称为栈指针(Stack Pointer);

【JS】React Fiber为什么使用链表来设计组件树

堆栈与React

React的协调阶段,之前使用了依赖于内置递归模型, 关于协调官方文档描述了此过程

假设我们有如下的组件树:

【JS】React Fiber为什么使用链表来设计组件树

我们最简洁的虚拟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会一直保持迭代,直到处理完所有组件并且堆栈为空为止。

链表树遍历

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

如果需要实现链表树的遍历,链表树的每个节点需要包含下面三个属性:

  1. child, 第一个子级的引用
  2. sibling, 第一个同级的引用
  3. return, 父级的引用

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

【JS】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);

创建完成,单链表的结构应该如下图所示:

【JS】React Fiber为什么使用链表来设计组件树

// 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的思路

  1. 从根节点root获取第一个子节点
  2. 如果root有子节点,将当前指针设置为第一个子节点,并进入下一次迭代。(深度优先遍历)
  3. 如果root的第一个子节点,没有子节点,则尝试获取它的第一个兄弟节点。
  4. 如果有兄弟节点,将当前指针设置为第一个子节点,然后兄弟节点进入深度优先遍历。
  5. 如果没有兄弟节点,则返回父节点。最后结束遍历

节点遍历的过程如下图:

【JS】React Fiber为什么使用链表来设计组件树

我们现在保留对当前堆栈帧的引用,就可以随时停止遍历然后再恢复遍历

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

运行结果:

【JS】React Fiber为什么使用链表来设计组件树

从上面的例子可以看出,我们只需要拿到当前堆帧的引用,就可以暂停遍历,随后恢复遍历

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)

以上是 【JS】React Fiber为什么使用链表来设计组件树 的全部内容, 来源链接: www.h5w3.com/113483.html

回到顶部