Compiler hints, inlining and syntax consistency

[Jakob Ovrum]

On Saturday, 28 December 2013 at 17:23:38 UTC, Ola Fosheim 
Grøstad wrote:
> STL is not great, has never been great, and probably will never 
> be great. Cool idea, bad execution for the language it was 
> implemented in. So they had to change C++ to support i better! 
> :-P
>
> How much time does a committee need to agree on a hash-table 
> implementation? Or should I say decades? STL is so 
> designed-by-a-committee that it hurts. It is not a shining 
> star! Not at all.
>
> STL is ok for early prototyping with C++11, but if you care 
> about performance you roll your own.

Nice tirade, but I only referenced STL for its take on 
algorithmic complexity requirements. If it makes the concept more 
palatable, you could instead imagine it as the anti-thesis of 
Java's collection interfaces.

> Single linked lists is very useful for situations where you 
> want lists that are mostly empty or short, but where you do not 
> want to impose an upperbound. O(N) on length() does not matter 
> much in many real-world scenarios.

In these cases you can use `walkLength` which is in itself the 
very warning you want.

> What you want is a (mild) warning if you use a templated 
> algorithm and that algorithm use a O(N) primitive where it is 
> invisible to the library user. A warning you should be able to 
> suppress (basically telling the compiler "trust me, this is 
> deliberate").

You could define a wrapper type to explicitly attach O(n) 
primitives onto ranges and/or containers, but generally the 
response is that you're using the wrong container, so this 
probably won't find its way to Phobos.

However, it should be noted that D supports flexible 
metaprogramming which has resulted in algorithms with looser 
requirements, such as Andrei's 
`std.algorithm.levenshteinDistance` which doesn't require random 
access, circumventing the problem entirely.

> Why is that?  If your non-associative array on average is of 
> length 3-4 then it might outperform an associative array.

In terms of advantages, it is only a minor syntactical benefit 
over using std.algorithm.among/canFind/find.

But the disadvantages are serious, most notably generic code that 
uses `in` and assumes it has some complexity guarantee would 
experience a blow-up in complexity when an array is passed.

Further, adding syntax sugar to such an operation sends the wrong 
signal and is thus asking for trouble during code maintenance - 
initially the array might have been small and use of `in` 
judicious, but later down the line the array grows while the use 
of `in` is preserved because it *looks* low-cost (after all, it 
looks identical to AA lookup). Alternatively, it can be a 
teaching problem; by having the scalable AA lookup and the 
non-scalable array lookup use the same syntax, a beginner could 
produce really bad code as a result of the hidden but vital 
difference.

(Also, for many typical element types, a length of 3-4 is an 
extremely conservative measure. The number where an array starts 
to be slower can be much, much higher than that, but the idea is 
that scalability is initially more important than 
micro-optimization [unless it's a C program, in which case using 
anything but an array is often not even worth the effort])