←back to thread

386 points ingve | 1 comments | | HN request time: 0.228s | 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. mihaic ◴[] No.35740049[source]
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.