Re: [Ocaml-lib-devel] VList

[Alain F. <Ala...@in...>]

Hi,

Bardur Arantsson wrote:
> 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

Cute.

>   $ ./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

(The last line is actually List.tl)

I'm quite surprised that the slowdown for VList.tl is so small, 
considering it has to allocate a block. Isn't it the case that most of 
the time is actually spent in the loop itself, and no the tl operation ?

The good thing is that iterators (fold, map, iter) can be implemented 
without allocating that much.

The paper describes a way to represent a list with a single pointer, 
which would avoid allocating for the tl operation. I guess this cannot 
be easily implemented in OCaml, since it requires cooperation with the 
GC. Do you have any idea about it ?

Also, I'm concerned with your Obj.magic to create dummy elements to fill 
the array. Are you sure it will work with vlists of floats ?  Why don't 
you use the element you add (in ::) and an equivalent of Array.map (in 
map) ?  (Array.map as it is would produce a different traversal order 
for the vlists)

-- Alain