Re:Binary search is a pathological case for caches
by steerb on Monday July 30, 2012 @05:48AM
(#4311587)
Using the heap layout, you can sometimes even eliminate branch misspredictions and subsequent (expensive) pipeline flushes.
The basic idea is to allow your compiler to use predicated instructions. Do do this, you have to transform control dependencies (e.g., `if (a > b)`) to data dependencies on index computations (e.g., `j = 2*j + (a > b)`).
The basic idea is to allow your compiler to use predicated instructions. Do do this, you have to transform control dependencies (e.g., `if (a > b)`) to data dependencies on index computations (e.g., `j = 2*j + (a > b)`).
For a complete explanation, see http://algo2.iti.kit.edu/sanders/papers/ssss.ps.gz