Overhaul std collections and algorithm documentation

[gnzlbg]

The documentation of the std::collections:

• lacks enough rigor to make good informed decisions about using the collections and their methods as well as most algorithms.
• some of the information is there, but it is not easy to get to it from a particular method (e.g. if I want to find the complexity of some container insert method googling for "Rust HashSet insert" would lead me to the documentation of the insert function, but this information is in a performance table in the main page of the collection API.
• the place for rigor is in the docs and not in the book. The docs are the reference.

I really think that being more thorough with the documentation will help both find and fix bugs in the documentation and make the std library way better.

The solution I propose is to make all the relevant information accessible from all the methods.

The first thing to do would be to achieve consensus on which information should be available for each method. Taking inspiration from the C++ standard, and to kickstart the discussion, I would propose that each method / algorithm / function documentation comment should contain the following "fields" below the short and long descriptions. If a field doesn't make sense for some particular method, I would propose to still have it there but explicitly leave it blank.

• Algorithmic complexity: with big O in terms of the relevant operations (which can be multiple: copies/moves in terms of the number of elements, number of swaps, number of comparisons, hashing...), with exact number of operations when guaranteed (performs exactly N moves, performs exactly M - N swaps, ...), and for those methods that have amortized/expected complexity it should contain both the complexity in the amortized case as well as the worst case (and maybe best case), and under which conditions they trigger.
  • Example: Vec::push(t): amortized O(1): exactly 1 move/copy of t if Vec::size() < Vec::capacity(), otherwise worst case O(N): exactly N + 1 moves/copies where N == Vec::size().
  • Example: Vec::reserve(M): O(1) time if M <= Vec::capacity(), O(N) otherwise: exactly N moves/copies where N == Vec::size().
• Memory complexity: does it use O(1) stack space? Is it recursive and it uses O(logN) stack space? Does it allocate memory using an allocator? If so how much?
  • Example: Vec::push(t): amortized O(1) stack space, otherwise worst case O(1) stack space and a single memory allocation of O(k*N) where k is an implementation-defined growth factor independent of N and where N == Vec::size().
  • Example: Vec::reserve(M): O(1) stack space if M <= Vec::capacity(), otherwise a single allocation of O(k*N) where k is an implementation-defined growth factor independent of N and N == Vec::size().
• Effects: What are the effects of the operation?
  • Example: Vec::push(t): Before: size() == N, capacity == M, After: size() == N + 1, capacity() == M (amortized case) or capacity() == k*M (worst case, where k is an implementation defined growth factor), pop() == Some(t).
  • Example: Vec::reserve(N): Before: capacity() == M, After: capacity() == max(N, M).
• Panics: When is an operation supposed to panic?
  • Example: Vec::push(t) panics if OOM or if a copy of t is performed and copying panics.
  • Example: Vec::size() never panics.

I consider this the bare minimum level of "formalization" that at least the basic collections and algorithms in the standard library should have, but as you can see things become extremely verbose so one might want to explore how to factor out some parts of the documentation (e.g. that for Vec the growth-factor is a constant independent of the number of elements or the capacity of the vector) that are to be repeated in a lot of comments.

So that's for my strawman proposal. I guess the steps to follow (please correct me if I'm wrong):

• Achieve consensus on how to document the methods of the std library algorithms and collections. Maybe through an RFC? Or isn't an RFC required here?
• Explore if there is an easy way to reuse some documentation bits (e.g. OOM panics, never panics, explanation for amortized / expected complexity).
• Go (again) through all methods and document them rigorously (i.e. actually implement this).
• Orthogonal to this, since not all collections are mentioned in the main collections page (e.g. HashSet), probably we want to go over the main collection page and overhaul it as well.

For a feeling of the current state of things:

