5 ms·
> In this post, I don't think there is a comparison with a classical binary search implemented in a branch-free fashion? Searching along dyadic intervals is a c
by orlp 3y ago
> In this post, I don't think there is a comparison with a classical binary search implemented in a branch-free fashion? Searching along dyadic intervals is a cute trick, but it's not clear whether the improvement comes from that or simply from being branch-free.
There isn't. Ultimately I felt that the article should be an algorithmic one on bitwise binary search, not one about finding the best binary search implementation. The latter changes heavily based on compiler, architecture, input distribution, cache size, etc, and there's no way a simple article could do it justice.
For your curiosity I have implemented a classic binary search branch-free as well:
template<typename It, typename T, typename Cmp>
It lower_bound_classic_branchless(It begin, It end, const T& value, Cmp comp) {
size_t n = 1 + end - begin;
size_t i = -1;
while (n > 1) {
i += comp(begin[i + n/2], value) ? n/2 : 0;
n -= n/2;
}
return begin + i + 1;
}
It turns out that it performs exactly the same number of comparisons as my lower_bound_overlap.
For larger sizes, lower_bound_overlap is better, on Apple M1: https://i.imgur.com/dCvlZZj.png https://i.imgur.com/dCvlZZj.png
For smaller sizes they are essentially the same: https://i.imgur.com/04s4M6r.png https://i.imgur.com/04s4M6r.png
Looking at the assembly, we see that lower_bound_overlap has a (naturally) longer preamble before the main loop, but has a tighter core loop.
lower_bound_overlap:
; %bb.0:
subs x8, x1, x0
b.eq LBB14_4
; %bb.1:
asr x8, x8, #2
clz x9, x8
mov x10, #-9223372036854775808
lsl x11, x8, #1
and x11, x11, #0xfffffffffffffffc
ldr w11, [x0, x11]
lsr x10, x10, x9
ldr w9, [x2]
sub x8, x8, x10
cmp w11, w9
csinv x8, x8, xzr, lo
lsr x10, x10, #1
cbz x10, LBB14_3
LBB14_2: ; =>This Inner Loop Header: Depth=1
add x11, x10, x8
ldr w12, [x0, x11, lsl #2]
cmp w12, w9
csel x8, x11, x8, lo
lsr x10, x10, #1
cbnz x10, LBB14_2
LBB14_3:
add x8, x0, x8, lsl #2
add x0, x8, #4 ; =4
LBB14_4:
ret
lower_bound_classic_branchless
; %bb.0:
sub x8, x1, x0
add x8, x8, #4 ; =4
asr x8, x8, #2
cmp x8, #2 ; =2
b.lo LBB8_3
; %bb.1:
ldr w10, [x2]
mov x9, #-1
LBB8_2: ; =>This Inner Loop Header: Depth=1
lsr x11, x8, #1
add x12, x9, x11
ldr w12, [x0, x12, lsl #2]
cmp w12, w10
csel x12, x11, xzr, lo
add x9, x12, x9
sub x8, x8, x11
cmp x8, #1 ; =1
b.hi LBB8_2
b LBB8_4
LBB8_3:
mov x9, #-1
LBB8_4:
add x8, x0, x9, lsl #2
add x0, x8, #4 ; =4
ret
- ot 3y agoThanks for checking! > It turns out that it performs exactly the same number of comparisons as my lower_bound_overlap. This is surprising, shouldn't the number of comparisons be identical to the standard implementation?
- orlp 3y ago> This is surprising, shouldn't the number of comparisons be identical to the standard implementation? No, to make it branchless (in an efficient way, it can be done regardless of course), you always take ceil(n / 2) as your remaining size, whereas the branchy version chooses either floor(n / 2) or ceil(n / 2) as appropriate. And in fact, you don't want the number of comparisons to be identical to the standard implementation, for a branchless implementation. Because this makes the branch on loop exit unpredictable. I did find that by changing the implementation slightly: template<typename It, typename T, typename Cmp> It lower_bound(It begin, It end, const T& value, Cmp comp) { size_t n = 1 + end - begin; size_t i = -1; while (n > 1) { size_t half = n / 2; size_t m = i + half; if (comp(begin[m], value)) i = m; n -= half; } return begin + i + 1; } that clang gives slightly better code on the Apple M1 (avoiding an unnecessary add in the tight loop): ; %bb.0: sub x8, x1, x0 add x8, x8, #4 ; =4 asr x8, x8, #2 cmp x8, #2 ; =2 b.lo LBB8_3 ; %bb.1: ldr w10, [x2] mov x9, #-1 LBB8_2: ; =>This Inner Loop Header: Depth=1 lsr x11, x8, #1 add x12, x11, x9 ldr w13, [x0, x12, lsl #2] cmp w13, w10 csel x9, x12, x9, lo sub x8, x8, x11 cmp x8, #1 ; =1 b.hi LBB8_2 b LBB8_4 LBB8_3: mov x9, #-1 LBB8_4: add x8, x0, x9, lsl #2 add x0, x8, #4 ; =4 ret which results in the classic algorithm beating the overlap method on smaller sizes, but not on larger sizes, on Apple M1: https://i.imgur.com/VjD5EK7.png https://i.imgur.com/VjD5EK7.png