精读 Immutable 结构共享

2,608 阅读5分钟
原文链接: zhuanlan.zhihu.com

本期精读的文章是:Immutable 结构共享是如何实现的

鉴于 mobx-state-tree 的发布,实现了 mutable 到 immutable 数据的自由转换,将 mobx 写法的数据流,无缝接入 redux 生态,或继续使用 mobx 生态。

这是将事务性,可追溯性与依赖追踪特性的结合,同时解决开发体验与数据流可维护性。万一这种思路火了呢?我们先来预热下其重要特征,结构共享。

1 引言

结构共享不仅仅是 “结构共享” 那么简单,背后包含了 Hash maps tries 与 vector tries 结构的支持,如果让我们设计一个结构共享功能,需要考虑哪些点呢?本期精读的文章给了答案。

2 内容概要

使用 Object.assign 作用于大对象时,速度会成为瓶颈,比如拥有 100,000 个属性的对象,这个操作耗费了 134ms。性能损失主要原因是 “结构共享” 操作需要遍历近10万个属性,而这些引用操作耗费了100ms以上的时间。

解决办法就是减少引用指向的操作数量,而且由于引用指向到任何对象的损耗都几乎一致(无论目标对象极限小或者无穷大,引用消耗时间都几乎没有区别),我们需要一种精心设计的树状结构将打平的引用建立深度,以减少引用操作次数,vector tries 就是一种解决思路:

上图的 key: t0143c274,通过 hash 后得到的值为 621051904(与 md5 不同,比如 hash("a") == 0,hash("c") == 2),转化为二进制后,值是 10010 10000 01001 00000 00000 00000,这个路径是唯一的,同时,为了减少树的深度,按照 5bit 切分,切分后的路径也是唯一的。因此寻址路径就如上图所示。

因此结构共享的核心思路是以空间换时间。

3 精读

本精读由 recoder ascoders cisen BlackGanglion jasonslyvia TingGe twobin camsong 讨论而出,以及我个人的吐血阅读论文原文总结而成。

Immutable 树结构的特性

camsong 的动态图形象介绍一下共享的操作流程:


但是,当树越宽(子节点越多)时,相应树的高度会下降,随之查询效率会提高,但更新效率则会下降(试想一下极限情况,就相当于线性结构)。为寻求更新与查询的平衡,我们便选择了 5bit 一分割。

因此最终每个节点拥有 2^5=32 个子节点,同时通过 Vector trie 和 Hash maps trie 压缩空间结构,使其深度最小,性能最优。

Vector trie

通过这篇文章查看详细介绍

其原理是,使用二叉树,将所有值按照顺序,从左到右存放于叶子节点,当需要更新数据时,只将其更新路径上的节点生成新的对象,没有改变的节点继续共用。

Hash maps trie

Immutablejs 对于 Map,使用了这种方式优化,并且通过树宽与树高的压缩,形成了文中例图中的效果(10010 10000 聚合成了一个节点,并且移除了同级的空节点)。

树宽压缩:

树高压缩:
再结合 Vector trie,实现结构共享,保证其更新性能最优,同时查询路径相对较优。

Object.assign 是否可替代 Immutable?

结构共享指的是,根节点的引用改变,但对没修改的节点,引用依然指向旧节点。所以Object.assign 也能实现结构共享

见如下代码:


const objA = { a: 1, b: 2, c: 3 }
const objB = Object.assign({}, objA, { c: 4 })
objA === objB     // false
objA.a === objB.a // true
objA.b === objB.b // true

证明 Object.assign 完全可以胜任 Immutable 的场景。但正如文章所述,当对象属性庞大时, Object.assign 的效率较低,因此在特殊场景,不适合使用 Object.assign 生成 immutable 数据。但是大部分场景还是完全可以使用 Object.assign 的,因为性能不是瓶颈,唯一繁琐点在于深层次对象的赋值书写起来很麻烦。

Map 性能比 Object.assign 更好,是否可以替代 Immutable?

当一层节点达到 1000000 时,immutable.get 查询性能是 object.key 的 10 倍以上。

就性能而言可以替代 Immutable,但就结合 redux 使用而言,无法替代 Immutable。

redux 判断数据更新的条件是,对象引用是否变化,而且要满足,当修改对象子属性时,父级对象的引用也要一并修改。Map 跪在这个特性上,它无法使 set 后的 map 对象产生一份新的引用。

这样会导致,Connect 了 style 对象,其 backgroundColor 属性变化时,不会触发 reRender。因此虽然 Map 性能不错,但无法胜任 Object.assign 或 immutablejs 库对 redux 的支持。

3 总结

数据结构共享要达到真正可用,需要借助 Hash maps tries 和 vector tries 数据结构的帮助,在上文中已经详细阐述。既然清楚了结构共享怎么做,就更加想知道 mobx-state-tree 是如何做到 mutable 数据到 immutable 数据转换了,敬请期待下次的源码分析(不一定在下一期)。

如何你对原理不是很关心,那拿走这个结论也不错:在大部分情况可以使用 Object.assign 代替 Immutablejs,只要你不怕深度赋值的麻烦语法;其效果与 Immutablejs 一模一样,唯一,在数据量巨大的字段上,可以使用 Immutablejs 代替以提高性能。

讨论地址是:Immutable 结构共享是如何实现的? · Issue #14 · dt-fe/weekly


如果你想参与讨论,请点击这里,每周都有新的主题,每周五发布。