Rendered at 16:02:00 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
kazinator 15 hours ago [-]
> The main benefit of the Eytzinger layout is that all values needed for the first steps of the binary search are close together, so they can be cached efficiently: we put the root at index 1 and the two children of the node at index i are at 2i and 2i + 1.
This is exactly what is done in good old binary heaps; though binary heaps do not maintain a balanced binary tree, only the property that key(parent) < key(left_child) and key(parent) < key(right_child). Binary heaps don't support efficient search for a particular key.
I don't remember ever reading a description of binary heaps which mentioned Eytzinger. This is because the layout for binary heaps was discovered without knowledge of Eytzinger. It may have been Knuth who discovered Eytzinger and made the connection?
It's quite obvious that this layout is good for caching. The first few layers of the tree will all fit into a single VM page, the nodes closest to the root into one cache line. Then the subsequent layers are similarly packed in order.
Let's say that k layers of the tree fit into page. If the search path from root to leaf is 3k, it should touch only three pages, right?
jackhalford 10 hours ago [-]
Is « cacheability » a property of the data structure or of the lookup algorithm?
hansvm 2 hours ago [-]
Both. The hypothesis with Eytzinger is that you're doing vanilla binary search on a data structure where each hop is one operation. It doesn't, by itself, do anything to optimize around particular hot leaves, so assuming you aren't doing a weighted rebalance operation before construction it additionally assumes access patterns are somewhat uniform. That's the algorithm and input pattern whose cachability we're trying to optimize.
Imagine, e.g., doing a b-tree lookup on a binary Eytzinger layout. You would always grab more cache lines than optimal. Even more obviously, consider an inorder traversal. The properties of an algorithm and data structure depend properly on both components.
noctune 9 hours ago [-]
Locality is a property of how data is arranged, so it's a property of the data structure, no?
inigyou 3 hours ago [-]
Data arrangement and data structure are the same word...
Tostino 4 hours ago [-]
It's a combination of both. Your data layout could be very cachable for one algorithm, but very much not so for another algorithm.
IceDane 2 hours ago [-]
It has to be both. You can lay things out in memory so they are tightly packed together and thus ostensibly cache efficient but that doesn't help you if you index into that data structure in such a way that every new index loads a new cache line.
That one’s cache-oblivious so nominally the right answer if you don’t know how your cache works or have to deal with several of them at once, but the constants are bad enough to make it impractical[1,2].
Personally I’ve been on the lookout for a good vEB implementation for a while: there’s like one of them on the whole Internet, and it does things like recurse while figuring out where the next node down is, so no wonder it’s slow; and when I look at the definitions myself I can’t really figure out a faster way of doing it either.
> Input. A sorted list of 32bit unsigned integers vals: Vec<u32>.
Okay, but that's not even remotely like the kind of input that this tree was created for. From the next paragraph, this work is in part
> [...] to make efficient datastructures to index DNA [...]. One such datastructure is the suffix array, that sorts the suffixes of the input string. Classically, one can then find the locations where a string occurs by binary searching the suffix array.
So where is the analysis of how it performs for that use-case? Searching through "already sorted 32 bit numbers" has nothing to do with searching a 3 billion character string (that by definition cannot be internally sorted) for substrings.
petters 5 hours ago [-]
Why does figure 1 use the same color and style for two different graphs?
rurban 9 hours ago [-]
Those yes, Eytzinger not. On normal sized data Eytzinger is worse than sorted.
This is exactly what is done in good old binary heaps; though binary heaps do not maintain a balanced binary tree, only the property that key(parent) < key(left_child) and key(parent) < key(right_child). Binary heaps don't support efficient search for a particular key.
I don't remember ever reading a description of binary heaps which mentioned Eytzinger. This is because the layout for binary heaps was discovered without knowledge of Eytzinger. It may have been Knuth who discovered Eytzinger and made the connection?
It's quite obvious that this layout is good for caching. The first few layers of the tree will all fit into a single VM page, the nodes closest to the root into one cache line. Then the subsequent layers are similarly packed in order.
Let's say that k layers of the tree fit into page. If the search path from root to leaf is 3k, it should touch only three pages, right?
Imagine, e.g., doing a b-tree lookup on a binary Eytzinger layout. You would always grab more cache lines than optimal. Even more obviously, consider an inorder traversal. The properties of an algorithm and data structure depend properly on both components.
Not sure why
Personally I’ve been on the lookout for a good vEB implementation for a while: there’s like one of them on the whole Internet, and it does things like recurse while figuring out where the next node down is, so no wonder it’s slow; and when I look at the definitions myself I can’t really figure out a faster way of doing it either.
[1] http://arxiv.org/abs/1509.05053
[2] https://espindo.la/posts/array-layouts.html
Okay, but that's not even remotely like the kind of input that this tree was created for. From the next paragraph, this work is in part
> [...] to make efficient datastructures to index DNA [...]. One such datastructure is the suffix array, that sorts the suffixes of the input string. Classically, one can then find the locations where a string occurs by binary searching the suffix array.
So where is the analysis of how it performs for that use-case? Searching through "already sorted 32 bit numbers" has nothing to do with searching a 3 billion character string (that by definition cannot be internally sorted) for substrings.