在 C# 中，我们可以在 OrderBy().OrderBy() 或 OrderBy().ThenBy() 的帮助下对集合进行排序。

但是这些调用之间有什么区别？要回答这个问题，我们需要深入研究源代码。

文章分为三章：

1. 背景：对于那些喜欢在阅读文章之前先热身的人。在这里，你将了解为什么我决定进行一些研究并找出OrderBy().OrderBy()和OrderBy().ThenBy()之间的区别。
2. 性能比较：在这里，我们将比较这些排序方法的性能和内存消耗。
3. 行为差异：在这里，我们将深入研究 .NET 的源代码，以找出这些排序方法效率不同的原因。

背景

这一切都始于以下文章：“ Unity、ASP.NET Core 等中的可疑排序”。本文描述了OrderBy().OrderBy()调用的顺序可能导致错误的情况。然而，事实证明，有时开发人员故意使用OrderBy().OrderBy()，而不是OrderBy().ThenBy()。

看一个例子。假设我们有一个Wrapper类和一个以下类型的实例数组：

class Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

var arr = new Wrapper[]
{
  new() { Primary = 1, Secondary = 2 },
  new() { Primary = 0, Secondary = 1 },
  new() { Primary = 2, Secondary = 1 },
  new() { Primary = 2, Secondary = 0 },
  new() { Primary = 0, Secondary = 2 },
  new() { Primary = 0, Secondary = 3 },
};

我们要对这个数组进行排序：首先按Primary值，然后按Secondary。

如果我们按如下方式进行排序——我们就犯了一个错误：

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);
....

结果如下：

Primary: 2 Secondary: 0
Primary: 0 Secondary: 1
Primary: 2 Secondary: 1
Primary: 0 Secondary: 2
Primary: 1 Secondary: 2
Primary: 0 Secondary: 3

我们得到错误的结果。为了正确排序集合，我们需要使用OrderBy().ThenBy()：

var sorted = arr.OrderBy(p => p.Primary)
                .ThenBy(p => p.Secondary);
....

结果如下：

Primary: 0 Secondary: 1
Primary: 0 Secondary: 2
Primary: 0 Secondary: 3
Primary: 1 Secondary: 2
Primary: 2 Secondary: 0
Primary: 2 Secondary: 1

但是，我们也可以使用OrderBy().OrderBy()来获得正确的结果。我们只需要swap the calls。

我们不应该这样做：

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);

而是应该这样：

var sorted = arr.OrderBy(p => p.Secondary)
                .OrderBy(p => p.Primary);

事实证明，要得到正确的结果；我们可以使用这两个选项：

// #1
var sorted1 = arr.OrderBy(p => p.Secondary)
                 .OrderBy(p => p.Primary);

// #2
var sorted2 = arr.OrderBy(p => p.Primary)
                 .ThenBy(p => p.Secondary);

明显，第二个选项更具可读性。

当你看到OrderBy().OrderBy()时，你会想：难道就一定没有错误吗？

所以，最好使用OrderBy().ThenBy()：代码更容易阅读，开发者的意图也很明确。

然而，这些排序方法不仅在外观上有所不同：它们的性能和内存消耗也有所不同。

性能比较

让我们尝试以下代码：

struct Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

Wrapper[] arr = ....;

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

所以，让我们总结一下要点：

• Wrapper是一个具有两个整数属性的结构。我们将使用它们作为排序的键；
• arr是我们需要排序的Wrapper实例数组。它的创建方式对于测试并不重要。我们将测量排序和获得最终数组的性能；
• 有两种排序方式：第一种是OrderBy().OrderBy()，第二种是OrderBy().ThenBy()；
• ToArray()调用用于启动排序。

为了运行测试，我使用了两组生成的测试数据（Wrapper类型的实例）。在第一组中，Primary和Secondary值的分布更大，在第二组中，它更小。我在arr中编写了Wrapper对象（从 10 到 1,000,000）并对其进行了排序。

