Tree Wars (latest round :-)

[Daan Leijen]

On Wed, 26 May 2004 10:53:54 +0100, Adrian Hey <ahey at iee.org> wrote:
> I got these results:
>
> For 500,000 random elements
>                  Insert  Lookup  Delete
> Data.Tree.AVL    0.923   0.203   0.798
> Data.FiniteMap   1.150   0.203   1.259
> DData.Map        1.177   0.205   1.084
> DData.IntMap     0.648   0.163   0.627
>
>
> For 500,000 ordered elements:
>                  Insert  Lookup  Delete
> Data.Tree.AVL    0.210   0.060   0.117
> Data.FiniteMap   0.473   0.076   0.137
> DData.Map        0.488   0.079   0.145
> DData.IntMap     0.108   0.039   0.054


Very cool results for AVL :-)

>  We still have no idea how well AVL trees perform for
>  set operations (haven't written the necessary code yet).

Let me take this opportunity to remind us all of being
careful when interpreting these numbers: most programs don't
just insert and lookup in that order, but mix the operations
in a lazy fashion which can lead to wildly different results.
Furthermore, I tend to use "union" a lot -- I know/suspect from
simple tests that DData.IntMap tends to outperform Data.Map by
a wide margin on those kind of operations, etc.

Btw. Given the good performance of AVL, maybe we should try to
make the interface look like DData.Map (or maybe provide a seperate
AVL.Map module to does that). This would allow one to use
IntMap, AVL.Map or Map without changing (much) code.

All the best,
  Daan.


>
> I can post the test code to anyone who wants it.
> The mods to test287.hs are:
>
>  Removed size calculation, as this O(n) for AVL trees but O(1) for
>  FiniteMap and DData.map and is irrelevant to insertion/deletion times.
>
>  Increased testData size from 100,000 to 500,000.
>
>  Used foldl' instead of foldr to prevent stack overflow.
>
>  PerformGC at start of each test in test10
>
>  Had to swap args of Map.lookup in lookupsMap
>
>  Changed the way results are displayed to be more comprehensible (to me:-)
>
> Regards
> --
> Adrian Hey
>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>