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