4 ms·

A cool related algorithm is https://algorithmica.org/en/eytzinger https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cac

A cool related algorithm is https://algorithmica.org/en/eytzinger https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cache properties than a standard binary search tree. If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting extra strain on the cache (or the reads won't be cached). The CPU cache performs much better if the values you want to read are close to each other. Enter the Eytzinger Binary Search. The idea is that, if you're always going to be accessing the root of the tree, and then one of its two children--you should just put those children physically close to the root, so they'll all be on the same cache line!

srcreigh 3y ago
Pretty cool stuff. The algorithm returns the largest item that’s at most the size of x. At each step it checks array[k] and then checks either 2k or 2k+1 next. The last k will be past the end of the array so you have to backtrack to discover the actual lower bound. k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s. How to do that though? There’s an assembly instruction called ffs that will give you the first bit set from the right side. So invert k to get 010000, ffs gives you 4. So for k 101111, shift forward by 4, you get 10. Cancel the right turns, now you have the index of the lower bound.
- contravariant 3y ago
  Don't you just need to remove the trailing 1s? In that case it's just `x & (x+1)`
  - srcreigh 3y ago
    No, that would just set trailing 1s to 0. We want to trim them. The idea behind trimming trailing 1s is that they represent a sub tree that is all smaller than the lower bound. By trimming those 1s, we traverse back up the tree to find the smallest number which is larger than or equal to the lower bound (aka the answer).
- deleted 3y ago
  [deleted]
- srcreigh 3y ago
  typo: smallest number at least as big as x
mihaic 3y ago
Thinking about cache-optimality, I'm wondering if anyone is using a hybrid: the first levels are in this way (index K branches to 2K and 2K+1 if 1-based), but the end levels are consecutive to then can be loaded in a single cacheline anyway.
blondin 3y ago
are you going to have a printed version of your book?
utopcell 3y ago
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, lower_bound operations (aka binary searching) can be implemented in worst-case constant time for integer arrays.
vlovich123 3y ago
IIRC it really only works well if you have a rarely mutated structure that's read-heavy. Otherwise every time you try to mutate the array, you have to rebuild the layout & it's typically heavier than just sorting (i.e. you have to sort + regenerate the layout). It's a neat concept for sure.
jeffreygoesto 3y ago
Do they publish if getting the tree/array in shape initially or inserting an element is significantly different in speed to the plain sorted layout? The method is a nice read optimization and you'd need to check if it amortizes when sun together with the tree creation.
srcreigh 3y ago
Trying to figure this out myself. So cache line is 64 bytes. Ignoring pointers you can fit eight 8bit data/key values, or sixteen 4bit data/key values. Pointers are entirely implicit (thx user below) This would save you 3 or 4 memory reads respectively. The odds of this strategy helping past the first few layers seems unlikely. So for 100k elements binary tree, this should be a 21% or 31% performance improvement respectively. That’s 17 vs 14 and 17 vs 13 reads. And this would not help much for string data values unless the strings are at most 8 characters long :-) This same thinking can be used to optimize database queries. Given several table and index layouts how many 8kb disk reads will be needed in each case. Wish I could get a job doing that kind of design work!
- srcreigh 3y ago
  typo: mixed up bit and byte when referring to the different integer sizes
- atq2119 3y ago
  The big advantage of the Eytzinger layout actually comes into play when your binary search isn't branch-free. In that case, the CPU will speculate loads reasonably far ahead, and because both choices tend to be in the same cacheline, this prefetch is rarely wasted. In other words, the big win isn't about reducing the number of cacheline fetched, it's about reducing the effective latency of those fetches. That said, using a similar layout with higher fan-out and SIMD ops doesn't benefit from this effect and is probably still better.
  - srcreigh 3y ago
    I think effective latency and reducing the number of cache lines is probably the exact same thing. The point is instead of fetching 5 cache lines to get to the 5th layer of the tree from memory, you fetch just 2 and access the mega root node via cache.
- vidarh 3y ago
  You don't store data nodes, or pointers. You store the keys. If you need to store data, just store them at the same index in another array. The pointers are wholly implicit. E.g. assuming you let the index 0 be empty, the left pointer for a node k is at 2k and the right node is at 2k+1. In terms of benefit here, the main benefit appears to be that since you always know where the children will be, you can trade bandwidth for latency and trigger pre-fetching of the next step down before you've even decided if you're going left or right.
