On 10/24/05, Simon Marlow
On 22 October 2005 11:58, Adrian Hey wrote:
One problem with AVL is the complexity of most of the code means producing specialised unboxed implementations manually is not an attractive proposition. Hopefully compilers will do this sort of thing for us one day.
But in reality I expect this sort of thing to be more of an issue for benchmark style code using Ints. For more complex keys and comparisons the indirection cost will be relatively insignificant I think. For polymorpic implementations counting the actual number of comparisons required by some function is just as important IMO.
It's not just benchmark code - in GHC we use Int-based maps all over the place for speed. Given your promising results for polymorphic AVL trees, it's a fair bet that you could beat Data.IntMap with a specialised Int version. If you did, we would be forced to use Data.Tree.AVL in GHC :)
Wouldn't an Array (or DiffArray) based HashMap be even better? /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862