Re:Static search trees: 40x faster than binary search (2024)
by jackhalford on Saturday July 18, 2026 @02:13AM
(#48955665)
Is « cacheability » a property of the data structure or of the lookup algorithm?
Re:Static search trees: 40x faster than binary search (2024)
by noctune on Saturday July 18, 2026 @03:29AM
(#48955969)
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)
by Tostino on Saturday July 18, 2026 @08:22AM
(#48957484)
It's a combination of both. Your data layout could be very cachable for one algorithm, but very much not so for another algorithm.
Re:Static search trees: 40x faster than binary search (2024)
by inigyou on Saturday July 18, 2026 @09:10AM
(#48957846)
Data arrangement and data structure are the same word...
Re:Static search trees: 40x faster than binary search (2024)
by kazinator on Saturday July 18, 2026 @04:28PM
(#48962019)
Kind of. Many dynamic set data structures do not require the set elements to be in some layout inside an array; the storage is abstracted.
When we put the binary tree nodes into an array and move from the parent to children using indexing calculations, rather following pointers that could go anywhere, then it's an explicit part of the data structure.
Re:Static search trees: 40x faster than binary search (2024)
by IceDane on Saturday July 18, 2026 @09:54AM
(#48958160)
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.
Re:Static search trees: 40x faster than binary search (2024)
by hansvm on Saturday July 18, 2026 @10:04AM
(#48958271)
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.
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?