Some ideas

[yisar]

1. diff 算法

我研究了许久，感觉实现一个更好的 diff 确实很困难，得益于链表的数据结构，实在是太坑了

我已经放弃实现 最长递增子序列 的算法了，现在我想试试两端遍历，但也不一定能行，大约就这周开始研究

之前我研究了基于 LIS 的 O(nlgon) 的算法，这个算法非常好，inferno，ivi，vue3 都使用了这个算法

https://github.com/localvoid/ivi/blob/master/packages/ivi/src/vdom/reconciler.ts#L585

它可以做到最短编辑距离，但它的复杂度并不是线性的，将它用到 fre 这种链表的结构中，可能会有更多情况命中最坏的分支

两端遍历是个好方式，它的复杂度是 O(n)，这对 fre 来说会合适，但将它用于链表仍旧十分困难

https://github.com/Polymer/lit-html/blob/master/src/directives/repeat.ts#L141

我需要时间去研究

2. Fiber 协程

我这阵子研究了协程的几种实现，我认为之所以使用 Fiber，目的是在用户态实现协程，而不是语言级别 async/await 语法糖

我想重构 Fiber 模型，然后研究新的协程模型，目标和 react 不一样，我们是研究无感的协程，而不是用一堆 Suspense useTransition 来实现，当然，react 的总体思路是对的，只是我们需要找到更少的 API

https://github.com/bikeshaving/crank

crank 很有意思，但它不适用于 Fiber，我们衡量是否适合 Fiber 的标准是，是否会对时间切片造成影响，是否会对浏览器造成阻塞

同样的，我还在思考，思考一种最无感的协程模型

[yisar]

新的 diff 算法已经实现

接下来我要对代码进行一些重构和简化：

1. 重构 h 函数

主要是为了解决 Fragment/render-array 以及 nested-array 的场景

合并简单节点在保证复杂度为 O(n) 的前提下仍然需要

2. 重构 commitWork 为递归

根据我的研究，diff 算法的 runtime 性能在于预处理的命中率以及基于 vm 的性能优化

重构为递归，有机会引入尾递归的优化，减少堆栈的浪费

这一点在 fre 中非常绝望，主要是现在的 fre 使用 commitQueue 数组来装载 commit 操作，当操作变多就会爆栈

过去 react 使用 effectList，利用链表的特性减少堆栈的使用，但它已经被移除了

facebook/react#19673

3. Component 对应的真实 dom

render array 的时候，Component 对应的真实 dom 到底是啥，初步考虑使用 DocumentFragment