zelphirkalt 3y ago
Isn't that like storing a heap inside an array, with indices and values like this: 0: top of heap, 1: left of top, 2: right of top, 3: left of left of top ... ?
- contravariant 3y ago
  It is, but so is storing a sorted array.
  - account42 3y ago
    It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that case if you can control the data structure then there are many more options.
    - eska 3y ago
      I agree with you. Algorithms don’t exist in a bubble, but are always accompanied with a data structure. A heap sorted array is different from a linearly sorted array. Binary search is only defined for the latter.

srcreigh 3y ago

Pretty cool stuff. The algorithm returns the largest item that’s at most the size of x. At each step it checks array[k] and then checks either 2k or 2k+1 next. The last k will be past the end of the array so you have to backtrack to discover the actual lower bound. k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s. How to do that though? There’s an assembly instruction called ffs that will give you the first bit set from the right side. So invert k to get 010000, ffs gives you 4. So for k 101111, shift forward by 4, you get 10. Cancel the right turns, now you have the index of the lower bound.

contravariant 3y ago
Don't you just need to remove the trailing 1s? In that case it's just `x & (x+1)`
- srcreigh 3y ago
  No, that would just set trailing 1s to 0. We want to trim them. The idea behind trimming trailing 1s is that they represent a sub tree that is all smaller than the lower bound. By trimming those 1s, we traverse back up the tree to find the smallest number which is larger than or equal to the lower bound (aka the answer).
deleted 3y ago
[deleted]
srcreigh 3y ago
typo: smallest number at least as big as x

mihaic 3y ago

Thinking about cache-optimality, I'm wondering if anyone is using a hybrid: the first levels are in this way (index K branches to 2K and 2K+1 if 1-based), but the end levels are consecutive to then can be loaded in a single cacheline anyway.

blondin 3y ago

are you going to have a printed version of your book?

utopcell 3y ago

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, lower_bound operations (aka binary searching) can be implemented in worst-case constant time for integer arrays.

vlovich123 3y ago

IIRC it really only works well if you have a rarely mutated structure that's read-heavy. Otherwise every time you try to mutate the array, you have to rebuild the layout & it's typically heavier than just sorting (i.e. you have to sort + regenerate the layout). It's a neat concept for sure.

jeffreygoesto 3y ago

Do they publish if getting the tree/array in shape initially or inserting an element is significantly different in speed to the plain sorted layout? The method is a nice read optimization and you'd need to check if it amortizes when sun together with the tree creation.

srcreigh 3y ago

Trying to figure this out myself. So cache line is 64 bytes. Ignoring pointers you can fit eight 8bit data/key values, or sixteen 4bit data/key values. Pointers are entirely implicit (thx user below) This would save you 3 or 4 memory reads respectively. The odds of this strategy helping past the first few layers seems unlikely. So for 100k elements binary tree, this should be a 21% or 31% performance improvement respectively. That’s 17 vs 14 and 17 vs 13 reads. And this would not help much for string data values unless the strings are at most 8 characters long :-) This same thinking can be used to optimize database queries. Given several table and index layouts how many 8kb disk reads will be needed in each case. Wish I could get a job doing that kind of design work!

srcreigh 3y ago
typo: mixed up bit and byte when referring to the different integer sizes
atq2119 3y ago
The big advantage of the Eytzinger layout actually comes into play when your binary search isn't branch-free. In that case, the CPU will speculate loads reasonably far ahead, and because both choices tend to be in the same cacheline, this prefetch is rarely wasted. In other words, the big win isn't about reducing the number of cacheline fetched, it's about reducing the effective latency of those fetches. That said, using a similar layout with higher fan-out and SIMD ops doesn't benefit from this effect and is probably still better.
- srcreigh 3y ago
  I think effective latency and reducing the number of cache lines is probably the exact same thing. The point is instead of fetching 5 cache lines to get to the 5th layer of the tree from memory, you fetch just 2 and access the mega root node via cache.
vidarh 3y ago
You don't store data nodes, or pointers. You store the keys. If you need to store data, just store them at the same index in another array. The pointers are wholly implicit. E.g. assuming you let the index 0 be empty, the left pointer for a node k is at 2k and the right node is at 2k+1. In terms of benefit here, the main benefit appears to be that since you always know where the children will be, you can trade bandwidth for latency and trigger pre-fetching of the next step down before you've even decided if you're going left or right.

zelphirkalt 3y ago

Isn't that like storing a heap inside an array, with indices and values like this: 0: top of heap, 1: left of top, 2: right of top, 3: left of left of top ... ?

contravariant 3y ago
It is, but so is storing a sorted array.
- account42 3y ago
  It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that case if you can control the data structure then there are many more options.
  - eska 3y ago
    I agree with you. Algorithms don’t exist in a bubble, but are always accompanied with a data structure. A heap sorted array is different from a linearly sorted array. Binary search is only defined for the latter.