81–90 of 155 posts
first += (length + rem) * ((sign(cmp(...)) + 1) / 2)
How can you call it branchless if it has "while (length > 0) {"
How can you call it branchless if it has "while (length > 0) {"
People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.
Earlier quoted context omitted.
> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++. Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... At TigerBeetle, we have our own branchless implementation here: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...
Rust's binary search is here. Also a pretty textbook version of the function: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c... How much faster is the branchless version in practice? I make heavy use of binary search in some code I maintain, and I wonder if it would make much of a difference to switch to a more efficient version of the function.
old branchless version: https://github.com/rust-lang/rust/pull/45333/files
You need at least 1 branch to exit the loop.
How can you call it branchless if it has "while (length > 0) {"
That particular branch is well-predicted for long arrays. You probably only gonna have a single misprediction for the complete binary search function, the performance consequence of that branch is negligible. People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.
>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.
At least when I last read it a couple years ago, Intel's optimization manual recommends certain code layouts. For example in the absence of better information a conditional jump backwards would be predicted as true (because that's what loops look like) while a jump forward is seen as less likely to happen (error conditions and else branches look like that). Not sure how consistent this is across architectures, and ho…
but the only simpler approach is 'predict not taken' which in a sense is what a cortex-m0 does
Branchless? You need at least 1 branch to exit the loop.