I've been investigating an instance that I ran into while processing some data, in which multiSort had apparently stalled whereas two successive sort calls processed the data quickly. After reducing the code and 20 million points, I've reduced the problem to this test case:

enum N=1000000;
N.iota.retro.chain(N.only).array.sort();

Apparently, this simple case exhibits worst-case (quadratic) complexity in our sort implementation. The .retro isn't necessary - this also exhibits quadratic complexity (athough the total number of predicate calls is halved), because the first quickSort cycle will flip the order of elements during partitioning:

N.iota.chain(0.only).array.sort();

Closer inspection shows that the problem is manifested due to how the pivot is chosen. Currently, std.algorithm's getPivot uses the median-of-three method (median value of first, middle and last element[1]). However, in this case, the median element will always be the first element - this remains true in all quickSort iterations.

Here is an illustrated example with N=9. Note that at the same time as choosing the pivot, getPivot also orders the candidates (first, middle and last range elements) according to the sort predicate. After calling getPivot, quickSortImpl moves the pivot to the end of the range by swapping it with the last element.

getPivot(0..10)
8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
getPivot(2..10)
6,5,4,3,2,1,0,7 <- getPivot - before swap
7,5,4,3,6,1,0,2 <- getPivot - after swap
7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
(...)

The algorithm gets stuck on "slopes" in sorted data, which are not uncommon in real-world data (my data resembled a 1D heightmap). Although the median-of-three way of picking a pivot is recommended by some sources (notably Sedgewick), perhaps a better method would be better suitable for Phobos:

* Many sources recommend using a random element as a pivot. According to [2], "Randomized quicksort, for any input, it requires only O(n log n) expected time (averaged over all choices of pivots)". Also, if it is not possible to predict the pivot choice, it is impossible to craft worst-case input, which is a plus from a security point[3]. However, I'm not sure if making the behavior of std.algorithm's sort nondeterministic is desirable.
* It looks like many STL implementations use Introsort[4] - a hybrid sorting algorithm which starts with QuickSort, but switches to HeapSort if the recursion limit exceeds a threshold.
* I found a recent article[5] which describes an optimal algorithm of picking a pivot, however it is behind a paywall.

[1]: Apparently the term is also used to refer to choosing three points *randomly*, instead of first/middle/last: http://stackoverflow.com/a/164183/21501
[2]: http://en.wikipedia.org/wiki/Quicksort#Analysis_of_Randomized_quicksort
[3]: https://www.google.com/search?q=quicksort+worst+case+denial+of+service
[4]: http://en.wikipedia.org/wiki/Introsort
[5]: https://news.ycombinator.com/item?id=6629117

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev
wrote:
clip
>
> The algorithm gets stuck on "slopes" in sorted data, which are not uncommon in real-world data (my data resembled a 1D heightmap). Although the median-of-three way of picking a pivot is recommended by some sources (notably Sedgewick), perhaps a better method would be better suitable for Phobos:
If you use median-of-five (or seven) then you would start getting
reasonable pivots in such an instance, though I am sure someone
could craft an input set that defeats that. Does the Sedgewick
source mention why 3 is picked?  Easy to implement I assume.

> * Many sources recommend using a random element as a pivot. According to [2], "Randomized quicksort, for any input, it requires only O(n log n) expected time (averaged over all choices of pivots)". Also, if it is not possible to predict the pivot choice, it is impossible to craft worst-case input, which is a plus from a security point[3]. However, I'm not sure if making the behavior of std.algorithm's sort nondeterministic is desirable.
What are the arguments against using a randomized algorithm?


