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

121–130 of 155 posts

Re: Fastest branchless binary search

#121

Post by jasonwatkinspdx »

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…

I'm sorry but this is completely mistaken.

Transmeta's translation did not somehow eliminate branch costs.

In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible."

Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real world, even with the monster caches we have now.

Itanium thought it could eliminate branch costs with static analysis. How did that work out?

I really wish programmers would actually read a book about computer architecture before they so confidently conclude that it's simple to build things better than state of the art processors. You are underestimating the scale of smart that has gone into current processors by at least 7 orders of magnitude in my opinion.

Re: Fastest branchless binary search

#122

Post by rtomanek »

jasonwatkinspdx wrote: post #121
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…

I'm sorry but this is completely mistaken. Transmeta's translation did not somehow eliminate branch costs. In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible." Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real…

Can you give some book recommendations, please?

Re: Fastest branchless binary search

#124

Post by jasonwatkinspdx »

rtomanek wrote: post #122
jasonwatkinspdx wrote: post #121

Earlier quoted context omitted.

I'm sorry but this is completely mistaken. Transmeta's translation did not somehow eliminate branch costs. In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible." Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real…

Can you give some book recommendations, please?

Hennessy and Patterson's Computer Architecture: A Quantitative Approach is the definitive textbook. They also have a 2nd textbook Computer Organization and Design. The former is more focused on people who might go after a Computer Engineering degree while the latter is more an exploration of microprocessor architecture relevant to a wide audience of programmers.

Previous editions are available free online and just as good for learning the big picture imo. Actually the older editions might be better for learning microarchitecture specifically because the more recent editions have cut some material on that in order to cover mobile and cloud computing.

Re: Fastest branchless binary search

#125

Post by mhdm »

LoganDark wrote: post #9

Does anyone know where the "BUT RUST" link was supposed to lead? It seems to be already out of date due to being unversioned, I can't tell whether it's supposed to lead to the middle of the `starts_with` doc comment or not.

It was meant to link to rust's binary search implementation. Updated to https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

Re: Fastest branchless binary search

#126

Post by mhdm »

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…

Prefetching is the right tradeoff for large arrays. Addressed at the end of the article: https://mhdm.dev/posts/sb_lower_bound/#prefetching

Re: Fastest branchless binary search

#127

Post by dzaima »

ot wrote: post #19
pixelesque wrote: post #15

Earlier quoted context omitted.

clang has one: https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...

Which also does not affect cmov conversion. Every time this comes up I bring up this long-standing LLVM bug: https://bugs.llvm.org/show_bug.cgi?id=40027

__builtin_unpredictable is gonna be fixed in LLVM/clang 17: https://github.com/llvm/llvm-project/commit/09515f2c20111628...

(also, bugs.llvm.org is old; the more up-to-date (but still open) issue is https://github.com/llvm/llvm-project/issues/39374)

Re: Fastest branchless binary search

#128

Post by kccqzy »

fn-mote wrote: post #36
andyg_blog wrote: post #25

This is not a valid drop in replacement for lower_bound. Accessing iterators as front[index] is only for random access iterators like vector has. The author may have realized this if they benchmarked on other containers.A forward iterator must be advanced and then dereferenced.

Can you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?

Observe that you can restrict your code to only call std::advance on the iterator. So definitely you could do binary search without random access, and you would actually iterate over all elements, but you just skip the comparison function for the majority of elements.

Re: Fastest branchless binary search

#129

Post by w0mbat »

sltkr wrote: post #118
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?

I am possibly confused, getting moreso the more I read the code. As it is ignoring the sign of the result of compare I don't even see how it would work at all. The sign is what tells you which half to throw away as you search.

Re: Fastest branchless binary search

#130

Post by postalrat »

einpoklum wrote: post #108
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.

It's not impossible to remove that branch. Until you do that then this is a reduced branch implementation.
Post reply on HN