Reconsidering the recent changes in sort guarantees

The PR in question is #38192.

@steveklabnik had some objections to new guarantees of the sort algorithm.

Old guarantees: "This sort is stable and O(n log n) worst-case but allocates approximately 2 * n where n is the length of self."
New guarantees: "This sort is stable and O(n log n) worst-case, but allocates temporary storage half the size of self."

The new version is ATM in nightly only, so we still have time to adjust it. I agree that saying "approximately half the size" would be slightly better.

However... should we perhaps leave the guarantees as they were (2 * n), in order not to make alternative implementations non-compliant? What exactly should the documentation say?

Here's my stance on the issue:

First, sort algorithms should never ever allocate 2 * n additional memory. That's just way too much and I'm strongly against 2 * n. Even the old merge sort can be easily tweaked to allocate just n without compromising performance.

Second, stable sorts can often get away with allocating just n / 2. In fact, I successfully tweaked the old merge sort to allocate just n / 2 before I jumped on the TimSort ship.

Any stable sort that requires n memory can be made to work with just n / 2. Here's how. Split the input array in half. Sort each half using the allocated auxilliary buffer (which is of same length as the half itself). Move one of the halves into the buffer. Merge them into the original orray. Done.

Guarantees in some other programming languages:

1. Python (source) - TimSort allocates n / 2.
2. Java (source) - TimSort allocates n / 2.
3. C++ (docs) - std::stable_sort allocates n.

I believe it's safe to say that the standard sort allocates approximately n / 2, but would be okay with guaranteeing n, too.

Libs team, what do you think? @bluss?

[sfackler]

I'm not sure I understand in what contexts 2 * n allocation is a deal breaker but n or n / 2 isn't?

[brson]

It seems to me like the question here is only about what the docs say. I don't know the answers to your concerns, but the specificity of the documentation here, and that it has changed at all, both raise suspicion with me.

@sfackler I think the concern is that the documentation is constraining the implementation by being so specific about its space requirements. There aren't many sorts that can guarantee exactly n / 2 extra space. So alternate implementations are basically going to have to do what we're doing now, and we are constrained in our own choices in the future.

My instinct is that the docs should not make it sound like the implementation is guaranteed to use n / 2 space.

[nrc]

IMO, the docs should not be considered a normative spec for the implementation

@brson Yes, the question is only about what the docs say. Sorry that this change slipped through.

What you said makes sense, and I no longer believe that guaranteeing n/2 is a good idea. Or anything too specific, while we're at it.

By the way, here's what the C++ standard says about std::stable_sort: pdf, page 911 (or 925 in the pdf).
TL;DR: It doesn't specify how much it allocates, just that it will allocate if extra memory is available.

Allow me then to move forward and suggest two ways of expressing our guarantees:

1. "This sort is stable and O(n log n) worst-case, but may allocate temporary memory up to approximately the size of self."
2. "This sort is stable and O(n log n) worst-case, but may allocate some temporary memory."

Which one do you like best? I'm open to other suggestions, too.

[notriddle]

This sort is stable. It is O(n log n) with respect to comparisons and swaps, and O(n) with respect to memory allocated, worst-case.

[steveklabnik]

IMO, the docs should not be considered a normative spec for the implementation

I am also very happy to have this be true, if that's what @rust-lang/libs wants. This issue, as @stjepang mentions, is mostly about gaining clarity: if this comment was normative, then this would have been a breaking change.

I have no personal opinion on if it should be or not, but I fear it appears normative today.

[aturon]

@nrc

IMO, the docs should not be considered a normative spec for the implementation

Why not?

In general, we need a place to document the guarantees that client code should be able to rely on, and documentation is the natural place to do that. There are plenty examples of giving such contracts in documentation throughout the standard library.

Personally, I would take any behavior mentioned in the documentation as something you can and should rely on in your code, unless stated otherwise. I'm not sure how else to reliably program against an API.

Also, the Rust reference is explicitly non-normative. Isn't there an official decision regarding normativity of the stdlib documentation?

[nrc]

@aturon

Why not?

I might be wrong, but I believe that when adding documentation, a reviewer does not review on the basis that this is the spec for the API for evermore and will be binding up to our stability policy. Therefore it seems possible that there is documentation that we would not be happy to take as a normative spec.

Put another way, I would expect that any specification should be opted in to, rather than opted out of and documentation should indicate whether it is expected to be taken as a source of truth. Otherwise, I would treat docs as informative only with the same level of reliability as the source code when it comes to correctness (i.e., we are able to fix bugs in documentation in the same way as bugs in the source).

In general, we need a place to document the guarantees that client code should be able to rely on

Ideally, yes we do, but IMO, we don't have such a place at the moment. Likewise, we should have a proper specification for the language, but we don't (we have the RFCs and references and book, all of which are approaching such a thing, but are not there yet).

[aturon]

This definitely seems worth a live discussion on the libs team; nominating for the next meeting.