侧边栏

Fiber与循环diff

发布于 | 分类于 源码分析/diff算法

在上一篇文章VNode与递归diff中，我们了解了VNode的作用，如何将VNode映射为真实DOM，并通过递归实现了diff操作，最后研究了三种不同的diff方式带来的性能差异。

本文将紧接上文，研究如何通过循环的方式实现diff，并在此基础上实现对应的调度系统，从而理解React中的一些核心原理。

本文包含大量示例代码，主要实现

  • createFiber，创建一个fiber节点
  • diff，通过循环的方式diff节点
  • scheduleWork，对于循环diff任务进行调度，从而避免递归diff长时间占用线程的问题

本系列文章列表如下

排在后面文章内会大量采用前面文章中的一些概念和代码实现，如createVNode、diffChildren、doPatch等方法，因此建议逐篇阅读，避免给读者造成困惑。本文相关示例代码均放在github上，如果发现问题，烦请指正。

fiber ​

为了将vnode树从递归遍历修改为循环遍历，我们需要再次修改一下vnode的结构，为了向React表示敬意，我们使用fiber这个名称

js
function createFiber(type, props, children) {
    let vnode = {
        type,
        props,
        key: props.key,
        $el: null,
    }
    let firstChild
    vnode.children = children.map((child, index) => {
        // ...处理文本节点

        child.$parent = vnode // 每个子节点保存对父节点的引用
        if (!firstChild) {
            vnode.$child = child // 父节点保存对于第一个子节点的引用
        } else {
            firstChild.$sibling = child // 保存对于下一个兄弟节点的引用
        }
        firstChild = child
        return child
    })
    return vnode
}

我们在vnode的基础上增加了$child（第一个子节点）和$sibling（右侧第一个兄弟节点）两个属性，此外$parent仍旧表示对父节点的引用，基于这三个属性，我们可以将vnode树转换成一个链表，从而就可以将树的递归遍历修改为链表的循环遍历。

diff ​

处于同样的策略，我们将整个diff过程分为了diff遍历节点收集变化和doPatch将变化更新到视图上两个过程。

将递归修改为循环 ​

有了$child、$sibling和$sibling，我们就可以通过循环的方式来遍历链表。为了简化代码，我们为fiber增加一个oldFiber的属性，保持对上一次旧节点的引用。

js
function diff(oldFiber, newFiber) {
    newFiber.oldFiber = oldFiber
    let cursor = newFiber // 当前正在进行diff操作的节点
    let patches = []

    while (cursor) {
        cursor = performUnitWork(cursor, patches)
    }

    return patches
}

需要注意的是，在单次performUnitWork中仅会完成一个节点的diff工作

js
function performUnitWork(fiber, patches) {
    let oldFiber = fiber.oldFiber

    // 任务一：对比当前新旧节点，收集变化
    diffFiber(oldFiber, fiber, patches)
    // 任务二：为新节点中children的每个元素找到需要对比的旧节点，设置oldFiber属性，方便下个循环继续执行performUnitWork
    diffChildren(oldFiber && oldFiber.children || [], fiber.children, patches)

    // 将游标移动至新vnode树中的下一个节点，以
    // (div, {}, [
    //     (h1, {}, [text]), 
    //     (ul, {}, [
    //         li1, li2,li3
    //     ])]
    // ]) 为例，整个应用的的遍历流程是 
    // div -> h1 ->  h1(text) -> h1 -> ul ->li1 -> li2 -> li3 -> ul -> div

    // 上面的diffFiber就是遍历当前节点
    // 有子节点继续遍历子节点
    if (fiber.$child) return fiber.$child
    while (fiber) {
        // 无子节点但是有兄弟节点，继续遍历兄弟节点
        if (fiber.$sibling) return fiber.$sibling
        // 子节点和兄弟节点都遍历完毕，返回父节点，开始遍历父节点的兄弟节点，重复该过程
        fiber = fiber.$parent;
        if (!fiber) return null
    }
    return null
}

diffFiber与递归diff的diff方法很相似，用于对比两个节点

