8 ms·
How We Beat C++ STL Binary Search
- blt 11y agoLoosely related: STL binary search suffers from the same weakness as several other comparator-based STL algorithms for certain classes of expensive comparators: https://www.reddit.com/r/cpp/comments/36sqtq/more_efficient_interface_for_algorithms_taking_a/ https://www.reddit.com/r/cpp/comments/36sqtq/more_efficient_...
- elitheeli 11y agoIf you take version 4, stop the first while loop once the size is at most 32, and then do linear search from there, it's faster (on my machine). For example, version 4 is 102ms and this tweak puts it at 83ms. (On clang x64.)
- CJefferson 11y agoOne 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).
- nanofortnight 11y agoI think the fact this violates the standard would be the greatest difficulty.
- twoodfin 11y agoGreat 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 craftsmanship in the most critical of paths. Structuring loops for autovectorization is another useful habit to get into.
- cautious_int 11y agoWouldn'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.
- twoodfin 11y agoIf 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?
- cautious_int 11y agoWell a branch will fetch the incorrect cache line if it mispredicts, but a conditional move will fetch both cache lines every time.
- rrrlasse 11y agoThe 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.
- cautious_int 11y agoThe conditional move still depends on both values taken from the array, via other variables.
- Noughmad 11y agoThere is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator< on the value. 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 -1 to an unsigned integer (size_t). So this is something you can use in your project if you need the performance, but can't put it into GCC.
- lhecker 11y agoJust 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.
- Joky 11y agoI believe there is a standard cross-platform maximum value, and you mention it in your last sentence: std::numeric_limits!
- lhecker 11y agoUhm... Using "-1" to assign the maximum value is in fact as standard and cross-platform as using std::numeric_limits, which was basically my entire point. The difference between those is only "textual solution" VS "mathematical solution" and thus a matter of personal preference.
- arbre 11y ago~0u ?
- oleks 11y agoGenericity 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".
- myle 11y agoIsn't version 2 wrong, because size_t probe = (low + high) / 2; may overflow?
- eloff 11y agoNot 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-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
- cautious_int 11y agoThat blog is wrong. The program won't be undefined( unsigned wrap is defined ), but the offset will not be correct.
- eloff 11y agoThey 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 11y ago[deleted]
- banachtarski 11y agoThat's not true. Unsigned wrap is well-defined and wraps around to 0. Signed wrap is undefined.
- cautious_int 11y agoIt is not true that unsigned wrap is defined? Did you even read my comment, here is the relevant part: unsigned wrap is defined
- 11y ago
- mmozeiko 11y agoFor 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 5.2.0 on Linux x86_64 (i7-4770S) stl : 629.231 miliseconds version 1: 629.436 miliseconds version 2: 897.143 miliseconds version 3: 862.827 miliseconds version 4: 863.22 miliseconds clang 3.6.2 on Linux armv7h (CuBox-i, Cortex-A9) stl : 3380.29 miliseconds version 1: 3428.9 miliseconds version 2: 3433.65 miliseconds version 3: 3391.86 miliseconds version 4: 3376.91 miliseconds Oh, and Visual Studio doesn't have "/O3" argument they say they are using for cl.exe.
- nhaehnle 11y agoThis 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.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- detrino 11y agoIt should be noted that their version gives different results to std::upper_bound if your range contains duplicates.
- avdicius 11y agoMy version: template <class T> INLINE size_t fast_upper_bound5(const vector<T>& 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] <= value) index = probe + 1; } return index; } 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
- sbahra 11y agoPaul has been doing great work here: http://repnop.org/pd/slides/bsearch.pdf http://repnop.org/pd/slides/bsearch.pdf
- xjia 11y ago(76% + 81% + 80% + 75% + 70%) / 5 = 76% http://www.cse.unsw.edu.au/~gernot/benchmarking-crimes.html http://www.cse.unsw.edu.au/~gernot/benchmarking-crimes.html
- arbre 11y agoThis is nice but what are the use cases for such an optimization ? My understanding is that such an optimization will not matter anyway compared to all the I/O and other expensive operations. And if a program is really too slow then the true optimization is to scale with threads or distributed computing.
- zubairsaif007 11y agohttp://googler700.blogspot.com/ http://googler700.blogspot.com/
- zubairsaif007 11y agohttp://googler700.blogspot.com/ http://googler700.blogspot.com/
- chardan 11y agoI think it's at the very least been hinted at below (and there are other good points), but note that their implementation makes copies. If the copy ctor of type T is the least bit expensive, the STL (implementation in glibc) for this same benchmark is far faster than theirs. Try it. :)