Tree Wars, IntMap strikes back.
ahey at iee.org
Fri May 28 10:39:04 EDT 2004
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..
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.
More information about the Libraries