How We Beat C++ STL Binary Search
1–10 of 52 posts
Re: How We Beat C++ STL Binary Search
#2Loosely 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_...
Re: How We Beat C++ STL Binary Search
#3If 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.)
Re: How We Beat C++ STL Binary Search
#4One 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).
Re: How We Beat C++ STL Binary Search
#5Great 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.
Re: How We Beat C++ STL Binary Search
#6Great 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.
Re: How We Beat C++ STL Binary Search
#7There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operatorThe "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.
Re: How We Beat C++ STL Binary Search
#8Isn't version 2 wrong, because
size_t probe = (low + high) / 2;
Re: How We Beat C++ STL Binary Search
#9For 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
stl : 629.231 miliseconds
version 1: 629.436 miliseconds
version 2: 897.143 miliseconds
version 3: 862.827 miliseconds
version 4: 863.22 miliseconds
stl : 3380.29 miliseconds
version 1: 3428.9 miliseconds
version 2: 3433.65 miliseconds
version 3: 3391.86 miliseconds
version 4: 3376.91 miliseconds
Re: How We Beat C++ STL Binary Search
#10Isn'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-...