数组排序LINQ的性能优势初步分析 —— 不起眼的属性

话说前阵子姜敏兄对Ar***.Sort和En***rable.OrderBy方法进行了一次足够严密的性能测试。可结论似乎与理论和预期不符，但这个结论却是在一个相对严谨的环境下测出，也勾起了各位大牛的兴趣。偶也在偶的机器上测试了一把，当然偶先把一些无关的代码整理了一下：

using System;
using Sy***m.Collections.Generic;
using Sy***m.Diagnostics;
using Sy***m.Linq;
using Sy***m.Runtime.InteropServices;
using Sy***m.Threading;

namespace Exam11
{
  public static class CodeTimer
  {

    public static void Initialize()
    {
      Pr***ss.GetCurrentProcess().PriorityClass = Pr***ssPriorityClass.High;
      Th***d.CurrentThread.Priority = Th***dPriority.Highest;
      Time( "", 1, () => { } );
    }

    public static void Time( string name, int iteration, Action action )
    {
      if ( St***g.IsNullOrEmpty( name ) ) return;
      // warm up           
      action();
      // 1.          
      ConsoleColor currentForeColor = Co***le.ForegroundColor;
      Co***le.ForegroundColor = Co***leColor.Yellow;
      Co***le.WriteLine( name );
      // 2.         
      GC***llect( GC***xGeneration, GC***lectionMode.Forced );
      int[] gcCounts = new int[GC***xGeneration + 1];
      for ( int i = 0; i <= GC***xGeneration; i++ )
      {
        gcCounts[i] = GC***llectionCount( i );
      }
      // 3.        
      Stopwatch watch = new Stopwatch();
      wa***.Start();
      ulong cycleCount = GetCycleCount();
      for ( int i = 0; i < iteration; i++ ) action();
      ulong cpuCycles = GetCycleCount() - cycleCount;
      wa***.Stop();
      // 4.          
      Co***le.ForegroundColor = currentForeColor;
      Co***le.WriteLine( "tTime Elapsed:t" + wa***.ElapsedMilliseconds.ToString( "N0" ) + "ms" );
      Co***le.WriteLine( "tCPU Cycles:t" + cp***cles.ToString( "N0" ) );
      // 5.       
      for ( int i = 0; i <= GC***xGeneration; i++ )
      {
        int count = GC***llectionCount( i ) - gcCounts[i];
        Co***le.WriteLine( "tGen " + i + ": tt" + count );
      }
      Co***le.WriteLine();
    }
    private static ulong GetCycleCount()
    {
      ulong cycleCount = 0;
      QueryThreadCycleTime( GetCurrentThread(), ref cycleCount );
      return cycleCount;
    }
    [DllImport( "ke***l32.dll" )]
    [return: MarshalAs( Un***agedType.Bool )]
    static extern bool QueryThreadCycleTime( IntPtr threadHandle, ref ulong cycleTime );
    [DllImport( "ke***l32.dll" )]
    static extern IntPtr GetCurrentThread();
  }

  class Program
  {
    static void Main( string[] args )
    {

      var random = new Random( Da***ime.Now.Millisecond );
      var array = En***rable.Repeat( 0, 50000 ).Select( _ => new Person { ID = ra***m.Next() } ).ToArray();

      //老赵程序
      Co***imer.Initialize();

      Co***imer.Time( "SortWithCustomComparer", 500, () => SortWithCustomComparer( CloneArray( array ) ) );

      Co***imer.Time( "SortWithLinq", 500, () => SortWithLinq( CloneArray( array ) ) );

      Co***le.ReadLine();
    }

    private static void SortWithCustomComparer( Person[] array )
    {
      Ar***.Sort( array, new PersonComparer() );
    }

    private static void SortWithLinq( Person[] array )
    {
      var sorted =
          ( from person in array
            orderby pe***n.ID
            select person ).ToList();
    }

    private static T[] CloneArray( T[] source )
    {
      var dest = new T[so***e.Length];
      Ar***.Copy( source, dest, so***e.Length );
      return dest;
    }
   
  }
  public class Person
  {
    public string FirstName
    {
      get;
      set;
    }

    public string LastName
    {
      get;
      set;
    }

    public int ID
    {
      get;
      set;
    }
  }
  public class PersonComparer : IComparer
  {
    public int Compare( Person x, Person y )
    {
      return x.ID - y.ID;
    }

  }
}

测试的结果的的确确是En***rable.OrderBy明显可以察觉出来的优势，即使是在Release编译方式下。

从原理上来说，这是不可能的，那么他们一定有什么地方存在某种不公平竞争。

我重新审视了整个代码，调整了两个测试代码的位置：

Co***imer.Time( "SortWithLinq", 100, () => SortWithLinq( CloneArray( array ) ) );

Co***imer.Time( "SortWithCustomComparer", 100, () => SortWithCustomComparer( CloneArray( array ) ) );

当然，这不会有任何效果。其次我又发现这个comparer实例被创建了多次（其实也就100次），遂优化如下：

private static PersonComparer comparer = new PersonComparer();

private static void SortWithCustomComparer( Person[] array )
{
  Ar***.Sort( array, comparer );
}
对结果也没有什么改善。

所以我只能将目光集中到comparer的实现上：

public class PersonComparer : IComparer
{
  public int Compare( Person x, Person y )
  {
    return x.ID - y.ID;
  }

}

这并不是一个公平的做法，但应该也不会引起性能问题，将其改成如下形式：

public int Compare( Person x, Person y )
{
  return x.***CompareTo( y.ID );
}

性能依然没有什么改善，反而还有小幅下降（这也正常）。

似乎陷入了僵局？事实上我们已经非常接近事实的真相了，其实标题都已经将答案公布了。因为问题就出在pe***n.ID是一个属性，这里其实调用了三次方法。

所以只需要简单的将ID改成一个字段，性能结果便与预期的相近了。

那么在这里，LINQ为什么会有优势呢？啊，如果你了解LINQ的排序原理，其实不难想到，LINQ可以节省很多次Pe***n.get_ID的调用。我相信这个分析，会在大牛的下一篇文章详细阐述的，我就不在这里献丑了。

所以结论也可以出来了，但还是令人有点小意外，LINQ在某些环境下的确是有性能优势的，这个理论上是成立的。但我想说的是，其实还有很多因素会影响到这个结论，我们真的不能以偏概全的说，LINQ一定有性能优势或是Ar***.Sort一定有性能优势。