Re: Tree Wars, IntMap strikes back.

On Friday 28 May 2004 1:59 pm, JP Bernardy wrote:

--- Simon Marlow 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