[Ocaml-lib-devel] Re: VList

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

Alain Frisch wrote:
>>   $ ./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    <== VList.tl
>>   10000000 x cdr(VList)... 0.116828    <== List.tl
> 

(corrections above, just to make it absolutely clear)

> 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 ?

I guess that could be quite likely.

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

- iter doesn't need to allocate anything

- fold doesn't need to allocate anything (I *think*... it may need a 
logarithmic number of 'pointers')

- map of course needs to allocate data blocks, but by using blocks 
directly it avoids having to allocate lots of (temporary) pointers.

> 
> 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 ?

I only briefly considered it, but if one were to do it in pure OCaml it 
would probably need more magic than I can pull off. :)

> 
> 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 ?

A test with three elements suggests, yes. :) Aren't floats heap-allocated?

I think it will work in general because a 'NULL' pointer made through 
Obj.magic will be at least as large as any non-heap object (and heap 
objects are of course pointed to, so that'll work too).

>  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)

I'm not sure I follow... Once you have a pointer into the list (ie. the 
parameter you're calling VList.map with) everything back from that point 
is read-only, so you don't to construct anything using (::)...?!?

I'm also pretty sure the current VList.map does produce a result with 
the correct ordering. The resulting VLists are created as in e.g.


        |-------| --> |-------| --> |-------| -> (NIL)
        | l'[2] |     | l'[5] |     | l'[6] |
        | l'[1] |     | l'[4] |
   l -> | l'[0] |
        | ..... |

(Coincidentally the reason I'm not just calling Array.map, but actually 
traversing the array backwards (and copying each element individually), 
is that I want the *application* of the user's closure to be performed 
in-order as well... if their closure has side-effects this would be the 
natural way to expect things to work, although I haven't checked to see 
if List.map actually specifies this.)

Cheers,

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

- Thank God it landed in that smoking crater!
                               Chief Clancy Wiggum, 'The Simpsons'