Re: [Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

On Sat, 28 May 2005, John Skaller <sk...@us...> wrote:
> 
> The library supplies the maximally efficient and simplest
> representation by Occam's Razor, and that cannot be empty.

So it all boils down to efficiency.  Of course the problem -- as we
experience with the shootout -- is that it is not so easy to measure
(because we are talking of the big-O constant, not about asymptotic
complexity).  So instead of discussing, I propose to experiment!
Attached is an updated version of the interface together with an
implementation (hopefully without mistakes :).  According to my little
experiments, it is not so bad.  (Hereafter, Dllist' refers to this
library and Dllist to Extlib one.  The Benchmark module is used.)

Example 1: inserting 10000 elements using Dllist'.append and
---------- Dllist.add (they don't exactly do the same thing but
           Dllist.add doesn't need the "list" to be handled through a
           reference):

Throughputs for Dllist' running 4 times for at least 4 CPU seconds:
   Dllist':  7 WALL ( 6.25 usr +  0.31 sys =  6.56 CPU) @ 185.98/s (n=1220)
             7 WALL ( 6.25 usr +  0.29 sys =  6.54 CPU) @ 186.54/s (n=1220)
             7 WALL ( 5.62 usr +  0.30 sys =  5.92 CPU) @ 206.08/s (n=1220)
             4 WALL ( 3.92 usr +  0.22 sys =  4.14 CPU) @ 294.69/s (n=1220)
Throughputs for Extlib running 4 times for at least 4 CPU seconds:
    Extlib:  5 WALL ( 4.02 usr +  0.19 sys =  4.21 CPU) @ 187.41/s (n=789)
             4 WALL ( 4.01 usr +  0.21 sys =  4.22 CPU) @ 186.97/s (n=789)
             4 WALL ( 4.00 usr +  0.20 sys =  4.20 CPU) @ 187.86/s (n=789)
             5 WALL ( 4.02 usr +  0.18 sys =  4.20 CPU) @ 187.86/s (n=789)
         Rate      Extlib Dllist'
 Extlib 188+- 0/s      --  [-14%]
Dllist' 218+-43/s   [16%]      --

(The results are between brackets because the variability in the
measures does not confirm that the rates are significantly different.
The experiment should be repeated more times.  A full_major garbage
collection was done between the two tests.)


Example 2: Inserting 10000 elements and removing them with
---------- Dllist'.remove_last and Dllist.remove (again same canva
           applies):

Throughputs for Dllist' running 4 times for at least 4 CPU seconds:
   Dllist':  8 WALL ( 7.29 usr +  0.25 sys =  7.54 CPU) @ 295.36/s (n=2227)
             6 WALL ( 5.72 usr +  0.21 sys =  5.93 CPU) @ 375.55/s (n=2227)
             5 WALL ( 4.85 usr +  0.16 sys =  5.01 CPU) @ 444.51/s (n=2227)
             5 WALL ( 3.97 usr +  0.15 sys =  4.12 CPU) @ 540.53/s (n=2227)
Throughputs for Extlib running 4 times for at least 4 CPU seconds:
    Extlib:  5 WALL ( 4.03 usr +  0.19 sys =  4.22 CPU) @ 152.84/s (n=645)
             4 WALL ( 3.98 usr +  0.15 sys =  4.13 CPU) @ 156.17/s (n=645)
             5 WALL ( 3.96 usr +  0.17 sys =  4.13 CPU) @ 156.17/s (n=645)
             4 WALL ( 3.95 usr +  0.17 sys =  4.12 CPU) @ 156.55/s (n=645)
         Rate      Extlib Dllist'
 Extlib 155+- 1/s      --    -62%
Dllist' 414+-86/s    166%      --

You will probably not agree with the above results -- and maybe I made
mistakes in my hastiness -- but the code is there to discuss upon.

Cheers,
ChriS