7 ms·
Pattern-defeating quicksort
- beagle3 9y agoAnyone knows how this compares to Timsort in practice? A quick google turns out nothing
- mastax 9y agohttps://github.com/rust-lang/rust/pull/40601 https://github.com/rust-lang/rust/pull/40601 "stable" is a simplified Timsort: https://github.com/rust-lang/rust/pull/38192 https://github.com/rust-lang/rust/pull/38192 "unstable" is a pdqsort
- stjepang 9y agoTo summarize: If comparison is cheap (e.g. when sorting integers), pdqsort wins because it copies less data around and the instructions are less data-dependency-heavy. If comparison is expensive (e.g. when sorting strings), timsort is usually a tiny bit faster (around 5% or less) because it performs a slightly smaller total number of comparisons.
- nneonneo 9y agoI would love to see the benchmark results against Timsort, the Python sorting algorithm that also implements a bunch of pragmatic heuristics for pattern sorting. Timsort has a slight advantage over pdqsort in that Timsort is stable, whereas pdqsort is not. I see that timsort.h is in the benchmark directory, so it seems odd to me that the README doesn't mention the benchmark results.
- nightcracker 9y agoThere are multiple reasons I don't include Timsort in my README benchmark graph: 1. There is no authoritative implementation of Timsort in C++. In the bench directory I included https://github.com/gfx/cpp-TimSort https://github.com/gfx/cpp-TimSort, but I don't know the quality of that implementation. 2. pdqsort intends to be the algorithm of choice of a system unstable sort. In other words, a direct replacement for introsort for std::sort. So std::sort is my main comparison vehicle, and anything else is more or less a distraction. The only reason I included std::stable_sort in the benchmark is to show that unstable sorting is an advantage for speed for those unaware. But, since you're curious, here's the benchmark result with Timsort included on my machine: http://i.imgur.com/tSdS3Y0.png http://i.imgur.com/tSdS3Y0.png This is for sorting integers however, I expect Timsort to become substantially better as the cost of a comparison increases.
- jorgemf 9y agoWhere 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.
- klodolph 9y agoThe readme file actually contains a fairly thorough description of how it differs from quicksort. Start with the section titled "the best case".
- jorgemf 9y ago> On average case data where no patterns are detected pdqsort is effectively a quicksort that uses median-of-3 pivot selection So basically is quicksort with a bit more clever pivot selection, but only for some cases.
- _hrfd 9y agoYou're forgetting probably the most important optimization: block partitioning. This one alone makes it almost 2x faster (on random arrays) than typical introsort when sorting items by an integer key.
- wiz21c 9y agoIs there a analysis of its complexity ? The algorithm looks very nice !
- nightcracker 9y agoHey, 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_T0Fxeno1a0lGT0E https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
- ouid 9y agoBest case? Give worst and average case when describing complexities.
- nightcracker 9y agoI already did, you may want to re-read my comment.
- ouid 9y agoAm I misinterpreting your usage of "best case"?
- nightcracker 9y agoWithout enlightening me on what your interpretation is, I have no way of telling. pdqsort has a worst case of O(n log n). That means, no matter what, the algorithm never takes more than a constant factor times n log n time to complete. Since pdqsort is strictly a comparison sort, and comparison sorts can do no better than O(n log n) in the average case, pdqsort is asymptotically optimal in the average case (because the average case can never be worse than the worst case). On top of the above guarantees, if your input contains only k distinct keys, then pdqsort has a worst case complexity of O(nk). So when k gets small (say, 1-5 distinct elements), pdqsort approaches linear time. That is pdqsort's best case.
- atilimcetin 9y agoRust's stable sort is based on timsort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort 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.sort_unstable 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 sequences.'
- k__ 9y agohow much faster?
- sgift 9y agoHere are a few benchmarks results from a recent rayon pull: https://github.com/nikomatsakis/rayon/pull/379 https://github.com/nikomatsakis/rayon/pull/379 So, for a dual-core with HT 8.26s vs 4.55s
- gnarbarian 9y agoI like merge sort. Average time may be worse, but it's upper bound is better and it is conceptually cleaner and easier to understand (IMO).
- partycoder 9y agoJust that it takes extra space and that's sometimes a constraint.
- chii 9y agohttps://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm https://stackoverflow.com/questions/2571049/how-to-sort-in-p... In place merge sort exists. It's hard to write tho
- jkabrg 9y ago[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 reasonably likely to trigger the worst case of randomised quicksort, or you're not working with such lists. By likely, I mean the probability is not extremely small. Consider the case when the worst case is very unlikely: you're so unlikely to have a worst case that you're gaining almost nothing for accounting for it except extra complexity. So you might as well only use quicksort with optimisations that are likely to actually help. Next is the case that a worst case might actually happen. Again, this is not by chance; it has to be because someone can predict your "random" pivot and screw with your algorithm; in that case, I propose just using heapsort. Why? This might be long, so I apologise. It's because usually when you design something, you design it to a high tolerance; a high tolerance in this case ought to be the worst case of your sorting algorithm. In which case, when designing and testing your system, you'll have to do extra work to tease out the worst case. To avoid doing that, you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort.
- nightcracker 9y agoThe 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 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.
- jkabrg 9y agoThanks for your reply. > 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.
- dpcx 9y agoQuestion as a non low-level developer, and please forgive my ignorance: 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?
- jorgemf 9y agoAs far as I understood, the base algorithm is the same which has an average case of n log(n). The new algorithms only try to improve the pivot selection to avoid the worst cases and try to be better than the average case for most practical cases. But at the end there are not new algorithms improving the limit of n log(n).
- paulddraper 9y agoThis is an improvment in practical cases, not theoretical ones.
- stjepang 9y agoBasically all comparison-based sort algorithms we use today stem from two basic algorithms: mergesort (stable sort, from 1945) and quicksort (unstable sort, from 1959). Mergesort was improved by Tim Peters in 2002 and that became timsort. He invented a way to take advantage of pre-sorted intervals in arrays to speed up sorting. It's basically an additional layer over mergesort with a few other low-level tricks to minimize the amount memcpying. Quicksort was improved by David Musser in 1997 when he developed introsort. He set a strict worst-case bound of O(n log n) on the algorithm, as well as improved the pivot selection strategy. And people are inventing new ways of pivot selection all the time. E.g. Andrei Alexandrescu has published a new method in 2017[1]. In 2016 Edelkamp and Weiß found a way to eliminate branch mispredictions during the partitioning phase in quicksort/introsort. This is a vast improvement. The same year Orson Peters adopted this technique and developed pattern-defeating quicksort. He also figured out multiple ways to take advantage of partially sorted arrays. Sorting is a mostly "solved" problem in theory, but as new hardware emerges different aspects of implementations become more or less important (cache, memory, branch prediction) and then we figure out new tricks to take advantage of modern hardware. And finally, multicore became a thing fairly recently so there's a push to explore sorting in yet another direction... [1] http://erdani.com/research/sea2017.pdf http://erdani.com/research/sea2017.pdf
- stjepang 9y agoI think it's fair to say that pdqsort (pattern-defeating quicksort) is overall the best unstable sort and timsort is overall the best stable sort in 2017, at least if you're implementing one for a standard library. 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 https://github.com/rust-lang/rust/pull/38192 [2] https://github.com/rust-lang/rust/issues/40585 https://github.com/rust-lang/rust/issues/40585 [3] https://github.com/rust-lang/rust/pull/40601 https://github.com/rust-lang/rust/pull/40601 [4] https://github.com/nikomatsakis/rayon/pull/379 https://github.com/nikomatsakis/rayon/pull/379
- Retric 9y agoComparing sorting algo's often says more about your benchmark than the algo's themselves. Random and pathological are obvious, but often your dealing with something in between. Radix vs n log n is another issue. So, what where your benchmarks like?
- 9y ago
- deleted 9y ago[deleted]
- j_s 9y agoHas HN ever discussed the possibilities when purposely crafting worst-case input to amplify a denial-of-service attack?
- nightcracker 9y agoIf whoever you're targeting uses libc++, I already did the analysis: https://bugs.llvm.org/show_bug.cgi?id=20837 https://bugs.llvm.org/show_bug.cgi?id=20837 To my knowledge it's still not fixed.
- beagle3 9y agoDoug McKilroy did some 20 years ago, for quick sort: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
- graycat 9y agoI always wondered if there would be a way to have quicksort run slower than O(n ln(n)). Due to that possibility, when I code up a sort routine, I use heap sort. It is guaranteed O(n ln(n)) worst case and achieves the Gleason bound for sorting by comparing keys which means that on average and worst case, on the number of key comparisons, it is impossible to do better than heap sort's O(n ln(n)) forever. For a stable sort, sure, just extend the sort keys with a sequence number, do the sort, and remove the key extensions. Quicksort has good main memory locality of reference and a possibility of some use of multiple threads, and heap sort seems to have neither. But there is a version of heap sort modified for doing better on locality of reference when the array being sorted is really large. But, if are not too concerned about memory space, then don't have to care about the sort routine being in place. In that case, get O(n ln(n)), a stable sort, no problems with locality of reference, and ability to sort huge arrays with just the old merge sort. I long suspected that much of the interest in in-place, O(n ln(n)), stable sorting was due to some unspoken but strong goal of finding some fundamental conservation law of a trade off of processor time and memory space. Well, that didn't really happen. But heap sort is darned clever; I like it.
- Franciscouzo 9y ago> I long suspected that much of the interest in in-place, O(n ln(n)), stable sorting was due to some unspoken but strong goal of finding some fundamental conservation law of a trade off of processor time and memory space. Well, that didn't really happen. But heap sort is darned clever; I like it. It did happen, it's called block sort, but it's not used because of the complexity of implementing it, the constants of its runtime, it's not easy to parallelize, and its best case complexity is still O(n ln n).
- torrent-of-ions 9y agoIt's cool to play with a pack of cards and run sorting algorithms on them. To see the worst case of quicksort, use the first element as the pivot and give it an already sorted list. It will take quadratic time to give back the same list.
- graycat 9y ago
- torrent-of-ions 9y agoI can see why one might blindly call qsort on already sorted data (when using user input), but why sorted data with one out of place element? Presumably that element has been appended to a sorted array, so you would place it properly in linear time using insertion and not call a sort function at all. Why does such a pattern arise in practice?
- nightcracker 9y agoYou would be surprised how often people just use a (repeatedly) sorted vector in spite of a proper data structure or proper insertion calls. It's a lot simpler to just append and sort again. Or the appending happens somewhere else in the code entirely. As a real-world example, consider a sprite list in a game engine. Yes, you could keep it properly sorted as you add/remove sprites, but it's a lot simpler to just append/delete sprites throughout the code, and just sort it a single time each frame, even if it only adds a single sprite. So yes, technically this pattern is not needed if everyone always recognized and used the optimal data structure and algorithm at the right time. But that doesn't happen, and it isn't always the simplest solution for the programmer.
- ComputerGuru 9y agoJust because I was confused: this is by Orson Peters who first invented pdq. It's not brand new (as in yesterday), but is a very, very recent innovation (2016).
- kleiba 9y agoThis book is one of the most general treatments of parameterized Quicksort available: http://wild-inter.net/publications/wild-2016.pdf http://wild-inter.net/publications/wild-2016.pdf
- unruledboy 9y agoit's interesting that .Net built-in quicksort is actually doing the same thing, with introsort behind the scenes.