Commit `ff5850183e`

Niles Salter <Validark@pm.me>

2023-06-21 01:32:07

[priority_deque] simplify & optimize isMinLayer

LLVM has trouble compiling the old implementation, (presumably) because `leading_zeros` is thought to be a `u7` rather than a `u6`, which means `63 - clz` is not equivalent to `63 ^ clz`, which means it can't deduce that the final condition can simply be flipped. (I am assuming `usize` is a `u64` here for ease of understanding, but it's the same for any power of 2) https://zig.godbolt.org/z/Pbj4P7ob3 The new version is slightly better too because `isMinLayer(maxInt(usize))` is now well-defined behavior.

master

1 parent 991e00c

Changed files (1)

lib

std

priority_dequeue.zig

@@ -69,9 +69,7 @@ pub fn PriorityDequeue(comptime T: type, comptime Context: type, comptime compar
             // The first element is on a min layer;
             // next two are on a max layer;
             // next four are on a min layer, and so on.
-            const leading_zeros = @clz(index + 1);
-            const highest_set_bit = @bitSizeOf(usize) - 1 - leading_zeros;
-            return (highest_set_bit & 1) == 0;
+            return 1 == @clz(index +% 1) & 1;
         }
 
         fn nextIsMinLayer(self: Self) bool {

Commit ff5850183e

Commit `ff5850183e`