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

Question

我已经开始学习 Clojure 并正在阅读有关结构共享的内容。我对以下场景感到困惑:以下 clojure 代码按照下面定义的顺序在 REPL 中键入:

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 处的值？

这与 Structural Sharing in Clojure 有一定关系，但我还是很困惑。任何形式的帮助将不胜感激。

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))

一般来说，每当 conj如果将一个对象放到现有向量上，则新向量要么 (1) 与原始向量共享整个内部树，但具有新的尾部，要么 (2) 在原始内部树的每个级别与原始向量共享除最右边的一个(并且可能有一个比原始树高一级的内部树)。 (但是，显然原始向量的所有元素都与新向量共享。)

至于通过索引查找值，在每种情况下都会以相同的方式发生 - 向量不关心它们的结构是否恰好与其他向量共享(并且没有理由它们需要，因为它永远不会改变)。