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

41–50 of 198 posts

Re: Beautiful branchless binary search

#41

Post by Dwedit »

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`.

Re: Beautiful branchless binary search

#42

Post by SleepyMyroslav »

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 control what they write. Plug and pray compilation is not a solid engineering approach.

Re: Beautiful branchless binary search

#43

Post by Sesse__ »

kevingadd wrote: post #19
2102922286 wrote: post #12

Earlier quoted context omitted.

Cmov doesn't branch. A branch refers specifically to the program counter ending up in more than one possible place after an instruction has executed. It is this behavior that mucks with the CPU state and slows everything down. It's true that the cmov instruction uses the CPU flags register (which I'm sure the CPU designers at Intel hate), but that doesn't mean that it branches. You can achieve the same effect as cmov…

The main problem with branches in an algorithm like this is that they create a dependency, where not only do the future instructions depend on the possibly-mispredicted outcome of the previous instruction and need to get thrown out, but you may have started executing the wrong instructions. A cmov doesn't affect the instruction pointer, so that 'executing the wrong instructions' condition is gone, but it still affect…

> IMO, cmov was far more valuable back when it was new, because branches were more expensive then.

Branches in general are cheaper now (since they are generally predicted better), but mispredicted branches are more expensive. They are similar in terms of cycles (IIRC Pentium 4 and Skylake are both typically around 20 cycles if you don't get second-order effects tacked on), but you generally get a lot more done in those cycles on a newer CPU, so they are much more important than they used to be. And a binary search will, almost by definition, tend to have 50% mispredicted branches on the compare (i.e., entirely unpredictable, so no better than random chance).

Re: Beautiful branchless binary search

#44

Post by zelphirkalt »

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…

Isn't that like storing a heap inside an array, with indices and values like this:

    0: top of heap,
    1: left of top,
    2: right of top,
    3: left of left of top
    ...

?

Re: Beautiful branchless binary search

#45

Post by cocoflunchy »

cmovq wrote: post #15

> 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 It’s been a long time since I looked into this, if I recall correctly binary search with close to power of 2 sized data is slower because of some interaction with the caches which causes the data to constantly have to be reloaded from memory.

[flagged]

Re: Beautiful branchless binary search

#46

Post by frankreyes »

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…

Because in the context of security you associate "branchless" with the time it takes is always the same regardless of the data/values, in order to mitigate a timing attack.

In this context, branchless means something different: the performance of the CPU is maximized for the given hardware, by not flushing the speculative execution of the CPU.

Re: Beautiful branchless binary search

#47

Post by gsliepen »

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…

What you gain is hardware independence. There is a lot of variation in CPUs, even if you stick with one vendor they will have in-order efficiency cores and out-of-order performance cores, and an algorithm optimized for one might not work as great on the other. I think it's better if time is spent by compiler engineers to produce good assembly on all CPUs, instead of giving tools to programmers to optimize their code for one particular CPU.

Re: Beautiful branchless binary search

#48

Post by pjmlp »

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…

The myth that they match has been busted since at very least Pentium came to be.

A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.

Re: Beautiful branchless binary search

#49

Post by vidarh »

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…

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 bandwidth for latency and trigger pre-fetching of the next step down before you've even decided if you're going left or right.

Re: Beautiful branchless binary search

#50

Post by TuringTest »

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.

Post reply on HN