←back to thread

386 points ingve | 1 comments | | HN request time: 0s | source
Show context
2102922286 ◴[] No.35738100[source]
A cool related algorithm is 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!

replies(8): >>35738287 #>>35738451 #>>35738561 #>>35739155 #>>35740049 #>>35740397 #>>35740690 #>>35744101 #
1. jeffreygoesto ◴[] No.35738287[source]
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.