• HashMap::insert doesn't mention that insertions are O(1) so if one lands there (e.g. via google) one is on its own. Relevant information should be visible right away.
• vec::insert: in the amortized case requires O(1) stack memory and will perform exactly O(end - pos) moves but in the worst case it requires O(kN) memory and O(N) moves. None of this is "obvious" from the docs. We should make it obvious.
• std::slice::sort complexity is O(NlogN) in the number of elements, but it mentions that it allocates approximately "2*n" elements. Does that mean at worst 2N? Can it be more? While this is better documented than other methods, it is still extremely vague. In particular, trivial stable sort implementations require 1/2N extra memory, a bad one at least N, and the good ones are in place (e.g. GrailSort requires O(1)). The rust standard library doesn't have an inplace unstable sorting algorithm (AFAIK), but the documentation of one implemented with something quicksort-based like intro-sort should say that it uses O(logN) stack space in some cases (I did not have any examples above with anything but O(1) stack space, but basically every recursive algorithm requires something different than O(1)).

cc @GuillaumeGomez

[hanna-kruppe]

I'm not against additional rigor, but I would rather have the API documentation err on the side of too little details than too many:

• API docs aren't ISO standards, they don't have to spell out every little detail, only those that actually aid programmers. In particular, some "obvious" things don't necessarily need to be spelled out (e.g., the effect of Vec::push on a subsequent Vec::pop call is fully clear from the current prose descriptions).
• Since the review process is presumably just one person with permissions giving an r+, there is a danger of sneaking in more guarantees than "the team" wants to give (this wouldn't be the end of the world as API docs aren't standards—see previous bullet point—but these non-guarantees can be broken accidentally, which defeats the point of documenting them). RFCs could alleviate this but are pretty heavy duty for something so relatively unimportant.

Also, spec'ing the number of moves/copies makes little sense (except as one of many factors influencing run time): C++ specifies it because moves and copies call constructors and are thus observable behavior, but in Rust they're plain memcpys (except Clone). I also have doubts about the usefulness and practicality of spec'ing asymptotic stack space requirements, where the usual objection of constant factors being incredibly important applies even more than everywhere else.

[gnzlbg]

I'm not against additional rigor, but I would rather have the API documentation err on the side of too little details than too many

