Runtime: LINQ OrderBy performance drops by bazillion times in some cases

[maxzav]

Input data:

List<int> list = new List<int>();

Prepare data:

random:
var rnd = new Random(); for (var i = 0; i < n; i++) list.Add(rnd.Next());
desc:
for (var i = 0; i < n; i++) list.Add(n - i);
asc:
for (var i = 0; i < n; i++) list.Add(n - i);
desc+asc:
for (var i = 0; i < n / 2; i++) list.Add(n - i); for (var i = n / 2; i < n; i++) list.Add(i);
asc+desc:
for (var i = 0; i < n / 2; i++) list.Add(i); for (var i = n / 2; i < n; i++) list.Add(n - i);

Sorting functions:

List:
List<int> SortByList() { var result = list.ToList(); result.Sort(); return result; };
LINQ:
List<int> SortByLINQ() => list.OrderBy(x => x).ToList();
LINQOptimizer (https://github.com/nessos/LinqOptimizer):
List<int> SortByLINQOptimizer() => list.AsQueryExpr().OrderBy(x => x).Run().ToList();

Results:

10,000 items

                LINQOptimizer           LINQ            List
random          00:00:00.0016349    00:00:00.0031569    00:00:00.0007014
asc             00:00:00.0012643    00:00:00.0014618    00:00:00.0001882
desc            00:00:00.0013321    00:00:00.0014991    00:00:00.0002963
desc+asc        00:00:00.0018149    00:00:00.0118873    00:00:00.0007774
asc+desc        00:00:00.0020868    00:00:00.2250114    00:00:00.0008123

100,000 items

                LINQOptimizer           LINQ            List
random          00:00:00.0149506    00:00:00.0341792    00:00:00.0087713
asc             00:00:00.0084689    00:00:00.0184448    00:00:00.0019559
desc            00:00:00.0130457    00:00:00.0190296    00:00:00.0037221
desc+asc        00:00:00.0177337    00:00:00.4118966    00:00:00.0115277
asc+desc        00:00:00.0178328    00:00:19.7172326    00:00:00.0109617

1,000,000 items

                LINQOptimizer           LINQ            List
random          00:00:00.1587396    00:00:00.1570763    00:00:00.1013578
asc             00:00:00.0809392    00:00:00.0828751    00:00:00.0228805
desc            00:00:00.1027216    00:00:00.1947723    00:00:00.0423382
desc+asc        00:00:00.1941634    00:02:09.9069785    00:00:00.1331413
asc+desc        00:00:00.1919311    ----------------    00:00:00.1365317

Waiting about 30 MINUTES on 1,000,000 items test with asc+desc data but LINQ is still sorting... (1 core 100% used)

P.S.: Tests for LINQ and List - .Net Core 2.0, LINQOptimizer - .Net Framework 4.7. Windows 7 x64

[danmosemsft]

At a guess, because OrderedEnumerable always picks the midpoint for the quicksort partition. List uses the median of three which has less pathological behavior on nearly sorted input.

"LinqOptimizer" seems to do parallellized merge sort.

[SunnyWar]

These two look the same to me, perhaps you made cut-n-paste error.

desc:
for (var i = 0; i < n; i++) list.Add(n - i);
asc:
for (var i = 0; i < n; i++) list.Add(n - i);

This is just going to put a random number at the end of the list so I doubt it shows anything of value. At best it could be used to evaluate the sorting routines but not for measuring Add.

var rnd = new Random(); for (var i = 0; i < n; i++) list.Add(rnd.Next());

[SunnyWar]

@maxzav One more thing. Did you roll your own benchmarking system or did you use https://github.com/dotnet/BenchmarkDotNet? Which, I recommend BTW. Rolling your own can quite difficult and error prone.

[maxzav]

At a guess, because OrderedEnumerable always picks the midpoint for the quicksort partition. List uses the median of three which has less pathological behavior on nearly sorted input.

Anyway, sorting of 1,000,000 int values more than 30 minutes... and how about 100,000,000 values? If this is a bug - it must be fixed, if this is "feature" of sorting algorithm of OrderBy - it must be changed. I think .Net Core is not a place for algorithms with performance blackholes.

These two look the same to me, perhaps you made cut-n-paste error.

copy/paste :) asc: list.Add(i)

Did you roll your own benchmarking system or did you use https://github.com/dotnet/BenchmarkDotNet?

Using Stopwatch, run test 10 times, skip 2 times with longest duration (warmup).

