[Pre-RFC] Unstable sort in libcore

stjepang · 2017-01-30T20:45:23.097Z

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.

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

gnzlbg · 2017-01-30T22:26:51.379Z

stjepang:

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 · 2017-01-31T19:53:13.350Z

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 · 2017-02-01T08:31:18.312Z

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 · 2017-02-01T14:49:40.515Z

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

stjepang · 2017-02-02T01:27:36.534Z

scottmcm:

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.

scottmcm:

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.

orlp · 2017-02-02T11:18:20.180Z

But don’t worry, pdqsort does not suffer if the input slice contains a lot of duplicates.

Rather, the opposite happens. pdqsort is both O(n log n) and O(nk), where k is the number of unique elements you’re sorting. Both are upper bounds, so when k is fixed, pdqsort is actually linear. This shows in the ‘shuffled 16 values’ benchmark from my github repo:

jongiddy · 2017-02-06T21:36:47.295Z

stjepang:

there is obviously a strong desire for really fast unstable non-allocating sorting

I think there may be a desire for really fast sorting and sometimes a requirement for non-allocating sorting, but I can’t remember ever hearing anyone express a desire or requirement for unstable sorting. Usually, the requirement is for stable sorting or is indifferent to stability. Hence, I agree with

kornel:

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

zackw · 2017-02-06T21:45:18.315Z

So I think the naming bikeshed boils down to this poll:

Which of these is more important to express in the name of the function?

“Use this function if you need an in-place sort.”
“Don’t use this function if you need a stable sort.”

0 voters

Show results

stjepang · 2017-02-07T13:15:28.997Z

Thanks for making this poll!

I voted “don’t use this function if you need a stable sort”. My reasoning is that it’s more important to express what you lose when departing from the default (you lose stability), rather than expressing one of the benefits (being in-place, in addition to better performance). Especially so because there is just one drawback and multiple benefits. Moreover, the stable/unstable dichotomy is surely familiar to C++ users.

By the way, an RFC is already submitted so you may want to participate in the discussion there:

github.com/rust-lang/rfcs

Add unstable sort to libcore

by stjepang on 09:32PM - 03 Feb 17

9 commits changed 1 files with 221 additions and 0 deletions.

gnzlbg · 2017-02-10T11:42:51.420Z

Why not just provide two functions: unstable_sort (which does not guarantee being inplace), and unstable_inplace_sort (which guarantees being inplace) ?

Whether unstable_sort just calls unstable_inplace_sort internally is an implementation detail, and we can change it at any time without breaking the API in case a better unstable non-in-place sorting algorithm is implemented in the future (which will probably be in place for some inputs, and out-of-place for others).

stjepang · 2017-03-18T16:04:11.358Z

A PR that implements unstable sort in libcore has been submitted: https://github.com/rust-lang/rust/pull/40601

leonardo · 2017-03-22T12:03:43.216Z

Today I’ve tried the unstable sort functions, and they seem rather nice, I’ve seen a small speedup of my code.

system · 2019-03-25T08:27:47.987Z

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.