brainsort

Use it

Add the crate brainsort to your project. It is a port of the C++ library function by function, held to the C++ golden numbers by its test suite: every element read and write, every comparison and table access, the peak memory and the exact access sequence must match, cell for cell. No dependencies, no_std + alloc, MIT licensed; AVX2 and BMI2 chosen at run time on x86-64, the same code minus the vector paths elsewhere.

[dependencies]
brainsort = "0.5.0"

let mut v = vec![3, 1, 2];
brainsort::sort(&mut v);                                         // stable, by value
brainsort::sort_by_key(&mut rows, |r| r.id);                     // by a key
brainsort::sort_by_key_ref(&mut rows, |r| r.name.as_str());      // by a borrowed key
brainsort::sort_by_key(&mut rows, |r| (r.id, brainsort::Desc(r.score)));
brainsort::sort_by(&mut rows, |a, b| a.name.cmp(&b.name));       // a comparator

The API docs are on docs.rs; step by step with examples: the Rust usage guide.

At a glance

Why these sorts. An opponent has to offer what brainsort offers, so that a win or a loss means something: it is stable, it sorts every key type on this page and it takes an arbitrary comparator. And it is the upstream code as it ships, never a port written here. That is slice::sort, its cached-key form and glidesort; slice::sort_unstable and the radix crates are unstable or sort scalar keys only, an easier job, and are not opponents.

How to read this page

Six things to know, then every number below makes sense.

What each algorithm does deterministic

These numbers are the same on every computer. They are counted, not timed: how many comparisons a sort makes, how often their outcome flips, how often the cached-key sort asks for a key, how much memory it asks for. The other sorts are the stable sorts a Rust program can call, as shipped: the standard library's driftsort, its sort by a cached key and the glidesort crate, counted through what a program can observe of them (the comparator they are given, the key function they call, the allocator). What cannot be observed of a sort one did not write, the bytes it moves, is counted for brainsort alone in the golden file and compared with the C++ pool on the C++ page; the crate's own bytes moved are exactly those, held by its test suite. Choose a metric:

Method

cd rust
cargo test --release                                             # the crate against the golden counts, among the tests
cargo run --release -p brainsort-bench -- --golden               # the counted view of every cell, checked against results/counts.csv
cargo run --release -p brainsort-bench -- --rust-counts          # the Rust sorts as shipped: results/rust-counts.csv, the deterministic numbers of this page
cargo run --release -p brainsort-bench -- --rust-golden          # that file recomputed and checked
cargo run --release -p brainsort-bench -- --bench --out ../results/<id>.rust.api.md   # the timing of this machine
python3 ../scripts/website.py                                    # both pages of the website, from results/

The algorithms

"Best opponent" on this page means the best of the other sorts in a cell. Every sort here is the published code, run unchanged: the deterministic numbers count what it asks of the program (comparisons, key reads, memory), the timed numbers what it costs. The pool is the Rust sorts that can do what brainsort does: stable, every key type, an arbitrary comparator. slice::sort_unstable and the radix crates (radsort, voracious_radix_sort, rdst) are not in it, because an unstable sort or a scalar-only radix sort has an easier job, so a comparison with them would not be like for like; the Rust ecosystem has two such sorts, the standard library's and glidesort, and the cached-key form of the standard one is the route a program takes for a sort by key. Element moves cannot be observed from outside in Rust, so bytes moved, reads, writes and the cache model are not counted for these sorts; the C++ page has them for the C++ pool.

The key types

The inputs

All numbers

Every value behind this page, for the selected size and key types: the deterministic columns once, the measured columns per machine. Open a cell to render it.