ID #64935

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

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

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading;



namespace Exam11
{
  public static class CodeTimer
  {


    public static void Initialize()
    {
      PRocess.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
      Thread.CurrentThread.Priority = ThreadPriority.Highest;
      Time( "", 1, () => { } );
    }


    public static void Time( string name, int iteration, Action action )
    {
      if ( String.IsNullOrEmpty( name ) ) return;
      // warm up            
      action();
      // 1.           
      ConsoleColor currentForeColor = Console.ForegroundColor;
      Console.ForegroundColor = ConsoleColor.Yellow;
      Console.WriteLine( name );
      // 2.          
      GC.Collect( GC.MaxGeneration, GCCollectionMode.Forced );
      int[] gcCounts = new int[GC.MaxGeneration + 1];
      for ( int i = 0; i <= GC.MaxGeneration; i++ )
      {
        gcCounts[i] = GC.CollectionCount( i );
      }
      // 3.         
      Stopwatch watch = new Stopwatch();
      watch.Start();
      ulong cycleCount = GetCycleCount();
      for ( int i = 0; i < iteration; i++ ) action();
      ulong cpuCycles = GetCycleCount() - cycleCount;
      watch.Stop();
      // 4.           
      Console.ForegroundColor = currentForeColor;
      Console.WriteLine( "\tTime Elapsed:\t" + watch.ElapsedMilliseconds.ToString( "N0" ) + "ms" );
      Console.WriteLine( "\tCPU Cycles:\t" + cpuCycles.ToString( "N0" ) );
      // 5.        
      for ( int i = 0; i <= GC.MaxGeneration; i++ )
      {
        int count = GC.CollectionCount( i ) - gcCounts[i];
        Console.WriteLine( "\tGen " + i + ": \t\t" + count );
      }
      Console.WriteLine();
    }
    private static ulong GetCycleCount()
    {
      ulong cycleCount = 0;
      QueryThreadCycleTime( GetCurrentThread(), ref cycleCount );
      return cycleCount;
    }
    [DllImport( "kernel32.dll" )]
    [return: MarshalAs( UnmanagedType.Bool )]
    static extern bool QueryThreadCycleTime( IntPtr threadHandle, ref ulong cycleTime );
    [DllImport( "kernel32.dll" )]
    static extern IntPtr GetCurrentThread();
  }



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



      var random = new Random( DateTime.Now.Millisecond );
      var array = Enumerable.Repeat( 0, 50000 ).Select( _ => new Person { ID = random.Next() } ).ToArray();


      //老赵程序
      CodeTimer.Initialize();


      CodeTimer.Time( "SortWithCustomComparer", 500, () => SortWithCustomComparer( CloneArray( array ) ) );

      CodeTimer.Time( "SortWithLinq", 500, () => SortWithLinq( CloneArray( array ) ) );


      Console.ReadLine();
    }



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

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

    private static T[] CloneArray<T>( T[] source )
    {
      var dest = new T[source.Length];
      Array.Copy( source, dest, source.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<Person>
  {
    public int Compare( Person x, Person y )
    {
      return x.ID - y.ID;
    }

  }
}


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

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



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

CodeTimer.Time( "SortWithLinq", 100, () => SortWithLinq( CloneArray( array ) ) );

CodeTimer.Time( "SortWithCustomComparer", 100, () => SortWithCustomComparer( CloneArray( array ) ) );


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

private static PersonComparer comparer = new PersonComparer();

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

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

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

}

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

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

性能依然没有什么改善,反而还有小幅下降(这也正常)。

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

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

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



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


2011-08-24 19:42
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

使用LINQ to SQL更新数据库(中):几种解决方案

使用LINQ to SQL更新数据库(上):问题重重

按中文首个拼音字母排序的sql语句如何写

LINQ查询基础

安装SQL Server 2005发现了一个错误“如何在SQL Server 2005中为安装程序增加计数器注册表项值”