5 ms·

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

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.
- srcreigh 3y ago
  That’s what I meant re keys, but ya nice point about pointers. Forgetting details of my data structures classes. updated my post (used to count 1 bit per node for pointers)
- WithinReason 3y ago
  So binary search should actually not be binary but... octary?
  - vidarh 3y ago
    I wondered about this too, there's an ongoing tradeoff there between the cost of computing which branch to take vs. how much that improves locality. 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)
  - martincmartin 3y ago
    Yes, these are the same issues faced by databases on spinning rust disks. The solution was to figure out how many keys fit in a disk block / cache line, let's call it k, then have a k-ary tree instead of a binary tree. This is called a B-tree. https://en.wikipedia.org/wiki/B-tree 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.

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.

srcreigh 3y ago
That’s what I meant re keys, but ya nice point about pointers. Forgetting details of my data structures classes. updated my post (used to count 1 bit per node for pointers)
WithinReason 3y ago
So binary search should actually not be binary but... octary?
- vidarh 3y ago
  I wondered about this too, there's an ongoing tradeoff there between the cost of computing which branch to take vs. how much that improves locality. 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)
- martincmartin 3y ago
  Yes, these are the same issues faced by databases on spinning rust disks. The solution was to figure out how many keys fit in a disk block / cache line, let's call it k, then have a k-ary tree instead of a binary tree. This is called a B-tree. https://en.wikipedia.org/wiki/B-tree 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.