react diff算法

框架

浏览数:230

2019-6-22

AD:资源代下载服务

一、react diff算法

  1. diff算法的作用
    计算出Virtual DOM中真正变化的部分,并只针对该部分进行原生DOM操作,而非重新渲染整个页面。
  2. 传统diff算法
    通过循环递归对节点进行依次对比,算法复杂度达到 O(n^3) ,n是树的节点数,这个有多可怕呢?——如果要展示1000个节点,得执行上亿次比较。。即便是CPU快能执行30亿条命令,也很难在一秒内计算出差异。

备注:传统算法的复杂度计算方法有兴趣可以参考如下地址:https://grfia.dlsi.ua.es/ml/a…

  1. React的diff算法(React16以下版本)
    (1)什么是调和?

    将Virtual DOM树转换成actual DOM树的最少操作的过程 称为 调和 。

    (2)什么是React diff算法?

     diff算法是调和的具体实现。diff算法的本质是对传统tree遍历算法的优化

    (3)diff策略

     React用 三大策略 将O(n^3)复杂度 转化为 O(n)复杂度

    策略一(tree diff):

      Web UI中DOM节点跨层级的移动操作特别少,可以忽略不计。

    策略二(component diff):

      拥有相同类的两个组件 生成相似的树形结构,
      拥有不同类的两个组件 生成不同的树形结构。

    策略三(element diff):

      对于同一层级的一组子节点,通过唯一id区分。
      

    tree diff
    (1)React通过updateDepth对Virtual DOM树进行层级控制。
    (2)对树分层比较,两棵树 只对同一层次节点 进行比较。如果该节点不存在时,则该节点及其子节点会被完全删除,不会再进一步比较。
    (3)只需遍历一次,就能完成整棵DOM树的比较。

如下图所示:

那么问题来了,如果DOM节点出现了跨层级操作,diff会咋办呢?
答:diff只简单考虑同层级的节点位置变换,如果是跨层级的话,只有创建节点和删除节点的操作。

如上图所示,以A为根节点的整棵树会被重新创建,而不是移动,因此 官方建议不要进行DOM节点跨层级操作,可以通过CSS隐藏、显示节点,而不是真正地移除、添加DOM节点。

component diff
React对不同的组件间的比较,有三种策略
(1)同一类型的两个组件,按原策略(层级比较)继续比较Virtual DOM树即可。
(2)同一类型的两个组件,组件A变化为组件B时(A、B类型相同、结构相同),可能Virtual DOM没有任何变化,如果知道这点(变换的过程中,Virtual DOM没有改变),可节省大量计算时间,所以 用户 可以通过 shouldComponentUpdate() 来判断是否需要 判断计算。
(3)不同类型的组件,将一个(将被改变的)组件判断为dirty component(脏组件),从而替换 整个组件的所有节点。
注意:如果组件D和组件G的结构相似,但是 React判断是 不同类型的组件,则不会比较其结构,而是删除 组件D及其子节点,创建组件G及其子节点。

element diff
当节点处于同一层级时,diff提供三种节点操作:删除、插入、移动。

插入:组件 C 不在集合(A,B)中,需要插入

删除:
(1)组件 D 在集合(A,B,D)中,但 D的节点已经更改,不能复用和更新,所以需要删除 旧的 D ,再创建新的。
(2)组件 D 之前在 集合(A,B,D)中,但集合变成新的集合(A,B)了,D 就需要被删除。

移动:组件D已经在集合(A,B,C,D)里了,且集合更新时,D没有发生更新,只是位置改变,如新集合(A,D,B,C),D在第二个,无须像传统diff,让旧集合的第二个B和新集合的第二个D 比较,并且删除第二个位置的B,再在第二个位置插入D,而是 (对同一层级的同组子节点) 添加唯一key进行区分,移动即可。

重点说下移动的逻辑:
情形一:新旧集合中存在相同节点但位置不同时,如何移动节点
移动1、

(1)看着上图的 B,React先从新中取得B,然后判断旧中是否存在相同节点B,当发现存在节点B后,就去判断是否移动B。
B在旧的节点中的index=1,它的lastIndex=0,不满足 index < lastIndex 的条件,因此 B 不做移动操作。此时,一个操作是,lastIndex=(index,lastIndex)中的较大数=1.
注意:lastIndex有点像浮标,或者说是一个map的索引,一开始默认值是0,它会与map中的元素进行比较,比较完后,会改变自己的值的(取index和lastIndex的较大数)。
(2)看着 A,A在旧的index=0,此时的lastIndex=1(因为先前与新的B比较过了),满足index<lastIndex,因此,对A进行移动操作,此时lastIndex=max(index,lastIndex)=1。
(3)看着D,同(1),不移动,由于D在旧的index=3,比较时,lastIndex=1,所以改变lastIndex=max(index,lastIndex)=3
(4)看着C,同(2),移动,C在旧的index=2,满足index<lastIndex(lastIndex=3),所以移动。
由于C已经是最后一个节点,所以diff操作结束。

