November 16, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote: > ... I'm a horrible procrastinator, I should have had this fixed over a year ago, lol. Anyways, I posted a bug report about this problem long ago and a working solution has been gathering dust waiting to be implemented in Phobos. Bug report (poorly titled): http://d.puremagic.com/issues/show_bug.cgi?id=7767 Solution: https://github.com/Xinok/XSort/blob/master/unstablesort.d * It's an introsort which falls back to a bottom-up binary heap sort after so many recursions to guarantee O(n log n) performance in the worst-case. * It chooses the pivot from a median-of-five. It adds nearly zero overhead and results in a noticeable decrease in comparisons (predicate calls). I see no reason why not to add this. * My solution uses a binary insertion sort for sublists up to 32 elements long. This reduces comparisons as well but also adds a fair amount of overhead. It's about 15-20% slower when sorting an array of integers. My idea is to use this by default and specialize the linear insertion sort when the element type and predicate are known. * Regardless of these improvements, I think Timsort should be the default sorting algorithm. It's the better choice in many (most?) cases and, well, it's stable. Quick sort would still be available for those cases in which it's faster and stable sorting isn't needed. Well, it's Saturday and I have no plans. Let's see if I can't get a pull request done by the end of the day... |
November 16, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Xinok | On 11/16/13 11:46 AM, Xinok wrote:
> * Regardless of these improvements, I think Timsort should be the
> default sorting algorithm. It's the better choice in many (most?) cases
> and, well, it's stable. Quick sort would still be available for those
> cases in which it's faster and stable sorting isn't needed.
There's something fishy about a more restricted algorithm doing better than one that's less restricted. We must improve unstable sort, not make stable sort the default.
Andrei
|
November 16, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote: > On 11/16/13 11:46 AM, Xinok wrote: >> * Regardless of these improvements, I think Timsort should be the >> default sorting algorithm. It's the better choice in many (most?) cases >> and, well, it's stable. Quick sort would still be available for those >> cases in which it's faster and stable sorting isn't needed. > > There's something fishy about a more restricted algorithm doing better than one that's less restricted. We must improve unstable sort, not make stable sort the default. > > Andrei Timsort is an "adaptive" sort. It's able to achieve better performance in many cases by exploiting patterns in the data. I decided to make a nice little test using my benchmark code here: https://github.com/Xinok/XSort/blob/master/benchsort.d This is the permutation I designed for the test: static uint[] base; base.length = 1024 * 1024; foreach(i, ref v; base) v = i; foreach(i; 0..1024) { auto rand() { rndGen.popFront(); return rndGen.front % base.length; } switch(rand() % 3) { // Swap two ranges of elements case 0: { auto arr = [rand(), rand(), rand(), rand()]; sort(arr); swapRanges(base[arr[0]..arr[1]], base[arr[2]..arr[3]]); } break; // Reverse a range of elements case 1: { auto a = rand(), b = rand(); if(a > b) swap(a, b); reverse(base[a..b]); } break; // Shuffle a small range of elements case 2: { auto a = rand(); while(a < 1024) a = rand(); assert(a >= 1024); randomShuffle(base[a - 1024 .. a]); } break; default: assert(0); } } And the results (last number is predicate calls): Current Unstable Sort 50ms 32783474 New Unstable Sort 69ms 21503542 Timsort 35ms 3905887 That's why I suggest making Timsort the default sorting algorithm. |
November 16, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Xinok | On 11/16/13 2:11 PM, Xinok wrote: > On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote: >> On 11/16/13 11:46 AM, Xinok wrote: >>> * Regardless of these improvements, I think Timsort should be the >>> default sorting algorithm. It's the better choice in many (most?) cases >>> and, well, it's stable. Quick sort would still be available for those >>> cases in which it's faster and stable sorting isn't needed. >> >> There's something fishy about a more restricted algorithm doing better >> than one that's less restricted. We must improve unstable sort, not >> make stable sort the default. >> >> Andrei > > Timsort is an "adaptive" sort. It's able to achieve better performance > in many cases by exploiting patterns in the data. This is in response to what? Are you trying to talk me out of the pigeonhole principle? > I decided to make a nice little test using my benchmark code here: > https://github.com/Xinok/XSort/blob/master/benchsort.d I understand and appreciate that Timsort is a nicely optimized algorithm. This has nothing to do with it doing more work than an unstable sort that is just as nicely optimized. At the end of the day whatever stable sorting algorithms are out there, their set is included in the set of all sorting algorithms. In order to preserve stability, stable sorting algorithms need to do nonnegative extra work. Andrei |
November 16, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jean Christophe | On Saturday, 16 November 2013 at 14:20:32 UTC, Jean Christophe
wrote:
clip
>
> BTW I'm very interested in finding a library which could Quicksort an array of pointers, where each pointer points to a class object (or a structure) address. The library would make possible, for example, to sort the `class objects` using one of their members as the key. Because the swaps are done on the actual pointers (and not the Objects pointed), the Quicksort should be very efficient. However, the algorithm woulnd't be so trivial to implement because each comparison shall be done using the Object's member's value :
>
> eg. Obj1.foo < Obj2.foo.
>
> Of course, the programmer can choose any relevant member property to sort the collection. And it should be as easy to use as:
>
> class SomeClass { string foo; double bar;}
> SomeClass[] a;
> // put 100 000 objects into a
> a.sort("foo");
>
> Do we already have something like that available somewhere or is it possible to make one eventually?
>
> -- JC
This is sort of an interesting problem that you propose, because
while sorting just the pointers means moving things around less,
you would also get absolutely horrible locality of
reference/cache hit performance.
Have you thought about ways to deal with that?
|
November 17, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Saturday, 16 November 2013 at 23:40:39 UTC, Andrei Alexandrescu wrote:
>
> This is in response to what? Are you trying to talk me out of the pigeonhole principle?
>...
> I understand and appreciate that Timsort is a nicely optimized algorithm. This has nothing to do with it doing more work than an unstable sort that is just as nicely optimized.
>
> At the end of the day whatever stable sorting algorithms are out there, their set is included in the set of all sorting algorithms. In order to preserve stability, stable sorting algorithms need to do nonnegative extra work.
>
>
> Andrei
I think it's more complicated than that. Let's assume for a moment that you've proven that such an unstable sort must exist that is faster (I'm not convinced that it necessarily must take extra work to maintain stability). You have not shown how much faster it might be (it could be only 1% faster) nor how much work it would take to discover (even an ideal pivot choice for quicksort actually cannot be as fast as Timsort on an already sorted sequence, and quicksort is not an appropriate algorithm for accepting presorted subsequences). If it takes 2 years to come up with an unstable sort faster than Timsort, then it seems like a long time to be using something that isn't the best that we currently have. Especially if D is to be used in benchmarks against other languages.
Timsort is implemented now and has no real cost to use as default. If, at some point, an unstable sort is discovered that is faster on average than Timsort AND (extremely important) it has no potential for an attacker to be able to choose a sequence to sort that causes poor performance, then unstable could be switched back as the default at some point.
Right now, this could, in fact, cause a security hole (DOS-type attack) depending on how it is used. I think it's better to use a safer default in this case, even if we could make it faster than Timsort somehow.
|
November 17, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Chris Cain | On 11/16/13 4:18 PM, Chris Cain wrote: > I think it's more complicated than that. Let's assume for a moment that > you've proven that such an unstable sort must exist that is faster (I'm > not convinced that it necessarily must take extra work to maintain > stability). Very simple. Any sequence with a large number of equivalent elements will cause timsort to work more than an unstable algorithm, because it would need to shift around those elements. (Consider e.g. 1, 0, 0, 0, ..., 0.) The discussion then shifts to how many equivalent elements are in the typical range etc. > You have not shown how much faster it might be (it could be > only 1% faster) nor how much work it would take to discover (even an > ideal pivot choice for quicksort actually cannot be as fast as Timsort > on an already sorted sequence, and quicksort is not an appropriate > algorithm for accepting presorted subsequences). There are well known tweaks to quicksort that make it operate well on sorted or almost sorted sequences. > If it takes 2 years to > come up with an unstable sort faster than Timsort, then it seems like a > long time to be using something that isn't the best that we currently > have. Especially if D is to be used in benchmarks against other languages. > > Timsort is implemented now and has no real cost to use as default. If, > at some point, an unstable sort is discovered that is faster on average > than Timsort AND (extremely important) it has no potential for an > attacker to be able to choose a sequence to sort that causes poor > performance, then unstable could be switched back as the default at some > point. We could do that, but that would be masking a bug instead of fixing it. We should instead focus on fixing unstable sort. One additional issue with making stable sort the default for a while is that people will grow to assume sort() is stable, and will have broken code when we switch back. Let's fix unstable sort. If it's slower on any other data than Timsort's happy case, we have a bug. Andrei |
November 17, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Chris Cain | On Sunday, 17 November 2013 at 00:18:24 UTC, Chris Cain wrote: > I think it's more complicated than that. Let's assume for a moment that you've proven that such an unstable sort must exist that is faster (I'm not convinced that it necessarily must take extra work to maintain stability). You have not shown how much faster it might be (it could be only 1% faster) nor how much work it would take to discover (even an ideal pivot choice for quicksort actually cannot be as fast as Timsort on an already sorted sequence, and quicksort is not an appropriate algorithm for accepting presorted subsequences). If it takes 2 years to come up with an unstable sort faster than Timsort, then it seems like a long time to be using something that isn't the best that we currently have. Especially if D is to be used in benchmarks against other languages. Regarding an ideal pivot choice for quicksort, I'd like to emphasize that it is simply non-existent. Here's why. Let us measure quicksort performance as the number of comparisons it makes. Let us make some assumptions: quicksort goes as --(1) choose a pivot p in O(1) comparisons; --(2) partition the segment into two; --(3) run quicksort recursively on the two resulting segments. Now, (2) is effectively done by comparing every element with p, thus in Theta(n) (on the order of n) comparisons where n is the length of the current segment. Under these assumptions, we can construct the killer array for an arbitrary quicksort of such kind, even if we don't know how exactly the pivot is chosen (say, closed source or obfuscation), but we have the following interface to it: Instead of accessing the array a[], quicksort calls the function less(i,j) which tells it whether a[i]<a[j], and we control that function. Now, we start with all values in array a[] undefined. With each a[i], we associate a counter c[i]: how many times it took part in a comparison. As we can see from the above, during a single call to quicksort, in steps (1) and (2) the pivot will eventually get Theta(n) comparisons, while other elements will all get only O(1) comparisons each. So here's what we'll do. 1. When a comparison asks to relate two undefined values, we pick one of them with the larger c[i] and make it the lowest number possible. That is, the first fixed value will be 0, the next 1, and so on. (In the end, a[] will be a permutation of 0, 1, ..., n-1.) 2. When we are asked to relate a defined value to an undefined one, the defined value will always be lower (because, when we eventually define the undefined one, it will be higher than all the values defined before it). 3. When we are asked about two known values, just tell the truth. This simple algorithm ensures that, on each call to quicksort, we quickly fix the pivot as one of the O(1) lowest values on the segment. So, one of the next two segments will have length n-O(1), and the recursion gives us Theta(n) segments of linearly decreasing lengths, and thus Theta(n^2) total running time. Now, the assumption of picking a pivot in O(1) comparisons covers a broad variety of pivot choices, including first/last/middle/random element, median of three or five, median of medians, or any combination of these. The random pick fails in the following sense: if we seed the RNG, construct a killer case, and then start with the same seed, we get Theta(n^2) behavior reproduced. Double-pivot quicksort can be forced to go quadratic in a similar fashion. Now, introsort escapes this fate by switching to a guaranteed-n-log-n algorithm instead of (3) when it goes too deep. This comes at a (small) cost of checking the current depth on every call to quicksort. The above is just my retelling of a great short article "A Killer Adversary for Quicksort" by M. D. McIlroy here: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf Ivan Kazmenko. |
November 17, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Sunday, 17 November 2013 at 00:56:46 UTC, Andrei Alexandrescu wrote: > Very simple. Any sequence with a large number of equivalent elements will cause timsort to work more than an unstable algorithm, because it would need to shift around those elements. (Consider e.g. 1, 0, 0, 0, ..., 0.) The discussion then shifts to how many equivalent elements are in the typical range etc. Ah, very nicely described. So a stable sort can take more time when there is more than one equal element than a theoretical unstable sort. > There are well known tweaks to quicksort that make it operate well on sorted or almost sorted sequences. I'd have to see them to comment on them. I'd doubt that they only use quicksort if they support taking advantage of large parts of the array being sorted. I'd expect some sort of merging to occur in that case. > We could do that, but that would be masking a bug instead of fixing it. We should instead focus on fixing unstable sort. One additional issue with making stable sort the default for a while is that people will grow to assume sort() is stable, and will have broken code when we switch back. > > Let's fix unstable sort. If it's slower on any other data than Timsort's happy case, we have a bug. Sure, but could we at least agree on a timescale? If we can't come up with something significantly better than Timsort in the next year, it seems pointless to hold out for something that may never come. Hidden bug or not, deliberately exposing a bug that has no effective plan to be fixed isn't a good tactic either. Especially if D is expected to be competitive to other native languages in speed. Seeing D falter in the "sort" column of a shootout could be disconcerting to some and we can't count on everyone knowing to specify stable sort in those head-to-heads until we work out improving unstable sort. That said, your point that people might grow comfortable with sort being stable is a good one. Unfortunately, I don't have an answer for that. Documentation detailing that sort is not guaranteed a particular stability is about the best that could be done. Perhaps a variant of Timsort could be prepared that deliberately changes the order of equal elements. Designed instability could suffice as a stopgap against that (at least until the unstable sort is worked out). |
November 17, 2013 Re: Worst-case performance of quickSort / getPivot | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ivan Kazmenko | On Sunday, 17 November 2013 at 01:07:20 UTC, Ivan Kazmenko wrote: > Now, the assumption of picking a pivot in O(1) comparisons covers a broad variety of pivot choices, including first/last/middle/random element, median of three or five, median of medians, or any combination of these. The random pick fails in the following sense: if we seed the RNG, construct a killer case, and then start with the same seed, we get Theta(n^2) behavior reproduced. Correction: this does *not* cover the median-of-medians case [1]. Median of medians does not fall under our assumption that selecting a pivot is O(1). It also actually guarantees O(n log n) worst case performance, but of course at a cost of being slower than your typical pivot selection on an average case. [1] http://en.wikipedia.org/wiki/Median_of_medians Ivan Kazmenko. |
Copyright © 1999-2021 by the D Language Foundation