On 25 May 2004 15:52, Daan Leijen wrote:

Ok, here is a new "IntMap" module that might improve the performance of "lookup". Please, let's first test it before adding the changes to the real distribution.

I have: 1) removed calls to "natFromInt" and "intFromNat". Supposedly, they should expand to nothing but who knows...

These calls were being optimised away by GHC. However, something else wasn't: namely the value of maxBound::Word which is used by complement. There's no substitue for actually looking at the code that GHC generates!

2) I have commented out the guard that tests if the integer is in the tree at all. When a key is present, lookup will be faster -- if the key is not present, lookup might be slower.

Simon, I would be interested to see how it performs with and without the comment (2) (line 269). If performance is better without the comment, it means that ghc is spending time doing intFromNat/natFromInt which means that we might improve matters by storing Nat's instead of Int's in the IntMap. (I don't know if such tweaking is worth the trouble though.)

I'll run your new code tomorrow and let you know the results. Cheers, Simon