Bitwise Binary Search: Elegant and Fast

https://orlp.net/blog/bitwise-binary-search/

by orlp • 3 years ago

3 3 3 years ago

xoranth2• 3 years ago

However, I’ve found that some compilers, e.g. GCC on x86-64 will refuse to make this variant branchless. I hate how fickle compilers can be sometimes, and I wish compilers exposed not just the likely/unlikely attributes, but also an attribute that allows you to mark something as unpredictable to nudge the compiler towards using branchless techniques like CMOV’s.

Clang has `__builtin_unpredictable`[^1]. Both of the have `__builtin_expect_with_probability` [^2], which could help. But these builtins are fickle/make no guarantees as far as I can tell.

[^1] https://clang.llvm.org/docs/LanguageExtensions.html#builtin-... [^2] https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index...

orlp• 3 years ago

I wasn't aware of __builtin_unpredictable until yesterday. I was aware of __builtin_expect_with_probability. Unfortunately I've found both of them to be essentially useless with today's compilers.

xoranth2• 3 years ago

Mmm, it looks like LLVM even has a pass to actively convert generated cmovs into branches if one of the operands touches memory [^1], and that only supported way to force things to be brancheless is inline assembly [^2].

[^1] https://reviews.llvm.org/D36858 [^2] See: - https://groups.google.com/g/llvm-dev/c/qwogIiwHCAc/m/lSP1jh2... - https://groups.google.com/g/llvm-dev/c/qwogIiwHCAc/m/EAt643e...

Bitwise Binary Search: Elegant and Fast

Related Stories