improve benchmarks for Data.IntMap

[jwaldmann]

Benchmarks should

• use several sets of data (currently: just one, contiguous keys [1 .. 2^12])
• test bulk operations (union, intersection) - currently, they don't? https://github.com/haskell/containers/blob/master/containers-tests/benchmarks/IntMap.hs

NB: these bulk ops are the main reason for IntMap? if we only operate by-element, we could use hashmaps?

[int-e]

Here's a potential source for inspiration: https://gist.github.com/int-e/36578cb04d0a187252c366b0b45ddcb6#file-intmapfal-hs-L20-L45

[jwaldmann]

yeah, also https://github.com/jwaldmann/containers/blob/intmap-fromList/containers-tests/benchmarks/IntMap.hs

[sjakobi]

@jwaldmann That looks like a nice improvement! Why don't you simply make a PR?

[jwaldmann]

"Why don't you.." - because it's a drastic change that should be discussed first? Current benchmark:

defaultMain
        [ bench "lookup" $ whnf (lookup keys) m ...

my proposal

  defaultMain $ do
    e <- [ 10, 15 .. 25 ]
    return $ bgroup ("2^" <> show e)
      [ bulk
        [ ("contiguous/overlapping", [1..2^e], [1..2^e]) ...

[sjakobi]

@jwaldmann I guess a PR would be the perfect platform for that discussion! :)

[gereeter]

test bulk operations (union, intersection) - currently, they don't?

These are tested in the set-operations-intmap benchmark, which also uses a variety of data sets.

[sjakobi]

For reference: In #653, there's some performance work on fromList[WithKey] that needs better benchmarks with more realistic inputs.

[sjakobi]

For reference: In #653, there's some performance work on fromList[WithKey] that needs better benchmarks with more realistic inputs.

Also related: https://github.com/haskell/containers/issues/652

[sjakobi]

Regarding the problem of realistic inputs for fromList and friends: How about using e.g. splitmix to generate them randomly? Certainly that's not very realistic for many applications, but it adds another data point.

prettyprinter has a benchmark that is similarly based on randomly generated data: https://github.com/quchen/prettyprinter/blob/ab2c09419cca51fcc37760e71ef6861d26753e94/prettyprinter/bench/LargeOutput.hs#L173-L181