写入量 · GC 压力 · 引用相等

结构共享的代价与收益

前面六页都在讲结构共享怎么省。这一页把账反过来算：省下的是什么、没省下什么、以及付出了什么。

1 · 写入量与时间

基准是「10 万元素、1 万次改一格并保留旧版本」。全量复制数组要写 $10^9$ 个格子，persistent vector 新建 39992 个节点，写入量相差 25005 倍。

墙钟时间的差距小得多：125 ms 对 3 ms，38 倍（node v26.8.1）。差三个数量级的原因不难理解——数组复制是连续内存的批量拷贝，现代 CPU 每周期能搬几十字节；树的写入要走 4 层指针、分配 4 个对象、各自复制一个 32 长的数组。单位写入的代价高出一大截，抵掉了大部分数量级优势。

这个 38 倍不该当成常数记。同一段代码在 Chrome 里跑出来是 97 倍，两个引擎对「小对象分配」与「大数组拷贝」的优化侧重不同。图 1-1 每次重算都实跑一遍，读数以当下环境为准；能跨环境成立的只有写入量那一栏。

图 1-1 · 同一串修改在两种表示下的写入量与实跑耗时。可调元素数与修改次数，观察写入量的比值随规模线性增长而时间比值几乎不动。

规律是：写入量的比值随 $n$ 线性增长（ $n$ 除以树深），时间比值基本不随 $n$ 动。选型时该看哪个，取决于瓶颈在带宽还是在延迟。

2 · GC 压力

结构共享省的是「同一时刻活着的对象」，不是「一共造过多少对象」。这两个数在只保留最新版本的场景里差得很远。

同一组基准，只留最后一个版本：新建 39992 个节点，最终活着 3227 个，91.9% 当场成为垃圾。这些是典型的朝生夕死对象，分代 GC 处理得很便宜（新生代扫描只看存活对象，死掉的不花钱），但它们仍然占据分配带宽，也仍然会推高新生代的回收频率。

警示 · 「不可变结构对 GC 更友好」这个说法要分情况。留档场景下它确实友好：全部 1 万个版本都保留时，路径复制的 39992 个节点全部活着，而全量复制要留 $10^9$ 个格子、按 8 字节算 7.6 GB。但只要最新版本的场景恰好相反——路径复制制造了 36765 个短命对象，而原地改数组一个也不制造。判据仍是「有没有人要看旧版本」。

3 · 引用相等

前两节的账都能用别的手段改善（对象池、增量快照、写时复制的页表）。引用相等不能，它是结构共享独有的。

结论一句话：两个版本的某棵子树若在修改中没被触碰，它在两个版本里就是同一个对象，a === b 为真。反过来，a === b 为真就能推出这两棵子树的全部内容相同。于是「这一大片数据变了没有」这个问题从 $O(n)$ 的逐项比较降到一次指针比较。

实测这两者的差距：10 万项的数组逐项比较单次 45.5 µs，指针比较单次 17.2 ns。比值是 2642 倍。

这个比值该怎么读，值得说清楚。17.2 ns 已经贴着空循环的开销，测的与其说是比较本身不如说是循环体；真正的结论不是「快 2642 倍」，而是「一个随 $n$ 增长、一个不随 $n$ 增长」。 $n$ 再大十倍，左边的数字乘十，右边纹丝不动。

图 3-1 · 改一格之后，根的哪些孩子引用变了、哪些没变。可反复修改不同下标，观察未被触碰的子树始终判定为同一个对象。

这条性质是前端 memo 机制的地基。React.memo 与 useMemo 的默认比较是 Object.is 的浅比较，用可变对象时它形同虚设（对象原地改过，引用没变，组件不重渲染，界面不更新），只有配上不可变数据才成立。同一条逻辑在细粒度响应式里换了个形式，见响应式：push 与 pull 的合流。

4 · 不该用的场合

三种情形下结构共享是净亏损。

只有一个可变状态、没人看旧版本。 计数器、缓冲区、临时累加数组。此时持久化的全部收益为零，代价照付。批量构建也归这一类，解法是 transient。

顺序遍历为主。 数组的顺序遍历是纯连续访存，预取器全程命中；32 叉 trie 的遍历要在几千个小对象间跳。10 万元素的 vector 有 3227 个树节点散在堆上，逐个 get 的代价明显高于 arr[i]。Clojure 用 chunked seq 缓解这一点，本质是一次取一整片叶子再线性走。

元素本身很大。 结构共享共享的是节点，不是元素。元素若是大对象，复制成本本来就在元素上，换数据结构改变不了什么。

反过来，值得付这笔代价的判据只有一条：有人要看旧版本，或者有人要靠引用相等做剪枝。undo 栈、时间旅行调试、并发读写下的快照隔离、前端的 memo，都落在这条里。

5 · 参考文献

Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press.
Driscoll, J. R., Sarnak, N., Sleator, D. D., & Tarjan, R. E. (1989). Making data structures persistent. Journal of Computer and System Sciences, 38(1), 86–124.
Steindorfer, M. J., & Vinju, J. J. (2015). Optimizing hash-array mapped tries for fast and lean immutable JVM collections. OOPSLA 2015, 783–800.
React 文档中 memo 的浅比较语义与不可变数据的配合。
Immer 的 draft 方案：不换数据结构，用 Proxy 记录改动再做浅复制的结构共享。