带有自定义比较器的 OrderBy 的执行速度比默认比较器慢得多

Question

在下面的示例中，有人可以解释为什么使用自定义比较器的版本比其他方法慢得多吗？

我期望他们是相似的，因为他们本质上做同样的事情？

是因为自定义比较器版本要调用两个方法吗？ Compare 然后是 double.CompareTo？我猜第一个版本只调用了 double.CompareTo？但这真的能解释这么大的差异吗？

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>();
    }
}

编辑以包括绩效衡量：

方法	意思是	错误	标准偏差
排序1	111.6 毫秒	1.46 毫秒	1.79 毫秒
排序2	343.5 毫秒	4.01 毫秒	7.42 毫秒

Answer 1

自定义排序比默认排序慢 3 倍，这并不奇怪。当 LINQ 求值时

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

类

EnumerableSorter<TElement, TKey>

通过调用

double []? _keys;

方法

一次

来构造

TKey

数组（因为在本例中

double

是keySelector）。然后，它使用 default

double

比较 （通过

GenericComparer<double>.CompareTo)()

）对该数组进行就地排序，这将被大约调用

n log(n)

次。由于没有装箱或拆箱的东西，所以这应该相当快。

相反，当你这样做时：

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

EnumerableSorter<TElement, TKey>

将构造一个

Row []

数组，然后调用自定义排序方法

x.Values[Column].CompareTo(y.Values[Column])

n log(n)

次。由于此方法比默认的双重比较方法复杂得多，并且涉及多个指针取消引用和列表查找，因此它需要更长的时间也就不足为奇了。

您可以通过在排序之前将每个

Row

投影到

ValueTuple<Row, double>

来优化代码，然后比较该值，这应该消除

n log(n)

排序期间的大部分取消引用和所有列表索引：

[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.
}

我目前无法访问

BenchmarkDotNet

，但是 here 的演示小提琴显示，在对 40,000 行列表进行排序时，

Sort3()

仅比

Sort1()

慢 15-25%：

Average time per repetition for 100 reps of Sort1: 13.2105 ms.
Average time per repetition for 100 reps of Sort2: 32.1409 ms (143.30% slower).
Average time per repetition for 100 reps of Sort3: 15.5325 ms (17.58% slower).