js
function diffFiber(oldNode, newNode, patches) {
    if (!oldNode) {
        // 当前节点与其子节点都将插入
        patches.push({ type: INSERT, newNode })
    } else {
        // 如果存在有变化的属性，则使用新节点的属性更新旧节点
        let attrs = diffAttr(oldNode.props, newNode.props) // 发生变化的属性
        if (Object.keys(attrs).length > 0) {
            patches.push({ type: UPDATE, oldNode, newNode, attrs })
        }

        // 节点需要移动位置
        if (oldNode.index !== newNode.index) {
            patches.push({ type: MOVE, oldNode, newNode })
        }
        newNode.$el = oldNode.$el // 直接复用旧节点
        // 继续比较子节点
    }
}

略有差别的diffChildren ​

对于diffChildren而言，我们在递归diff中已经研究了一些不同的diff策略，最终选择了结合key与type的方式尽可能地复用DOM节点，此处的diff逻辑不需要改动。

唯一的区别在于，我们现在不需要在diffChildren中递归调用diff方法，仅仅为新节点找到并绑定需要diff的旧节点即可，至于具体的diff，我们将在下一次performUnitWork中执行

js
// 根据type和key来进行判断，避免同类型元素顺序变化导致的不必要更新
function diffChildren(oldChildren, newChildren, patches) {
    newChildren = newChildren.slice() // 复制一份children，避免影响父节点的children属性
    // 找到新节点列表中带key的节点
    let keyMap = {}
    newChildren.forEach((child, index) => {
        let { key } = child
        // 只有携带key属性的会参与同key节点的比较
        if (key !== undefined) {
            if (keyMap[key]) {
                console.warn(`请保证${key}的唯一`, child)
            } else {
                keyMap[key] = {
                    vnode: child,
                    index
                }
            }
        }
    })

    // 在遍历旧列表时，先比较类型与key均相同的节点，如果新节点中不存在key相同的节点，才会将旧节点保存起来
    let typeMap = {}
    oldChildren.forEach(child => {
        let { type, key } = child
        // 先比较类型与key均相同的节点
        let { vnode, index } = (keyMap[key] || {})
        if (vnode && vnode.type === type) {
            newChildren[index] = null // 该节点已被比较，需要弹出
            delete keyMap[key]
            vnode.oldFiber = child
        } else {
            // 将剩余的节点保存起来，与剩余的新节点进行比较
            if (!typeMap[type]) typeMap[type] = []
            typeMap[type].push(child)
        }
    })

    // 此时key相同的节点已被比较
    for (let i = 0; i < newChildren.length; ++i) {
        let cur = newChildren[i]
        if (!cur) continue; // 已在在前面与此时key相同的节点进行比较
        if (typeMap[cur.type] && typeMap[cur.type].length) {
            let old = typeMap[cur.type].shift()
            cur.oldFiber = old
        } else {
            cur.oldFiber = null
        }
    }

    // 剩余未被使用的旧节点，将其移除
    Object.keys(typeMap).forEach(type => {
        let arr = typeMap[type]
        arr.forEach(old => {
            patches.push({ type: REMOVE, oldNode: old, })
        })
    })
}

可以看见在上面的过程中，与递归diff的diffChildren基本相同，区别自安于我们只是伪新节点找到并赋值了oldFiber，并没有递归调用diffFiber方法。

完全相同的doPatch ​

在整个diff过程结束后，我们同样需要将收集的patches更新到视图上，由于path本身与diff或者是循环无关，我们甚至不需要修改递归diff算法中doPatch的任何代码。

下面是利用循环diff实现的页面初始化和视图更新的测试代码，从使用方的角度看起来跟递归diff并没有什么差别。

js
let root = createRoot({
    title: 'hello fiber',
    list: [1, 2, 3]
})

root.$parent = {
    $el: app
}

// 初始化
let patches = diff(null, root)
doPatch(patches)

btn.onclick = function () {
    let root2 = createRoot({
        title: 'title change',
        list: [1, 2, 3]
    })

    let patches = diff(root, root2)
    console.log(patches) // title text标签发生了变化
    doPatch(patches) // 更新视图
}

暂停与恢复diff ​

思考 ​

在此之前，我们接触到的diff流程都是同步进行的。循环diff比递归diff最大的就是：可以在某个时刻暂停diff过程!!!

回头重新看一下diff方法中的核心代码

js
while (cursor) {
    cursor = performUnitWork(cursor, patches)
}
// 我们将该方法重命名为diffSync，表示同步循环执行diff流程

为了方便判断循环在何时暂停，我们增加一个shouldYeild方法

js
while (cursor && shouldYeild()) {
    cursor = performUnitWork(cursor, patches)
}

