Clojure中持久数据结构的内存共享

Question

我开始学习Clojure，并阅读了关于结构共享的内容。在以下情况下，我感到困惑： 按照以下顺序在REPL中键入以下Clojure代码：

1) (def a [1 2 3]), 2) (def b a), 3) (def a (conj a 4)), 4) (def b (conj b 5)),

第四步之后，a和b是否共享前三个元素的结构，还是所有值都将在第四步执行时被复制？如果结构是共享的，Clojure如何能够返回我们索引3处的值？

这与 Clojure中的结构共享有些相关，但我仍然感到困惑。任何形式的帮助都将不胜感激。

- abhishekmahawar

Answer 1

在问题文本中给出的示例中，根本没有发生任何结构共享。这是因为向量被实现为树形结构，其中实际元素存储在大小为32的叶节点中（最终叶子单独存储为向量的“尾巴”--性能优化），分支节点同样是32路的。因此，为了实现结构共享，需要一个足够大的向量：

;; a base vector:
(def v1 (vec (range 31)))

;; no structural sharing -- all elements are copied:
(def v2 (conj v1 31))

;; leftmost leaf of internal tree uses v2's tail as its internal array:
(def v3 (conj v2 32))

;; leftmost leaf shared with v3
(def v4 (conj v3 33))

一般来说，当将一个对象添加到现有向量时，新向量要么（1）与原始向量共享整个内部树但具有新尾部，要么（2）在原始内部树的每个级别上与原始向量共享除最右边的节点外的所有节点（并且可能比原始向量的内部树高一级）。 （显然，原始向量的所有元素都与新向量共享。）

至于按索引查找值，每种情况都以相同的方式发生--向量不关心它们的结构是否与其他向量共享（鉴于它永远不会改变，没有理由需要这样做）。

- Michał Marczyk

---

不错的回答。我希望有一个页面，用图像解释每个基本的Clojure数据结构。列表很明显，但向量并不那么明显，并且被命名为C++/Java向量，而实际上是基于树的结构，这只会增加人们对它们持久性的困惑。 - soulcheck

我不确定完全没有共享任何内容。你是说即使在第二步之后，a和b也不会共享任何东西吗？此外，如果在第四步之后它们不共享数据，则conj几乎是O(n)操作，这是很昂贵的。 - abhishekmahawar

就结构而言（与元素相反），a和b确实不会共享任何内容。这并不意味着conj是O(n)，因为复制的数量有限（每个树级别一个包含32个对象的数组）。恰好这种操作模式非常适合缓存，并且在今天的CPU缓存大小下，使用长度小于32的数组并不能节省多少时间。支持这一说法的经验证据来自基准测试，其中向量显示出优异的性能。 - Michał Marczyk

@abhishekmahawar 在Bagwell＆Rompf的[RRB-Trees文章]（http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf）中，有一个漂亮的索引（查找）和向量更新时间的图表; 8似乎是更新的最佳选择（而不是例如2，这意味着在您的示例中复制而不是共享基本上是一种优化！），而32提供稍慢的更新速度，但更快的索引。在另一台机器上，结果可能略有不同，但图表的一般形状将保持不变。 - Michał Marczyk

@abhishekmahawar 等等，我想我误读了你的评论。在第二步之后，a和b只是指向同一个向量。这不是结构共享，结构共享是指在不同向量之间共享内部树的部分；这只是将相同的值赋给两个Clojure变量的情况。（你可以类似地说(def a (java.util.HashMap.))，放入一些条目，然后说(def b a)。此时，a和b将引用相同的HashMap，但这不是结构共享的情况；实际上，这个概念根本不适用于java.util.HashMap。） - Michał Marczyk