> * It looks like many STL implementations use Introsort[4] - a hybrid sorting algorithm which starts with QuickSort, but switches to HeapSort if the recursion limit exceeds a threshold.
> * I found a recent article[5] which describes an optimal algorithm of picking a pivot, however it is behind a paywall.
>
> [1]: Apparently the term is also used to refer to choosing three points *randomly*, instead of first/middle/last: http://stackoverflow.com/a/164183/21501
> [2]: http://en.wikipedia.org/wiki/Quicksort#Analysis_of_Randomized_quicksort
> [3]: https://www.google.com/search?q=quicksort+worst+case+denial+of+service
> [4]: http://en.wikipedia.org/wiki/Introsort
> [5]: https://news.ycombinator.com/item?id=6629117

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
> I've been investigating an instance that I ran into while processing some data, in which multiSort had apparently stalled whereas two successive sort calls processed the data quickly. After reducing the code and 20 million points, I've reduced the problem to this test case:
>
> enum N=1000000;
> N.iota.retro.chain(N.only).array.sort();
>
> Apparently, this simple case exhibits worst-case (quadratic) complexity in our sort implementation. The .retro isn't necessary - this also exhibits quadratic complexity (athough the total number of predicate calls is halved), because the first quickSort cycle will flip the order of elements during partitioning:
>
> N.iota.chain(0.only).array.sort();
>
> Closer inspection shows that the problem is manifested due to how the pivot is chosen. Currently, std.algorithm's getPivot uses the median-of-three method (median value of first, middle and last element[1]). However, in this case, the median element will always be the first element - this remains true in all quickSort iterations.
>
> Here is an illustrated example with N=9. Note that at the same time as choosing the pivot, getPivot also orders the candidates (first, middle and last range elements) according to the sort predicate. After calling getPivot, quickSortImpl moves the pivot to the end of the range by swapping it with the last element.
>
> getPivot(0..10)
> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
> getPivot(2..10)
> 6,5,4,3,2,1,0,7 <- getPivot - before swap
> 7,5,4,3,6,1,0,2 <- getPivot - after swap
> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
> (...)
>
> The algorithm gets stuck on "slopes" in sorted data, which are not uncommon in real-world data (my data resembled a 1D heightmap). Although the median-of-three way of picking a pivot is recommended by some sources (notably Sedgewick), perhaps a better method would be better suitable for Phobos:
>
> * Many sources recommend using a random element as a pivot. According to [2], "Randomized quicksort, for any input, it requires only O(n log n) expected time (averaged over all choices of pivots)". Also, if it is not possible to predict the pivot choice, it is impossible to craft worst-case input, which is a plus from a security point[3]. However, I'm not sure if making the behavior of std.algorithm's sort nondeterministic is desirable.
> * It looks like many STL implementations use Introsort[4] - a hybrid sorting algorithm which starts with QuickSort, but switches to HeapSort if the recursion limit exceeds a threshold.
> * I found a recent article[5] which describes an optimal algorithm of picking a pivot, however it is behind a paywall.
>
> [1]: Apparently the term is also used to refer to choosing three points *randomly*, instead of first/middle/last: http://stackoverflow.com/a/164183/21501
> [2]: http://en.wikipedia.org/wiki/Quicksort#Analysis_of_Randomized_quicksort
> [3]: https://www.google.com/search?q=quicksort+worst+case+denial+of+service
> [4]: http://en.wikipedia.org/wiki/Introsort
> [5]: https://news.ycombinator.com/item?id=6629117

Improving quicksort is probably a good idea, but IIRC, the stable sort has been changed to Timsort, which I find to be faster in most cases. Probably what should be done is change the default to stable sort and improve the unstable version to be faster in some way.

Presumably you could use a "randomized version," but with a constant key. That way the algorithm would be deterministic but likely to have good characteristics in normal inputs. Unfortunately that wouldn't solve the issue of an attacker getting to choose an input and causing worst case performance (it would just make it harder to come up with such an input). Ultimately, using the stable version (Timsort) is safer for security use (hence why I'd suggest it be the default).

On Friday, 15 November 2013 at 22:56:58 UTC, Craig Dillabaugh wrote:
> What are the arguments against using a randomized algorithm?

- Inconsistent execution time - someone trying to benchmark Phobos sort functions might get really confused;
- QuickSort is an unstable sort. If there is more to the data than the items being compared, the data will end up in a different order on different program runs.
- std.algorithm's sort allows specifying arbitrary code as a predicate. If that code has side effects, the program will behave differently on different runs.

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
> I've been investigating an instance that I ran into while processing some data, in which multiSort had apparently stalled whereas two successive sort calls processed the data quickly. After reducing the code and 20 million points, I've reduced the problem to this test case:

I've been hit by this case too, half a year ago.  See the relevant discussion on D.learn:
http://forum.dlang.org/thread/drpbkvhlprkdjzhbcqjn@forum.dlang.org

The fact that the issue is raised once again perhaps means it is worth a bugreport.  What do you guys think?

Ivan Kazmenko.

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:

> getPivot(0..10)
> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
> getPivot(2..10)
> 6,5,4,3,2,1,0,7 <- getPivot - before swap
> 7,5,4,3,6,1,0,2 <- getPivot - after swap
> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
> (...)

One possible implementation suggests to swap Left and Right immediatly after choosing the Pivot (if Left > Right), then place the Pivot at Right-1. It seems that this option was not taken. Any reason?

As the efficiency of Quicksort is known to be bad in sorting a small number of elements, ie. < 10, it might be nice to implement an option to automatically switch to a more appropriate algorithm if it's relevant to do so.

> * Many sources recommend using a random element as a pivot. According to [2], "Randomized quicksort, for any input, it requires only O(n log n) expected time (averaged over all choices of pivots)".

IMO it would be costly and not so relevant if the goal is to be fast.

> Also, if it is not possible to predict the pivot choice, it is impossible to craft worst-case input, which is a plus from a security point[3]. However, I'm not sure if making the behavior of std.algorithm's sort nondeterministic is desirable.

