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