Tree Wars, IntMap strikes back.

[Adrian Hey]

On Friday 28 May 2004 1:59 pm, JP Bernardy wrote:
> --- Simon Marlow <simonmar at microsoft.com> wrote:
> > Interesting, I get pretty much the same results as
> > you, except that
> > DData.Map is now quicker on the lookup test than
> > both FiniteMap and AVL
> > (0.120 vs. 0.134 and 0.138 respectively).
>
> Ok, so that means that I should merge in the last
> change by Daan (and in IntSet too)?
>
> (patch in extenso at the end of the message)

I don't think the DData I was using included this, (I was using the most
recent bundled version from your website). 

Anyway, one thing I just tried to see if specialising AVL for maps would yield
significant improvement is to remove the additional level of indirection
currently caused by pairs by using AVL trees of Ints. Basically this means
using the original test code and replacing..
 pushKey,delKey,tryRead
with..
 push,del,contains

I got these results for 500,000 random elements
                 Insert  Lookup  Delete
Data.Tree.AVL    0.756   0.155   0.763 
Vs. originals    0.923   0.203   0.798
		 
So it does look as though specialising AVL for maps (and maybe even IntMaps)
would yield significant performance improvements. I don't propose to do this
at this stage though, as the basic AVL library isn't finished yet.

Regards
--
Adrian Hey