←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 2 comments | 28 Apr 23 05:46 UTC | HN request time: 0.627s | source
Show context
mgaunard ◴[28 Apr 23 06:55 UTC] No.35738305[source]▶
It's funny how people struggle so much to write branchless code.

The code is clearly not branchless as written, and relies on non-trivial optimizations for it to happen.

Just write it correctly to begin with.

replies(1): >>35739189 #
mgaunard ◴[28 Apr 23 09:27 UTC] No.35739189[source]▶
Modded down, I guess the average hackernews web dev can't do branchless either.

It's easy, just run all the instructions from all branches, and select the output you want based on conditionals.

replies(1): >>35742113 #
msla ◴[28 Apr 23 15:00 UTC] No.35742113[source]▶
> and select the output you want based on conditionals.

I thought you said it would be branchless.

replies(1): >>35746891 #
1. mgaunard ◴[28 Apr 23 20:45 UTC] No.35746891[source]▶
A branch refers to jumping to a different location. Performing comparing and blending values as a result of them is not a jump.
replies(1): >>35846362 #
2. preseinger ◴[06 May 23 23:32 UTC] No.35846362[source]▶
nope

https://en.wikipedia.org/wiki/Branch_(computer_science)

a jump is one kind of branch, but branch describes more things than just jumps