Hacker News Reader

Comment by Noughmad | Hacker News Reader

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.

View on HN

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.

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

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

~0u ?

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.

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

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

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

Reply on news.ycombinator.com