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

You can beat the binary search

lemire.me

Post reply on HN
Print view View original

151–160 of 175 posts

Re: You can beat the binary search

#151

Post by IIAOPSW »

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

>More generally, the best bet to solving a problem more efficiently is always to use more information about the specific problem you want to solve

It is both obvious and profound, the more information you already have, the more information you already have.

Re: You can beat the binary search

#152

Post by nchmy »

collabs wrote: post #147
eximius wrote: post #140

Earlier quoted context omitted.

Those are fairly indistinguishable. It's when they start removing letters from words to save... debug symbol bytes or something? That's when c-style naming annoys me.

This is also my pet peeve with a lot of code as well as commands like npm -g i package-name Like why would you teach people to do this? I understand people needed to save precious bytes in the sixties so we have cat and ls but saving 192 bytes or whatever with shorter variable names is not a worthwhile tradeoff anymore.

What exactly bothers you about this and what would you prefer to see?

Re: You can beat the binary search

#153

Post by unholiness »

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

More accurately, binary search is optimal only if you cannot determine distance between the data points (you can compute `<` but not `-`). It's inaccurate to say it's optimal if you know "nothing" about the distribution. If you encounter a point that's much closer to your high pivot vs much closer to your low pivot, there is no possible prior knowledge state uninformed enough to conclude that the best place to search in both cases is in the middle.

Re: You can beat the binary search

#154

Post by zug_zug »

I'd like to point out that all the graphs only go to 4,000 elements, which is basically non-data. Basically it'd be like measuring which car wins a 1cm race.

For small workloads binary search is slower than just checking every element.

To add to this, I think people can forget how small log(n) is... it can practically be seen as constant (as the log base 2 of ATOMS IN THE UNIVERSE is ~300).

Re: You can beat the binary search

#155

Post by charleslmunger »

ben-schaaf wrote: post #137
charleslmunger wrote: post #107

Earlier quoted context omitted.

I've spent some brainpower on binary search and have not been able to beat this: https://github.com/protocolbuffers/protobuf/blob/44025909eb7... 1. Check for dense list O(1) 2. Check upper bound 3. Constant trip count binary search The constant trip count is great for the branch predictor, and the core loop is pretty tightly optimized for the target hardware, avoiding multiplies. Every attempt to get more clever made…

For a pretty small N I've found that less clever can be quite a bit faster. I'd try a linear search - possibly SIMD if you can change the data format to struct-of-arrays. An adaptive approach that uses linear search up to a certain N can also yield some benefit.

The first implementation I encountered was a linear search, starting at the last-found field. Empirically it performed better to do a binary search with early exit and branchless bounds selection, I think due to branch predictor pressure. The data representation could be changed but it's tricky, as there are other traversals that want to go in sorted order, and there are lots of places that pass just one pointer for fields. But I agree any further improvement will probably have to come from that.

SIMD is tricky even with SoA because there is significant latency going between the general registers and the vector units, plus arm little cores can be configured to share a vector unit with another core.

Re: You can beat the binary search

#157

Post by drewg123 »

One thing that makes me nervous about the increased use of SIMD in new ways is that more processes will be using SIMD. This, in turn, make context switches that much more expensive as the SIMD registers must be saved and restored when switching to a new process that also uses SIMD.

Re: You can beat the binary search

#158

Post by Cthulhu_ »

drewg123 wrote: post #157

One thing that makes me nervous about the increased use of SIMD in new ways is that more processes will be using SIMD. This, in turn, make context switches that much more expensive as the SIMD registers must be saved and restored when switching to a new process that also uses SIMD.

Is this an actual, measurable, major issue or just a gut feeling? Context switches in general are suboptimal but pretty normal.

Re: You can beat the binary search

#159

Post by listeria »

This reminds me of two excellent articles[1][2] by Paul Khuong, in which he talks about using size-specialized binary search for power-of-two sized arrays (special-casing the first iteration for other sizes).

He uses conditional moves and defines the number of iterations in advance to ellide the often mispredicted branch, and in the second article goes on to fix cache aliasing issues for large vectors using ternary search.

[1]: https://pvk.ca/Blog/2012/07/03/binary-search-star-eliminates...

[2]: https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathologic...

Re: You can beat the binary search

#160

Post by taeric »

SuperV1234 wrote: post #23
taeric wrote: post #10

If you are talking smaller arrays, linear search with a sentinel value at the end is already tough to beat. The thing that sucks about that claim, is that "smaller" is such a nebulous qualifier that it is really hard to internalize.

That's not what the article is about.

Fair. I had meant my point to be an "in addition" and a pointer to more fun things to look up on it.
Post reply on HN