[erlang-questions] copy or reference?

[Thomas Lindgren]

--- June Kim <juneaftn@REDACTED> wrote:

> Hello,
> 
> 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.

To be precise, there is usually no copying as such;
instead you build an updated version of the data
structure. If you trace the execution by hand, I think
you will see that there is no OO-style "deep copying"
going on when you are replacing the Nth element of a
list. Instead, the old and new version of the data
structure will share parts.

For example, when you replace the n:th element of a
list x1,...xn....xm, you will normally build only new
list  cells x1',...,xn' but will still share xn+1...xm
from the old list, and also share all the contents of
the list. This is done routinely and safely precisely
because the list and its elements cannot be
destructively updated.

If you find yourself repeatedly walking a list and
replacing elements, you may still get an unpleasant
algorithmic complexity (as can happen for list
algorithms). In that case, you should first of all
change your algorithm or your data structure. Perform
several updates at once, for example, or use a tree
instead of a list. Or rethink your algorithm.

> What data structures and their operations in Erlang
> occur non-copy operations?

If you still need destructive updates, first look at
ets tables or mnesia. I would recommend reading up on
non-list data structures as well, such as dict or
gb_trees.

If you are worrying about low-level performance rather
than algorithmic performance, then I suggest you also
read the following part of the Erlang manual. 

http://www.erlang.org/doc/doc-5.5.4/doc/efficiency_guide/part_frame.html

Best,
Thomas



 
____________________________________________________________________________________
Finding fabulous fares is fun.  
Let Yahoo! FareChase search your favorite travel sites to find flight and hotel bargains.
http://farechase.yahoo.com/promo-generic-14795097