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

111–120 of 155 posts

Re: Fastest branchless binary search

#111

Post by gpderetta »

pclmulqdq wrote: post #106
gpderetta wrote: post #24

Earlier quoted context omitted.

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…

You do additional comparisons at each recursion depth, but you have a shallower recursion depth though. I think you break-even already at 4-way search.

Re: Fastest branchless binary search

#112

Post by alain94040 »

returningfory2 wrote: post #110
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?

Full array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.

Re: Fastest branchless binary search

#113

Post by LegionMammal978 »

insanitybit wrote: post #103
User23 wrote: post #59

Earlier quoted context omitted.

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…

It looks like CompCert explicitly does not attempt to prevent UB from resulting in unpredictable behavior; all it guarantees is that "the observable behavior of [the compiled code] C improves on one of the allowed observable behaviors of [the source program] S", where "improving on" allows for arbitrary behavior on UB [0]:

> Third, the compiler is allowed to improve the behavior of the source program. Here, to improve means to convert a run-time error (such as crashing on an integer division by zero) into a more defined behavior. This can happen if the run-time error (e.g. division by zero) was optimized away (e.g. removed because the result of the division is unused). However, if the source program is known to be free of run-time errors, perhaps because it was verified using static analyzers or deductive program provers, improvement as described above never takes place, and the generated code behaves exactly as one of the allowed behaviors of the source program.

So you still have to prove your program's correctness by some other means.

[0] https://compcert.org/man/manual001.html#sec3

Re: Fastest branchless binary search

#114

Post by dragontamer »

phire wrote: post #104
dragontamer wrote: post #75

Earlier quoted context omitted.

> 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…

Yeah, its not so much a game of "don't use the branch predictor". Its more so a game of "definitely use the branch predictor, but eliminate unnecessary branches so that the branch-predictor can be used on more important parts of your code".

I don't think people realize how much branch predictor + Out-of-Order + superscalar builds and combines with each other to build modern CPUs. Its done this way for a reason.

Re: Fastest branchless binary search

#115

Post by [deleted] »

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…

[deleted]

Re: Fastest branchless binary search

#116

Post by mhh__ »

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…

People have spent probably a billion dollars trying to get this to work. It's a noble goal but when will it actually stick?

Re: Fastest branchless binary search

#117

Post by thefifthsetpin »

alain94040 wrote: post #112
returningfory2 wrote: post #110

Earlier quoted context omitted.

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

Full array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.

Binary search reduces the search space exponentially as it proceeds, so actually quite a lot of the total comparisons can hit L1d cache. (Maybe half of them for a ~250GB dataset.)

Of course, you could keep a cacheable partial index of your huge dataset to accelerate the early part of your search as well.

Re: Fastest branchless binary search

#118

Post by sltkr »

w0mbat wrote: post #23

Is that still lower_bound? Maybe I am misreading the code but it looks like this returns any match, not the earliest match (when there are dupes). It’s common to have multiple matches even in a unique list if the comparison function is say looking for a certain string prefix to do autocomplete, but we want the earliest in the list.

As far as I can tell it does return the earliest match. Why do you think it doesn't?

Re: Fastest branchless binary search

#119

Post by User23 »

LegionMammal978 wrote: post #113
insanitybit wrote: post #103

Earlier quoted context omitted.

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…

It looks like CompCert explicitly does not attempt to prevent UB from resulting in unpredictable behavior; all it guarantees is that "the observable behavior of [the compiled code] C improves on one of the allowed observable behaviors of [the source program] S ", where "improving on" allows for arbitrary behavior on UB [0]: > Third, the compiler is allowed to improve the behavior of the source program. Here, to impro…

You have to scroll down a bit, but see here[1]. Also searching [site:regehr.org compcert] will find more. CompCert C makes it impossible to reproduce at least some UB bugs:

  For CompCert, the high-level correctness theorems I proved are all of the first kind above: if the source program goes wrong, nothing is guaranteed about the behavior of the compiled code.  It happens, however, that the stepwise simulation lemmas I build on actually prove property 2 above: the compiled code cannot crash "earlier" than the source code, and will produce the same pre-crash observables, then possibly more.  So maybe I should strengthen my high-level correctness theorems...
That was over a decade ago, so perhaps it's been done. I confess I haven't closely followed CompCert in some time, due to having priorities elsewhere. As you can see elsewhere in that reference CompCert C will fail to generate the example UB code.

But yes, mechanically proving additional properties with some kind of SAT solver is also an open area of research. Dafny is the example I’m familiar with. Its conditions and invariants allow things like automatically proved binary search[2]. Converting CompCert C statements to SMTLibv2 assertions (which is, to an extremely rough first approximation what Dafny does) would certainly be considerably easier than it would be for most other languages. It would still be a serious effort of course.

[1] https://blog.regehr.org/archives/232

[2] https://github.com/dafny-lang/dafny/blob/master/Test/dafny4/...

Re: Fastest branchless binary search

#120

Post by sltkr »

postalrat wrote: post #77

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

This is literally addressed in the article:

    More branchless, more better?
    Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k  0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through.
    
    size_t length = last - first;
    size_t rem;
    switch(std::bit_width(length)) {
       case 64:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       case 63:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       // ...
       case 1:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
    }
    return first;
    
    If you’re not familiar with switch, think of it as a jump into code. In our case to the exact place from which there are exactly the right number of comparisons left to do.
    
    “Is it any faster?” No. Modern x86 processors handle loop conditions well as they’re predictable; we’re very likely to remain in the loop. And that’s good especially because it saves us from writing templates or macros or copy-paste-edit the 64 cases.
(Maybe people will RTFA if I paste it into the comments.)
Post reply on HN