diff options
| author | Lukas Bergdoll <lukas.bergdoll@gmail.com> | 2023-02-10 18:00:31 +0100 |
|---|---|---|
| committer | Lukas Bergdoll <lukas.bergdoll@gmail.com> | 2023-02-10 18:05:12 +0100 |
| commit | 7e072199a6e650698c2f5f1e1053b20d48be43d3 (patch) | |
| tree | 9d943637e7fcd5d0175a734b7fde1e763679c7cb | |
| parent | d1ac43a9b9a8250d858705b0796dfed6186e18db (diff) | |
| download | rust-7e072199a6e650698c2f5f1e1053b20d48be43d3.tar.gz rust-7e072199a6e650698c2f5f1e1053b20d48be43d3.zip | |
Speedup heapsort by 1.5x by making it branchless
`slice::sort_unstable` will fall back to heapsort if it repeatedly fails to find a good pivot. By making the core child update code branchless it is much faster. On Zen3 sorting 10k `u64` and forcing the sort to pick heapsort, results in: 455us -> 278us
| -rw-r--r-- | library/core/src/slice/sort.rs | 4 |
1 files changed, 1 insertions, 3 deletions
diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 2181f9a8118..990540f55f5 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -198,9 +198,7 @@ where } // Choose the greater child. - if child + 1 < v.len() && is_less(&v[child], &v[child + 1]) { - child += 1; - } + child += (child + 1 < v.len() && is_less(&v[child], &v[child + 1])) as usize; // Stop if the invariant holds at `node`. if !is_less(&v[node], &v[child]) { |
