Benchmarking and Profiling

Benchmarking is the process of measuring the performance of a program. It can be used to compare the execution time of two different algorithms. Profiling can be used to analyze where time is spent during the evaluation of an algorithm. We suggest to use criterion for benchmarking and flamegraph for profiling.

Benchmarking with Criterion

Criterion supports statistical analysis of the runtime of your program. A plotting library has to be installed to generate graphs. You can find more information and help here:

Criterion-rs GitHub
Cargo-criterion GitHub
Criterion Book (!Watch out for the criterion version, as of writing this, the book is not on the latest version!)

Commands

a) cargo criterion <benchmark name regex>
Has to be installed with cargo install cargo-criterion.
Pros:

You can remove features = ["html_reports"] from the Cargo.toml, leading to (slightly) faster compile times.
Criterion aims to move to just using cargo criterion
The large Probability Density Function graph shows the samples and marks the outlier categorization borders.
can use either gnuplot or plotters

b) cargo bench <benchmark name regex>
Pros:

Can visualize the change in performance compared to the previous run or other baseline Cons
can only use gnuplot

Profiling with Flamegraph

Flamegraphes provide insights into where execution time is spent.

Details can be found here:

Flamegraph GitHub.

Installation

Installing Flamegraph in Linux and macOS is easy, since you only need to install flamegraph. But in WSL you need some more steps, since you need to install "perf" manually.

So after cargo install flamegraph, you need to update "apt" with sudo apt update and install "build-essential's" by sudo apt install -y build-essential libelf-dev libnuma-dev flex bison libdw-dev libunwind-dev libaudit-dev libslang2-dev libperl-dev python3-dev binutils-dev liblzma-dev libiberty-dev.
Then you go into the home directory with cd ~ and install the linux kernel with
wget - https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.15.5.tar.xz (Adjust the version as needed).
After that you extract it with tar -xvf linux-5.15.5.tar.xz and move into "perf" with cd linux-5.15.5/tools/perf there you use make to compile it. The last step is to make "perf" visible by e.g. sudo cp ./perf /usr/local/bin/.

Command

cargo flamegraph --freq 63300 --bench benchmarks -- --bench --profile-time 5 <benchmark name regex>
Generates a flamegraph that allows us to approximate how long each function executes. The accuracy of the approximation is better the more samples are produced. That can be improved by

increasing the sampling frequency (--freq 63300). This frequency is throttled to the highest possible frequency, which depends on the CPU, CPU-temperature, power settings and much more...
increasing profile-time (in seconds). That is how long the benchmark code will be executed. This parameter also disables the statistical analysis of the criterion which prevents it from showing up in the graph. This parameter is optional but suggested.