[Pre-RFC] Unstable sort in libcore

[orlp]

As I mentioned in my email, pdqsort is not slightly slower than introsort when not sorting integers.

There are two pdqsort variants: one with regular partitioning and one with block partitioning. The block partitioning is significantly (50-80%) faster than introsort when the comparison function is branchless. When the comparison function is not branchless, it’s 5-15% slower.

The version with regular partitioning is indistinguishable from a properly implemented introsort on random data, but is significantly faster on data with patterns (ascending, descending, one element out of order, all equal keys, etc).

pdqsort is intended to be a strict upgrade over introsort. The only confusion here is that I recently added block partitioning, which heavily sped up integer sorting, but slowed other things down slightly. The latest C++ version of pdqsort automatically dispatches the right version of partitioning depending on the comparison operator and data type given to sort.

[birkenfeld]

Timsort and wikisort are pretty similar - the difference is that timsort does not allocate.

but in the table it’s the other way round.

[orlp]

The table is correct.

EDIT: the table is incorrect for pdqsort. pdqsort is comparison-based.

[stjepang]

As I mentioned in my email, pdqsort is not slightly slower than introsort when not sorting integers.

Understood. I fixed this in my writeup.

but in the table it’s the other way round.

Fixed.

EDIT: the table is incorrect for pdqsort. pdqsort is comparison-based.

Fixed.

[Ixrec]

Since I’m not a sort algorithm performance guru, my qualms with this proposal are:

1. Having a function in std:: and a function in core:: with the same exact name (“sort”) but different implementations strikes me as misleading. I’m used to std::X always being either a reexport or something that can’t exist in core.

2. Having “unstable_sort” be the name of the “sort that doesn’t allocate” function also seems misleading, unless there’s some deep theoretical reason I’m not aware of why instability obviously and necessarily means an in-place/non-allocating algorithm and instability is considered more important than non-allocation.

I’d rather be more explicit and have “noalloc_sort”, “unstable_sort” and maybe even “noalloc_unstable_sort” be distinct functions from just “sort” so there’s zero confusion over what functions guarantee what, or what is and isn’t a reexport. Then we can move on to figuring out whether pdqsort or wikisort or whatever is the optimal implementation for each one.

[stjepang]

1. Having a function in std:: and a function in core:: with the same exact name (“sort”) but different implementations strikes me as misleading. I’m used to std::X always being either a reexport or something that can’t exist in core.

After some more thinking, this is something I actually tend to agree with. I’m not so sure about having stable sort in libcore anymore.

2. Having “unstable_sort” be the name of the “sort that doesn’t allocate” function also seems misleading, unless there’s some deep theoretical reason I’m not aware of why instability obviously and necessarily means an in-place/non-allocating algorithm and instability is considered more important than non-allocation.

Well, naming is hard. The reason why “unstable_sort” and “noalloc_sort” are the same function is that they go hand in hand:

• If you’re implementing “unstable_sort”, you don’t need allocation because it won’t gain you anything in terms of performance. There isn’t a deep theoretical reason for that, but is something that has been consistently true in practice.
• If you’re implementing “noalloc_sort”, then a stable variant will be considerably slower than an unstable variant (about twice as slow).

I think most Rust users in most situations prefer performance over stability. They also prefer zero allocation over stability. If they’re using #![no_std] there is no sort function at all!

All that said, stable sorting by default was a good decision, but there is obviously a strong desire for really fast unstable non-allocating sorting. It’s a fortunate fact that high performance, zero-allocation, instability, and inclusion into libcore can be uncompromisingly covered by a single function.

[Ixrec]

One thing I forgot to consider in my last post is that “inclusion into libcore” already implies “zero-allocation”, so with that in mind I wouldn’t object to “unstable_sort” being the name of the sort function that gets to be in libcore. Then libstd would have “sort” (guarantees stability but might allocate) and a reexport of “unstable_sort” (guarantees no allocation but might be unstable), which seems reasonable to me.

The only case that wouldn’t satisfy would be a sorting algorithm that guarantees both stability and zero-allocation. I assume that’s sufficiently niche we can simply ignore it, i.e. leave it to 3rd-party crates?

[stjepang]

Then libstd would have “sort” (guarantees stability but might allocate) and a reexport of “unstable_sort” (guarantees no allocation but might be unstable), which seems reasonable to me.

I’d be very happy with this solution!

The only case that wouldn’t satisfy would be a sorting algorithm that guarantees both stability and zero-allocation. I assume that’s sufficiently niche we can simply ignore it, i.e. leave it to 3rd-party crates?

