侧边栏

Fiber与循环diff

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

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

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

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

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

本系列文章列表如下

排在后面文章内会大量采用前面文章中的一些概念和代码实现,如createVNodediffChildrendoPatch等方法,因此建议逐篇阅读,避免给读者造成困惑。本文相关示例代码均放在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流程,可以使用定时器或requestAnimationFramerequestIdleCallback等方案来实现

基于上面的整理,我们开始编写代码,首先是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任务优先级考虑的需求,通过requestAnimationFramerequestIdleCallback实现了注册和恢复diff任务
  • 通过workLoop的返回值,通知调度器当前diff是否执行完毕
  • 通过currentRoot保存当前diff节点,判断是否需要取消上一次diff并重新重头执行diff任务

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

你要请我喝一杯奶茶?

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

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