情形二:新集合中有新加入的节点,旧集合中有删除的节点

移动2、

(1)B不移动,不赘述,更新l astIndex=1
(2)新集合取得 E,发现旧不存在,故在lastIndex=1的位置 创建E,更新lastIndex=1
(3)新集合取得C,C不移动,更新lastIndex=2
(4)新集合取得A,A移动,同上,更新lastIndex=2
(5)新集合对比后,再对旧集合遍历。判断 新集合 没有,但 旧集合 有的元素(如D,新集合没有,旧集合有),发现 D,删除D,diff操作结束。

diff的不足与待优化的地方

移动3、

看图的 D,此时D不移动,但它的index是最大的,导致更新lastIndex=3,从而使得其他元素A,B,C的index<lastIndex,导致A,B,C都要去移动。
理想情况是只移动D,不移动A,B,C。因此,在开发过程中,尽量减少类似将最后一个节点移动到列表首部的操作,当节点数量过大或更新操作过于频繁时,会影响React的渲染性能。

二、 React Fiber(React16版本)
引言:
diff算法相对传统算法已经是比较高效的计算机制了,但是人总是要有追求,三年前左右react就发现了reconciliation的一个潜在问题,就是在对比两颗树的时候,花费的时间太长,可能导致浏览器假死,所以就启动了一个项目来重写reconciliation,那就是react fiber.

为什么?
这里不得不提浏览器的渲染机制,现在基本上公认的是60fps,也就是说浏览器会在每秒内渲染60次,也就是基本上16.7ms渲染一次。
(为什么是60fps呢,这里和硬件的刷新频率有关系,有兴趣的可以查下)
基本渲染流程如下
1,执行js
2,样式计算
3,计算布局,执行
4,pait,绘制各层
5,合成各层的绘制结果,呈现在浏览器上。
所以基本上就是在16.7ms内执行完这些操作,就是比较完美的啦,但是事情不可能这么完美,比如如果js代码执行时间特别长的话,一直在等你的js执行完之后,才会去渲染,页面就是一直空白。

1、 React从版本16开始弃用diff算法,改为Fiber渲染方式进行组件差异化比较

旧版的diff算法是递归比较,对virtural dom的更新和渲染是同步的。就是当一次更新或者一次加载开始以后,virtual dom的diff比较并且渲染的过程是一口气完成的。如果组件层级比较深,相应的堆栈也会很深,长时间占用浏览器主线程,一些类似用户输入、鼠标滚动等操作得不到响应。造成线程柱塞,因此React官方改变了之前的Virtual Dom的渲染机制,新架构使用链表形式的虚拟 DOM,新的架构使原来同步渲染的组件现在可以异步化,可中途中断渲染,执行更高优先级的任务。释放浏览器主线程。

我们使用两张图来区分两种算法之间的区别

这个就是以前的diff算法渲染图:

当所有的事情都等待reconciliation结束的时候,可能有其他更高级别的功能需求进来,比如用户点击输入框,或者是点击按钮等操作,但是由于还在执行,就会就一直卡住,让用户认为页面在假死。
所以最好的办法,也是用的最多的办法,不管是在计算机系统还是哪里,那就是分片,我借了你的东西,我用一段时间,就得过来就还给你,等你用完了之后,我再过来借一次,好借好还,再借不难。

这个是新的Fiber渲染机制:


这基本就是react fiber的核心所在!

同时应该说明:React15与React16 两个 DOM 的结构和遍历方式已经完全不同。

2、 算法流程
fiber tree 算法
具体流程和原来的差不多,其实也还是找出两次更新之间的差异,然后渲染到浏览器上面。
fiber会在首次render函数执行完之后,react会保存一份react fiber树,然后会循环利用,不会重复建立,称为current 树。
2,当有setstate或者其他更新的时候,就会根据现在的current树重新生成一份包含变化的树。这里最重要的就是在对比两颗树的过程中是异步的,随时可以中断,恢复,但是当更新的时候是同步的,也就是说 diff 过程中,是异步,commit是同步的。