Exactly. Stable zero-allocation sort is very niche.

[stjepang]

I’ve reduced the scope of this pre-RFC.

Stable sorting in libcore (wikisort) is ditched, and all the fuss with block-partitioning was just a distraction. The unstable sort is now named slice::unstable_sort.

[leonardo]

I like this reduction in the RFC scope. Further changes are better moved in successive RFCs.

What about adding slice::unstable_sort_by and slice::unstable_sort_by_key too?

Since stable and unstable sorting are indistinguishable from each other when sorting integers, it might be a good idea to specialize slice::sort for those cases and switch to pdqsort. But I’m not too fond of this idea. I’d prefer to have more consistent and predictable performance.

What are exactly the disadvantages of adding this specialization? It seems nice.

[stjepang]

What about adding slice::unstable_sort_by and slice::unstable_sort_by_key too?

I thought it’s obvious that those variants would exist, too. Will mention them.

What are exactly the disadvantages of adding this specialization? It seems nice.

I look at this issue from the standpoint of documentation.

If you look at how slice::sort is documented, you’ll see it’s not difficult to understand the performance characteristics of this function. Someone who has a rough idea of how timsort works might want to take advantage of it’s peculiarities. If a user wants to efficiently merge 5 sorted sequences, timsort will probably be faster than pdqsort.

Now, if you patch the function with special cases and say pdqsort is used for this, this, and that case, then it gets ugly. Then, the user might not have the choice of choosing timsort vs pdqsort anymore!

This might seem like a contrived example, but having straightforward implementations that don’t patch various cases with wildly different algorithms is certainly desirable.

[zackw]

Let’s make sure we document the difference between a “stable sort” and an “unstable sort” and give some examples of when it matters.

[stjepang]

Let’s make sure we document the difference between a “stable sort” and an “unstable sort” and give some examples of when it matters.

Done!

[gnzlbg]

I would prefer if the API of unstable sort in libcore would optionally take a buffer (as a slice) since typically is possible to significantly speed up unstable sort with one. Obviously, unstable sort should still work when provided with an empty buffer. I think that taking a slice for the buffer would be the correct thing to do, but I am not 100% confident about this. Are there any alternatives?

For lib std, on the other hand, it would make sense to have an unstable sort function that does not take a buffer but always tries to allocate one. Those who want to avoid the allocation can always resort to using the one from libcore.

[stjepang]

I would prefer if the API of unstable sort in libcore would optionally take a buffer (as a slice) since typically is possible to significantly speed up unstable sort with one.

I’m very skeptical of this claim. How would you significantly speed up unstable sort with a buffer?

[gnzlbg]

I’m very skeptical of this claim.

That’s the right attitude!

How would you significantly speed up unstable sort with a buffer?

So I just checked because I had in mind that some c++ sort implementations do this, but in fact none of the unstable ones do so I was mistaken. The stable sort implementations in libc++, libstdc++, and MSVC do allocate memory (using std::get_temporary_buffer for merge sort) but the unstable sort ones do not allocate memory. Sorry about the noise.

[ahmedcharles]

Everything you said applies to stable sort. The reason std::get_temporary_buffer exists is because it was believed that operating systems would have a way of allocating memory based on memory pressure, such that if you asked for 50MB and that request would end up being slow, but 20MB could be returned cheaply, then you’d get 20MB of memory instead.

Anyways, that never happened, but the stable_sort implementation is required to work whether it gets a temporary buffer or not and there’s no real reason that the sort implementation in either standard or core can’t use that strategy.

[scottmcm]

The faster sort PR (https://github.com/rust-lang/rust/pull/38192) showed its improvement with a bunch of data sets. Will those be the right ones to demonstrate perf of this too, or are there other cases because of the different algorithm?

Should this RFC talk about what kind of quicksort is expected? Single/double pivot? Fat partition because cmp is ternary?

[kornel]

I’d call it inplace_sort(), in case a non-allocating stable sort is used in the future.

[stjepang]

Will those be the right ones to demonstrate perf of this too, or are there other cases because of the different algorithm?

Those data sets are mostly okay, but I have plans to expand the set of benchmarks.

Should this RFC talk about what kind of quicksort is expected? Single/double pivot? Fat partition because cmp is ternary?

Yes, this is something worth discussing in the RFC.

The short story is: pdqsort gains massive speedups purely from block partitioning. Double pivoting gives us much smaller gains and is incompatible with block partitioning, so it goes out the window. The same thing applies to fat partitioning. But don’t worry, pdqsort does not suffer if the input slice contains a lot of duplicates.