Is everything in Elixir a reference type?

Question

Reading about Elixir immutability and how it avoids memory copying wherever possible, it seems like the only possible explanation, but I haven't seen it explicitly stated anywhere. For example, when appending a new element to a list, it is described that the operation takes exactly n steps, with n being the length of the list, but that it only shallow-copies the original. So my assumption is:

Say we have a list [1, 2, 3, 4]. It consists of 4 nodes, but the nodes themselves do not contain the values. 1, 2, 3, 4 are stored somewhere else and each node contains a reference to the corresponding value, as well as a reference to the next node. When we append 10 to the list, not just one but actually five new nodes get created, since in the original list the node for the number 4 has to have 'nil' as its 'next' reference, but in the new list the node for the number 4 has to have 'next' pointing to the newly created node for the number 10. So it can't be reused. And that in turn means that the node for the number 3 also can't be reused, etc. etc. So five new nodes get created, but first four are shallow copies, meaning that they point to the exact same memory locations as the original nodes.

Does what I just described make sense?

Answer 1

how it avoids memory copying wherever possible

I think you are referring to structural sharing, which is the property of persistent data structures to not only be immutable, but also be able to operate on them efficiently by generating a modified copy which reuses a part of the underlying structure.

Linked lists are an example of this, but only support efficient prepending. As you pointed out, appending needs to completely rebuild the list from scratch. There is no reuse (structural sharing) possible.

l1 = [1, 2, 3] is actually syntactic sugar for [1 | [2 | [3 | []]]].

l2 = l1 ++ [4] ([1, 2, 3, 4]) is actually [1 | [2 | [3 | [4 | []]]]] and does not contain/reuse l1.

On the other hand, l3 = [0 | l1] or [0] ++ l1 is [0 | [1 | [2 | [3 | []]]]] does reuse l1.

One way to visualize how it points to the same structure under the hood:

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

It is very common to build a list by successive prepending (within recursion / reduce) and finally reverse the result.

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

This section in the Erlang efficiency guide provides a nice explanation.

Other data structures, such as Maps, :arrays or :gb_trees also leverage structural sharing: e.g. when doing Map.put(my_big_map, 0, 0), the tree-structure under the hood (technically an hash array mapped trie) can be mostly reused and there is no need to do a deep copy of 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