I both agree and disagree here. I think it is worth it to document as much as it makes sense (that is "many details") but I think it makes sense to err in the "conservative" side, like for example specify conservative complexity guarantees (e.g. for stable sort "at most O(N) extra memory" doesn't prevent the implementation from switching to grail sort, which requires O(1) memory, for those cases in which it is faster).

API docs aren't ISO standards, they don't have to spell out every little detail, only those that actually aid programmers. In particular, some "obvious" things don't necessarily need to be spelled out (e.g., the effect of Vec::push on a subsequent Vec::pop call is fully clear from the current prose descriptions).

Yes I agree in that these things are obvious, and repetitive. The tricky part will be achieving consensus on what should be documented here and what should not be documented, particularly in the effect section. My strawman tries to mention everything since that is one of the extremes, but probably something in between will be better.

Having said this, I do think that having a terse bullet-point form of all the side-effects of an operation is useful even if they are already documented in the prose. For example for Vec::pop, spelling the side -effects out might help users avoiding the wrong assumption that thesize() afterwards is always the size before minus one. It's trivial, it's already said somewhere else, but IMO important things are said twice (in particular when "refreshing" an algorithm one might directly just go to the complexity/effects section and just read that).

Since the review process is presumably just one person with permissions giving an r+, there is a danger of sneaking in more guarantees than "the team" wants to give (this wouldn't be the end of the world as API docs aren't standards—see previous bullet point—but these non-guarantees can be broken accidentally, which defeats the point of documenting them).

Even though API docs aren't standards, guaranteeing O(N) complexity and changing that afterwards to O(N log N) is an API breaking change, so we want to be very conservative at first with what do we guarantee for each method. Tightening any of those guarantees can always be done later, but I think that should follow the RFC process, e.g., want to tighten the guarantee that stable sort requires O(1) extra memory instead of O(N)? Write a (small) RFC for it.

Also, spec'ing the number of moves/copies makes little sense (except as one of many factors influencing run time): C++ specifies it because moves and copies call constructors and are thus observable behavior, but in Rust they're plain memcpys (except Clone)

I should have said move/clone instead of move/copy but I still do think that it is worth it to guarantee or at least document this to allow users to reason about performance. Some algorithms are in place and do not require any memcpys, while others need to perform a memcpy of O(N). Again I am not suggesting to making these guarantees as tight as possible (or as tight as the current implementation), but guaranteeing that O(N) copies happen as opposed to O(N^2) copies tells users that:

• copies might be happening (which is something that they might not have thought about)
• the number of copies happening won't make the algorithm explode (and somebody has given thought to this).

I think a good example are the two kinds of sorting algorithms one generally encounters: unstable in-place, and stable with a buffer. The number of comparisons alone don't tell you the whole picture about both algorithms. For unstable in-place the number of swaps and the stack usage (O(1) vs O(logN)) tell you the larger story (*), while for stable sort you also need to know how much memory it allocates, how often is it going to copy elements into the buffer, whether it can survive OOM (in Rust obviously it cannot, but maybe in the future with Allocators it could be made to work without a buffer).

(*) I think that with respect to stack usage constant factors don't matter "that much", since for a O(1) algorithm you know that if it works for zero elements it won't overflow the stack for N elements, but the same cannot be said about an algorithm with O(logN) stack usage.

[hanna-kruppe]

Even though API docs aren't standards, guaranteeing O(N) complexity and changing that afterwards to O(N log N) is an API breaking change

That is precisely my worry. Giving any guarantee at all is a commitment that needs to be made carefully and consciously, unless the bounds given are incredibly loose. Such loose bounds, on the other hand, can be harmful by confusing people and giving a wrong impression.

move/clone

clone calls might be worth documenting (for the same reason as in C++), but I don't understand the focus on memcpys. The fact that something takes, say, O(n) time tips you off about the main implication of the copies. As far as constant factors go, a memcpy is often among the cheapest operations you can do, compared to many other things that nobody proposes to specifically call out in the documentation. So I do not see any reason to emphasize memcpy over a myriad other metrics (scratch allocations, multiple passes in an algorithm that one might expect to be single-pass, overflow checks, the number of system calls, etc.)

You are right that some of these metrics give a better idea of the algorithm used, but this requires giving bounds that aren't trivially true for any sensible implementation. Again, giving overly loose bounds (e.g., O(log N) stack space, O(N) scratch space, O(N²) comparisons and swaps worst case) would be misleading, and narrowing it down would be a large commitment that I do not believe people would be or should be willing to make. Guaranteeing details of the algorithm used (the raison d'être for these metrics) is precisely what we should be reluctant to do.

---

The more I think and write about this topic, the less happy I am about giving precise asymptotic complexity bounds. Don't get me wrong, knowing that a program takes somewhere between O(1) and O(N log N) time and space is a very valuable sanity check that it won't blow up on larger data sets. We should give this information. But more details are both hard to provide, and may not give all that much detail. For realistic performance estimates, one needs more information than a programming language should be willing to guarantee, including information that can't be captured in asymptotic complexity at all.

In short, it is information about the specific implementation your program is actually using, and that's the exact opposite of what API docs should do. I don't know if and how this information should be made available to those fine-tuning their code's performance, but I am increasingly convinced that API docs are the wrong place for these sorts of details.

[mark-i-m]

@rkruppe Perhaps it might be valuable to create another RFC to finalize asymptotic bounds for operations on standard library collections before putting them in the docs.

Also, I think it would be nice if docs could mention significant dropping and ownership behavior (e.g. Vec::pop gives ownership of the popped item) and events that could cause unwanted behavior (e.g. killing another thread while that thread is executing Vec::drain could result in memory leaks).