在每次循环结束后中，都会重新调用shouldYeild方法判断是否需要暂停循环，这样，我们就可以将整个diff流程按时间进行切片，当单个切片循环用时到期，就暂停整个循环，并在合适的时候从cursor开始继续循环，直到整个链表遍历完毕。这里我们需要考虑如下几个问题

  • 如何对整个diff过程按按时间切片，一个切片的占用多少时间更合适？
  • 在什么时机重新恢复循环继续diff过程？
  • 在暂停期间，数据可能又发生了变动，导致我们需要重新更新视图，这种时候，我们需要抛弃cursor，重新从根节点开始diff过程

我们需要实现一个简易的调度机制处理这些问题，

  • 调度器需要告诉diff流程是否应该暂停，这里需要实现上面的shouldYeild方法
  • diff流程应该告诉调度器是否已经执行完毕，我们在diff流程被中断的时候同时传输当前状态给调度器
  • 调度器需要在合适的时候继续执行diff流程，可以使用定时器或requestAnimationFrame、requestIdleCallback等方案来实现

基于上面的整理，我们开始编写代码，首先是shouldYield方法

js
// 默认1秒30帧运行，即一个切片最多运行的时间
const frameLength = 1000 / 30

let frameDeadline // 当前切片执行时间deadline，在每次执行新的切片时会更新为getCurrentTime() + frameLength

function getCurrentTime() {
    return +new Date()
}
function shouldYield() {
    return getCurrentTime() > frameDeadline
}

这样我们就解决了上面的第一个问题：调度器需要告诉diff流程是否应该暂停。

然后我们为调度器暴露一个注册diff任务的接口scheduleWork，该方法接受一个diff任务的切片，并根据该切片的返回值判断diff任务是否指向完毕，为true则表示有未完成的diff任务，需要调度器继续管理并在合适的时候继续执行下一个diff切片。

js
let scheduledCallback
function scheduleWork(workLoop) {
    scheduledCallback = workLoop
    
    // TODO 我们需要在这里实现任务调度的相关逻辑，在每个切片内，更新当前切片的frameDeadline，执行切片的diff任务
    // 大致伪代码如下
    // frameDeadline = getCurrentTime() + frameLength
    // if(scheduledCallback()){
    //     // 继续注册下一个执行切片的任务
    // }
}

可以看见，我们在这里约定了scheduleWork注册的任务workLoop会返回一个bool值，这样就能够解决上面的第二个问题：diff流程应该告诉调度器是否已经执行完毕。

最后，我们重写diff，在内部scheduleWork注册diff任务，完成整个逻辑

js
// 现在diff过程变成了异步的流程，因此只能在回调函数中等待
function diff(oldFiber, newFiber, cb) {
    newFiber.oldFiber = oldFiber
    // 当前正在进行diff操作的节点
    let cursor = newFiber
    let patches = []
    // workLoop可以理解每个切片需要执行的diff任务
    const workLoop = () => {
        while (cursor) {
            // shouldYield在每diff完一个节点之后都会调用该方法，用于判断是否需要暂时中断diff过程
            if (shouldYield()) {
                // workLoop返回true表示当前diff流程还未执行完毕
                return true
            } else {
                cursor = performUnitWork(cursor, patches)
            }
        }
        // diff流程执行完毕，我们可以使用收集到的patches了
        cb(patches)
        return false
    }
    // 将diff流程进行切片，现在只能异步等待patches收集完毕了
    scheduleWork(workLoop)
}

可以看见，任务切片workLoop通过闭包维持了对cursor节点的引用，因此下次diff可以直接从上一次的暂停点继续执行。由于现在diff流程可能被中断，因此我们需要通过回调的方式在diff流程结束之后再使用整个流程收集到的patches，所以diff函数签名变成了diff(oldFiber, newFiber, cb)

接下来我们回到scheduleWork中，研究实现调度任务切片的方法，解决第三个问题。在这里，我们可以回头思考一下diff流程的意义：

  • diff新旧节点树，找到整个视图的变化，最后统一将变化更新到页面上
  • 在长时间的diff流程下浏览器会卡死，因此我们将整个流程进行切割，每次仅执行一部分diff工作，然后将控制权交给浏览器，那么问题来了：
    • 对于某些变化，我们希望尽快地diff完毕并更新到页面上，如动画、用户交互等
    • 对于某些变化，我们希望不会影响现有浏览器现有的动画和交互等，因此希望在浏览器空闲时再执行diff工作

