为什么List <T> .Sort使用Comparer <int> .Default的速度是等效自定义比较器的两倍多？

Question

结果

使用1000万随机ints 的列表(每次相同的种子,平均10次重复):

listCopy.Sort(Comparer<int>.Default)需要314ms.

运用

sealed class IntComparer : IComparer<int>
{
  public int Compare(int x, int y)
  {
    return x < y ? -1 : (x == y ? 0 : 1);
  }
}

listCopy.Sort(new IntComparer())需要716毫秒.

一些变化:

• 使用struct IntComparer而不是sealed class:771ms
• 使用public int Compare(int x, int y) { return x.CompareTo(y); }:809ms

评论

Comparer<int>.Default返回一个GenericComparer<int>.根据dotPeek,我们有:

internal class GenericComparer<T> : Comparer<T> where T : IComparable<T>
{
  public override int Compare(T x, T y)
  {
    if ((object) x != null)
    {
      if ((object) y != null)
        return x.CompareTo(y);
      else
        return 1;
    }
    else
      return (object) y != null ? -1 : 0;
  }

...
}

显然,这不应该比我IntComparer使用的变种更快CompareTo.

我没有找到任何相关内容ArraySortHelper<T>,这似乎是其核心内容List<T>.Sort.

我只能猜测JIT在这里做了一些神奇的特殊套管(替换那些Comparer<int>.Default由不进行任何IComparer<T>.Compare调用或类似事件的专门排序实现使用的排序)？

编辑:上面的时间太低了5.9214729782462845(Stopwatch并且TimeSpan"Tick"的定义不同).但是,不影响这一点.

Answer 1

原因很容易在Reference Source,system/array.cs源代码文件中看到:

   [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
   public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) {
       // Argument checking code omitted
       //...

       if (length > 1) {
           // <STRIP>
           // TrySZSort is still faster than the generic implementation.
           // The reason is Int32.CompareTo is still expensive than just using "<" or ">".
           // </STRIP>
           if ( comparer == null || comparer == Comparer<T>.Default ) {
               if(TrySZSort(array, null, index, index + length - 1)) {
                   return;
               }
           }

           ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
       }
   }

标记的注释<STRIP>解释了它,尽管英语破坏了:)默认比较器的代码路径通过TrySZSort(),这是一个在CLR中实现并用C++编写的函数.您可以从SSCLI20获取其源代码,它在clr/src/vm/comarrayhelpers.cpp中实现.它使用名为的模板类方法ArrayHelpers<T>::QuickSort().

它能够使用<运算符,单个cpu指令而不是Int32.CompareTo()所需的10个指令,从而获得速度优势.或者换句话说,IComparable <>.CompareTo被过度指定用于简单排序.

这是一个微优化,.NET Framework有很多很多.处于依赖链最底层的代码不可避免的命运,微软永远不会假设他们的代码在客户的应用程序中不会对速度至关重要.