Compiler hints, inlining and syntax consistency

[Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang at gmail.com>]

On Saturday, 28 December 2013 at 16:35:41 UTC, Jakob Ovrum wrote:
> I have *no* idea where you got this idea from. D and its 
> standard library follows in the footsteps of STL when it comes 
> to the algorithmic complexity of primitives

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.

> an important tenet from *at least* the early days of D2. A few 
> examples include std.container's maximum complexity requirement 
> for primitives (including `length`) and the existence of

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.

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

> std.range.walkLength. A recent example of enforcement includes 
> the rejection of adding binary `in` functionality for 
> non-associative arrays.

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

Just like insertion sort will outperform other sorts for 
mostly-sorted arrays where the elements are offset by jitter (so 
they are 3-4 elements out-of-place). O(N*N) can easily beat O(N) 
if the dataset is a good fit. If not, everybody would use 
radix-sort and nobody would even consider quicksort.

Worst case analysis assuming unbounded arbitrary input is only of 
theoretical interest, in the real world you care about the 
average cost over the dataset you actually run the algorithm on. 
Unless you write hard realtime systems (life-support, weapon 
systems, etc).

> You could say this about any restriction in the type system.
>
> (`@obsolete`? Did you mean `deprecated`?)

(sure, or "@forbid" or "@notimplemented" etc)