
A 1987 Shellsort variant is 3x faster than Shellsort when branch-free
In 1987, a Shellsort variant called shaker sort ran about 15% slower than
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
In 1987, a Shellsort variant called shaker sort ran about 15% slower than a well-tuned Shellsort on a VAX 11/780. Written branch-free and run on a current CPU, the same algorithm is about 3× faster than Shellsort.
This repo has the benchmark (Rust, no dependencies), reference implementations and correctness tests (Python), and the raw results.
It started as an AI-generated "new" sorting algorithm called Utah Sort. That turned out to be the 1987 algorithm plus three additions that don't help, and the 1987 algorithm itself was the interesting part. More on that below.
Sorting 1,000,000 random u32 keys on one core of an AMD Ryzen 9 9950X3D (best of 5 runs):
At 10,000,000 keys: 1,005 ms, 984 ms, 318 ms and 109 ms. These come from main-u32.md, the current code. An earlier build measured 24 ms (3.4×) for the branch-free row; that turned out to be a lucky code layout (details).
The second and third rows are the same algorithm with the same gaps. The only difference is how one compare-exchange is written:
// with a branch if v[i] > v[j] { v.swap(i, j); }
// branch-free: min/max compile to cmov (or SIMD min/max) let (a, b) = (v[i], v[j]); v[i] = a.min(b); v[j] = a.max(b);
For comparison, the 1987 paper (Table 5) reports 37.9 s for shaker sort and 32.4 s for Shellsort at n = 75,000 on a VAX 11/780.
All inputs and sizes are in results/. Shaker sort is not faster everywhere. On already-sorted input, Shellsort takes 6 ms and branch-free shaker sort takes 26 ms, because shaker sort does the same work no matter what the input looks like.
while j >= g && v[j - g] > t { v[j] = v[j - g]; j -= g; }
exits at a point that depends on the data. On random input the CPU's branch predictor often guesses wrong, and each wrong guess throws away a dozen or more cycles of work.
Shaker sort's passes do the same sequence of compare-exchanges whatever the data is. In the Python comparison count, it makes exactly 4,164,391 comparisons at n = 100,000 on every input pattern. The passes leave the array fully sorted, so the final insertion pass only confirms it. That is 1.6× the comparisons Shellsort makes on random input, but written branch-free, each one is a conditional move with nothing to mispredict.
It isn't SIMD. With target-cpu=native, LLVM auto-vectorizes the branch-free passes with AVX-512. With vectorization turned off (-C no-vectorize-loops -C no-vectorize-slp), the assembly is scalar cmov. In that comparison (commit d420208), shaker sort took 24 ms at 1M both with and without SIMD, so vectorization isn't what makes it fast. See main-no-simd.md.
Not yet confirmed. I haven't measured branch mispredictions with hardware counters. If you're on Linux, this would settle it:
cd rust RUSTFLAGS="-C target-cpu=native" cargo build --release perf stat -e branches,branch-misses ./target/release/utah_bench --only shellsort perf stat -e branches,branch-misses ./target/release/utah_bench --only shaker_branchless
Each --only run sorts 1M random keys 10 times. The counts also include generating the input and one reference sort, which are the same for both.
The headline is for u32. cargo run --release -- --keys u64 (or f64, str) runs the same table with other keys, built from the same input patterns. 1M random keys, all from one build:
The first published numbers (commit d420208) had 24 ms for branch-free shaker sort on u32, which is 3.4×. The inner loop compiles to the same instructions in that build and the current one. With loops forced to 64-byte alignment, both take 26.4 ms, so 24 ms was a lucky code layout. The headline table now uses the current build. More in docs/details.md.
An AI tool proposed "Utah Sort" as a new algorithm and presented its pieces as new. When checked, the core turned out to be shaker sort from Incerpi & Sedgewick (1987). Its three additions:
All three are correct. The proofs are in docs/details.md, and python/check_correctness.py checks them on 695,129 inputs using a list that refuses negative indices. They don't make it faster on random data (branch-free, 1M keys, range over three runs of commit d420208):
With both the mirror pass and the window, Utah Sort is no faster than plain shake-and-insert (38 vs 37 ms). Individually they move the time about 10% in opposite directions, and the mirror pass's effect reversed sign in an earlier build, so I wouldn't read much into either. The real cost is inserting after every gap: about 1.4× (35 vs 24 ms). Shaker sort also needs its denser 1.7× gap sequence. With Shellsort's gaps, a single shake per gap leaves too much work for the final insertion. The additions only pay off on input that is already sorted or exactly reversed, where Utah Sort takes 4 ms.
One machine, one core. The headline is for u32. u64 and f64 give similar speedups, and strings don't (Other key types).
Code layout matters. Two builds with identical inner-loop instructions gave 3.4× and 3.1× for the headline, and some other cells have moved by up to a third. Treat small differences between builds as noise.
Each algorithm uses the gap sequence its own literature recommends.
The standard library's sort is still about 3× faster than branch-free shaker sort. This matters only where you'd pick Shellsort anyway: tiny code, no allocation, no standard library.
If the explanation is right, the speedup depends on a deep, speculative pipeline. Small in-order microcontrollers may behave more like the VAX did. That's untested.
I haven't done an exhaustive literature search. If this has been published, please open an issue and I'll credit it here.
Run it
Rust (stable, 1.88 or newer, no dependencies):
cd rust export RUSTFLAGS="-C target-cpu=native" cargo run --release # main table, about a minute cargo run --release -- --keys f64 # same with u64, f64 or str keys (default u32) cargo run --release -- --ablate # Utah Sort ablation, about two minutes cargo run --release -- --list # algorithm names for --only
On Windows PowerShell, use $env:RUSTFLAGS="-C target-cpu=native" instead of export.
cd python python check_correctness.py # a few minutes python count_comparisons.py
Help wanted
Other machines. Intel, Apple Silicon and other ARM chips, older x86, a Raspberry Pi, a microcontroller. Open an issue with your CPU model and the output of the main table and --ablate, and if you can, --keys u64, f64 and str.
perf stat numbers for the two commands above.
Prior art for the branch-free result.
Layout
python/sorts.py Shellsort, shaker sort, Utah Sort (reference versions) python/check_correctness.py exhaustive and random correctness tests python/count_comparisons.py comparison counts for all three rust/src/main.rs timing benchmark and ablation results/ raw output and machine details docs/details.md algorithms, Utah Sort proofs, full tables, references
How this was made
The "Utah Sort" proposal came from a generative AI tool. I used Claude, an AI coding assistant, to check it against the literature and to write the tests, the benchmark and this README. Every number here comes from running the code in this repo, and you can rerun it yourself.
J. Incerpi, R. Sedgewick. Practical variations of Shellsort. Information Processing Letters 26(1):37–43, 1987.
D. L. Shell. A high-speed sorting procedure. Communications of the ACM 2(7):30–32, 1959.
M. Ciura. Best increments for the average case of Shellsort. FCT 2001.
S. Edelkamp, A. Weiß. BlockQuicksort: Avoiding branch mispredictions in quicksort. ESA 2016.
W. Dobosiewicz. An efficient variation of bubble sort. IPL 11(1):5–6, 1980.
D. E. Knuth. The Art of Computer Programming, Vol. 3, §5.2.1–5.2.2.
License
MIT
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。