测试项目在 .NET 6 上运行。

表现

我使用BenchmarkDotNet来跟踪性能。

您可以在下面看到执行排序和获取数组需要多少时间。我们对绝对值不感兴趣——排序方法之间的差异更重要。

数据集#1：

数据集#2：

如果我们一次执行多个排序，让我们继续看看时间差。为此，我们使用for循环：

for (int i = 0; i < iterNum; ++i)
{
  // Perform sorting
}

以下是对 1,000,000 个Wrapper类型实例进行排序所花费的时间（以秒为单位）：

好吧，20秒的差异值得考虑。

内存消耗

内存也有类似的情况——OrderBy().OrderBy()消耗更多。在大量数据和多次迭代中尤其明显。

以下是每次迭代创建的对象数量的差异：

如表所示，OrderBy().OrderBy()调用创建了另外两个数组。当我运行有 100 次排序的测试时，我得到了 1GB 的分配内存差异。

重要的是要注意排序后的集合越大，“额外”数组就越大。结果，消耗的内存量也增加了。

行为差异

现在，是时候“深入了解”了。提醒你——我们正在考虑两种排序方式：

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

要了解差异，我们需要分析：

• 被调用的方法；
• 调用方法的对象的状态；
• 执行流程。

.NET 6 的源代码可在GitHub 上获得。

顶级方法

我们需要讨论三个顶级方法：OrderBy、ThenBy和ToArray。让我们考虑它们中的每一个。

排序依据

OrderBy是一个扩展方法，它返回OrderedEnumerable<TElement, TKey>类型的实例：

public static IOrderedEnumerable<TSource> 
OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
                       Func<TSource, TKey> keySelector)
  => new OrderedEnumerable<TSource, 
                           TKey>(source, keySelector, null, false, null);

这是 OrderedEnumerable<TElement, TKey>构造函数：

internal OrderedEnumerable( IEnumerable<TElement> source, 
                            Func<TElement, TKey> keySelector, 
                            IComparer<TKey>? comparer, 
                            bool descending, 
                            OrderedEnumerable<TElement>? parent
                           ) : base(source)
{
  ....
  _parent = parent;
  _keySelector = keySelector;
  _comparer = comparer ?? Comparer<TKey>.Default;
  _descending = descending;

在这里，我们对基本构造函数调用感兴趣 - base(source)。基本类型是OrderedEnumerable<TElement>。构造函数如下所示：

protected OrderedEnumerable(IEnumerable<TElement> source) 
  => _source = source;

让我们回顾一下我们已经讨论过的内容：作为OrderBy调用的结果，创建了OrderedEnumerable<TElement, TKey>实例。以下字段确定其状态：

• _source;
• _parent;
• _keySelector;
• _comparer;
• _descending.

然后通过

ThenBy是一个扩展方法：

public static IOrderedEnumerable<TSource> 
ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, 
                      Func<TSource, TKey> keySelector)
{
  ....
  return source.CreateOrderedEnumerable(keySelector, null, false);
}

在我们的例子中，源变量的类型是OrderedEnumerable<TElement, TKey>。让我们看一下将被调用的CreateOrderedEnumerable方法的实现：

IOrderedEnumerable<TElement> 
IOrderedEnumerable<TElement>
 .CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, 
                                IComparer<TKey>? comparer, 
                                bool descending) 
  => new OrderedEnumerable<TElement, 
                           TKey>(_source, 
                                 keySelector, 
                                 comparer, 
                                 @descending, 
                                 this);

我们看到调用了OrderedEnumerable<TElement, TKey>类型的构造函数（我们已经在OrderBy部分讨论过）。调用的参数不同，因此创建的对象的状态也不同。

让我们复习一下：在我们的例子中， ThenBy（如OrderBy）返回OrderedEnumerable<TElement, TKey>类型的实例。

数组

ToArray是一个扩展方法：

