Data.* collections maintenance

Adrian Hey ahey at
Tue Oct 25 06:27:54 EDT 2005

On Monday 24 Oct 2005 2:24 pm, Daan Leijen wrote:
> It is amazing that lookup is faster on AVL trees -- this goes against
> all my intuition -- did you measure random lookups?

Yes, I've just run the benchmarks again (with ghc 6.4), results for
maps of 500000 random Ints are (time in no particular units)..

                Data.IntMap    AVL.IntMap
Insert          214.0          227.0
Lookup          146.6          104.8
Delete          253.0          254.0
Union           66.0           96.0
Intersection    15.0           41.0

However, I seem to recall somebody finding a bug somewhere in
Data.IntMap a while ago. I'm not sure if that's the case, but if
so in may be influencing the timings, for better or worse.
Can anybody enlighten me about that? (or refute this allegation :-)

I can supply AVL.IntMap code and benchmark code if anybody's

Adrian Hey

More information about the Libraries mailing list