Document all the performance

[Gankro]

This is, I guess, a metabug.

As I discuss in #16267, I believe that libcollections should provide both high-level asymptotic performance as well as practical performance guidelines (e.g. Vec.push is faster than RingBuf.push and DList.push for most workloads) for all relevant functions and methods.

The biggest open question in my mind is whether performance should be indistinguishable from regular documentation, or take on a special form that Rustdoc can manipulate. For instance, perf docs could be prefixed by //? or placed in an annotation like [#perf-time(O(1) amor.)]. The former would need further special syntax to differentiate time/space information, the latter would need some augmentation to permit extended discussion.

Regardless of the form it takes, making this available to Rustdoc would allow some cool stuff like Traits including a performance table for their implementers. See Qt's Algorithmic Complexity section for an example of what these tables might look like.

I would also suggest we adopt the following notation conventions, or something similar:

• O(n): Worst-case bound
• *O(n): Amortized bound
• ~O(n): Expected bound

[killercup]

Well, while we are dreaming big… It would be amazing to automatically validate performance properties (to some extend) using #[bench]. E.g.

#[bench(time O(log n), space O(1))]
fn bench_something(b: &mut Bencher) {
    b.iter_with_size(|n| {
        perform_magic!(n)
    });
}

This would of course require (a) a structure where one can easily generate large examples and (b) benching various sized ns up to ones large enough to get a significant assumption for asymptotic properties.

(Combine this with a code generator, quickcheck and a small datacenter and you might never need computer science again!)

[Gankro]

@killercup I don't think the relation between asymptotic and real performance is well-defined enough to permit such functionality. Especially in the face of expected and amortized behaviors. Even O(1) can be unstable because e.g. performance is bounded above by some constant, but still scales with input.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#636