"in" everywhere

[Stanislav Blinov]

Andrei Alexandrescu wrote:

> 
> Complexity composes very badly. Issues tend to manifest at moderate 
> sizes and may make things unbearable at large sizes. I'm really grateful 
> I'm at a workplace where the exclamation "Damn! I was waiting like an 
> idiot for this quadratic append!" is met with understanding nods from 
> workmates who've made the same mistake before.
> 
> As an example, only last week I was working on cramming a sort of an 
> index of the entire Wikipedia on one machine. I was waiting for the 
> indexer which ran slower and slower and slower. In the end I figured 
> there was only _one_ quadratic operation - appending to a vector<size_t> 
> that held document lengths. That wasn't even the bulk of the data and it 
> was the last thing I looked at! Yet it made the run time impossible to 
> endure.
> 

But that is not a matter of library interface isn't it? It's a matter of 
algorithm/container choice. It's not the push_back that was slow in the 
end, it was std::vector (yes, that's arguable, but the point is that 
container defines rules for its methods, not vice-versa).

>>
>> I think it's an abuse of the type system to use it to guarantee
>> performance.  However, if I wanted the type system to provide
>> performance guarantees, I would need a lot more language support than a
>> convention that certain operations are supposed to be O(n).  I'm talking
>> performance specification on *all* functions, with a compile-time error
>> if the compiler can't prove that the compiled function meets those
>> guarantees.  And *even then*, I would like to be able to use an O(n)
>> implementation of 'in' where I know that O(n) performance is acceptable.
> 
> std.container introduces the convention that O(n) methods start with 
> "linear".

I find such convention useful indeed, though it brings a fact to 
surface: if we need to emphasize method that make strong promises about 
complexity with prefixes/suffixes, or say by putting them into separate 
module, then why don't we have an non-emphasized counterpart that won't 
make strong promises but would fit wider range of containers? After all, 
std.algorithm offers different search mechanisms with varying complexity 
(e.g. find() vs boyerMooreFinder()).