Benchmarking (again:-)

[Adrian Hey]

Hello,

I enclose a copy of some results I posted in a c.l.f thread FYI..

> Adrian Hey wrote:
>  
>> It would be nice to have some data for other tree types too, like
>> red-black trees maybe.
> 
> Malcolm Wallace sent me some code for red-black and 234 trees which is
> used in nhc98 compiler. It contains no set operations, or even delete, but
> I thought it would be interesting to see how these compared with my own
> AVL implementation and DData.Set (weight balanced) for simple insert,
> lookup (and delete if available).
> 
> So here are my results for trees of 500000 Int elements (execution times
> and comparison counts) for ordered data and random data.
> 
> Ordered Data (times in mS)
>           AVL    DData.Set  RedBlack    234
> -------------------------------------------
> Insert    150       366       217       255
> Lookup     53        76       116       114
> Delete    126       135       ---       ---
> 
> Ordered Data (Comparisons)
>           AVL    DData.Set  RedBlack    234
> ----------------------------------------------
> Insert  8975713   15689425  12668235  13167977
> Lookup  8975732    9166555   9132570   9132601
> Delete  6785282    6612512    ---       ---
>  
> Random Data (times in mS)
>           AVL    DData.Set  RedBlack    234
> -------------------------------------------
> Insert    763      1003       815       852
> Lookup    153       181       224       215
> Delete    803       ???       ---       ---
> 
> Random Data (Comparisons)
>           AVL    DData.Set  RedBlack    234
> ----------------------------------------------
> Insert  8953286    9155823   9104153   9106882
> Lookup  9184653    9418309   9331310   9332922
> Delete  8229843    8405601    ---       ---
> 
> Notes:
> * These figures are for the entire test (not per element).
>   The timing measurements are averaged over 10 runs (same
>   test data each run).
> * The Insert test constructs a tree by inserting a list of
>   Ints into an empty tree.
> * The Lookup test checks each Int in the original list is
>   a member of the set (in the same order that they appear
>   in the list).
> * The Delete test deletes each element from the set
>   successively, resulting in an empty set (in the order
>   they appear in the original list).
> * There are no results for deletion from RedBlack or 234
>   trees (because these functions don't exist :-)
> * There is no timing result for deletion of random data from
>   DData.Set because the test segfaults???. But only with
>   random data and only when I try to time it, not with ordered
>   data and not if I just count comparisons. Ermm..
> 
> The actual execution times may be suspect (a lot will depend on
> implementation details, so they don't necessarily reflect on the
> algorithm).
> 
> But the comparison counts tell us something. DData.Set, RedBlack, and
> 234 all seem to be struggling with insertion of ordered data, but for AVL
> it makes virtually no difference. I think my earlier remark about the
> AVL algorithm being difficult to improve on is justified by these results.
> 
> So I still say AVL is a darned good algorithm that takes a lot of beating
> in practice. But I'd still be interested in being proven wrong :-)

Regards
--
Adrian Hey