public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source)
{
  ....
  return source is IIListProvider<TSource> arrayProvider
    ? arrayProvider.ToArray()
    : EnumerableHelpers.ToArray(source);
}

在这两种情况下，源都是OrderedEnumerable<TElement, TKey>类型的实例。此类型实现IIlistProvider<TSource>接口。因此，执行将通过arrayProvider.ToArray()调用进行。实际上，会调用OrderedEnumerable<TElement>.ToArray方法：

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

在这里，主要的区别就出现了。在我们继续深入研究之前，我们需要检查我们将使用的对象的状态。

OrderedEnumerable 对象的状态

让我们回到源示例：

// #1
_ = arr.OrderBy(p => p.Secondary) // Wrapper[] -> #1.1
       .OrderBy(p => p.Primary)   // #1.1 -> #1.2
       .ToArray();                // #1.2 -> Wrapper[]

// #2
_ = arr.OrderBy(p => p.Primary)  // Wrapper[] -> #2.1
       .ThenBy(p => p.Secondary) // #2.1 -> #2.2
       .ToArray();               // #2.2 -> Wrapper[]

我们需要比较四个成对排列的对象：

• #1.1 和 #2.1 是两个示例中的第一个OrderBy调用创建的对象；
• #1.2 和#2.2 是由第一个示例中的第二个OrderBy调用和第二个示例中的ThenBy调用创建的对象。

结果，我们得到了 2 个用于比较对象状态的表。

以下是第一个OrderBy调用创建的对象的状态：

这对是相同的。只有选择器不同。

