Data.* collections maintenance

[Adrian Hey]

On Monday 24 Oct 2005 10:43 am, Simon Marlow wrote:
> It's not just benchmark code - in GHC we use Int-based maps all over the
> place for speed.

Sure. What I meant was that the only reason anybody is likely to use
the polymorphic version with Ints is for benchmarking the polymorphic
version. In real code they'll be using something better suited to Ints.
I didn't mean IntMaps/Sets wouldn't be used at all in real code.

>  Given your promising results for polymorphic AVL
> trees, it's a fair bet that you could beat Data.IntMap with a
> specialised Int version.

Well, as it happens I do have a cut down unboxed version of AVL
for IntMaps which I produced just to see how it performed. I'm sure
you're all eager to know how it compared with Data.IntMap.

Results were a bit mixed..

IIRC lookup was about 30% faster, insertion and deletion were about
10% slower and union was about 70% slower.

The union used the same divide and conquer algorithm as the proper
AVL library. This might be a case where comparison is so cheap that
the Hedge algorithm would be a net win. But as I felt disinclined
to write the code needed to find out for sure that is just
speculation :-)

Regards
--
Adrian Hey