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

21–30 of 52 posts

Re: How We Beat C++ STL Binary Search

#21

Post by oleks »

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…

Genericity usually comes at the cost of performance. But it seems that we've come to terms with a handful of basic datatypes in our databases, and so I think it makes a great deal of sense to specialize our fancy, theoretically fast, generic algorithms for this handful of datatypes. Also, I don't see how you can "beat" someone in terms of genericity? But I agree, the title could be a bit less abusive of the STL "brand": it could've used the word "performance" and downplayed generics.

Funnily enough, the HTML title behind the link is indeed "Performance Engineering at Realm: How we optimized binary search".

Re: How We Beat C++ STL Binary Search

#22

Post by jongraehl »

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-...

for 64 bit size_t it's pretty academic, but no, not correct.

suppose low is M-3 and high is M-1 (where M is 2^[#bits]) then mid should be M-2. but (M-3 + M-1) is (modulo M) equal to M-4. and half that is M/2 - 2, which is a lot less than the correct M-2. (pretend it's 2 bit unsigned ints so M is 4)

the correct 'mid' computation is low + (high - low)/2.

Re: How We Beat C++ STL Binary Search

#23

Post by lhecker »

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 and for std::string's npos.

Re: How We Beat C++ STL Binary Search

#24

Post by CJefferson »

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…

operator+(int) is fine. The libstdc++ code is using std::advance, which will compile down to operator+ for random access iterators (and will be O(n) for forward iterators, but performance is already going to be awful). The vector issue requires care but is fixable (I'd probably test the total length, and branch to a more basic implementation for big ranges). The assigning -1 really is just unfixable.

Re: How We Beat C++ STL Binary Search

#26

Post by avdicius »

My version:

  template  INLINE size_t fast_upper_bound5(const vector& vec, T value)
  {
      size_t index = 0;
      size_t size = vec.size();
      while (size > 0) {
          size /= 2;
          size_t probe = index + size;
          if (vec[probe]
Slightly faster with gcc:

  $ g++-mp-4.9 -std=c++11 -O3 -DNDEBUG -o blog blog.cpp 
  $ ./blog 
  size = 8192:
      stl      : 144.883 miliseconds
      version 1: 145.406 miliseconds
      version 2: 129.713 miliseconds
      version 3: 109.231 miliseconds
      version 4: 103.578 miliseconds
      version 5: 102.282 miliseconds
But sucks with clang, apparently because of the described problem with non-using cmov instruction.

  $ clang++-mp-3.6 -std=c++11 -O3 -DNDEBUG -o blog blog.cpp
  $ ./blog 
  size = 8192:
      stl      : 147.466 miliseconds
      version 1: 145.978 miliseconds
      version 2: 145.547 miliseconds
      version 3: 113.546 miliseconds
      version 4: 106.968 miliseconds
      version 5: 144.231 miliseconds

Re: How We Beat C++ STL Binary Search

#27

Post by rrrlasse »

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 list length, for correctness.

Re: How We Beat C++ STL Binary Search

#28

Post by nhaehnle »

mmozeiko wrote: post #9

For 8192 elements I also get result that their search function is faster than STL. But 8192 elements is tiny size of array where to search, for larger array I get opposite - STL is faster. Here is output for 8 * 1024 * 1024 elements (~8.4million). gcc 5.2.0 on Windows x64 (i5-3210M) stl : 881 miliseconds version 1: 880 miliseconds version 2: 1607 miliseconds version 3: 1260 miliseconds version 4: 1271 miliseconds gcc…

This is fascinating. Do you have any idea what might cause this?

A shot in the dark: Their benchmarking uses a very simple "random" generation to choose the index to search for, which is actually just a linear scan (modulo the size of the array). Could it be that with the larger array, the generated sequence of test indices happens to work nicely with the CPU's branch prediction - after all, your results show a performance drop-off for the versions that use conditional moves, and the behavior depends suspiciously on the CPU microarchitecture.

Re: How We Beat C++ STL Binary Search

#29

Post by eloff »

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.

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!

Re: How We Beat C++ STL Binary Search

#30

Post by rrrlasse »

cautious_int wrote: post #15
twoodfin wrote: post #11

Earlier quoted context omitted.

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.

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.

Post reply on HN