[erlang-questions] vlists & varrays

[Fredrik Svahn]

I cannot say that I have been following the erlang mailing list day to day,
but some quick googling indicates that no one has yet mentioned vlists or
varrays here.

http://en.wikipedia.org/wiki/VList

Just for fun I made a small test implementation in erlang (no optimizations,
and probably a lot of bugs) and did some benchmarking against normal list
operations with a list of 1000 and 10000 elements. Adding an element ( i.e.
[ NewElement |  List ] ) is 3 times slower with lists, but the rest of the
operations seem to be quite ok at least when doing the benchmarks with hipe
compiled code. That is not bad considering for instance that lists:reverse/1
is a bif.

$ erl -noshell -run vlists test 1000 -s erlang halt
        {insert,insert_last,iterate,first,last,reverse,length}
lists:  {250,22010,194,6,516,40,15}
vlists: {774,2507,213,6,3,16,22}

$ erl -noshell -run vlists test 10000 -s erlang halt
        {insert,insert_last,iterate,first,last,reverse,length}
lists:  {1420,3536945,3353,11,5071,824,228}
vlists: {4250,27324,1760,6,5,5,23}

Now the vlists module is really using a list as a wrapper around hipe
arrays. Is there anyone who can spot something which is apparently dangerous
or could cause unexpected side effects with the way they are used here? Are
hipe arrays garbage collected for instance? Can they be passed around
between erlang nodes as other data structures? Any way to optimize the
insert operation? Code is attached.

The paper by Phil Bagwell referenced at the end of the wikipedia page is
worth reading. It states among other things that it is quite easy to change
a vlist into a dynamic array with O(1) time for addition and deletion and
where copying can be avoided altogether. It also describes how to write a
deque using the same principles, and some other interesting pieces of
information. I guess I will leave the varray and deque as an exercise to the
reader if anyone is up to the challenge... :-)

BR /Fredrik Svahn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20070917/67046ea7/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vlists.erl
Type: application/octet-stream
Size: 7440 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20070917/67046ea7/attachment.obj>