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.