Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Bitwise Binary Search: Elegant and Fast (orlp.net)
3 points by orlp on May 16, 2023 | hide | past | favorite | 3 comments


> 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...


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.


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...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: