OrderBy with custom comparer performs much slower than default comparer

Question

In the following example, can someone explain why the version using the custom comparer is so much slower than the other method?

I was expecting them to be similar as they're essentially doing the same thing?

Is it because the custom comparer version has to call two methods? the Compare and then the double.CompareTo? where as I guess the first version is only calling the double.CompareTo? but would that really account for such a big difference?

public class Program
{
    public class ColumnComparer : IComparer<Row>
    {
        public ColumnComparer(int column)
        {
            Column = column;
        }

        public int Column { get; }

        public int Compare(Row x, Row y) => x.Values[Column].CompareTo(y.Values[Column]);
    }

    public class Row
    {
        public int Index { get; }

        public List<double> Values { get; } = new();

        public Row(int index)
        {
            Index = index;
        }
    }

    public class Sort
    {
        private readonly List<Row> _rows;

        public Sort()
        {
            _rows = new List<Row>();
            var r = new Random(0);

            for (int i = 0; i < 500000; ++i)
            {
                var row = new Row(i);
                for (int j = 0; j < 32; ++j)
                {
                    row.Values.Add(r.Next(0, 1000));
                }

                _rows.Add(row);
            }
        }

        [Benchmark]
        public void Sort1()
        {
            _rows.OrderBy(x => x.Values[8]).ToArray();
        }

        [Benchmark]
        public void Sort2()
        {
            var comparer = new ColumnComparer(8);
            var sort2 = _rows.OrderBy(e => e, comparer).ToArray();
        }
    }

    static void Main(string[] args)
    {
        BenchmarkRunner.Run<Sort>();
    }
}

Edited to include performance measuring :

Method	Mean	Error	StdDev
Sort1	111.6 ms	1.46 ms	1.79 ms
Sort2	343.5 ms	4.01 ms	7.42 ms

Edit :

Added metrics including Sort3 (@dbc)

Method	Mean	Error	StdDev	Allocated
Sort1	112.0 ms	0.90 ms	0.85 ms	13.35 MB
Sort2	344.4 ms	2.27 ms	2.12 ms	13.35 MB
Sort3	138.7 ms	0.64 ms	0.57 ms	17.17 MB

Answer 1

It is not at all surprising that your custom sort is 3x slower than the default sort. When LINQ evaluates

_rows.OrderBy(x => x.Values[8]).ToArray();

The class EnumerableSorter<TElement, TKey> constructs an arrays of double []? _keys; (since TKey is double in this case) by calling the keySelector method once per item. It then sorts that array in-place using the default double comparison (by way of GenericComparer<double>.CompareTo()), which will get called roughly n log(n) times. Since nothing is boxed or unboxed, this should be quite fast.

Conversely, when you do:

_rows.OrderBy(e => e, comparer).ToArray()

EnumerableSorter<TElement, TKey> will construct a Row [] array, then call your custom sort method x.Values[Column].CompareTo(y.Values[Column]) n log(n) times. Since this method is much more complex than the default double comparison method and involves multiple pointer dereferences and list lookups, it's not surprising that it takes substantially longer.

This is an example of a general rule that, when sorting a large collection using a complex sort method is insufficiently performant, it can pay to precompute as much of the work done by the comparer as possible in the key selector. Which is exactly what you are doing with your x => x.Values[8] key selector.

If you need access to the precomputed key values after the sort finishes, you could project to a ValueTuple<TElement, TKey> before sorting, e.g.:

[Benchmark]
public void Sort3()
{
    var sort3 = _rows
        .Select(row => (row, value : row.Values[8])) // Precompute the value
        .OrderBy(p => p.value)                       // Compare the value
        .Select(p => p.row).ToArray();               // And extract the original row.
}

I don't have access to BenchmarkDotNet currently, but a demo fiddle here shows that Sort3() is only 15-25% slower than Sort1() when sorting a list of 45,000 rows:

Average time per repetition for 100 reps of Sort1: 12.2888 ms.
Average time per repetition for 100 reps of Sort2: 37.8331 ms (207.87% slower).
Average time per repetition for 100 reps of Sort3: 14.6479 ms (19.20% slower).