[mark-i-m]

I'm not against additional rigor, but I would rather have the API documentation err on the side of too little details than too many

Also, I would rather err on the side of too many details as long as they are well organized. People can skim through stuff they don't care about, but not getting the information you need is maddening...

[gnzlbg]

I think it is worth remembering that currently we are at the opposite end of the spectrum, in which "almost nothing" is documented (a lot is documented, but not really in a method per method basis with strict guarantees that users can rely on).

Maybe I started this discussion with the wrong foot by suggesting specific things to document. I guess it would be better to agree on general goals for the API documentation first (from the point-of-view of an user), and after we have consensus on that, try to formulate some more specific guidelines that achieve those goals (and then iterate).

In my opinion, for a user reading the API documentation of some collection method or algorithm, it should be clear whether the method:

1. "Can be called in a loop", and estimate the complexity of the loop in terms of the method input.
2. Can overflow their stack, and in that case, how does the stack grow (particularly important for embedded development),
3. Can panic at all and, when possible, under which circumstances (only due to OOM, stack overflow, etc.)
4. Has some observable side-effects like allocating memory (transferring ownership, spawning threads, performing a sys-call, etc...).
5. Changes the collection invariants and which ones (e.g. can leak memory under which situations).
6. Has some performance properties that depend on properties of the input or the collection invariants, or both.

So what do I mean by the "opposite end of the spectrum above"? Consider finding a key in a HashSet, using HashSet::contains, quoting from the docs:

fn contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Hash + Eq

Returns true if the set contains a value.

The value may be any borrowed form of the set's value type, but Hash and Eq on the borrowed form must match those for the value type.

So going through the goals stated above, the current documentation basically fails at all of them. The API docs don't specify the complexity (so I don't know if calling it inside a loop will blow up my program), whether it is implemented recursively or not (i.e. if the stack could overflow), whether this operation can panic, can leak or allocate memory, ...

Does this mean that contains is useless? Obviously no. But it kind of does mean that changing any of the above is not a breaking change, since the API doesn't promise anything. This is a serious stability issue, since the complexity of most operations could change tomorrow, and make my program blow up with the next rustc version.

Realistically though, I seriously doubt that anybody at this point would break any of the current guarantees that HashSet provides, and the same goes for the other collections. If anything, those guarantees might get better, but not worse. At least I would consider making e.g. the complexity worse a breaking change "even if the API doesn't promise anything". So IMO we might as well just go on and document this. This would not only serve as guidelines for users, but also as guidelines for those improving HashSet (what can/cannot be done without breakage).

I think that how to exactly document this should probably be handled in an RFC, but at least agreeing on a set of goals for the documentation first would make it much easier to start writing such an RFC.

---

@rkruppe

That is precisely my worry. Giving any guarantee at all is a commitment that needs to be made carefully and consciously, unless the bounds given are incredibly loose. Such loose bounds, on the other hand, can be harmful by confusing people and giving a wrong impression

For me changing the complexity (among other things mentioned above, like memory usage, stack usage, allocating memory, panics, ...) is a breaking change even if it is not documented. If the std collections do not guarantee any of these things, this means to me that:

• I cannot reason about my programs, and that even if I look at the implementation, my reasoning needs to be updated with every new rustc version
• I cannot use std collections if I need stable behavior, since currently most methods have no rigorous (as in properly specified, not as in tight) guarantees (so they can change anytime).

but I don't understand the focus on memcpys. The fact that something takes, say, O(n) time tips you off about the main implication of the copies. As far as constant factors go, a memcpy is often among the cheapest operations you can do

Cheapest compared to what? Comparisons while using stable sort? They are relatively cheap for types that are small and expensive to compare, and relatively expensive for types that are large and cheap to compare (like struct { buffer: [u8; 16384], unique_id_for_cmp: u8 }).

