Benchmarking Graphix performance

[matulni]

Currently, Graphix lacks a systematic way of benchmarking the codebase. #403 is a tentative PR to fill this gap, but this issue demands a deeper examination. The goal of this discussion is to identify our needs, set up a road map and collect useful references.

Basic questions

1. Which functionality of the codebase do we want to benchmark and on which samples ?

2. Which benchmarking tool to use ?

Benchmarking frameworks

• Airspeed velocity

  • Used by numpy, scipy and astropy.
  • Designed to show performance evolution over commit history.
  • See [DRAFT] Add Airspeed velocity support #403 for a draft implementation. It seems to be possible to locally compare between two different commits.
  • Supports integration with cProfile.
  • Discussion on the limitations of airspeed velocity

• Codspeed
  (To be explored)

• pytest-benchmark

  • We introduced it in $O(N^3)$ Pauli-flow finding algorithm #337 but I personally found it a bit cumbersome to use.

• pyperformance

  • This is specific to benchmarking Python implementations. It relies on pyperf which could be used for our purposes.

Additional references

• Analysis of GitHub actions and asv
• Examples of less-known projects with asv integration:
  • https://gitlab.com/datadrivendiscovery/d3m/-/merge_requests/156
  • feat: benchmarking django-components/django-components#999

[matulni]

Here's a list of functions which I believe could be a good starting point, either because they are most relevant or because they have a "heavy algorithmic component". Feel free to disagree, I'm certainly biased to the parts of the library I'm most familiar with.

• Pattern simulation

  • Support all backends including upcoming plugins.
  • Here, the challenge is to design sensible samples. Transpilation from random circuits is probably too naive. See Interface with MQTBench for simulator benchmarking #365.

• Pauli presimulation

  • Comparison between Graphix built-in and stim backend.

• Pattern manipulation:

  • Standardization.
  • Composition (since relevant for VQE).

• Circuit to pattern transpilation.

• Flow extraction from open graphs

  • It may make sense to implement low-level benchmarks for the module graphix._linalg.py.
  • Sensible benchmarking samples for the Pauli-flow extraction algorithm can be found here.

• Open graph composition (since it's relevant for the brickworks transpilers).

[emlynsg]

Agree with all these, and that we have to be careful with the sample pattern simulation. We already have differences between existing backends (e.g. support for noise) and future backends (include Perceval) will likely be limited in different ways too. It may be that we need to come up with a small set of patterns that are universally supported, and then different sets that support subsets of the backends.

[emlynsg]

Thanks for starting thinking about this Mateo! I like the ideas, and from my brief research it seems that ASV or pytest-benchmark would be the best options (since there are pre-existing examples for both).
I found a repo that contains Github Actions for continuous benchmarking using pytest-benchmark and that also supports Rust and other languages.

[matulni]

Thanks for the reply @emlynsg ! So far I'm more inclined to use pytest-codspeed (which is essentially a drop-in replacement of pytest-benchmark) for the following reasons:

• We already use pytest for unit testing.
• It seems to be more versatile than asv for local benchmarking.
• It think it will be easier to implement some sort of CI performance check with pytest-codspeed than with asv. Codspeed looks promising for that.
• I don't think we really need to showcase the evolution of performance over commit history (or at least, it's not a priority for now). If that were the case in the future, we might find a tool to convert benchmarks formats, e.g., asvdb).

I'll keep fiddling with it to see its usability.

A secondary question if we use pytest for benchmarking: should we create a new module with the benchmarks separated from the unit tests or should we use a benchmark fixture in some of the unit tests ?
Currently, we do the latter (see e.g. test_linalg), but I'd prefer to have separate modules, since now it's difficult to have a bird's-eye view of what and how we are benchmarking. Also, benchmarks are run multiple times and they slow the CI (they are unnecessarily run on multiple python versions, OS, etc. and we don't extract any info from those runs). The downside is that having two separate modules may lead to some code duplication.
What are your thoughts on this @emlynsg, @thierry-martinez ?