以下是第二次调用OrderBy (#1.2) 和ThenBy (#2.2) 创建的对象的状态：

这里的选择器也不同——这是意料之中的。好奇_source和_parent字段不同。在ThenBy (#2.2) 调用的情况下对象的状态似乎更正确：对源集合的引用被保存，并且有一个“父”——前一次排序的结果。

执行流程

现在我们需要找出对象的状态如何影响执行流程。

让我们回到ToArray方法：

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

请记住，不同调用接收到的对象具有不同的_source字段：

• OrderBy().OrderBy()指的是 OrderedEnumerable<TElement, TKey>实例；
• OrderBy().ThenBy()指的是Wrapper[]实例。

让我们考虑确定Buffer<TElement>类型：

internal readonly struct Buffer<TElement>
{
  internal readonly TElement[] _items;
  internal readonly int _count;

  internal Buffer(IEnumerable<TElement> source)
  {
    if (source is IIListProvider<TElement> iterator)
    {
      TElement[] array = iterator.ToArray();
      _items = array;
      _count = array.Length;
    }
    else
    {
      _items = EnumerableHelpers.ToArray(source, out _count);
    }
  }
}

这是行为开始不同的地方：

• 对于OrderBy().OrderBy()调用，执行遵循 then 分支，因为OrderedEnumerable实现了IIListProvider<TElement>接口；
• 对于OrderBy().ThenBy()调用执行跟随 else 分支，因为数组（在我们的例子 中是 Wrapper[]）没有实现这个接口。

在第一种情况下，我们回到上面给出的ToArray方法。然后，我们再次进入Buffer构造函数，但执行将跟随 else 分支，因为对象 #1.1 的_source是Wrapper[]。

EnumerableHelpers.ToArray只是创建数组的副本：

internal static T[] ToArray<T>(IEnumerable<T> source, out int length)
{
  if (source is ICollection<T> ic)
  {
    int count = ic.Count;
    if (count != 0)
    {        
      T[] arr = new T[count];
      ic.CopyTo(arr, 0);
      length = count;
      return arr;
    }
  }
  else
    ....

  ....
}

执行遵循 then 分支。我省略了其余的代码，因为在我们的例子中，它并不重要。

调用堆栈中的差异更加明显。注意粗体的“额外”调用：

 

顺便说一句，这也解释了创建对象数量的差异。这是我们之前讨论过的表格：

这里最有趣的数组是：Int32[]和Wrapper[]。它们的出现是因为执行流程不必要地再次通过OrderedEnumerable<TElement>.ToArray方法：

public TElement[] ToArray()
{
  ....
  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  ....
}

提醒你——数组和映射数组的大小取决于排序集合的大小：它越大，开销就越大——因为不必要的OrderedEnumerable<TElement>.ToArray调用。

表演也是如此。我们再看一下OrderedEnumerable<TElement>.ToArray方法的代码：

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

我们对地图数组感兴趣。它描述了数组中元素位置之间的关系：

• index 是结果数组中元素的位置；
• 索引值是源数组中的位置。

假设map[5] == 62。这意味着该元素在源数组中排在第 62 位，在结果数组中排在第 5 位。

为了获得所谓的“关系图”，使用了SortedMap方法：

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

这是GetEnumerableSorter方法：

private EnumerableSorter<TElement> GetEnumerableSorter() 
  => GetEnumerableSorter(null);

让我们看一下方法重载：

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}

这是我们正在讨论的排序方法之间的另一个区别：

• OrderBy().OrderBy() :对象 #1.2 的_parent为null。结果，创建了一个EnumerableSorter实例。
• OrderBy().ThenBy() :对象#2.2 的_parent指向对象#2.1。这意味着将创建两个相互关联的EnumerableSorter实例。发生这种情况是因为再次调用了_parent.GetEnumerableSorter(sorter)方法。

这是调用的EnumerableSorter构造函数：

internal EnumerableSorter(
  Func<TElement, TKey> keySelector, 
  IComparer<TKey> comparer, 
  bool descending, 
  EnumerableSorter<TElement>? next)
{
  _keySelector = keySelector;
  _comparer = comparer;
  _descending = descending;
  _next = next;
}

构造函数只是初始化对象字段。构造函数中没有使用另一个字段 - _keys。稍后将在ComputeKeys方法中对其进行初始化。

让我们考虑一下这些字段负责什么。为此，让我们讨论一种排序方式：

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

要通过OrderBy执行排序，将创建一个EnumerableSorter实例。它具有以下字段：

• _keySelector：负责将源对象映射到键的委托。在我们的例子中，它是Wrapper -> int。代表：p => p.Primary；
• _comparer：用于比较键的比较器。Comparer<T>.Default如果没有明确指定；
• _descenging : 表示集合按降序排序的标志；
• _next ：对负责以下排序标准的EnumerableSorter对象的引用。在上面的示例中，有一个对象的引用，该对象是为根据ThenBy的标准排序而创建的。

创建并初始化EnumerableSorter实例后，将为其调用Sort方法：

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

这是Sort方法的主体：

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

这是ComputeMap方法：

private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}

我们来看看ComputeKeys方法：

internal override void ComputeKeys(TElement[] elements, int count)
{
  _keys = new TKey[count];
  for (int i = 0; i < count; i++)
  {
    _keys[i] = _keySelector(elements[i]);
  }

  _next?.ComputeKeys(elements, count);
}

在这个方法中，初始化了EnumerableSorter实例的_keys数组。_next ?.ComputeKeys(elements, count)调用允许初始化相关EnumerableSorter对象的整个链。

为什么我们需要_keys字段？该数组存储在源数组的每个元素上调用选择器的结果。因此，我们得到一个键数组，用于执行排序。

这是一个例子：

var arr = new Wrapper[]
{
  new() { Primary = 3, Secondary = 2 },
  new() { Primary = 3, Secondary = 1 },
  new() { Primary = 1, Secondary = 0 }
};

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

在此示例中，将创建两个相关的EnumerableSorter实例。

因此，_keys存储源数组的每个元素的排序键。

让我们回到ComputeMap方法：

private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}