我们暂且将变化分为两种类型：高优先级和低优先级。所幸的是，浏览器恰好提供了两个API

基于这两个接口，我们可以实现对应的调度策略。

requestAnimationFrame ​

首先来看看requestAnimationFrame

js
function onAnimationFrame() {
    if (!scheduledCallback) return;
    // 更新当前diff流程的deadline，保证任务最多执行frameLength的时间
    frameDeadline = getCurrentTime() + frameLength;

    // 在每一帧中执行注册的任务workLoop
    // 在workLoop的每次循环中都会调用shouldYield，如果当前时间超过frameDeadline时，就会暂停循环并返回true
    const hasMoreWork = scheduledCallback();
    // 根据workLoop返回值判断当前diff是否已经执行完毕
    if (hasMoreWork) {
        // 注册回调，方便下一帧更新frameDeadline，继续执行diff任务，直至整个任务执行完毕
        // 由于workLoop通过闭包维持了对于cursor当前遍历的节点的引用，因此下次diff可以直接从上一次的暂停点继续执行
        requestAnimationFrame(nextRAFTime => {
            onAnimationFrame();
        });
    } else {
        // 如果已经执行完毕，则清空
        scheduledCallback = null;
    }
}

需要注意的是，由于标签页在后台时会暂停requestAnimationFrame，会导致整个diff过程暂停，显然这并不是我们想要的，这种情况下我们可以使用定时器setTimeout来预防一下

js
// 由于标签页在后台时会暂停`requestAnimationFrame`，这也会导致整个diff过程暂停，可以使用定时器来处理这个问题
// 如果过了在某段时间内没有执行requestAnimationFrame，则会通过定时器继续注册回调
let rAFTimeoutID = setTimeout(() => {
    onAnimationFrame()
}, frameLength * 2);

requestAnimationFrame(nextRAFTime => {
    clearTimeout(rAFTimeoutID) // 当requestAnimationFrame继续执行时，移除
    onAnimationFrame();
});

requestIdleCallback ​

我们也可以使用requestIdleCallback来实现低优先级的调度策略

js
// 通过requestIdleCallback注册，在浏览器的空闲时间时执行低优先级工作，这样不会影响延迟关键事件，
// 通过timeout参数可以控制每次占用的调用的时长
function onIdleFrame(deadline) {
    if (!scheduledCallback) return;
    let remain = deadline.timeRemaining()// 当前帧剩余可用的空闲时间
    frameDeadline = getCurrentTime() + Math.min(remain, frameLength) // 限制当前任务切片的执行deadline

    const hasMoreWork = scheduledCallback();
    if (hasMoreWork) {
        requestIdleCallback(onIdleFrame, { timeout: frameLength })
    } else {
        // 如果已经执行完毕，则清空
        scheduledCallback = null
    }
}

由于deadline.timeRemaining可以很方便地获得当前帧的剩余时间，用来更新frameDeadline貌似很不错。最后，我们来补全scheduleWork方法

js
function scheduleWork(workLoop) {
    scheduledCallback = workLoop
    // 注册diff任务，我们可以采用下面这两种策略来进行进行调度
    // requestAnimationFrame(onAnimationFrame)
    requestIdleCallback(onIdleFrame)
}

由于篇幅和主题的关系，本文不会涉及如何区分变化的优先级，只研究在这高低优先级两种变化下如何调度diff任务。

测试 ​

貌似已经大功告成了~我们写点代码来测试下。

js
function testSchedule() {
    // ...为了节省篇幅，下面代码省略了root和root2节点的初始化
    // 现在需要在回调函数中等待diff执行完毕
    let isInit = false
    diff(null, root, (patches) => {
        doPatch(patches)
        isInit = true
    })
    btn.onclick = function () {
        if (!isInit) {
            console.log('应用暂未初始化完毕，请稍后重试...')
            return
        }

        diff(root, root2, (patches) => {
            console.log(patches)
            doPatch(patches)
            root = root2
        })
    }
}

在整个过程中，diff方法是异步的，但doPatch并没有任何改动（基于这个原因，我更倾向于将diff和doPatch过程分开），当收集到全部变化之后，我们会同步地将整个变化更新到视图上。

当旧节点root和新节点root2进行diff时，当结构比较简单时，在一帧内就完成了整个diff，效果就会与diffSync相同；当结构比较复杂或单个diff节点的耗时很长时，我们就能看见明显的差别，为了便于测试，编写一个阻塞JS运行的同步函数，用于增加单个diff节点的耗时

