Commit e427ba9cd5

Andrew Kelley <andrewrk@noreply.codeberg.org>
2025-11-27 20:48:54
std.sort.partitionPoint: faster implementation (#30005)
Migrated from https://github.com/ziglang/zig/pull/21419 Co-authored-by: Jonathan Hallstrom <lmj.hallstrom@gmail.com> Reviewed-on: https://codeberg.org/ziglang/zig/pulls/30005
master
1 parent 854774d
Changed files (1)
lib
std
sort.zig
lib/std/sort.zig
@@ -678,18 +678,23 @@ pub fn partitionPoint(
     context: anytype,
     comptime predicate: fn (@TypeOf(context), T) bool,
 ) usize {
-    var low: usize = 0;
-    var high: usize = items.len;
+    var it: usize = 0;
+    var len: usize = items.len;
 
-    while (low < high) {
-        const mid = low + (high - low) / 2;
-        if (predicate(context, items[mid])) {
-            low = mid + 1;
-        } else {
-            high = mid;
+    while (len > 1) {
+        const half: usize = len / 2;
+        len -= half;
+        if (predicate(context, items[it + half - 1])) {
+            @branchHint(.unpredictable);
+            it += half;
         }
     }
-    return low;
+
+    if (it < items.len) {
+        it += @intFromBool(predicate(context, items[it]));
+    }
+
+    return it;
 }
 
 test partitionPoint {