Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How We Beat C++ STL Binary Search

realm.io

Post reply on HN
Print view View original

11–20 of 52 posts

Re: How We Beat C++ STL Binary Search

#11

Post by twoodfin »

cautious_int wrote: post #6
twoodfin wrote: post #5

Great link. The most educational bit for me was the careful structuring and eventual elimination of the if/else to shake out a conditional move rather than an unpredictable branch. Modern optimizers and CPU scheduling engines are so powerful, a lot of received wisdom on how to code for speed is outdated; manual loop unrolling, for example, is rarely very beneficial. It's nice to see that there's still some room for c…

Wouldn't a conditional move transfer the cost from branch mispredict to the cache miss. I wonder how realistic their test were, and if the same results would be achieved with some cache trashing.

If you're going to miss when you go back to the array, you're going to pay that cost regardless. But without the mispredict, you'll be able to issue the load that much sooner.

I'm not familiar enough with Intel's architecture to know one way or the other, but it wouldn't surprise me if not mispredicting the next memory access saves you more than just some pipeline flushing: The CPU could speculatively issue the load you don't actually need, wasting resources that could be used to service the correct addresses.

Or did you mean something else?

Re: How We Beat C++ STL Binary Search

#12

Post by nanofortnight »

CJefferson wrote: post #4

One of the problems with the extreme complexity of submitting code to GCC, and FSF projects in general, (having to complete copyright assignments, which are very slowly handled) is that this is unfortunately unlikely to end up in libstdc++ (although I would be happy to see it there).

I think the fact this violates the standard would be the greatest difficulty.

Re: How We Beat C++ STL Binary Search

#13

Post by cautious_int »

eloff wrote: post #10
myle wrote: post #8

Isn't version 2 wrong, because size_t probe = (low + high) / 2; may overflow?

Not if low and high are both unsigned (size_t is unsigned.) Even if it overflows, the result will be correct. See: http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

That blog is wrong. The program won't be undefined( unsigned wrap is defined ), but the offset will not be correct.

Re: How We Beat C++ STL Binary Search

#15

Post by cautious_int »

twoodfin wrote: post #11
cautious_int wrote: post #6

Earlier quoted context omitted.

Wouldn't a conditional move transfer the cost from branch mispredict to the cache miss. I wonder how realistic their test were, and if the same results would be achieved with some cache trashing.

If you're going to miss when you go back to the array, you're going to pay that cost regardless. But without the mispredict, you'll be able to issue the load that much sooner. I'm not familiar enough with Intel's architecture to know one way or the other, but it wouldn't surprise me if not mispredicting the next memory access saves you more than just some pipeline flushing: The CPU could speculatively issue the load…

Well a branch will fetch the incorrect cache line if it mispredicts, but a conditional move will fetch both cache lines every time.
Post reply on HN