js
function sleepSync(time) {
    let now = + new Date()
    while (now + time > +new Date()) { }
}

由于我们默认设置的1秒30帧，表示一个切片可以执行的时间是33.33ms，因此我们使用sleepSync控制一个切片只能执行一个节点的diff

js
// diffSync
while (cursor) {
    sleepSync(33.33)
    cursor = performUnitWork(cursor, patches)
}

// diff
const workLoop = () => {
    while (cursor) {
        if (shouldYield()) {
            return true
        } else {
            sleepSync(33.33) // 保证每一帧只能diff一个节点
            cursor = performUnitWork(cursor, patches)
    }
}

可以看见在diffSync中，在整个diff过程中，浏览器会处于卡死的状态，但在diff中，就不会存在这个问题。

此外，虽然更新任务存在高优先级可低优先级之分，但初始化任务我们往往希望用户能够尽快看见页面，因此在初始化时，调用diffSync是更合理的做法

重置diff ​

在diffSync中，整个diff和doPatch过程都是同步的，因此数据的变化将在该过程结束后直接更新到视图上。

在调度器介入后，情况变得不一样了。如果在diff暂停时数据重新发生了变化，我们应该如何处理呢？

假设原始节点root，还未完成diff过程的新节点root2，此时数据又发生了变化对应的新节点root3，我们有下面两种处理方案

  • 方案一，继续等待diff(root, root2)执行完毕，然后再对比diff(root2, root3)
  • 方案二，直接抛弃root2,从头开始进行diff(root, root3)

很显然，当新数据对应的节点树变成了root3，那么root2作为中间状态，本身就没有再展示的必要性了，如果重新执行diff(root2, root3)，性能上来说并不是一件十分划算的事情，因此我觉得最好的办法还是直接使用方案二：重新重头重新diff整个节点，尽管这看起来也是一件效率比较低下的事情。

我们通过currentRoot保存本地diff新的根节点，如果上一个diff任务尚未完成，但是又调用了新的diff，则会取消上一次在调度器中注册的任务，重新执行本次的diff

js
let currentRoot // 保存当前diff过程新的根节点，判断是否需要重置diff流程
function diff(oldFiber, newFiber, cb) {
    // 表示前一个diff任务尚未结束，但又调用了新的diff与原来的oldFiber进行对比
    if (currentRoot && currentRoot !== newFiber) {
        cancleWork()
    }
    currentRoot = newFiber // 记录
    // ...
    const workLoop = () => {
        // ...
        currentRoot = null // 重置
    }
    scheduleWork(workLoop)
}

// 取消之前注册的diff任务
function cancleWork() {
    scheduledCallback = null
}

下面是测试思路

js

// diff1
diff(root, root2, (patches) => {
    console.log('normal patches', patches)
    root = root2
})

// 在上面diff还未结束时，数据又发生了变化
setTimeout(() => {
    diff(root, root3, (patches) => {
        console.log('timer patches', patches)
        doPatch(patches)
        root = root3
    })
}, 1)
// diff(root, root2)尚未结束，又调用了diff(root, root3)，就会抛弃上一次diff，从根节点重新执行diff

小结 ​

当应用比较庞大时，我们不得不考虑diff过程带来的性能损耗。本文首先在createVNode方法上，为vnode扩展了一些引用属性，包括$child、$sibling，从而将vnode树转换为链表，通过循环链表的方式遍历整个应用。

对于整个循环diff的流程

  • 我们通过shouldYeild方法，实现了暂停循环；
  • 通过对diff任务优先级考虑的需求，通过requestAnimationFrame和requestIdleCallback实现了注册和恢复diff任务
  • 通过workLoop的返回值，通知调度器当前diff是否执行完毕
  • 通过currentRoot保存当前diff节点，判断是否需要取消上一次diff并重新重头执行diff任务

上一篇文章VNode与递归diff是对于Vue源码的一些理解，本文可以算作是对于React源码的一些理解。实际上diff过程性能优化不少，如提供shouldComponentUpdate等接口，在下一篇文章中，将介绍如何通过vnode构建组件及使用组件构建应用，到时候再进一步研究。

#React #diff

你要请我喝一杯奶茶？

版权声明：自由转载-非商用-保持署名和原文链接。

本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。