关于初期的性能优化(on early optimizations)

[tiye]

此前关于 Nim 版本的 ternary-tree 的介绍在:

• Ternary-tree: 不可变数据结构复用的一个尝试
• 关于 ternary-tree 不可变数据结构复用方案的一些解释

切换到 ts 之后, 在 calcit-runner 和 Respo/respo.calcit 当中尝试, 还是明显发现了一些问题, 并且做了一些优化. 粗略列举有:

• 内部的 hashing 策略, equality detection 策略, 需要外部定制.
• arguments spreading 的性能问题, 以及 arrayMode 优化.
• hash 函数性能问题, 和缓存方案.
• 函数的 hash 问题, 临时解决方案.
• Option<T> 类型的移除.
• iterator 语法跟 Array 相关的性能问题.
• repso.calcit 本身的性能优化问题, 以及 cljs 的性能优化.

早一点截的性能结果:

当前的性能结果(从时间看有一些提升):

内部的 hashing 策略, equality detection 策略, 需要外部定制.

之前 Nim 版本, 因为 method syntax 本身就有多态的功能, 从类库的外部定义对应的 proc hash(x: ...): Hash 就能够对 hash 计算方式进行扩展, 所以当时没多想. 到 js 这边没有动态了, 因为 ternary-tree 本身没有抽象成 class... 所以只能用 mutable 的方案支持从外部修改 hash 的函数, 对于 equality 也类似. 应该本身和性能问题不相关.

https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L1625-L1695
https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L431-L536

arguments spreading 的性能问题, 以及 arrayMode 优化.

用 CrDataList 实现的 list, 导致 args spreading 不顶用了, 函数定义中的 spreading, 函数调用中的 spreading, 所以无奈增加了 listToArray arrayToList 来转换, 继而发现转换本身增加了性能瓶颈.

https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L1595-L1608

于是想到一个歪招, 就是 CrDataList 初始化的时候暂时存 Array, 而不是直接转化到 ternary-tree 的结构, 这样如果只是读取, 遇到 Array 的地方直接从 Array 读取, 性能就很快了. 以及相关的函数都支持一下.

https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L79-L102

其中, 对于 list 的操作, first rest 在 Lisp 语言当中尤为普遍. 实际运行 Profiler 发现 rest 当中的性能问题比较明显, 然后我当时采取的办法是把 rest 改成了 Array.slice, 结果从 Profiler 看好像更快了? 这个结果有点意外, 当然 rest 内部首先初始化 TernaryTreeList 本身性能肯定是有不少开销的, 大致可以解释, 但也可以相对 V8 对 js 的优化很可能是比较深入的从而提升了 slice 的性能.

我考虑后续对 slice 再做一下特殊的优化. 基于不可变数据结构, 特殊的地方在于数据不会修改, 那么, 一个 slice 也就是同一份原始的 Array 的不同的截取, 数据一样. fromIndex 和 endIndex, 不一样, 这个算是特殊的场景可以优化, 而且能插入到当前的实现当中.

hash 函数性能问题, 和缓存方案.

代码当中的发现 hash 会有重复计算, 我想到一个脏的方案, 就是比如 keyword 出一个 CrDataKeyword 对象, 我就增加一个 cachedHash, 字段, 由于是不可变数据, 一次计算 hash 之后就是值对应的 Hash 了, 所以道理上讲应该是足够的.

https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L1636-L1643

函数的 hash 问题, 临时解决方案.

函数怎么计算 Hash 就是有点尴尬的事情了. Nim 里边可以获取到内存地址, 那么通过内存地址做 Hash 算是一个办法, 但是 js 里边就获取不到内存地址了. 稍微尝试了一下用 Function.toString 来生成 Hash, 但是转念一想, 我的尾递归调用就已经是高阶函数了, 处理过以后 toString 都一样的, 这个 Hash 方案已经失效了. 这样就想不好什么靠谱的方案了.

当前临时弄了一个是每个函数生成 cachedHash 字段, 然后在函数上存住...
https://github.com/calcit-lang/calcit-runner/blob/master/src/includes/calcit.procs.ts#L1655-L1660

也不清楚 ClojureScript 具体实现啥样子.

Option<T> 类型的移除.

原本 Nim 的版本当中用到了 Option 类型来模拟 Haskell Maybe 的效果, 然后在 Profiler 当中发现 .get 还有不少的垃圾回收的开销, 无奈还是去掉算了, 因为 Option 用 JavaScript 模拟的话就会生成对象, 每次生成对象的话性能开销就多了. 去掉的话影响倒是不大, 就是不能直接(要间接...)区分 nil 和数据不存在的情况了.
https://nim-lang.org/docs/options.html

iterator 语法跟 Array 相关的性能问题.

遍历 List, 遍历 HashMap 的操作. 两种思路:

• 用函数递归把树的节点抓取出来, 写入一个 mutable Array, 返回.
• 用 yield 语法, JavaScript 支持递归 yield, 可以直接构造出来迭代器.

此前 Nim 当中不支持 nested iterator, 所以后边这个方案是没尝试过的, 从思路上讲 yield 就比较顺了, 而且应该更快一些.
https://github.com/calcit-lang/ternary-tree.ts/blob/master/src/map.ts#L943-L957
然而试用的时候发现 iterator 性能反而不如通过 Array 直接拿到来得快? 挺奇怪的. 不知道是不是 generator function 内部的性能因素影响到.

Map merge 的性能问题

https://github.com/calcit-lang/ternary-tree.ts/blob/master/src/map.ts#L1016-L1030

当前版本的 Profiling 结果, Map 的 assoc 操作是有明显性能开销的. 定位到是 merge 函数. 当前的代码实现当中, merge 内部是多次 assoc 然后实现的, 确实会产生一些节点然后马上又被 GC 回收掉, 合理的方式是专门写个 merge 的操作函数, 避免掉中间无谓的 GC. 我大致有两个思路:

• 专门的 merge 函数, 通过传递多个 key/value 做 assoc, 减少中间过程的节点.
• 列表化的 merge, 相当于 buffer 的思路吧... merge 的时候不直接合并, 只是用数组存储多个 Map, 查询的时候逐次在多个 Map 上查询. get 操作有性能影响, 但 merge 操作开销降低. 另外在数量到 5 左右再真的执行 merge.

两个看起来不冲突, 打算都试试看, 看实现的进度决定做成什么样.

repso.calcit 本身的性能优化问题, 以及 cljs 的性能优化.

试验的 demo 当中 Respo Calcit 迁移过来以后有些问题, 就是 render 函数通过 memoization 做部分优化的策略失效了, 具体是 macro 结构改变, render 函数引用不稳定了. 还得后续想想办法.

另外就是 ternary-tree 虽然部分借鉴了 cljs 的优化, 但是 cljs 的优化细节和深度明显就多很多, 我的了解也挺散碎的, 这边的优化明显没有到那么深. 特别是相关的 PersistentHashMap 的优化, 后续大概率还是要借鉴的.