Static search trees: 40x faster than binary search (2024)
curiouscoding.nl
Static search trees: 40x faster than binary search (2024)
1–10 of 22 posts
Re: Static search trees: 40x faster than binary search (2024)
#2Thanks for sharing this
Re: Static search trees: 40x faster than binary search (2024)
#3My first instinct is https://en.wikipedia.org/wiki/Van_Emde_Boas_tree
Not sure why
Re: Static search trees: 40x faster than binary search (2024)
#4> 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) . 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?
Re: Static search trees: 40x faster than binary search (2024)
#5> 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) . Binary hea…
Is « cacheability » a property of the data structure or of the lookup algorithm?
Re: Static search trees: 40x faster than binary search (2024)
#6Those yes, Eytzinger not. On normal sized data Eytzinger is worse than sorted.
Re: Static search trees: 40x faster than binary search (2024)
#7> 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) . Binary hea…
Is « cacheability » a property of the data structure or of the lookup algorithm?
Locality is a property of how data is arranged, so it's a property of the data structure, no?
Re: Static search trees: 40x faster than binary search (2024)
#8[flagged]
Re: Static search trees: 40x faster than binary search (2024)
#9Why does figure 1 use the same color and style for two different graphs?
Re: Static search trees: 40x faster than binary search (2024)
#10My first instinct is https://en.wikipedia.org/wiki/Van_Emde_Boas_tree Not sure why
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.