Erlang data structures: copies or references

Question

I am playing with a binary tree implementation in Erlang. Here is a fragment of the code to give you an idea:

-record(node, {key, value, left, right}).

% ...

insert(Tree, {Key, Value}) when Key == Tree#node.key ->
    #node{key=Key,
          value=Value,
          left=Tree#node.left,
          right=Tree#node.right};

insert(Tree, {Key, Value}) when Key > Tree#node.key ->
    Tree#node{right=insert(
        Tree#node.right, {Key, Value})};

% ...

Here when I insert a new key and value to the tree, I return a new tree with the inserted (or modified) node.

Question: will VM actually copy the tree and GC the old one (which would be inefficient), or copy the references to the old branches and alter only nodes/branches affected by the new key?

Related:

score 4 · Accepted Answer · answered Sep 04 '13 at 11:07

The expression Tree#node{right=...} creates a new record (a tuple) that contains the same entries as Tree apart from the 'right' field. Each entry uses one machine word. If an entry is an "immediate" like an atom or an integer or an empty list, all the info is in that word. Otherwise, the entry is a tagged pointer to the actual data (like a tuple or a binary). In either case, only that word is copied into the new record; Erlang never does a "deep copy" except when you're sending messages. (Note that storing data in ETS tables behave like you send the data to the table.) Only the old Tree record will become garbage.

Erlang data structures: copies or references

1 Answers1