4 ms·
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< on the val
by Noughmad 11y ago
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< 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".
- CJefferson 11y agooperator+(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.
- rawnlq 11y agoIs there any technical reason why the STL implementation can't include optimized specializations when there are less generic operators it can use?
- twoodfin 11y agoIt does. That's what std::advance is. For a random access iterator it will use operator+.
- thechao 11y agoNo 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<bool>). 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.