3 ms·
See also "Optimal Hierarchical Layouts for Cache-Oblivious Search Trees", by Peter Lindstrom and Deepak Rajan: http://arxiv.org/abs/1307.5899 http://arxiv.org/a
by jbapple 11y ago
See also "Optimal Hierarchical Layouts for Cache-Oblivious Search Trees", by Peter Lindstrom and Deepak Rajan: http://arxiv.org/abs/1307.5899 http://arxiv.org/abs/1307.5899.
- pkhuong 11y agoThe layout is definitely interesting, but the experiments in that paper are of questionable usefulness. The numbers are for simulated caches (cachegrind), and don't take TLBs into account. They also only consider complete binary trees, and that is a worst case for binary search. I pointed out that issue to the authors and using ternary search cuts L1 and L2 misses by about 40-60% (VS binary search), without any change in layout. If I want to evaluate the Min-WEP layout for a real application, I have to run my own experiment to weigh the impact of reducing cache misses versus constant factors knowing that even the cache miss numbers are way off for the simplest layout (sorted array). The performance information in the paper can't help me make even an educated guess. That's why I really liked Pat Morin's approach of going for real time on a variety of microarchitectures… which helped us realise that cache misses aren't that good of a metric these days.