News for hackers. Stuff that matters.

rrrlasse

Re:How We Beat C++ STL Binary Search on Tuesday August 11, 2015 @07:06PM (#10045000)
The conditional move is the statement `low = v >= value ? low : other_low;` which either assigns `other_low` to `low` or does nothing.

And other_low is a variable, and not an arbitrary element of the list (which is a big difference with respect to cache), and it can also be seen from the assembly that it's stored in register. So there there is no "both cache lines" to fetch anything from.

Re:How We Beat C++ STL Binary Search on Tuesday August 11, 2015 @06:50PM (#10044939)
True, but only if the list has more than 2^31 entries on a 32-bit machine.

In practise that's not possible if it contains 32-bit integers because that would take up a 16 GB linear address space which doesn't exist on a 32-bit machine.

An academically correct version would be `size_t probe = low + ((high - low) / 2);` but that would be much slower.

You could instead just add an initial debug-mode-only assert on the list length, for correctness.