react diff算法

摘要：算法的本质是对传统遍历算法的优化策略用三大策略将复杂度转化为复杂度策略一中节点跨层级的移动操作特别少，可以忽略不计。当节点处于同一层级时，提供三种节点操作删除插入移动。在旧的节点中的，它的，不满足的条件，因此不做移动操作。

一、react diff算法

diff算法的作用
计算出Virtual DOM中真正变化的部分，并只针对该部分进行原生DOM操作，而非重新渲染整个页面。

传统diff算法
通过循环递归对节点进行依次对比，算法复杂度达到 O(n^3) ，n是树的节点数，这个有多可怕呢？——如果要展示1000个节点，得执行上亿次比较。。即便是CPU快能执行30亿条命令，也很难在一秒内计算出差异。

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

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（3）看着D，同（1），不移动，由于D在旧的index=3，比较时，lastIndex=1，所以改变lastIndex=max(index,lastIndex)=3
（4）看着C，同（2），移动，C在旧的index=2，满足index由于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理想情况是只移动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...