Re:Binary search is a pathological case for caches
by saurik on Tuesday July 31, 2012 @02:10AM
(#4315959)
So, a "binary search tree in an array, like the way heaps are implemented" actually would not experience the problem described in this article. The typical layout of the tree for a heap is "breadth-first, level-order" as opposed to the "depth-first, in-order" tree that is implicit to a sorted array. This means that your accesses to the first couple levels are in the same cache line, and your subsequence accesses as you move down the tree are less likely to line up. This is definitely not to say this is "optimal", however.
[ Parent
| on HN ]
There are no comments on this comment yet.