Again, giving overly loose bounds (e.g., O(log N) stack space, O(N) scratch space, O(N²) comparisons and swaps worst case) would be misleading,

Whether stack space used is O(1) or O(logN) is the difference between a stack overflow being possible or not (and thus the difference between a panic being possible or not, or at least that if the algorithm for N == 0 doesn't overflow the stack, it won't overflow the stack for any N). Maybe I am weird for caring about this, but I do like to know. And if I write some code that should never panic, and use some algorithm that uses O(1) stack space for this, I would not want this behavior to change in the next rustc upgrade under the covers.

I agree that this information does leak implementation details of the algorithm, and I agree the need to be conservative to give implementors enough leeway to perform optimizations, but one cannot have it both ways.

Guaranteeing details of the algorithm used (the raison d'être for these metrics) is precisely what we should be reluctant to do.

I think we should give enough guarantees to allow people to reason about how and when to use the methods and classes in std collections without severely constraining the implementation.

Documentation wise it is probably better to move some of the details to a "Non-binding implementation details" section in the API documentation comments that might add some extra information that might be relevant for those wanting to know exactly what is going on, but that is allowed to change between rustc versions.

The more I think and write about this topic, the less happy I am about giving precise asymptotic complexity bounds. Don't get me wrong, knowing that a program takes somewhere between O(1) and O(N log N) time and space is a very valuable sanity check that it won't blow up on larger data sets. We should give this information.

Deciding which information to give exactly and how is a hard. Sadly we only have the API docs for this, since that is the reference. As mentioned above I think it would be better to have a non-binding section in the API docs that tells users implementation details that "are good to know" but that are allowed to change (e.g. the value of Vec's growth factor is good to know and if you are benchmarking it might help you understand the result of your benchmarks, but you should not rely on it).

[mark-i-m]

@gnzlbg What you said makes a lot of sense :)

I have a question about your 5th point:

1. Changes the collection invariants and which ones

What do you mean by this?

Also, I would like to add to the list: "Has interesting static side effects, such as giving up ownership of some piece of data."

[Regarding space complexity] Maybe I am weird for caring about this, but I do like to know.

I think space complexity is important (especially for collection types), but I have not come across examples where stack space complexity has caused my program to overflow... In my limited experience, this tends to be more a function of time complexity... Do you have a specific example where you have had problems?

Documentation wise it is probably better to move some of the details to a "Non-binding implementation details" section in the API documentation comments that might add some extra information that might be relevant for those wanting to know exactly what is going on, but that is allowed to change between rustc versions.

Here, I disagree:

• People who want to know "exactly what is going on" should read the code (which is generally well-written and commented), while general users should be able to get enough information to do what they need to.
• If a detail is later determined to be important to the average programmer, it should be formally made part of the spec for that collection via an RFC and then included in the docs.
• If a user has a bizzare situation and needs to know something unusual, they should ask the rust team via an issue or on the IRC

The reason is that it breaks modularity. If we put something in the docs, even if it is marked "non-binding", somebody will write code that depends on the non-binding behavior, and that code will break when the non-binding behavior changes.

That said, I would like a section specifying what will not be standardized. For example, if for some reason it is not likely for the complexity of something to be specified, that should be well-noted.

More generally, I think it is also important to specify what should be mention in the module-level docs. IMHO, this should be:

1. Basic usage (unless obvious)
2. Design paradigms (e.g. RAII) that should guide the use of the library or help a programmer to understand the design better
3. The Unspecified/Unstandardized section

[hanna-kruppe]

@gnzlbg I have to agree that hashing out the details is out of scope for a single issue and at this stage the focus should be on the general direction. Unfortunately that still leaves us with a major philosophical disagreement: What to guarantee and what not. I don't really disagree with this sentiment:

At least I would consider making e.g. the complexity worse a breaking change "even if the API doesn't promise anything".

Certainly if someone filed an issue about a reasonable program that:

• regressed significantly in performance,
• ran into reasonable heap/stack limits,
• degraded in quality for other reasons (e.g., suddenly using many more syscalls),

then I am pretty sure someone would try to fix that. At the same time, I am entirely opposed to enshrining such "reasonable" guarantees to a degree that terms like "breaking change" float around. We even reserve the right to make programs stop compiling as a side effect of tweaking type inference or adding trait implementations. It is simply not realistic to freeze all the myriad details that can factor into a program compiling and running at peak performance, and occasionally some metric will get worse, accidentally or deliberately as part of a change that's for the better in other aspects.

So I am quite receptive to the idea of documenting these things as "non-binding"/"non-guarantees". This doesn't mean that you "cannot use std collections if [you] need stable behavior". Pragmatically, it just means that programs might occasionally get slower (and at other times faster). But this is nothing new and nothing that can be solved at the level of asymptotic complexity — codegen and optimization passes also have a huge effect and change much more frequently. For example, see #35408: rustc started overflowing its stack on some inputs, not because of any algorithmic changes but because of an inadequacy of MIR trans.

This is not something that can be willed away with API docs and RFCs, it is an unfortunate fact of software engineering.

[mark-i-m]

We even reserve the right to make programs stop compiling as a side effect of tweaking type inference or adding trait implementations.

But wouldn't this be labeled as a breaking change? I can't imagine something like this happening without at least an RFC? I'm just curious because this is a very strong statement...

[hanna-kruppe]

@mark-i-m See RFC 1122 for the official policy on language changes and RFC 1105 on library stuff like trait implementations. The people pulling the levers are responsible and careful enough that there aren't big changes dropping from the sky every other day (e.g., often there will be a crater run), but virtually every change anywhere in the API surface or certain parts of the compiler has the potential to break some code, even if it's usually hypothetical or pathological.

[mark-i-m]

Ah, I see what you mean now. Thanks

On Sep 7, 2016 12:07 PM, "Robin Kruppe" notifications@github.com wrote:

@mark-i-m https://github.com/mark-i-m See RFC 1122
https://github.com/rust-lang/rfcs/blob/master/text/1122-language-semver.md
for the official policy on language changes and RFC 1105
https://github.com/rust-lang/rfcs/blob/master/text/1105-api-evolution.md
on library stuff like trait implementations. The people pulling the levers
are responsible and careful enough that there aren't big changes dropping
from the sky every other day (e.g., often there will be a crater run), but
virtually every change anywhere in the API surface or certain parts of the
compiler has the potential to break some code, even if it's usually
hypothetical or pathological.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#36318 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AIazwKO-FZDnKrtk5ZNt_dJR60ArkPweks5qnu9QgaJpZM4J2xdf
.

[gnzlbg]

@mark-i-m

I have a question about your 5th point:

Changes the collection invariants and which ones

What do you mean by this?

I mean things like "this method changes the result of ::size(), ::capacity(), etc.". I should have said maybe "mutate the collection" or something like that.

Do you have a specific example where you have had problems?

Unstable sort is the typical example, e.g., if implemented using recursive quicksort it can overflow the stack, but if the implementation is a bit more clever and doesn't use recursion (or uses some sort of tail recursion), then that cannot happen. The guarantee is often O(1), and in some rare cases (dive and conquer algorithms) it might be O(logN), but the thing to read from there is "the implementation is allowed (or not) to use recursion, which as a consequence might overflow your stack". On a desktop this might be irrelevant (N would need to be too large), but on a tiny embedded system the amount of stack you get can be, well tiny.

People who want to know "exactly what is going on" should read the code (which is generally well-written and commented), while general users should be able to get enough information to do what they need to.

There are some things that are good to know, and having to read the code to find them is painful. For example, average programmers know that Vec has a growth factor and that they cannot rely on it. Still in some occasions it is nice to easily be able to find what it is. Examples are while benchmarking something you might see some effect that actually depends on the exact growth factor of a vector. Knowing the growth factor can help you better understand the benchmark results. Another example is writing an Allocators for a Vec. While you cannot rely on the growth factor, you might make your allocator faster by knowing in which ballpark it is (is it 1.2-1.4 or is it 1.9-2.). Another example is sort. It is useful to know the exact algorithm that sort uses (merge sort) without needing to go through the code. The exact algorithm might change, but if you know it is merge sort, and that merge sort is particularly bad suited for your input, that information would allow you to choose a better suited algorithm without having to dig through the code. Lots of sorting algorithms are ill suited for lots of patterns (like already sorted, almost already sorted, organ pipe, ...).

So I believe such a section with "summary of relevant implementation details that might change" is still worth it in some cases. Stuff like the complexities do hint at the implementation details, but having them in bullet point form avoid you to guess. For example if the worst case complexity of nth_element were O(N) that actually says which algorithm is used (since there is almost only one with that complexity), but while you don't want to guarantee that some specific algorithm is used, you can still save your users some work by spelling it out in some non-binding section (like "btw we use algorithm X, if somebody finds a better algorithm we might move to it, but your programs won't break because we won't make the complexity worse").

If a detail is later determined to be important to the average programmer, it should be formally made part of the spec for that collection via an RFC and then included in the docs.

Some details are always important, some are often important, and some might be important in corner cases. My point being, not all details are equally important. We might not be willing to commit on all details (e.g. the exact growth factor of a vector), but this doesn't mean we shouldn't pass this information to users. Requiring everybody to "read the code" doesn't scale.

The reason is that it breaks modularity. If we put something in the docs, even if it is marked "non-binding", somebody will write code that depends on the non-binding behavior, and that code will break when the non-binding behavior changes.

This happens independently of whether this information is inside some "do not rely on this" documentation section, or in the source code. That is, those users willing to rely on things they shouldn't rely on are going to do it independently of this. I don't think we should penalize all users by not including this information.

More generally, I think it is also important to specify what should be mention in the module-level docs. IMHO, this should be:

• Basic usage (unless obvious)
• Design paradigms (e.g. RAII) that should guide the use of the library or help a programmer to understand the design better
• The Unspecified/Unstandardized section

I think that if we mean the same thing by the unspecified/unstandardized section (what I was referring to as "non-biding"), that doesn't make much sense to me at the module level because that information is going to be highly method specific. Are you referring to something else?

---

@rkruppe

We even reserve the right to make programs stop compiling as a side effect of tweaking type inference or adding trait implementations.

Yes, for programs that are arguably already broken.

It is simply not realistic to freeze all the myriad details that can factor into a program compiling and running at peak performance, and occasionally some metric will get worse, accidentally or deliberately as part of a change that's for the better in other aspects. Pragmatically, it just means that programs might occasionally get slower (and at other times faster). But this is nothing new and nothing that can be solved at the level of asymptotic complexity — codegen and optimization passes also have a huge effect and change much more frequently.

@rkruppe Maybe we are talking past each other, but IIUC your point is that knowing the algorithmic and memory complexities of the methods, and whether they panic and have some form of side-effect or not, is worth documenting, but not worth "guaranteeing"? And that users should still rely on these even if they are not guaranteed, but if they change and their programs break, then they should complain? I'm a bit lost. I also have the feeling that for some reason you think that I am proposing guaranteeing that sorting X ints will run in Y micro-seconds on a Xeon Z, which couldn't be farther off from what I am proposing.

What I am proposing in a nutshell is guaranteeing the information required such that users know whether they can call sort in a loop of their application or not, whether that call can blow up their stack and segfault or not, and whether for some input they might get an OOM or not.

In particular, most of this information is already documented and guaranteed for sort, mainly because without this information nobody can really reason about whether sort is actually usable for their problem. This is actually true for all methods, so what I am proposing is doing this for all other methods as well.