Hi!

Consider a sorted array.  Append an element that is less than all the previous elements.  Then sort the array again by the sort function from std.algorithm.

An example follows:

-----
import std.algorithm;
import std.datetime;
import std.range;
import std.stdio;

void main ()
{
	int n = 30_000;
	auto a = array (iota (n)) ~ [0];
	auto st = Clock.currTime ();
	sort (a);
	auto et = Clock.currTime ();
	writeln (et - st);
}
-----

With n = 30_000 as in the example, this takes time of the order of a second on a modern computer, which is clearly O(n^2).  I am using DMD 2.062.

Well, now I have a point to make and a question.

My point is that I think this is bad because such a pattern (sorted array ~ small element, then sort) is fairly likely to occur - well, it did for me, hence the post.  Sure, every fast and simple method for choosing the pivot in quicksort will have its O(n^2) corner cases.  But there's a difference between a corner case that never occurs in "real" data (but still could be constructed artificially) and a corner case describable by such a simple pattern.

The question is rather predictable, really: what is the guaranteed-n-log-n replacement for sort in the standard library?  I've found the following way...
	sort !("a < b", SwapStrategy.stable) (a);
...but it forces to specify the redundant "a < b" and looks a bit clumsy for an everyday sort() call.

Tried to keep it short(er) this time,

Ivan Kazmenko.

Ivan Kazmenko:

> Consider a sorted array.  Append an element that is less than all the previous elements.  Then sort the array again by the sort function from std.algorithm.

If you know that, then don't do a sort. Make some free space in
the array, shift the items, sort just the first part with a slice.


> The question is rather predictable, really: what is the guaranteed-n-log-n replacement for sort in the standard library?  I've found the following way...
> 	sort !("a < b", SwapStrategy.stable) (a);

That uses the TimSort that contains the optimization you look for.


> ...but it forces to specify the redundant "a < b" and looks a bit clumsy for an everyday sort() call.

Then try to define an alias (untested):

alias mySort = sort!("a < b", SwapStrategy.stable);

Bye,
bearophile

20-Apr-2013 01:03, Ivan Kazmenko пишет:
>
> With n = 30_000 as in the example, this takes time of the order of a
> second on a modern computer, which is clearly O(n^2).  I am using DMD
> 2.062.

Optimization flags if any?


-- 
Dmitry Olshansky

>> With n = 30_000 as in the example, this takes time of the order of a
>> second on a modern computer, which is clearly O(n^2).  I am using DMD
>> 2.062.
>
> Optimization flags if any?

Both "-O" and no-flags give quadratic behavior.

Well, if that does not convince you the time grows faster than n-log-n, maybe this comparison shall (dmd -O, Core i7-2600K @3400 MHz):

n       T, seconds
 15_000   0.312
 30_000   1.076
 60_000   3.775
120_000  11.247

With n growing x2, the time grows x3 to x4 at each step.

20-Apr-2013 02:12, Ivan Kazmenko пишет:
>>> With n = 30_000 as in the example, this takes time of the order of a
>>> second on a modern computer, which is clearly O(n^2).  I am using DMD
>>> 2.062.
>>
>> Optimization flags if any?
>
> Both "-O" and no-flags give quadratic behavior.
>

I sought after
-O -inline -release

In non-release mode it tests that it's sorted on exit etc.
Anyway it's 8x times as fast with -release -inline for me but the progression is similarly bad.

> Well, if that does not convince you the time grows faster than n-log-n,
> maybe this comparison shall (dmd -O, Core i7-2600K @3400 MHz):
>
> n       T, seconds
>   15_000   0.312
>   30_000   1.076
>   60_000   3.775
> 120_000  11.247
>
> With n growing x2, the time grows x3 to x4 at each step.



-- 
Dmitry Olshansky

> That [SwapStrategystable] uses the TimSort that contains
> the optimization you look for.
>
> alias mySort = sort!("a < b", SwapStrategy.stable);

