haskell / haskell/containers

Data.IntMap.unionWithKey is slower than mergeWithKey

Open
#1,243 4 comments 0 reactions 0 assignees View on GitHub
IntMap performance
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.