[erlang-questions] copy or reference?

[Richard Carlsson]

June Kim wrote:
> It looks like there are copy operations in some functional data 
> structures in Erlang. Say, I have a list L and I want to update the 
> n-th element in L. Then, a copy would happen, and it is an expensive 
> operation, memory-wise and time-wise.
> 
> What data structures and their operations in Erlang occur non-copy
> operations?

It's usually not copying that happens, but rewriting. (Real copying
only happens when you send a message from one process to another,
at least when the processes are on different machines.)

For example, say you have a list L0 = ["a","b","c","d","e"]. You
want to change the third element to "x". To do this, you traverse
the list recursively until you find the sublist ["c","d","e"]. The
head element of this is "c", and the tail is T0=["d","e"]. You then
rewrite this to T1 = ["x" | T0], which _reuses_ the sublist ["d","e"]
(it just copies a pointer to the list). After that, you return
from the recursive calls, first creating T2 = ["b" | T1] (this also
only copies a pointer to "b"), and then creating L1 = ["a" | T2].

It's important to realise that the original list is not changed.
L0 is still ["a","b","c","d","e"], but it now shares the tail part
T0=["d","e"] with the new list L1=["a","b","x","d","e"]. The above
might sound like a lot of work, but it only created 3 new list cells
(each using only 2 words), and list cell creation is a very cheap
operation (compared to object creation in typical OO languages).

When the original list L0 has no more references that point to it,
those parts that are not shared with other data structures will be
garbage collected (in this case, the part ["a", "b" | _]).

The reasoning above also applies for tuples; you can see a list
cell as a special kind of tuple (or vice versa), so rewriting
tree structures built out of tuples will only create new tuples
with pointers to mostly the same old data - it will not copy data.

     /Richard