How to benchmark algorithm performance?

[andreacassioli]

As work on modernizing and hopefully one day expanding the library is under way, how do we assess performance? Is there some establish benchmark to avoid regression?

IMHO it is difficult to systematically assess the performance of such an extensive library, but at least some core components should be monitored (like core searches, or graph manipulations).

This relates to #480.

I would like to hear your opinion.

[Becheler]

Hi @andreacassioli !

Thanks for asking the right questions !

1. I think anything related to benchmarks could go to /benchmark and be run on CI on different platforms. Data gets collected as json, then CI wires it to summary python scripts then to the user through a PR bot and/or an updated documentation page

2. The tricky thing will be freezing inputs. There is already a question on Reddit about it. Meaning /benchmark/assets could contain a bunch of standard graph datasets on which to run algorithms. Deciding on a first subset that is sufficient for standard algorithms with known truths (BFS DFS etc) is a first step.

3. Benchmarking will probably need to happen with multiple graph representations.

4. What will be difficult is for algorithms that are heuristics where there is no ground truth, and where speed is in tension with correctness and depend on algorithm variant + input (eg tolerance, epsilon or something like this). A good example is Louvain algorithm. In that case one needs to compare to existing implementations (python libs, c, or whatever so it's a bunch of stuff to install) and make a more complex analysis of performance/input/variant. That is probably a separate project/study worth publication in a peer review journal 😬🤣 that's what I did for Louvain and it's probably unscable/unmaintainable

[andreacassioli]

I think there are (at least) two angles:

1. performance regression due to changes (think of the modernization under way)
2. comparison against other implementations

My main concern is at the moment (1). In my experience it is very easy to introduce such regressions, and not easy to systematically assess them. Given one of the selling point of BGL is its performance, it would be great to find a way to keep an eye on that.

One convenient way to integrate on CI somehow, but with the possibility to run on laptops.

Lately at work I have been using https://github.com/benchmark-action/github-action-benchmark combine with Google benchmark.

Is there any tooling used by other boost projects?

[Becheler]

Yes, regression should be the main focus. For now for "risky" PRs (dependency reduction) I did local benchmarks and copy pasted the results into the PR. It does not scale we agree on this ahah

We could copy the setup of Boost.Int128. But graphs are memory bound and I suspect runners on GitHub will come with quite some noise. If it comes to be verified in practice, to identify regressions inside a PR we could build both base and head on the same runner and interleave measurements. But then we have ~150 algorithms x 3 graphs representation x knobs (vecS sets etc) x 10 reps min so the matrix grows fast.

In practice we will figure it out little by little, beginning with a naive setup and refining if necessary.

I'm fine with google benchmark.