about summary refs log tree commit diff
diff options
context:
space:
mode:
authorLukas Bergdoll <lukas.bergdoll@gmail.com>2023-02-10 18:00:31 +0100
committerLukas Bergdoll <lukas.bergdoll@gmail.com>2023-02-10 18:05:12 +0100
commit7e072199a6e650698c2f5f1e1053b20d48be43d3 (patch)
tree9d943637e7fcd5d0175a734b7fde1e763679c7cb
parentd1ac43a9b9a8250d858705b0796dfed6186e18db (diff)
downloadrust-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.rs4
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]) {