数组排序LINQ的性能优势初步分析 —— 不起眼的属性
2024-07-21 02:45:12
供稿：网友
话说前阵子姜敏兄对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一定有性能优势。
