▲ 118 points
back
16 comments
Author here. There is a newer and significantly expanded version of the article: https://en.algorithmica.org/hpc/data-structures/binary-searc...
Thank you for your incredible work! I have been reading Algorithms for Modern Hardware as part of my after-work study and I have found it invaluable—I reference it daily.
I can’t wait for Part II :)
Thank you for your article. I had difficulty understanding the "Binary search implementation" section of the original article for various reasons, despite knowing what binary search is, being familiar with the 2k/2k+1 encoding (from binary heaps), and generally thinking I understood what you're trying to do. I wondered if was the only one struggling with this.
Among the difficulties:
"restore the index of the resulting element" - it's not clear what this means until after reading the remainder of the section (many times, in my case, due to other difficulties)
"We compare it against 4, 2, and 5..." - An error? You compared 'x' against 4, 2, and 3, or b[1], b[2], and b[5], but never against 5 - this would be to the right of 4 and a binary search would not visit it.
"..and so we just need to find the number of trailing ones in the binary notation and right-shift by exactly that amount." - You need to shift right that amount plus one. In your example for search(4), after the loop and prior to shifting k=11. In binary this is 1011, which has two trailing ones, but must be shifted right by 3 bits (not 2) to yield k=1 such that b[k] == 4.
"eytzinger: 4 2 5 1 6 3 7 8" - it took me surprisingly long to realize this was describing the permutation of values of a[] to indexes of b[] rather than listing the contents of b[] itself with the zero element elided (which coincidentally are the same for the first two elements, despite otherwise not making any sense). Perhaps brevity forces this sort of thing.
The presence of 8 in the example's array appears to be an error. At index 8 it would be the left child of 1, which it can't be. Letting n=7 and a={1,2,3,4,5,6,7} agrees with your example, whereas including 8 and setting n=8 rearranges things and forces the root to be 5 rather than 4.
Thanks for organizing this information into one place! It's super interesting and really relevant to high performance software. A lot of this material is scattered between conference talks, obscure forums, and hacks in closed-source software.
So, in your implementation, you always reduce the search range to n - n/2 to avoid branches. Why can it not be always n/2 - seeing as you've just examined and ruled out your middle element? i.e. seeing as how n/2 >= (n-1)-(n-1)/2 ?
This is a tricky part. The middle element is still part of the search range if we go "left" (≥). After we compare against it, the search range length becomes either floor(n/2) or ceil(n/2), in the latter case including the middle element (we will never compare against it again, but it still needs to be the first element of the search range).
To avoid additional checks and branching, we can just always make the next search range length ceil(n/2), effectively adding that middle element to the search range in case we go "right" (<).
There exists a 2022 CPPcon presentation covering efficient binary searching, which includes Eytzinger layouts [1].
[1] https://github.com/CppCon/CppCon2022/blob/main/Presentations...
Also available on YouTube: https://www.youtube.com/watch?v=1RIPMQQRBWk
Relevant recent HN thread:
https://news.ycombinator.com/item?id=35737862
(Beautiful branchless binary search)
very nice. small remark: iirc, there's a risk of overflow if you naively do `m = (l + r) /2`
tl;dr:
1. Avoid branching by always reducing the search range from n to n-n/2 (never n/2).
2. Preprocess the input (a sorted array) to Eytzinger order: Middle element, then first and third quartile elements etc. Now, if your search checks an element at position k, it will next want to look at either position 2k or 2k+1.
3. Some minor tweaks like aligned storage and rounding up size to a power of 2.
A good alternative to binary search on modern hardware that should not be overlooked is indexed sequential search.
I would recommend using a larger value (eg 10) to limit the amount of space overhead. RocksDB uses a similar data structure to search through SSTables although they call it something else (can’t find the link where they describe it).
This looks like a less efficient version of skip lists.
Skip lists are more complex, require more pointer storage and are really intended for more dynamic data.
I would label this more of a hybrid hash/lookup table --- but without any wasted storage space.
The key observation here is that on modern hardware, a simple, linear, fully cache based search of 20-30 elements is often faster than a binary search. If a pre-computed index can easily and efficiently narrow the average linear search range down to this level, it is likely to be faster.
But re-arranging into Eytzinger order is sorta equivalent to building an index so as always, apply your own judgment.
Eytzinger layouts are great, but they require more space if one is not allowed to touch the original sorted array. Then again, if you are allowed to use extra space, binary search can be implemented in worst-case constant time for integer arrays.