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

61–70 of 198 posts

Re: Beautiful branchless binary search

#61

Post by WithinReason »

vidarh wrote: post #49
srcreigh wrote: post #37

Earlier quoted context omitted.

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…

You don't store data nodes, or pointers. You store the keys. If you need to store data, just store them at the same index in another array. The pointers are wholly implicit . E.g. assuming you let the index 0 be empty, the left pointer for a node k is at 2k and the right node is at 2k+1. In terms of benefit here, the main benefit appears to be that since you always know where the children will be, you can trade bandw…

So binary search should actually not be binary but... octary?

Re: Beautiful branchless binary search

#62

Post by spc476 »

Dwedit wrote: post #41
rowanG077 wrote: post #2

Nice algorithm. I don't agree that it is branchless however. Cmov is a branching instruction for sure. And it doesn't really matter whether a branch can be well predicted. The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information. Calling this algorithm branchless devalues the term into something meaningless. Edit: Everybody in the comments is focusing on p…

I just had it pointed out to me that CMOV can be simulated with subtraction and bitwise operators. Specifically, subtraction, arithmetic shift right, and AND. `((A-B) ASR 31) AND C`. Your result is C if `A - B = 0`.

In C, shifting signed integers is undefined behavior.

Re: Beautiful branchless binary search

#64

Post by mcv »

TuringTest wrote: post #50
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…

Wasn't C created to avoid matching hardware? I.e. not caring about word size, number of registers, instruction set, etc. I thought the whole point of writing programs in C was originally being able to write portable software (and a portable OS) that could be executed at different machines? It only became specialized in giving machine-specific instructions when other languages took over.

Exactly. I'd rather have a way that guarantees this algorithm to be branchless regardless of the compiler and underlying hardware. Although I suppose it depends on the underlying hardware whether or not being branchless offers any advantage at all.

Of course compilers should be optimising for the hardware they're compiling for, but this article shows that can be very hit-and-miss.

Re: Beautiful branchless binary search

#65

Post by Aissen »

rowanG077 wrote: post #33
berkut wrote: post #3

Earlier quoted context omitted.

> "The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information." Erm, that likely depends on the industry you're in? In HPC, branchless algorithms are often needed to use wide architectures (SIMD / GPUs) to their full capacity...

It's a requirement thing. For security the requirement is code needs to be branchless. In HPC the requirement is high performance, the branchless algorithm is an implementation detail. In fact branchless code is often much slower then the branching version.

You don't really want branchless in security. The requirement is constant-time and side-channel resistance. The branchless algorithm is an implementation detail.

Re: Beautiful branchless binary search

#66

Post by pjmlp »

TuringTest wrote: post #50
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…

Wasn't C created to avoid matching hardware? I.e. not caring about word size, number of registers, instruction set, etc. I thought the whole point of writing programs in C was originally being able to write portable software (and a portable OS) that could be executed at different machines? It only became specialized in giving machine-specific instructions when other languages took over.

The whole point of creating C was to make UNIX portable, there were already other efforts with the same purpose going on the industry since JOVIAL creation in 1958.

Re: Beautiful branchless binary search

#67

Post by vidarh »

WithinReason wrote: post #61
vidarh wrote: post #49

Earlier quoted context omitted.

You don't store data nodes, or pointers. You store the keys. If you need to store data, just store them at the same index in another array. The pointers are wholly implicit . E.g. assuming you let the index 0 be empty, the left pointer for a node k is at 2k and the right node is at 2k+1. In terms of benefit here, the main benefit appears to be that since you always know where the children will be, you can trade bandw…

So binary search should actually not be binary but... octary?

I wondered about this too, there's an ongoing tradeoff there between the cost of computing which branch to take vs. how much that improves locality.

But seems they did as well. See the graph at the bottom which compares against a (Eytzinger-style) B-tree, which is basically taking that approach. You do more comparisons per node to figure out which branch to take, but fetch less memory.

Given the overall performance they show is very similar, the question if you want to scale this basically becomes whether your system saturates available cores or available memory bandwidth first.

(Would have been interesting to see comparisons of a quaternary and octonary version as well, though as their B-tree test seems to rely on 16 branches, and maybe the sweet spot is somewhere in between)

Re: Beautiful branchless binary search

#68

Post by gpderetta »

berkut wrote: post #36
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…

Yeah, it's mildly annoying there's no (at least to my knowledge?) compiler hint like the '__builtin_expect' ones to tell compilers that the values are very unlikely going to be predictable with enough accuracy to allow the branch predictors to be useful in general, and to use a cmov instead of the traditional branching instructions because of this.

GCC has __builtin_expect_with_probability now. YMMV.

Re: Beautiful branchless binary search

#69

Post by srcreigh »

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…

Pretty cool stuff. The algorithm returns the largest item that’s at most the size of x. At each step it checks array[k] and then checks either 2k or 2k+1 next.

The last k will be past the end of the array so you have to backtrack to discover the actual lower bound.

k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s.

How to do that though? There’s an assembly instruction called ffs that will give you the first bit set from the right side. So invert k to get 010000, ffs gives you 4. So for k 101111, shift forward by 4, you get 10. Cancel the right turns, now you have the index of the lower bound.

Re: Beautiful branchless binary search

#70

Post by witcher »

Thanks for sharing!

This is epic prove that we can still learn a lot from developers in 1980! Recently wrote "Effient Go" book and there were tons of valuable info from that era, and we usually skip this knowledge thinking it's irrelevant.

Post reply on HN