[Ocaml-lib-devel] VList-II (was: VList)

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

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

I've updated the code to avoid NULLs (actually only required minimal 
changes... which was nice). It's available here:

   http://www.imada.sdu.dk/~bardur/ocaml-vlist-20050306.tar.bz2

Here's a benchmark with the old code, this time using floats:

   ./examples/test1.opt
   Benchmarks...
   10000000 x VList.(::)... 3.1112
   10000000 x List.(::)... 5.49784
   50000 x VList.nth... 0.00185108
   50000 x List.nth... 30.003
   50000 x VList.length... 0.00599289
   50000 x List.length... 63.9696
   10000000 x cdr(VList)... 0.144912
   10000000 x cdr(VList)... 0.242838

... and here's the new code:

   ./examples/test1.opt
   Benchmarks...
   10000000 x VList.(::)... 0.364121
   10000000 x List.(::)... 5.17452
   50000 x VList.nth... 0.00150108
   50000 x List.nth... 29.8347
   50000 x VList.length... 0.00717998
   50000 x List.length... 64.5293
   10000000 x VList.tl... 0.182895
   10000000 x VList.tl... 0.246443

Quite a huge improvement for cons which fares *much* better against
List in the case of huge lists of floats. I'm not sure if anyone
actually uses huge lists of floats, but there you go. :)

Other than that the performance is basically the same as
before (both in the float case and the non-float case).

Cheers,

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

Just then, Neville caused a slight diversion by turning into a
large canary.
                                    J.K. Rawling, 'Goblet of Fire'