Thank you, these are good for now.

A seemingly easy way to provide the choice globally would be to have an assignable SwapStrategy.default in std.algorithm... or would that be a bad design decision to have such a global state?

>> Consider a sorted array.  Append an element that is less than all the previous elements.  Then sort the array again by the sort function from std.algorithm.
>
> If you know that, then don't do a sort. Make some free space in
> the array, shift the items, sort just the first part with a slice.

That behavior isn't always easy to predict.

Still, I think this is a problem in Phobos which should be fixed.  In most implementations of quicksort (even middle-element, the easiest to come up with), one expects it to perform in O(n log n) with probability close to one, except on some artificially constructed cases.

On a side note, I'm surprised that median-of-three (getPivot in std.algorithm) fails at such a simple test, so I had something new to learn there, too.  If I just comment out the switch in getPivot and "return mid" directly, it becomes fast enough in this case.

Another view at this is the following.  As far as I know by now, one of the points beyond D (and Phobos) design is to have everything safe by default, but faster if you want it explicitly and you know what you are doing.  In this particular case, that would mean having a worst-case O(n log n) sort, and/or a stable sort, by default - but with the opportunity to switch to the (time-wise and stability-wise) unsafe quicksort if you really need the extra speedup and know what you are doing.  So, why isn't TimSort the default?

The one reason I can imagine is that then D would suffer in language comparisons which just take the most easy-to-use "default sort" and don't care about the extra features it got.  Are there any other?

Ivan Kazmenko.

Ivan Kazmenko:

> A seemingly easy way to provide the choice globally would be to have an assignable SwapStrategy.default in std.algorithm... or would that be a bad design decision to have such a global state?

With that I think there is no way to write a pure sort. Hopefully someday the sort() will be pure. Generally global mutable state is bad to write unittests, and to reason about code. So I don't think Andrei will do that. It's not kosher.


> Still, I think this is a problem in Phobos which should be fixed.
>  In most implementations of quicksort (even middle-element, the easiest to come up with), one expects it to perform in O(n log n) with probability close to one, except on some artificially constructed cases.
>
> On a side note, I'm surprised that median-of-three (getPivot in std.algorithm) fails at such a simple test, so I had something new to learn there, too.  If I just comment out the switch in getPivot and "return mid" directly, it becomes fast enough in this case.

Your case is a common one, so I think this problem should be studied a little better. I suggest to write a little better benchmark that shows the problem, and put it in Bugzilla. At worst it will be closed with wontfix.


> Another view at this is the following.  As far as I know by now, one of the points beyond D (and Phobos) design is to have everything safe by default, but faster if you want it explicitly and you know what you are doing.

Right, but I think that D Zen rule is mostly about things like memory safety, etc.


> So, why isn't TimSort the default?

Probably because someone thinks that "on average" the other sort is faster.

