elixir - Elixir 中的所有内容都是引用类型吗？

Question

阅读有关 Elixir 不变性以及它如何尽可能避免内存复制的文章，这似乎是唯一可能的解释，但我还没有在任何地方看到它的明确说明。例如，当将一个新元素附加到列表时，它被描述为该操作恰好需要 n 个步骤，其中 n 是列表的长度，但它只是浅拷贝原始元素。所以我的假设是:

假设我们有一个列表 [1, 2, 3, 4]。它由 4 个节点组成，但节点本身不包含值。 1、2、3、4 存储在其他地方，每个节点包含对相应值的引用，以及对下一个节点的引用。当我们将 10 添加到列表中时，不仅创建了一个新节点，而且实际上创建了五个新节点，因为在原始列表中，数字 4 的节点必须将“nil”作为其“下一个”引用，但在新列表中，节点因为数字 4 必须有 'next' 指向为数字 10 新创建的节点。所以它不能被重用。这反过来意味着数字 3 的节点也不能被重用，等等。所以创建了五个新节点，但前四个是浅拷贝，这意味着它们指向与原始节点完全相同的内存位置节点。

我刚才描述的有道理吗？

Answer 1

how it avoids memory copying wherever possible

我认为您指的是结构共享，这是 persistent datastructures 的属性不仅是不可变的，而且能够通过生成修改后的副本来有效地操作它们它重用了底层结构的一部分。

链表就是一个例子，但只支持高效的前置。正如你所指出的，附加需要从头开始完全重建列表。没有重用(结构共享)可能。

l1 = [1, 2, 3] 实际上是 [1 | 的语法糖[2 | [3 | []]]].

l2 = l1++ [4] ([1, 2, 3, 4]) 实际上是 [1 | [2 | [3 | [4 | []]]]] 并且不包含/重复使用 l1。

另一方面，l3 = [0 | l1] 或 [0]++ l1 是 [0 | [1 | [2 | [3 | []]]]] 确实重用了 l1。

可视化它如何指向引擎盖下的相同结构的一种方法:

iex> Enum.take(l2, 3)
[1, 2, 3]
iex> Enum.drop(l3, 1)
[1, 2, 3]
iex> :erts_debug.same Enum.take(l2, 3), l1  # no structural sharing
false
iex> :erts_debug.same Enum.drop(l3, 1), l1  # structural sharing
true

通过连续前置(在递归/归约中)构建列表并最终反转结果是很常见的。

# artifical implementation of Enum.map
Enum.reduce(enum, [], fn x, acc -> [f.(x) | acc] end) |> Enum.reverse()

这section in the Erlang efficiency guide提供了很好的解释。

其他数据结构，例如 Maps、:array 或 :gb_trees 也利用结构共享:例如在执行 Map.put(my_big_map, 0, 0) 时，引擎盖下的树结构(技术上是 hash array mapped trie )大部分都可以重复使用，无需对 my_big_map 进行深拷贝。

iex> my_big_map = Map.new 1..10000, fn x -> {x, x} end
iex> new_map = Map.put(my_big_map, 0, 0)
iex> :erts_debug.size my_big_map
37898
iex> :erts_debug.size [my_big_map, new_map]  # almost no copy needed
37958