Beautiful branchless binary search • Hacker News Board

chaboud wrote: post #104

“Those spikes for std::lower_bound are on powers of two, where it is somehow much slower. I looked into it a little bit but can’t come up with an easy explanation. The Clang version has the same spikes even though it compiles to very different assembly.” I saw this and immediately went “oh, those look like Intel hardware”. Intel uses 12-bit memory port quick addressing in their hardware, resulting in an issue known a…

For those interested in a deeper dive, Richard Startin had a nice post on the topic https://richardstartin.github.io/posts/4k-aliasing

Re: Beautiful branchless binary search

#197

Post by touisteur » Sat, Apr 29, 2023, 3:40 PM UTC

waynecochran wrote: post #106

dist1ll wrote: post #101

Earlier quoted context omitted.

> Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to control what they write. Plug and pray compilation is not a solid engineering approach. Not sure how one relates to the other. Do you want more fine-grained control over emitted assembly? Or do you want a general-purpose CPU that e…

C++ could add a an explicit conditional move I suppose. `x` and `y` types would have to be restrictive: x = std::cmove(y,flag); The compiler would be slightly mrve compelled to use a hardware conditional move than in the following case: if (flag) x = y; The other option is to do something more like CUDA / SIMD kernels do ... every line gets executed but each each instruction inside the "false branch" becomes a no-op.…

Pushing this a bit more, one could read about SPMD and ISPC (originally by Matt Pharr) https://pharr.org/matt/blog/2018/04/30/ispc-all

I've used it (sparringly) for vectorizable, branchy code and it's mostly been a simple process, with very efficient binaries produced (often beating hand written intrinsics by intermediate level coder - themselves beating the autovectorizer).

Don't know about using it in prod on multi generational hardware though.

Re: Beautiful branchless binary search

#198

Post by preseinger » Sat, May 06, 2023, 11:32 PM UTC

mgaunard wrote: post #134

msla wrote: post #111

Earlier quoted context omitted.

> and select the output you want based on conditionals. I thought you said it would be branchless.

A branch refers to jumping to a different location. Performing comparing and blending values as a result of them is not a jump.

nope

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

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