Why is List<T>.Sort using Comparer<int>.Default more than twice as fast as an equivalent custom comparer?

Question

Results

Using a list of 10 million random ints (same seed each time, average of 10 repetitions):

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

Using

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

listCopy.Sort(new IntComparer()) takes 716ms.

Some variations:

• Using struct IntComparer instead of sealed class: 771ms
• Using public int Compare(int x, int y) { return x.CompareTo(y); }: 809ms

Comments

Comparer<int>.Default returns a GenericComparer<int>. According to dotPeek, we have:

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

...
}

Obviously, this shouldn't be faster than my IntComparer variant using CompareTo.

I didn't find anything relevant in ArraySortHelper<T>, which appears to be the core of List<T>.Sort.

I can only guess that the JIT does some magic special-casing here (Replace sorts which use Comparer<int>.Default by a specialized sorting implementation which doesn't do any IComparer<T>.Compare calls, or something similar)?

EDIT: The timings above are too low by a factor of 5.9214729782462845 (Stopwatch and TimeSpan have a different definition of "Tick"). Doesn't affect the point, though.

Answer 1

The reason is readily visible in the Reference Source, system/array.cs source code file:

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

The comment marked by <STRIP> explains it, in spite of its broken English :) The code path for the default comparer goes through TrySZSort(), a function that's implemented in the CLR and written in C++. You can get its source code from SSCLI20, it is implemented in clr/src/vm/comarrayhelpers.cpp. It uses a template class method named ArrayHelpers<T>::QuickSort().

It gets the speed advantage from being able to use the < operator, a single cpu instruction instead of the 10 required by Int32.CompareTo(). Or in other words, IComparable<>.CompareTo is over-specified for simple sorting.

It is a micro-optimization, the .NET Framework has lots and lots of them. The inevitable fate of code that sits at the very bottom of a dependency chain, Microsoft can never assume that their code isn't going to be speed-critical in a customer's app.

Answer 2

The default comparer for Int32 is the CompareTo(int,int) method. Your assumption of the default comparer is incorrect.

The IComparable interface provides a strongly typed comparison method for ordering members of a generic collection object. Because of this, it is usually not called directly from developer code. Instead, it is called automatically by methods such as List.Sort() and Add.

http://msdn.microsoft.com/en-us/library/4d7sx9hd.aspx. The IComparable interface mentioned defines the CompareTo method.

So we should expect your comparer to be about the same speed. So why might it be slower? If we dig down into the Sort method in .Net, we eventually get to this line:

if ((length > 1) && (((comparer != null) && (comparer != Comparer<T>.Default)) || !TrySZSort(array, null, index, (index + length) - 1)))
{
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}

If the comparer equals the default comparer for that type, the Array Sort will try to use an internal optimized sort method. Your comparer is not the default comparer, so it skips that optimized sort.

Answer 3

ILSpy decompiles thus:

    public override int Compare(T x, T y)
    {
        if (x != null)
        {
            if (y != null)
            {
                return x.CompareTo(y);
            }
            return 1;
        }
        else
        {
            if (y != null)
            {
                return -1;
            }
            return 0;
        }
    }

The null checks will always evaluate as true for a value type, so they will be optimized away; the end result will be

public override int Compare(T x, T y)
{
    return x.CompareTo(y);
}