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

31–40 of 52 posts

Re: How We Beat C++ STL Binary Search

#31

Post by rawnlq »

Noughmad wrote: post #7

There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator The "optimized" versions here all make more assumptions on the iterator, starting from operator+(int) in Version 1, so it no longer works on iterators with just "forward_iterator_tag". Further versions even restrict vector sizes (albeit to a very high number) and assign…

Is there any technical reason why the STL implementation can't include optimized specializations when there are less generic operators it can use?

Re: How We Beat C++ STL Binary Search

#32

Post by Joky »

lhecker wrote: post #23
Noughmad wrote: post #7

There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator The "optimized" versions here all make more assumptions on the iterator, starting from operator+(int) in Version 1, so it no longer works on iterators with just "forward_iterator_tag". Further versions even restrict vector sizes (albeit to a very high number) and assign…

Just a nitpick: Assigning a negative value to an unsigned integer is perfectly safe and well defined (i.e. integer overflow for unsigned integers is well defined in the C++ spec). Using -1 for size_t is sometimes even prefered to assign it's maximum value, since there is no cross-platform #define for it (most use either SIZE_T_MAX or SIZE_MAX). In fact llvm's libc++ uses it for it's std::numeric_limits implementation…

I believe there is a standard cross-platform maximum value, and you mention it in your last sentence: std::numeric_limits!

Re: How We Beat C++ STL Binary Search

#33

Post by [deleted] »

eloff wrote: post #29
cautious_int wrote: post #13

Earlier quoted context omitted.

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

They didn't say unsigned overflow was undefined, but you're right that the offset won't be correct. I thought it seemed intuitively wrong to me, but I figured google research is probably a reliable source!

[deleted]

Re: How We Beat C++ STL Binary Search

#34

Post by cautious_int »

rrrlasse wrote: post #30
cautious_int wrote: post #15

Earlier quoted context omitted.

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

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.

The conditional move still depends on both values taken from the array, via other variables.

Re: How We Beat C++ STL Binary Search

#36

Post by banachtarski »

cautious_int wrote: post #13
eloff wrote: post #10

Earlier quoted context omitted.

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.

That's not true. Unsigned wrap is well-defined and wraps around to 0. Signed wrap is undefined.

Re: How We Beat C++ STL Binary Search

#37

Post by twoodfin »

rawnlq wrote: post #31
Noughmad wrote: post #7

There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator The "optimized" versions here all make more assumptions on the iterator, starting from operator+(int) in Version 1, so it no longer works on iterators with just "forward_iterator_tag". Further versions even restrict vector sizes (albeit to a very high number) and assign…

Is there any technical reason why the STL implementation can't include optimized specializations when there are less generic operators it can use?

It does. That's what std::advance is. For a random access iterator it will use operator+.

Re: How We Beat C++ STL Binary Search

#38

Post by thechao »

rawnlq wrote: post #31
Noughmad wrote: post #7

There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator The "optimized" versions here all make more assumptions on the iterator, starting from operator+(int) in Version 1, so it no longer works on iterators with just "forward_iterator_tag". Further versions even restrict vector sizes (albeit to a very high number) and assign…

Is there any technical reason why the STL implementation can't include optimized specializations when there are less generic operators it can use?

No technical reason; just lack of effort! In fact, a well-optimized implementation of the STL should have a large number of machine-word specific optimizations (a la std::vector). However, none that I know of, do, other than light unrolling to promote vectorization. About the closest you can find is well-optimized versions of valarray.

Re: How We Beat C++ STL Binary Search

#39

Post by maxlybbert »

rrrlasse wrote: post #27
myle wrote: post #8

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

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 li…

Sun had to put out a JDK bug fix for this nine years ago ( http://googleresearch.blogspot.com/2006/06/extra-extra-read-... ).
Post reply on HN