Performance of Erlang data structures

[Raimo Niskanen]

You can have a look at:
http://otp.ericsson.se:8000/product/info/otp_unix/doc/efficiency_guide/part_frame.html
but there might be other documents that more directly answers your
question.

Regarding the basic types, lists are chains of cons cells and there
are no reverse pointers, nor pointers to the end of the list. This 
means that append, search, insert, indexing, etc. are O(n), while consing
or matching from the head is O(1).

Tuples are fixed size arrays, but when replacing an element in 
a tuple, a copy of the whole tuple except for one element 
has to be made. This means that search, replace, copy is O(n) while
indexing is O(1).

Often you want to use higher abstraction data organisation, e.g
ets, gb_trees, gb_sets. Look at their manpages. They might at
least contain a hint of what basic algorithms are used, 
tree or hash or such, and that might give you indirect
information about their performance.

sebastian@REDACTED (Sebastian Bello) writes:

> Hi,
> 
> is there a document regarding performance of Erlang data structures? For example, what is the performance (order, o(n), constant, etc) of the insertion in a list, the lookup, etc. Just to know what data structures to use when performance is an issue.
> Thanks,
>     Sebastian-
> 

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB