So you get at most seven 8bit data nodes or twelve 4bit data nodes per cache line. This would save you 2 or ~3.6 memory/highercache 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 13% or 18% performance improvement respectively. That’s 17 vs 15 and 17 vs 14.4 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!
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.
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.
But seems they did as well. See the graph at the bottom which compares against a (Eytzinger-style) B-tree, which is basically taking that approach. You do more comparisons per node to figure out which branch to take, but fetch less memory.
Given the overall performance they show is very similar, the question if you want to scale this basically becomes whether your system saturates available cores or available memory bandwidth first.
(Would have been interesting to see comparisons of a quaternary and octonary version as well, though as their B-tree test seems to rely on 16 branches, and maybe the sweet spot is somewhere in between)
https://en.wikipedia.org/wiki/B-tree
With caching on modern CPUs, as opposed to databases on disks, there are multiple levels of caching and you may not know the size of the caches. And the caches can be shared with other work you're doing, or other processes are doing, so the effective size can be smaller. So there's some benefit to algorithms that are independent of cache size.
When retrieving from disk you have far more cycles to work with before less disk-read sized blocks can get close to competitive.
Ya I agree re latency. In fact there’s no other option afaict. CPU always loads 64 bytes, just like Postgres always loads data in 8kb chunks (unless you compile Postgres to use different size)
0: top of heap,
1: left of top,
2: right of top,
3: left of left of top
...
?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.
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.
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).
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!