Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beautiful branchless binary search

probablydance.com

Post reply on HN
Print view View original

121–130 of 198 posts

Re: Beautiful branchless binary search

#121

Post by Paul-Craft »

secondcoming wrote: post #118
Paul-Craft wrote: post #112

Earlier quoted context omitted.

Thank you for this comment! I was sitting here, metaphorically scratching my head, trying to figure out how the hell you can call this branchless when there's clearly an `if` in there: for (step /= 2; step != 0; step /= 2) { if (compare(begin[step], value)) begin += step; } Your comment, especially this part, made it click for me: > You can achieve the same effect as cmov by using bitwise operations and a subtraction…

Most topics I've read/viewed on branchless stuff seems to boil down to doing arithmetic with bools. So your code above can be thought of as: bool b = compare(begin[step], value); begin += (step * b);

Yeah, I got that. That was the part u/2102922286's comment made click for me. I guess I just don't do enough low level stuff for that to be something that automatically occurs to me.

Re: Beautiful branchless binary search

#122

Post by kps »

compiler-guy wrote: post #119
spc476 wrote: post #62

Earlier quoted context omitted.

In C, shifting signed integers is undefined behavior.

Although it can bite you if you don’t know what you are doing, signed-integer shifting is not necessarily undefined behavior. Roughly, for positive signed integers, if the operation doesn’t overflow then the result is defined. For negative signed numbers, right shifts are implementation defined, but almost all modern systems define the result in the expected manner. https://en.cppreference.com/w/cpp/language/operator…

Oh, it's too bad C2x doesn't seem to be following C++20 here, since they're apparently mandating two's complement.

Re: Beautiful branchless binary search

#123

Post by eklitzke »

slashdev wrote: post #97
buybackoff wrote: post #54

Branchless or not in this case, it still touches memory in not so good pattern. I found that a significant speedup of a classic BS could be achieved by switching to vectorized search when the remaining range has a width of 3-4 SIMD lines (or maybe even a little more). The bounds of that range are likely already touched and in cache, then prefetching helps. It has high likelihood of finding the target on a single SIMD…

I’d be surprised if SIMD + branch to switch algorithms beats branchless binary search for data in cache. Were you comparing with that? Not saying it isn’t possible, god knows CPUs surprise in all kinds of wonderful ways. It’s not the outcome I would have guessed though. 4x AVX2 vectors of 32bit integers is 32 integers. So log2(32) = 5, 5 cmov instructions or a largely unpredictable branch + simd instructions and eith…

I haven't tested this either, but why would the branch be "largely unpredictable"? It's always going to evaluate to false except once, and the one time it evaluates to true the rest of the search will be finished within the branch.

Re: Beautiful branchless binary search

#124

Post by srcreigh »

srcreigh wrote: post #37
2102922286 wrote: post #11

A cool related algorithm is https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cache properties than a standard binary search tree. If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting…

Trying to figure this out myself. So cache line is 64 bytes. Ignoring pointers you can fit eight 8bit data/key values, or sixteen 4bit data/key values. Pointers are entirely implicit (thx user below) This would save you 3 or 4 memory reads respectively. The odds of this strategy helping past the first few layers seems unlikely. So for 100k elements binary tree, this should be a 21% or 31% performance improvement resp…

typo: mixed up bit and byte when referring to the different integer sizes

Re: Beautiful branchless binary search

#125

Post by eklitzke »

xmcqdpt2 wrote: post #99
2102922286 wrote: post #30

Earlier quoted context omitted.

This is one area where Profile-Guided Optimization (PGO) can help a lot! With PGO, you run your program on some sample input and it logs info like how many times each side of a branch was taken. From there, you can recompile your code. If the compiler sees that one side of the branch dominates, it can emit code to prioritize that branch. However if the branch counts are approximately even and the branch is hard to pr…

If your PGO program ends up in a situation which is the opposite of that you profiled, couldn't you end up with vastly worse performance than a non-optimized program? I've always felt uncomfortable about PGO for more complex programs because of this.

Right, this is why you should use AutoFDO nowadays not PGO. With AutoFDO you occasionally (e.g. in prod this might be something like record for 1s on average every 300s) record what branches were taken using perf-record from prod binaries, and then feed this back to the compiler.

Re: Beautiful branchless binary search

#126

Post by eklitzke »

2102922286 wrote: post #30
pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

This is one area where Profile-Guided Optimization (PGO) can help a lot! With PGO, you run your program on some sample input and it logs info like how many times each side of a branch was taken. From there, you can recompile your code. If the compiler sees that one side of the branch dominates, it can emit code to prioritize that branch. However if the branch counts are approximately even and the branch is hard to pr…

I commented on this elsewhere as well, but nowadays you should reach first for AutoFDO rather than PGO.

Re: Beautiful branchless binary search

#127

Post by eklitzke »

SleepyMyroslav wrote: post #42

If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know. 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 contr…

Every C and C++ compiler has supported inline asm for decades, so that's what you should use if you really need to control the assembly output. The fact that you can switch between the two within the same function is one of the selling points of both languages.

Re: Beautiful branchless binary search

#128

Post by localhost »

I asked GPT-4 to explain it to me, and asked if it could identify the algorithm. It didn't do a good job here (returned name of function). But when I told it that it was also called "Shar's algorithm", it immediately identified the author as Andrei Alexandrescu who apparently goes by the pseudonym Shar as well.

> Yes, with the name "Shar's algorithm," I can confirm that this branchless binary search algorithm is indeed known as Shar's algorithm. It's a variation of the Binary Search algorithm that focuses on minimizing branching to improve performance on modern CPUs. The algorithm is named after its creator, Andrei Alexandrescu, who goes by the pseudonym "Shar" on the internet.

Re: Beautiful branchless binary search

#129

Post by justincredible »

localhost wrote: post #128

I asked GPT-4 to explain it to me, and asked if it could identify the algorithm. It didn't do a good job here (returned name of function). But when I told it that it was also called "Shar's algorithm", it immediately identified the author as Andrei Alexandrescu who apparently goes by the pseudonym Shar as well. > Yes, with the name "Shar's algorithm," I can confirm that this branchless binary search algorithm is inde…

[dead]

Re: Beautiful branchless binary search

#130

Post by kps »

localhost wrote: post #128

I asked GPT-4 to explain it to me, and asked if it could identify the algorithm. It didn't do a good job here (returned name of function). But when I told it that it was also called "Shar's algorithm", it immediately identified the author as Andrei Alexandrescu who apparently goes by the pseudonym Shar as well. > Yes, with the name "Shar's algorithm," I can confirm that this branchless binary search algorithm is inde…

Pretty amazing that he did that when he was two. At that age I was still struggling with BASIC. Maybe he had help from GPT.

(The actual Leonard E Shar seems to have his name on a single paper, which is not about this, but about a pipelined processor, interesting in its own right.)

Post reply on HN