diff 具体过程
这里就是根据信息,来遍历fibertree树然后找不不同,这里不一样的一点是因为加了很多的指针,类似加了很多直达电梯,节省了很多时间,可以直接到达。
任何一项工作都会有下面几步, 首先获取该在哪里做,然后开始做,再接着就是花时间干完这项工作,最后退出,继续寻找下一步该在哪里工作。
对应关系就是
获取该在哪里做: performUnitOfWork
开始做: beginWork
完成工作: completeUnitOfWork
寻找下一步哪里做: completeWork
所有的函数都在(packages/react-reconciler/src/ReactFiberScheduler.js)
可以看下别人做的效果图

tree的执行顺序: a1-b1-b1完成-b2-c1-d1-d1完成-d2-d2完成-c1完成-b2完成-b3-c2-c2完成-b3完成-a1完成。

fiber 首次 render 的时候,就会调用一次 requestIdeCallback,这个 api 会进行循环
这个循环,它负责变更 current fiber(当前的 fiber 节点) 前面提到,链表天生可以拿到 节点本身,还能拿到父节点,兄弟节点,子节点

唯一要记住的一点就是这里的过程是异步的,随时可能会暂停,或者停止,或者需要恢复过来重新执行。

commit
这里就是同步的了,不过速度也会很快的,因为这里把哪些改变了的fiber node形成了一个链表,如果中间没有更新的话,会快速的跳到下面去。

类似于下图的链表

看一下fiber架构 组建的渲染顺序:
加入fiber的react将组件更新分为两个时期Reconciliation Phase和Commit Phase。Reconciliation Phase的任务干的事情是,找出要做的更新工作(Diff Fiber Tree),就是一个计算阶段,计算结果可以被缓存,也就可以被打断;Commmit Phase 需要提交所有更新并渲染,为了防止页面抖动,被设置为不能被打断。

这两个时期以render为分界,
render前的生命周期为phase1,
render后的生命周期为phase2

phase1的生命周期是可以被打断的,每隔一段时间它会跳出当前渲染进程,去确定是否有其他更重要的任务。此过程,React 在 workingProgressTree (并不是真实的virtualDomTree)上复用 current 上的 Fiber 数据结构来一步地(通过requestIdleCallback)来构建新的 tree,标记处需要更新的节点,放入队列中。
phase2的生命周期是不可被打断的,React 将其所有的变更一次性更新到DOM上。
这里最重要的是phase1这是时期所做的事。因此我们需要具体了解phase1的机制。

PS: componentWillMount componentWillReceiveProps componentWillUpdate 几个生命周期方法,在Reconciliation Phase被调用,有被打断的可能(时间用尽等情况),所以可能被多次调用。其实 shouldComponentUpdate 也可能被多次调用,只是它只返回true或者false,没有副作用,可以暂时忽略。

如果不被打断,那么phase1执行完会直接进入render函数,构建真实的virtualDomTree
如果组件再phase1过程中被打断,即当前组件只渲染到一半(也许是在willMount,也许是willUpdate~反正是在render之前的生命周期),那么react会怎么干呢? react会放弃当前组件所有干到一半的事情,去做更高优先级更重要的任务(当然,也可能是用户鼠标移动,或者其他react监听之外的任务),当所有高优先级任务执行完之后,react通过callback回到之前渲染到一半的组件,从头开始渲染。(看起来放弃已经渲染完的生命周期,会有点不合理,反而会增加渲染时长,但是react确实是这么干的)

看到这里,相信聪明的同学已经发现一些问题啦~

也就是 所有phase1的生命周期函数都可能被执行多次,因为可能会被打断重来
这样的话,就和react16版本之前有很大区别了,因为可能会被执行多次,那么我们最好就得保证phase1的生命周期每一次执行的结果都是一样的,否则就会有问题,因此,最好都是纯函数。

(所以react16目前都没有把fiber enable,其实react16还是以 同步的方式在做组建的渲染,因为这样的话,很多我们用老版本react写的组件就有可能都会有问题,包括用的很多开源组件,但是后面应该会enable,让开发者可以开启fiber异步渲染模式~)

对了,还有一个问题,饥饿问题,即如果高优先级的任务一直存在,那么低优先级的任务则永远无法进行,组件永远无法继续渲染。这个问题facebook目前好像还没解决,但以后会解决~
所以,facebook在react16增加fiber结构,其实并不是为了减少组件的渲染时间,事实上也并不会减少,最重要的是现在可以使得一些更高优先级的任务,如用户的操作能够优先执行,提高用户的体验,至少用户不会感觉到卡顿~

源码解析:
https://blog.csdn.net/qiqingj…

作者:千里之外