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

Fastest branchless binary search

mhdm.dev

Post reply on HN
Print view View original

101–110 of 155 posts

Re: Fastest branchless binary search

#101

Post by foldr »

twoodfin wrote: post #5
foldr wrote: post #2

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.

Presumably it’s not about matching the dynamic branch prediction estimate but rather exploiting static (or profile-provided) information to assist other optimizations. Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than on…

Good point. That's the only plausible explanation in this thread, I think. However, if you're at the level of performance tuning where you want to optimize inlining beyond the compiler defaults, I would have thought that it would make more sense to just experiment with forcing certain functions to be inlined or not.

Re: Fastest branchless binary search

#102

Post by bjourne »

On my Cascade Lake processor "-mllvm -x86-cmov-converter=false" almost halves the performance of the binary search:

    | Benchmark | gcc  | clang | clang -cmov |
    |-----------|------|-------|-------------|
    | slow u32  | 23.4 | 46.7  | 45.8        |
    | fast u32  | 18.1 | 19.8  | 31.4        |
The numbers are nanoseconds/bsearch on a 100mb uint32 array. Seem to me that clang (15.0.7) is just much worse at optimizing this particular piece of code than gcc (13.2.1). You can see the assembly here https://godbolt.org/z/cbx5Kdjs6. The gcc assembly looks way cleaner to me.

Re: Fastest branchless binary search

#103

Post by insanitybit »

User23 wrote: post #59
eru wrote: post #38

Earlier quoted context omitted.

> Also, what's wrong with C? Oodles and oodles of undefined behaviour, for example. C ain't clean.

Nah, thanks to CompCert[1] C actually has one of the highest quality and most predictable compilers. [1] https://compcert.org/

What is the practicality of actually using CompCert? And what does it actually defend against?

All I know is that it tries to ensure that the behavior of the program is the same as the input, meaning that the compiler itself does not have bugs. But how does that actually interact with undefined behavior in the language? What happens to an array out of bounds?

And what are the limitations imposed, since it only works on a subset of the C language?

It seems unlikely that I could just switch compilers and suddenly have a safe program written in C.

Re: Fastest branchless binary search

#104

Post by phire »

dragontamer wrote: post #75
3cats-in-a-coat wrote: post #72

Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…

> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run…

To add to this, the amount of speculation modern CPUs do is insane.

In the "theLoop" example, say the first load misses L1 and L2 cache and takes needs 40 cycles to load.

AMD's Zen 4 has enough resources to issue about 64 iterations of "theLoop:" all before that first load needs to complete. With the micro op cache, it can probably issue those 64 loop iterations in about 35 cycles.

Zen 4 has enough resources to start all 64 loads early, so they run in parallel.

Who cares if there is a branch mispredict and it you actually needed to do only 16 iterations of "theLoop"? In this example, the loop length isn't dependant on any of the loads so the CPU can actually finish executing the "add ecx, 4; cmp max; jnz theLoop;" instructions of the first 16 iterations of the "theLoop". And then detect the mispredict, flush the pipeline and load the correct branch location, all before the 40 cycles it takes for that first load to complete.

------

It's just absolutely insane. No short pipeline without a branch predictor could possibly compete.

Re: Fastest branchless binary search

#105

Post by scottlamb »

Const-me wrote: post #78
3cats-in-a-coat wrote: post #72

Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…

> as it's not a very stateful algorithm It might be stateless, but it depends on many things unknown at compile time. One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found. Another one is micro-architecture, most notably cache hierarchy, and composition of EUs inside codes. If you switch to ISA with instructions resembling the micr…

> > > as it's not a very stateful algorithm

> It might be stateless, but it depends on many things unknown at compile time.

> One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found.

Are you and 3cats-in-a-coat are talking about the same "it"? I think they're talking about the work that requires such a long pipeline [1], as they've stated that doing more ahead of time would reduce the length of the pipeline and thus importance of accurate branch prediction. You are talking about...the branch predictor? the application's algorithm being executed (binary search in this case)?

[1] my CPU microarchitectural knowledge isn't that good; I have only the vaguest idea of what that is. Register renaming / data dependency analysis / instruction scheduling, maybe? translation to micro-ops? other things? don't know!

Re: Fastest branchless binary search

#106

Post by pclmulqdq »

gpderetta wrote: post #24
pclmulqdq wrote: post #17

Earlier quoted context omitted.

I believe this happens because branch prediction lets you pipeline multiple simultaneous comparisons, and rewind whenever the branch predictor is wrong (about half the time for truly random data and inputs). The CMOV approach blocks after each comparison function due to the data dependency. On average, you're doing two comparisons at a time with branches, and one with CMOV, so when comparison time is greater than bra…

Switching to an N-way search (for N>2) could help extract the lost parallelism. At the cost of touching more cachelines though, so it is not necessarily a win.

You're also wasting a lot of work doing that. If you go two levels deep, you now do 2 comparisons per iteration (caching the result from the previous level), but you are guaranteed to waste one of those. The CPU with branch predictor is doing about 1.5 comparisons per iteration (worst case) thanks to the 50% mispredict rate, although this depends a lot on how long the comparison takes: a very long comparison function will converge to 1 comparison per iteration. Only if you replicate the speculation for yourself - which will necessarily have to be a lot worse than a CPU branch predictor to be fast and branchless - do you have any hope of an efficiency gain.

Re: Fastest branchless binary search

#108

Post by einpoklum »

postalrat wrote: post #77

How can you call it branchless if it has "while (length > 0) {"

Because that's a branch that's "always" taken, except for once - which, speed-wise, is very close to always taken, i.e. not a branch. The author counts the branching inside the loop, which is often taken and often not taken.

Re: Fastest branchless binary search

#109

Post by alain94040 »

I don't get it. The problem with binary search and branches is not the branches themselves, it's the fact that until you have done the comparison, you don't know which memory location in the array to fetch next. It doesn't matter if you use branches or anything else, the question is what do you want the processor to do?

There is a data dependency: until I read the middle index, I can't tell if I want to search the data in the upper section or the lower section. I can speculate and issue reads to both. That would fix the dependency, but create more memory traffic. Is this the right trade-off?

What do you want? Removing branches is not it.

Re: Fastest branchless binary search

#110

Post by returningfory2 »

alain94040 wrote: post #109

I don't get it. The problem with binary search and branches is not the branches themselves, it's the fact that until you have done the comparison, you don't know which memory location in the array to fetch next. It doesn't matter if you use branches or anything else, the question is what do you want the processor to do? There is a data dependency: until I read the middle index, I can't tell if I want to search the da…

If the array is fully in L1 cache, isn't the cost of the branch mis-predict much greater than the memory fetches?
Post reply on HN