Full code for ask+desc data:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace LinqConsoleApp
{
    class Program
    {
        static List<int> SortByLinq(List<int> list) => list.OrderBy(x => x).ToList();

        static void Main(string[] args)
        {
            var n = 100_000;
            var list = new List<int>();

            for (var i = 0; i < n / 2; i++)
                list.Add(i);
            for (var i = n / 2; i < n; i++)
                list.Add(n - i);

            var sw = new Stopwatch();
            var cnt = 10;
            TimeSpan[] ts = new TimeSpan[cnt];
            for (var i = 0; i < cnt; i++)
            {
                sw.Restart();
                var result = SortByLinq(list);
                sw.Stop();
                Console.WriteLine($"{sw.Elapsed}");
                ts[i] = sw.Elapsed;
            }
            var avg = TimeSpan.FromTicks((long)ts.OrderByDescending(x => x).Skip(2).Average(x => x.Ticks));
            Console.WriteLine($"Avg: {avg}");
        }
    }
}

Project: .Net Core 2.0, x64. On my laptop with Core2Duo T9800 2.93GHz, Windows 7 x64 - I get average time of 22.2 seconds for sorting 100,000 int values :) while LINQOptimizer takes 17.8 milliseconds (1247x times faster)

[danmosemsft]

I think .Net Core is not a place for algorithms with performance blackholes.

I agree it should be improved.

@JonHanna in case he is interested

[maxzav]

Forgot to add some important information:
This performance blackhole exists only in sequential LINQ .AsEnumerable()
Parallel LINQ works fine 16.1 milliseconds for 100,000 items
list.AsParallel().OrderBy(x => x).ToList();

[maxzav]

Did more tests, and I was wrong about Parallel LINQ.

With this initial data, I get performance drops by 251 times (on CPU with 2 cores)

for (var i = 0; i < n / 4; i++)
    list.Add(i);
for (var i = n / 4; i < n / 4 * 2; i++)
    list.Add(i - n / 4);
for (var i = n / 2; i < n / 2 + n / 4; i++)
    list.Add(i);
for (var i = n / 2 + n / 4; i < n; i++)
     list.Add(i - n / 4);

list.AsParallel().OrderBy(x => x).ToList();
sorting 100,000 items in 4041 milliseconds.

So, there is a serious bug in sorting alghoritm.

[JonHanna]

List uses the median of three which has less pathological behavior on nearly sorted input.

Though one can still produce sequences that'll hit its O(n²) worse case. (And they both do pretty well with nearly-sorted input, but have different varieties of merges of nearly sorted input such as the ascending/descending mix shown here with median-of-three's being more obscure). I put median-of-three into OrderBy in a PR some time ago and then took it out again partly because there was enough changes happening to OrderBy in that PR as it was without complicating matters further, but mostly because I wanted to consider whether random pivot selection would be better.

With non malicious cases random has been shown to pick a better pivot more often, though it has further pros and cons in that its less good if you have a nearly-sorted (but not mixed sorts) input which often comes up in real data, and there is more internal algorithmic complexity (though nicely encapsulated away) picking a pseudo-random number than a media of three, which adds some cost, but on the other hand finding the three potential pivots to find the median of has poor locality which adds some cost that way.

With malicious cases where someone is able to pick the data we are sorting only random selection protects us; median of three makes it harder to deliberately push us into the pathological case than a middle-item pivot, but not a lot harder, and then they can DoS the system. The question then is how plausible such an attack is; if it's plausible then random pivot selection is the only way to go (and should probably be used in other cases where we do quicksorts, too).

On the other hand, if pathological cases aren't going to come up in practice, we're arguably better staying as is.

I'll experiment with random pivot selection some time soon, but likely not for the next couple of days, so if anyone else feels like giving it a go, jump in.

[JonHanna]

List uses the median of three which has less pathological behavior on nearly sorted input.

More important here is that List is an introsort, so if it does hit the pathological case it will switch from quicksort to heapsort, which tends to be slower with a lot of inputs, but has a much better worse-case performance. This isn't an option on Enumerable.OrderBy since that's documented as providing a stable sort, which heapsort can't do (analogous OrderBy such as in PLINQ do not have that restriction).

[stephentoub]

This isn't an option on Enumerable.OrderBy since that's documented as providing a stable sort, which heapsort can't do (analogous OrderBy such as in PLINQ do not have that restriction).

The stability of the algorithm shouldn't matter, as the implementation is factoring the index into the comparison when the keys are considered equal, right?

[Petermarcu]

@stephentoub should we fix this in 2.0.X?

[stephentoub]

should we fix this in 2.0.X?

I suggest for now we not. This isn't a regression and so has existed for quite some time. Switching to Array's sort has lots of upside, but any time you change a sorting algorithm like this, you will find some degenerate cases where it's worse even though on many inputs it'll be better, e.g. if you get unlucky with the pivots chosen.