精读 Immutable 结构共享

[ascoders]

本期精读的文章是：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 精读

本精读由 rccoder 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

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