Sorting and searching, from textbook to fast
Eight sorting algorithms get the same array. Every tick is one comparison or one moved element, so the finishing order is the amount of work each one does. What that work costs on a real processor is measured further down.
Ticks count work, not time. On small arrays the tuned versions sometimes do a little more work than the textbook ones and still finish first on hardware, because their work is cheaper: no allocations, fewer mispredicted branches, fewer cache misses. Try sorted input, then the quicksort killer.
Step through one algorithm
Play it, drag the timeline, or step one operation at a time with the
arrow keys. The highlighted line is the C++ that operation comes from,
ported from include/aao/sort.hpp.
Searching a sorted array
127 sorted keys, searched four ways. Click a bar to search for its value. Shaded columns are the 64-byte cache lines a search touched: on an array bigger than the cache, every new line is a trip to main memory, roughly a hundred times slower than a comparison.
Measured on real hardware
Median time per element for sorting and per lookup for searching. Both axes are logarithmic. Dashed lines are the textbook versions, white lines the C++ standard library. Hover to read values; click a legend entry to hide it.
- Processor
- Compiler
- Measured
Sorting 32-bit integers
Show as a table
Looking up 65,536 random keys in a sorted array
Show as a table
Run it on your machine
The library is header-only C++20. The tests and the benchmark need a compiler and CMake, nothing else.
git clone https://github.com/mbn-code/Algorithmic-Analysis-and-Optimization
cd Algorithmic-Analysis-and-Optimization
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release
ctest --test-dir build -C Release
./build/aao_bench --out my-resultsYour numbers will differ from these, and that is the interesting part. Results from other processors are welcome as pull requests.