Data.IntMap.unionWithKey is slower than mergeWithKey
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
Here is an exagerated example
```haskell
#!/usr/bin/env cabal
{- cabal:
build-depends: base, containers >= 0.8, tasty-bench
default-language: GHC2024
ghc-options: -O2
ghc-options: "-with-rtsopts=-T"
ghc-options: -ddump-simpl -dsuppress-all -dno-suppress-type-signatures -ddump-to-file
-}
import Data.IntMap (IntMap)
import Data.IntMap qualified as IM
import Test.Tasty.Bench
import GHC.Exts (inline)
mkBench :: String -> (IntMap () -> IntMap () -> IntMap ()) -> Benchmark
mkBench name func = bench name $
nf (\acc -> foldl' func acc (replicate 1000 mempty)) (mempty :: IntMap ())
main :: IO ()
main = defaultMain
[ mkBench "union" IM.union -- good
, mkBench "unionWith" (IM.unionWith (<>)) -- bad
, mkBench "unionWith saturated" (\xs ys -> IM.unionWith (<>) xs ys) -- refuses to inline
, mkBench "unionWith inlined" (inline IM.unionWith (<>)) -- still refuses to inline
, mkBench "unionWithKey" (IM.unionWithKey (\_k x y -> x <> y)) -- bad
, mkBench "unionWithKey saturated" (\xs ys -> IM.unionWithKey (\_k x y -> x <> y) xs ys) -- refuses to inline
, mkBench "unionWithKey inlined" (inline IM.unionWithKey (\_k x y -> x <> y)) -- still refuses to inline
, mkBench "mergeWithKey" (IM.mergeWithKey (\_k x y -> Just $ x <> y) id id) -- good
]
```
On my laptop it gives the following measurements:
```
$ cabal run UnionWith.hs
All
union: OK
3.59 μs ± 206 ns, 0 B allocated
unionWith: OK
8.09 μs ± 437 ns, 117 KB allocated
unionWith saturated: OK
8.08 μs ± 434 ns, 117 KB allocated
unionWith inlined: OK
8.12 μs ± 492 ns, 117 KB allocated
unionWithKey: OK
8.17 μs ± 618 ns, 117 KB allocated
unionWithKey saturated: OK
8.09 μs ± 412 ns, 117 KB allocated
unionWithKey inlined: OK
8.13 μs ± 545 ns, 117 KB allocated
mergeWithKey: OK
4.10 μs ± 212 ns, 0 B allocated
```
Looking at dumped Core, it seems that `unionWithKey` fails to inline, even despite saturation and `inline`. Presumably that's simply because for some reason the interface file is missing its unfolding.
Could `containers` enable `-fexpose-all-unfolding` in the Cabal file? It's a blunt weapon, but at least it would give a user an option to force inlining despite GHC heuristics, if their use case benefits from it.
Contributor guide
Research direction
Start by running the embedded UnionWith.hs tasty-bench benchmark with cabal run and inspecting the generated dumped Core. Read the containers Cabal configuration and the Data.IntMap unionWithKey and mergeWithKey entry points, then verify whether exposing unfoldings changes inlining, allocation, and benchmark results without regressions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 58/100