Since the cpu always accesses a full cache line (64 bytes) at a time, you might as well search the entire cache line (it’s practically free once the data is on-cpu). So I’d like to try a ‘binary’ search that tests all the values in the ‘middle cache line’ and then chooses to go left or right if none match. You can do the cache line search as a single 512bit simd instruction. A cache line is 64 bytes (or 32 16-bit integers); such a search might well be almost 32 times faster than simple binary search; at least it’ll do 32x less memory accesses, which will dominate in most realistic programs.
You can beat the binary search
91–100 of 175 posts
Re: You can beat the binary search
#92Earlier quoted context omitted.
> 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 Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on thi…
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 delta from the previous item you looked at.
Re: You can beat the binary search
#93Earlier 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…
And you always start off knowing the total length of the array, and the width of the datatype.
Actually deciding what to do with that information without incurring a bunch more cache misses in the process may be tricky.
Re: You can beat the binary search
#94Earlier 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…
> knowing the position and value of two elements in a sorted list That's a prior about the distribution, if a relatively weak one (in some sense, at least).
Re: You can beat the binary search
#95See also: Static search trees: 40x faster than binary search
- https://curiouscoding.nl/slides/p99-text/
- https://curiouscoding.nl/posts/static-search-tree/
- https://news.ycombinator.com/item?id=42562847 (656 points; 232 comments)
Re: You can beat the binary search
#96Earlier quoted context omitted.
I guess it matters if you have to do lookup in a tight loop. If you do this occasionally, I think it's not worth it, especially for complex objects with custom comparators. The algorithm is still O(log(n)) just a more advanced "divide and conquer" with smaller constant.
I would expect the standard library of various languages to provide an optimised implementation such as this. Then everyone downstream benefits, and benefits from future improvements when compiled for a newer version of the language / executed under a newer version of the runtime. You see this in rust, where they replaced the hash tables many years ago, the channel a couple of years ago, and most recently the sort im…
I wouldn't. This is very specialized to the type of the elements.
Re: You can beat the binary search
#97Since the cpu always accesses a full cache line (64 bytes) at a time, you might as well search the entire cache line (it’s practically free once the data is on-cpu). So I’d like to try a ‘binary’ search that tests all the values in the ‘middle cache line’ and then chooses to go left or right if none match. You can do the cache line search as a single 512bit simd instruction. A cache line is 64 bytes (or 32 16-bit int…
Searching the upper cache lines in your binary search tree (sorted vector) for your target is unlikely to yield results. Instead you want to use the extra data in the line to shorten the search, which leads you to a B-Tree or B+tree.
For 4 byte keys and 4 byte child pointers (or indexes in to an array) your inner nodes would have 7 keys, 8 child pointers and 1 next pointer, completely filling a 64 byte cache-line and your tree depth for 1 million entries would go down from ~20 to ~7, the top few levels of which are likely to remain cache resident.
With some thought, it's possible to use SIMD on B-tree nodes to speed up the search within the node, but it's all very data dependent.
Re: You can beat the binary search
#98If you know about the distribution of keys you can do even better by factoring that knowledge into where you split.
Re: You can beat the binary search
#99Earlier quoted context omitted.
You can't beat binary search in Guess Who. From the abstract: >> Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. The reason that's optimal, if you're losing, is that you assume that your opponent, who isn't losing, is going to use binary search. They're going to use binary search because it's the optimal way to find the secret. Since you're behind, if you…
You're mixing two different objectives the paper presents. You can't beat binary search when the objective is to minimise the expected number of turns in a single player setting . However, in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played. Here's another visual demonstration: https://www.youtube.com/watch?v=zmv…
What do you think you're saying that I didn't already say?
> in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played.
This is technically true. But 50 percentage points of your "more than 50%" of games played are games where you exclusively use binary search. For the remainder, you're redistributing luck around between potential games in a way that is negative-sum, exactly like I just said.
Re: You can beat the binary search
#100I always wondered if we could get any faster than O(log n). Glad we're making progress!