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

131–140 of 175 posts

Re: You can beat the binary search

#131

Post by LorenPechtel »

kryptiskt wrote: post #92
molf wrote: post #88

Earlier quoted context omitted.

It's not possible to learn anything about other elements when performing binary search, _except_ the only thing there is to learn: if the target is before or after the recently compared element. If we would guess that there is a bias in the distribution based on recently seen elements, the guess is at least as likely to be wrong as it is to be right. And if we guess incorrectly, in the worst case, the algorithm degra…

> It's not possible to learn anything about other elements when performing binary search, _except_ the only thing there is to learn: if the target is before or after the recently compared element. You have another piece of information, you don't only know if the element was before or after the compared element. You can also know the delta between what you looked at and what you're looking for. And you also have the d…

Assuming your key space is anything like randomly distributed.

Thinking about it--yeah, if you can anticipate anything like a random distribution it's a few extra instructions to reduce the number of values looked up. In the old days that would have been very unlikely to be a good deal, but with so many algorithms dominated by the cache (I've seen more than one case where a clearly less efficient algorithm that reduced memory reads turned out better) I suspect there's a lot of such things that don't go the way we learned them in the stone age.

Re: You can beat the binary search

#132

Post by jibal »

ahartmetz wrote: post #117
echelon wrote: post #114

Earlier quoted context omitted.

I know protobuf code is extremely high quality, but I really can't stand the c-style naming conventions. I know people train themselves into grokking this and reading and emitting this way, but it sounds like writing "bork bork bork bork" runes to me. I'm glad Rust feels more like Ruby and Python and that method and field names are legible. My eyes just glaze over: UPB_API_INLINE const struct upb_MiniTableField* upb_…

I think this needs way more "upb" and "UPB" to make it clear that it is, in fact, dealing with UPBs. Whatever these are.

> μpb (often written 'upb') is a small protobuf implementation written in C.

Re: You can beat the binary search

#133

Post by dragontamer »

ted_dunning wrote: post #130

Seems like you can use the core intuition here of SIMD comparison of multiple elements on more than just the terminal scale. The outline would be: a) use a gather to grab multiple elements from 16 evenly spaced locations b) compare these in parallel using a SIMD instruction c) focus in on the correct block d) if the block is small revert to linear search, else repeat the gather/compare cycle Even though the gather in…

Gather is extremely slow. Anyone aiming for efficiency will avoid gathers.

I bet you a binary search is in fact faster than any gather based methodology.

Re: You can beat the binary search

#134

Post by dnnddidiej »

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…

For humans binary searching a dict is slower because it requires a different physical action vs. scanning and we have advanced OCR and flipping through capabilites. Especially recognizing when something hasnt changed e.g. still on Es keep flipping is maybe 10ms.

Re: You can beat the binary search

#135

Post by theptip »

dnnddidiej wrote: post #134
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…

For humans binary searching a dict is slower because it requires a different physical action vs. scanning and we have advanced OCR and flipping through capabilites. Especially recognizing when something hasnt changed e.g. still on Es keep flipping is maybe 10ms.

No the point is you know exactly where T is just by looking at the dictionary (or at least, you learn this if you use a dictionary a lot).

IOW your prior on the data distribution lets you skip the first 4-5 binary chops.

Re: You can beat the binary search

#137

Post by ben-schaaf »

charleslmunger wrote: post #107
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…

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.

Re: You can beat the binary search

#138

Post by ChadNauseam »

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.

If you control the layout, eytzinger layout typically will give you the best of both worlds. As fast as a linear scan for small N, much faster than binary search over a sorted array for large N.

Re: You can beat the binary search

#139

Post by locknitpicker »

darknoon wrote: post #82
locknitpicker wrote: post #78

Earlier quoted context omitted.

> If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. You don't even need priors. See interpolation search, where knowing the position and value of two elements in a sorted list already allows the search to make an educated guess about where the element it's searching for is by estimating the likely place it would be by inter…

This relies on knowledge of the distribution, just querying in the middle of A = [1, 2, 4, 8, 16, ..., 2^(n-1)] is slower than binary search

> just querying in the middle

It's an interpolation search. You interpolate the values you evaluated by whatever method you'd like. No one forces you to do linear interpolation. You can very easily fit a quadratic polynomial with the last 3 points, for example.

Interpolation search seems to have a convergence rate of log log n. That's pretty efficient.

Re: You can beat the binary search

#140

Post by eximius »

teo_zero wrote: post #119
echelon wrote: post #114

Earlier quoted context omitted.

I know protobuf code is extremely high quality, but I really can't stand the c-style naming conventions. I know people train themselves into grokking this and reading and emitting this way, but it sounds like writing "bork bork bork bork" runes to me. I'm glad Rust feels more like Ruby and Python and that method and field names are legible. My eyes just glaze over: UPB_API_INLINE const struct upb_MiniTableField* upb_…

> I really can't stand the c-style naming conventions. Honestly I don't see much difference between upb_MiniTable_FindFieldByNumber and upb::MiniTable::FindFieldByNumber

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.
Post reply on HN