This was an algorithmic problem first discussed in ADSP Episode 72: C++ Algorithm Family Feud!. Then Tyler Weaving did some initial profiling that he shared on Twitter which then Conor responded to. Conor later wrote some initial and most likely totally incorrect profiling code that yielded the graph below. This repo will set up some benchmarks that profile these algorithms correctly.
CPUs are constantly changing their voltage and frequency in response to load and temperature. This means how "fast" your CPU is can change from moment to moment and may be different in the winter vs the summer! While this is useful for day to day usage, it is harmful when trying to gather deterministic and reproducible performance numbers.
In order to generate the most reliable numbers possible, one should disable CPU frequency scaling.
On Ubunutu, install the cpupower
utility:
sudo apt-get install -y linux-tools-$(uname -r)
For more information or instructions for other distros, see https://wiki.archlinux.org/title/CPU_frequency_scaling