调用ComputeKeys方法后，会创建并初始化映射数组。这是描述源和结果数组中的位置之间关系的数组。在这个方法中，它仍然描述了 i -> i 的关系。这意味着源数组中的位置与结果数组中的位置一致。

让我们回到Sort方法：

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

我们对QuickSort方法感兴趣，它使地图数组看起来像我们需要的那样。在这个操作之后，我们得到了源数组和结果数组中元素位置之间的正确关系。

下面是QuickSort方法的主体：

protected override void QuickSort(int[] keys, int lo, int hi) 
  => new Span<int>(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);

我们不会深入研究Span及其Sort方法的细节。让我们关注考虑比较委托对数组进行排序的事实：

public delegate int Comparison<in T>(T x, T y);

这是一个用于比较的经典代表。它需要两个元素，比较它们，然后返回值：

• < 0 如果x小于y；
• 0 如果x等于y；
• > 0 如果x大于y。

在我们的例子中，CompareAnyKeys方法用于比较：

internal override int CompareAnyKeys(int index1, int index2)
{
  Debug.Assert(_keys != null);

  int c = _comparer.Compare(_keys[index1], _keys[index2]);
  if (c == 0)
  {
    if (_next == null)
    {
      return index1 - index2; // ensure stability of sort
    }

    return _next.CompareAnyKeys(index1, index2);
  }

  // ....
  return (_descending != (c > 0)) ? 1 : -1;
}

所以，让我们看看我们有什么：

int c = _comparer.Compare(_keys[index1], _keys[index2]);
if (c == 0)
  ....

return (_descending != (c > 0)) ? 1 : -1;

通过用_comparer编写的比较器比较两个元素。由于我们没有明确设置任何比较器，因此使用了Comparer<T>.Default（在我们的例子中 – Comparer<Int32>.Default）。

如果元素不相等，则不执行c == 0条件，执行流程转到return。_descending字段存储有关元素如何排序的信息——以降序或升序。如有必要，该字段用于更正方法返回的值。

但是如果元素相等呢？

if (c == 0)
{
  if (_next == null)
  {
    return index1 - index2; // ensure stability of sort
  }

  return _next.CompareAnyKeys(index1, index2);
}

这是相互关联的EnumerableSorter实例链。如果比较的键相等，则执行检查以查看是否有任何其他排序标准。如果有（_next != null），则通过它们执行比较。

事实证明，在一次调用Sort方法时考虑了所有排序标准。

如果我们使用OrderBy().OrderBy()会发生什么？为了找出答案，让我们回到创建EnumerableSorter实例：

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}

作为第二次OrderBy调用的结果获得的对象的_parent值为null。这意味着创建了一个EnumerableSorter实例。它与某事无关，_next的值为null。

事实证明，我们需要执行上述所有操作两次。我们已经讨论过这如何影响性能。为了提醒您，我将复制上面给出的表格之一。

以下是对 1,000,000 个Wrapper类型实例进行排序所花费的时间（以秒为单位）：

简而言之，差异

OrderBy和ThenBy方法创建用于执行排序的OrderedEnumerable实例。EnumerableSorter类型的实例有助于执行排序。它们影响算法，使用指定的选择器和比较器。

OrderBy().OrderBy()和OrderBy().ThenBy()调用之间的主要区别在于对象之间的关系。

OrderBy().OrderBy()。OrderedEnumerable或EnumerableSorter之间没有关系。结果，创建了“额外”对象——而不是一个排序，我们得到两个。内存消耗越来越大，代码运行速度变慢。

OrderBy().ThenBy()。OrderedEnumerable和EnumerableSorter实例都是相关的。正因为如此，一次排序操作由多个标准同时执行。不会创建额外的对象。内存消耗减少，代码运行速度更快。

结论

使用OrderBy().ThenBy()而不是OrderBy().OrderBy()的代码：

• 更好地阅读；
• 不易出错；
• 工作更快；
• 消耗更少的内存。

原文作者：Sergey Vasiliev