In theory the other should be faster, because if you relax the constraints of the sort being stable I think in theory you should be able to write a little faster sorting algorithm (I don't know if this is true).

Bye,
bearophile

On Friday, 19 April 2013 at 22:56:00 UTC, bearophile wrote:
>> So, why isn't TimSort the default?
>
> Probably because someone thinks that "on average" the other sort is faster.
>
> In theory the other should be faster, because if you relax the constraints of the sort being stable I think in theory you should be able to write a little faster sorting algorithm (I don't know if this is true).

I'm just throwing my 2c in, but I think TimSort ought to be the default. It's simply the safer option. Since worst-case performance can be designed (and it can be designed unless the pivots are, at least, pseudo-randomly chosen), there is a very real risk of the default sort being used in a way that can be compromised by an attacker. From this perspective, seems to be like TimSort being default would support the design goal #5 of D, "Make doing things the right way easier than the wrong way."

Plus, TimSort seems to be faster in most cases in my attempts. The only cases I could find that it wasn't faster is when I could guarantee that the data I was passing in had no order to it. In cases where you suspect (but can't guarantee) data is sorted when passed in (think fetching from a web API and it gives you sorted data, but the docs don't say it should), calling TimSort is nearly as fast as calling an "isSorted" ... So, my recommendation is to just call TimSort and don't worry about the extra branching code ([checking sortedness, if not sorted, call sort] vs [call sort]). This makes it so the "fast" code is also very convenient to write.

TBH, though, I think the reason that TimSort is not the default is because it was added only semi-recently. The old stable sort was not nearly as fast as the unstable sort (and, in fact, IIRC, it didn't work properly when I tried it). I doubt that someone intentionally said that quicksort was faster than TimSort on average ... it's just that no one thought to change the default when TimSort was added.

Maybe an enhancement request could be made on this?

20-Apr-2013 16:22, Chris Cain пишет:
> On Friday, 19 April 2013 at 22:56:00 UTC, bearophile wrote:
>>> So, why isn't TimSort the default?
>>
>> Probably because someone thinks that "on average" the other sort is
>> faster.
>>
>> In theory the other should be faster, because if you relax the
>> constraints of the sort being stable I think in theory you should be
>> able to write a little faster sorting algorithm (I don't know if this
>> is true).
>
> I'm just throwing my 2c in, but I think TimSort ought to be the default.
> It's simply the safer option. Since worst-case performance can be
> designed (and it can be designed unless the pivots are, at least,
> pseudo-randomly chosen), there is a very real risk of the default sort
> being used in a way that can be compromised by an attacker. From this
> perspective, seems to be like TimSort being default would support the
> design goal #5 of D, "Make doing things the right way easier than the
> wrong way."

And this all is good but TimSort allocates O(N) memory. The constant in front of N is smallish less then 1.0 but it could cause some grief.


-- 
Dmitry Olshansky

On 4/19/13 6:37 PM, Ivan Kazmenko wrote:
>> That [SwapStrategystable] uses the TimSort that contains
>> the optimization you look for.
>>
>> alias mySort = sort!("a < b", SwapStrategy.stable);
>
> Thank you, these are good for now.
>
> A seemingly easy way to provide the choice globally would be to have an
> assignable SwapStrategy.default in std.algorithm... or would that be a
> bad design decision to have such a global state?

Yah, that would mean one can't reason what a piece of code does without knowing what the context was.

>>> Consider a sorted array. Append an element that is less than all the
>>> previous elements. Then sort the array again by the sort function
>>> from std.algorithm.
>>
>> If you know that, then don't do a sort. Make some free space in
>> the array, shift the items, sort just the first part with a slice.
>
> That behavior isn't always easy to predict.
>
> Still, I think this is a problem in Phobos which should be fixed. In
> most implementations of quicksort (even middle-element, the easiest to
> come up with), one expects it to perform in O(n log n) with probability
> close to one, except on some artificially constructed cases.
>
> On a side note, I'm surprised that median-of-three (getPivot in
> std.algorithm) fails at such a simple test, so I had something new to
> learn there, too. If I just comment out the switch in getPivot and
> "return mid" directly, it becomes fast enough in this case.

I could have sworn I made getPivot choose at random at some point. I agree this should be fixed; there are a number of possibilities:

a) choose median of five

b) if the array is large, sort a stride of it first (e.g. 1%) then choose the pivot as the median point of that stride

c) add introspection to the algorithm, i.e. if an attempt to partition hits the worst case or near worst case, just try another pivot instead of moving forward with the sorting stage.

> Another view at this is the following. As far as I know by now, one of
> the points beyond D (and Phobos) design is to have everything safe by
> default, but faster if you want it explicitly and you know what you are
> doing.

That view of safety is different (memory safety).

> In this particular case, that would mean having a worst-case O(n
> log n) sort, and/or a stable sort, by default - but with the opportunity
> to switch to the (time-wise and stability-wise) unsafe quicksort if you
> really need the extra speedup and know what you are doing. So, why isn't
> TimSort the default?

TimSort is slower on average.


Andrei