[Ocaml-lib-devel] VList

[Bardur A. <sp...@sc...>]

Hi all,

Just for the heck of it I implemented the VList data
structure described in

    http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200244.pdf

I've only implemented the basic stuff needed to do some
benchmarking, but if there is interest I might implement
the rest of the List interface. There are two things to note about the 
implemenetation as it is:

- It is not currently thread safe, but achieving thread safety
   should only require very minor modifications.
- For small lists, a considerable amount of memory is wasted,
   but as the lists grow, the space consumed gets asymptotically
   closer to that of an array(!).

A snapshot can be retrieved from

 
http://www.imada.sdu.dk/~bardur/personal/programs/ocaml-vlist/ocaml-vlist-20050305.tar.bz2

The test results are quite interesting. On my Athlon64
3500+, with 2GB of memory, a couple of test runs yield:

   $ ./examples/test1.opt
   Benchmarks...
   10000000 x VList.(::)... 1.05192
   10000000 x List.(::)... 2.28799
   50000 x VList.nth... 0.000813007
   50000 x List.nth... 14.4831
   50000 x VList.length... 0.00608492
   50000 x List.length... 32.4571
   10000000 x cdr(VList)... 0.176178
   10000000 x cdr(VList)... 0.116828
   $ ./examples/test1.opt
   Benchmarks...
   10000000 x VList.(::)... 0.926367
   10000000 x List.(::)... 2.01412
   50000 x VList.nth... 0.00077486
   50000 x List.nth... 12.8647
   50000 x VList.length... 0.00628901
   50000 x List.length... 32.2211
   10000000 x cdr(VList)... 0.179661
   10000000 x cdr(VList)... 0.131431

which looks quite good especially considering that it's
100% pure OCaml.

Maybe a candidate for ExtLib?

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- What is it? The language? Or the nudity, hopefully...?
                                  David Letterman, 'The Late Show'