[erlang-questions] how are implemented lists?

[Kostis Sagonas]

On 05/18/2015 10:33 AM, Benoit Chesneau wrote:
> how are implemented lists? What is the algorithm behind them? Especially
> for key* functions? I am asking myself if i need to implement a
> skip-list or if the lists module would fit my needs. I indeed need a
> fast and concurrent data structure that allows me to retrieve the items
> in order and do pop/tail, while still being abble to remove them by key.

To avoid confusion, let me remind you that in Erlang the only data 
structures that are shared between processes, and could thus be 
classified as "concurrent", are ETS tables.  There are no others.  So 
plain lists do not fit your needs, independently of how they may be 
implemented.

Given that you want "ordered traversal/retrieval", ETS tables of type 
ordered_set are the data structures that would fit your need.  Alas, 
their current performance in the presence of concurrent accesses is not 
so great.  The following publication describes some of the issues that 
are involved:

 
http://www.it.uu.se/research/group/languages/software/ca_tree/erlang_paper.pdf

We have done quite a bit of work in extending CA trees, the data 
structure described in this publication, to e.g. provide efficient 
support for range queries and range updates, but this work is not (yet) 
part of Erlang/OTP.  More information can be found at:

   http://www.it.uu.se/research/group/languages/software/ca_tree

Kostis