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