Add benchmarks

[treeowl]

I think I've picked off most of the low-hanging fruit, performance-wise. To make good decisions about smaller performance tweaks, we really need a benchmark suite. I would very much prefer to borrow someone else's, if there's a good one out there, but we can write our own if need be.

[jwaldmann]

Hi.

I am using pqueue here https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/-/blob/master/src/Matchbox/Closure/Simple.hs

I am not sure whether PQ operations cost is dominant but I will profile this.

[treeowl]

@jwaldmann thanks! While you're at it, how hard would it be for you to compare the master branch to the latest released version? I expect a substantial improvement for most workloads.

[jwaldmann]

Sure I will do that. I can just put this repo as extra-dep in my stack.yaml?

[treeowl]

I imagine so. I'm no stackspert.

[jwaldmann]

I mean, your recent commits didn't change the API?

[treeowl]

Nothing removed or substantially changed.

[treeowl]

(mapM and sequence in the Traversable instances are slightly stricter, but that shouldn't matter unless you're doing something very strange.)

[jwaldmann]

I think that my application does not really depend on the performance of pqueue, see https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/-/issues/368

Sadly, my measurements are non-reproducible, so I need to remove some non-determinism.

[jwaldmann]

Now I have better reproducibility https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/-/issues/368#note_37421 The numbers indicate that improvements in pqueue don't help my application, as it burns most cycles elsewhere. Still I appreciate the work you're doing!

The typical application of a PQ would be shortest path or MST algorithms, but this needs to update (decrease) the keys, which can only be done with state (the insert method returns a pointer)?

I wonder how FGL does this. Perhaps their https://hackage.haskell.org/package/fgl-5.7.0.3/docs/Data-Graph-Inductive-Internal-Queue.html could be replaced with pqueue , to obtain test cases (assuming that fgl has them). I now see your related issue haskell/fgl#41