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

51–60 of 155 posts

Re: Fastest branchless binary search

#51

Post by andyg_blog »

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?

The C++ standard measures the time complexity of lower_bound and binary_search by the number of comparisons performed. So yes, it's possible on e.g., a linked list like std::list (by this definition)

Re: Fastest branchless binary search

#52

Post by shultays »

klysm wrote: post #40
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.

I guess it’s good to have the option of not caring if you want even more speed

My lower_bound is a bit better then

  template 
  constexpr ForwardIt super_optimized_lower_bound(
        ForwardIt first, ForwardIt last, const T& value, Compare comp) {
    return first;
  }
It doesn't really work like for some cases std::lower_bound but it is super fast

Re: Fastest branchless binary search

#53

Post by commonlisp94 »

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.

Good point. I don't think anyone actually uses it for containers that only support forward iteration. But the author did declare the signature with ForwardIterator.

Re: Fastest branchless binary search

#56

Post by ape4 »

hajrice wrote: post #22

I wish all blog posts started the way his does: "You’re a busy person so I’ll first jump right to it. Here it is, the fastest general (and simple) binary search C++ implementation:"

Except I am too busy to read "You’re a busy person"

Re: Fastest branchless binary search

#57

Post by TillE »

shmageggy wrote: post #3

> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to h…

An equivalent generic sort function in C would, at best, require a bunch of additional distracting cruft. This is exactly what C++ templates are for.

Re: Fastest branchless binary search

#58

Post by ectospheno »

Every post like this makes me update my junior engineer watchlist. Then I have to go patiently explain why mucking about in the code to save one instruction because you read a blog post is a horrible idea. Easily half of all silly junior code is pointless optimization.

Having said that, I did enjoy the post.

Re: Fastest branchless binary search

#59

Post by User23 »

eru wrote: post #38
shmageggy wrote: post #3

> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to h…

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

Re: Fastest branchless binary search

#60

Post by sph »

ectospheno wrote: post #58

Every post like this makes me update my junior engineer watchlist. Then I have to go patiently explain why mucking about in the code to save one instruction because you read a blog post is a horrible idea. Easily half of all silly junior code is pointless optimization. Having said that, I did enjoy the post.

What kind of junior engineers are you hiring that prematurely rewrite a hot loop to use branchless assembly logic?

The junior employees I have had to deal with tended to build towering abstractions that no one really needed, rather than optimising hot loops.

Post reply on HN