Array Layouts for Comparison-Based Searching

Just came across a good paper that discusses these issues: http://arxiv.org/pdf/1509.05053v1 The approach it from a different angle, but come to similar conclusions: Our conclusion is contrary to our expectations and to previous findings and goes against conventional wisdom, which states that accesses to RAM are slow, and should be minimized. A more accurate statement, that accounts for our findings, is that accesses to RAM have high latency and this latency needs to be mitigated. ... Our results show that, in a processor that has speculative execution, one can obtain many of the benefits of runahead even on processors that do not specifically implement it. While this may not be news to hardware experts, to the best of our knowledge, we are unaware of any algorithms (or even implementations) that deliberately make use of it. I would suggest this is a very fruitful direction to pursue.

That one’s cache-oblivious so nominally the right answer if you don’t know how your cache works or have to deal with several of them at once, but the constants are bad enough to make it impractical[1,2]. Personally I’ve been on the lookout for a good vEB implementation for a while: there’s like one of them on the whole Internet, and it does things like recurse while figuring out where the next node down is, so no wonder it’s slow; and when I look at the definitions myself I can’t really figure out a faster way of doing it either. [1] http://arxiv.org/abs/1509.05053 [2] https://espindo.la/posts/array-layouts.html

auto length = last - first; while (length > 0) { auto half = length / 2; if (comp(first[half], value)) { // length - half equals half + length % 2 first += length - half; } length = half; } return first; can be restructured with a conditional `first += half` and instead `length -= half` (see, e.g., Listing 2 in https://arxiv.org/abs/1509.05053). Doing it this way requires one final comparison when `length > 0` on entry, because the while condition is `length > 1`, but moves the subtraction off the critical path.

> That is because you no longer need to compute a mid-point at every iteration, those are now pre-computed in the ordered array. This is called the Eytzinger layout [1]. [1] https://arxiv.org/abs/1509.05053

The more recent results (by the same author) is this paper: https://arxiv.org/pdf/1509.05053.pdf The conclusion is still that CMOV is best, but once the data stops fitting in the cache there's alternatives worth considering.

Reminds me of this paper on binary search, which also shows a speed up using branch-free comparisons. "Array Layouts for Comparison-Based Searching" https://arxiv.org/pdf/1509.05053.pdf

Have a look at https://arxiv.org/abs/1509.05053 from pkhuong. They discuss this issue and other variants that paper. So e.g. branchless binary search, the branchy binary search + speculative execution as a form of prefetching, branchless binary search with explicit prefetching.