IntMap lookup is slow
When working on a paper @sgraf found that
Data.IntMap.lookup performed allocation. This is silly: it is simply traversing a tree, and should not allocate. Moreover this allocation occurred even if the map is empty (which is not so unusual).
He writes: looking at the defn of
IntMap.lookup, we see that it indeed allocates a closure for the local SAT'd
go function if not inlined (I think Map.lookup is marked INLINE precisely for that reason). What a shame, I can hardly imagine that specialisation for the key is beneficial in any way...
Here's the code
lookup :: Key -> IntMap a -> Maybe a lookup !k = go where go (Bin p m l r) | nomatch k p m = Nothing | zero k m = go l | otherwise = go r go (Tip kx x) | k == kx = Just x | otherwise = Nothing go Nil = Nothing
It looks as if we allocate a local function
go before even looking at the map.
It would probably be better if
lookup was simply self-recursive, thus
lookup k (Bin p m l r) | nomatch k p m = Nothing | zero k m = lookup k l | otherwise = lookup k r lookup k (Tip kx x) | k == kx = Just x | otherwise = Nothing lookup !k Nil = Nothing
Worth trying with some careful profiling.
You might think this should be an issue on
containers and perhaps it should. But I'm also puzzled about why GHC didn't optimise the first form into the second -- it has a STG lambda lift pass I think.