I think it's not desirable.

--

Quicksorting a collection of Objects?

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

On Saturday, 16 November 2013 at 14:20:32 UTC, Jean Christophe wrote:
> On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
>
>> getPivot(0..10)
>> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
>> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
>> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
>> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
>> getPivot(2..10)
>> 6,5,4,3,2,1,0,7 <- getPivot - before swap
>> 7,5,4,3,6,1,0,2 <- getPivot - after swap
>> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
>> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
>> (...)
>
> One possible implementation suggests to swap Left and Right immediatly after choosing the Pivot (if Left > Right), then place the Pivot at Right-1. It seems that this option was not taken. Any reason?

getPivot sorts the first, middle and last element in the range right after it figures out their order. Is there any advantage to your suggestion over this?

> As the efficiency of Quicksort is known to be bad in sorting a small number of elements, ie. < 10, it might be nice to implement an option to automatically switch to a more appropriate algorithm if it's relevant to do so.

It does, actually - it switches to optimisticInsertionSort for ranges of 25 elements or shorter. I disabled that behavior for illustration.

> IMO it would be costly and not so relevant if the goal is to be fast.

The impact shouldn't be big if a simple RNG, like LCG or XorShift, was used.

> Quicksorting a collection of Objects?

?

> 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?

You mean, sort!`a.foo < b.foo` ?

On 11/16/13 3:29 AM, Ivan Kazmenko wrote:
> On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
>> I've been investigating an instance that I ran into while processing
>> some data, in which multiSort had apparently stalled whereas two
>> successive sort calls processed the data quickly. After reducing the
>> code and 20 million points, I've reduced the problem to this test case:
>
> I've been hit by this case too, half a year ago.  See the relevant
> discussion on D.learn:
> http://forum.dlang.org/thread/drpbkvhlprkdjzhbcqjn@forum.dlang.org
>
> The fact that the issue is raised once again perhaps means it is worth a
> bugreport.  What do you guys think?
>
> Ivan Kazmenko.

I think a median of five pivot selection is in order.

Andrei

On 11/16/13 6:20 AM, Jean Christophe wrote:
> On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
>
>> getPivot(0..10)
>> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
>> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
>> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
>> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
>> getPivot(2..10)
>> 6,5,4,3,2,1,0,7 <- getPivot - before swap
>> 7,5,4,3,6,1,0,2 <- getPivot - after swap
>> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
>> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
>> (...)
>
> One possible implementation suggests to swap Left and Right immediatly
> after choosing the Pivot (if Left > Right), then place the Pivot at
> Right-1. It seems that this option was not taken. Any reason?

That may help this particular situation, but does it do anything interesting in general?

> As the efficiency of Quicksort is known to be bad in sorting a small
> number of elements, ie. < 10, it might be nice to implement an option to
> automatically switch to a more appropriate algorithm if it's relevant to
> do so.

That's done already.

>> * Many sources recommend using a random element as a pivot. According
>> to [2], "Randomized quicksort, for any input, it requires only O(n log
>> n) expected time (averaged over all choices of pivots)".
>
> IMO it would be costly and not so relevant if the goal is to be fast.
>
>> Also, if it is not possible to predict the pivot choice, it is
>> impossible to craft worst-case input, which is a plus from a security
>> point[3]. However, I'm not sure if making the behavior of
>> std.algorithm's sort nondeterministic is desirable.
>
> I think it's not desirable.

Vladimir also enumerated a few disadvantages of random pivot selection. I think those notwithstanding, random pivot is an option we should consider very seriously. It's easy to use a fast random number generators (randomness doesn't need to be very good).

The only reason for which I've hesitated to add random pivot selection is that it's less usual and might surprise some. It is _very_ solidly motivated.

> Quicksorting a collection of Objects?
>
> 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?

I had a diff at a point that added overloads to sort allowing the called to only specify the key. It turned out to be confusing, and all it saved was to save a tad of duplication "expr" instead of "expr(a) < expr(b)".


Andrei

On 11/16/13 3:29 AM, Ivan Kazmenko wrote:
> On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
>> I've been investigating an instance that I ran into while processing
>> some data, in which multiSort had apparently stalled whereas two
>> successive sort calls processed the data quickly. After reducing the
>> code and 20 million points, I've reduced the problem to this test case:
>
> I've been hit by this case too, half a year ago.  See the relevant
> discussion on D.learn:
> http://forum.dlang.org/thread/drpbkvhlprkdjzhbcqjn@forum.dlang.org
>
> The fact that the issue is raised once again perhaps means it is worth a
> bugreport.  What do you guys think?
>
> Ivan Kazmenko.

Yah, I thought one is in place already.

Andrei