11–20 of 79 posts
Rust's stable sort is based on timsort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ) and unstable sort is based on pattern-defeating quicksort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted seq…
Anyone knows how this compares to Timsort in practice? A quick google turns out nothing
"stable" is a simplified Timsort: https://github.com/rust-lang/rust/pull/38192
"unstable" is a pdqsort
Rust's stable sort is based on timsort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ) and unstable sort is based on pattern-defeating quicksort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted seq…
how much faster?
https://github.com/nikomatsakis/rayon/pull/379
So, for a dual-core with HT 8.26s vs 4.55s
Is there a analysis of its complexity ? The algorithm looks very nice !
Hey, author of pdqsort here, the draft paper contains complexity proofs of the O(n log n) worst case and O(nk) best case with k distinct keys: https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
[Post-edit] I made several edits to the post below. First, to make an argument. Second, to add paragraphs. [/Post-edit] Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort. Long version: Here's my reasoning for the above: You're either working with lists that are reasonabl…
Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs.
There are no real disadvantages to the hybrid approach.
Earlier quoted context omitted.
Hey, author of pdqsort here, the draft paper contains complexity proofs of the O(n log n) worst case and O(nk) best case with k distinct keys: https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
Best case? Give worst and average case when describing complexities.
[Post-edit] I made several edits to the post below. First, to make an argument. Second, to add paragraphs. [/Post-edit] Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort. Long version: Here's my reasoning for the above: You're either working with lists that are reasonabl…
The overhead of including the fallback to heapsort takes a negligible, non-measurable amount of processing time that guarantees a worst case runtime of O(n log n), and to be more precise, a worst case that is 2 - 4 times as slow as the best case. Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would…
> Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs.
Why is that a wrong conclusion? It might be, I'm not a dev. But if I found myself caring about that sort of minutiae, I would reach exactly that conclusion.
Reasons:
* the paranoid possibility that enough users can trigger enough DoS attacks that your system can fall over. If this is likely enough, maybe you should design for the 2-4x worst case, and make your testing and provisioning of resources easier.
* a desire for simplicity when predicting performance, which you're losing by going your route because you're adding the possibility of a 2-4x performance drop depending on the content of the list. Ideally, you want the performance to solely be a function of n, where n is the size of your list; not n and the time-varying distribution of evilness over your users.
Finally, adding a fallback doesn't seem free to me, because it might fool you into not addressing the points I just made. That O(n^2) for Quicksort might be a good way to get people to think; your O(n log n) is hiding factors which don't just depend on n.
How is it that we're essentially 50 years in to writing sorting algorithms, and we still find improvements? Shouldn't sorting items be a "solved" problem by now?
The standard sort algorithm in Rust is timsort[1] (slice::sort), but soon we'll have pdqsort as well[2] (slice::sort_unstable), which shows great benchmark numbers.[3] Actually, I should mention that both implementations are not 100% equivalent to what is typically considered as timsort and pdqsort, but they're pretty close.
It is notable that Rust is the first programming language to adopt pdqsort, and I believe its adoption will only grow in the future.
Here's a fun fact: Typical quicksorts (and introsorts) in standard libraries spend most of the time doing literally nothing - just waiting for the next instruction because of failed branch prediction! If you manage to eliminate branch misprediction, you can easily make sorting twice as fast! At least that is the case if you're sorting items by an integer key, or a tuple of integers, or something primitive like that (i.e. when comparison is rather cheap).
Pdqsort efficiently eliminates branch mispredictions and brings some other improvements over introsort as well - for example, the complexity becomes O(nk) if the input array is of length n and consists of only k different values. Of course, worst-case complexity is always O(n log n).
Finally, last week I implemented parallel sorts for Rayon (Rust's data parallelism library) based on timsort and pdqsort[4].
Check out the links for more information and benchmarks. And before you start criticizing the benchmarks, please keep in mind that they're rather simplistic, so please take them with a grain of salt.
I'd be happy to elaborate further and answer any questions. :)
[1] https://github.com/rust-lang/rust/pull/38192
[2] https://github.com/rust-lang/rust/issues/40585
Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
The readme file actually contains a fairly thorough description of how it differs from quicksort. Start with the section titled "the best case".
So basically is quicksort with a bit more clever pivot selection, but only for some cases.