News for hackers. Stuff that matters.
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)`).

For a complete explanation, see http://algo2.iti.kit.edu/sanders/papers/ssss.ps.gz

There are no comments on this comment yet.