數組排序LINQ的性能優勢初步分析 —— 不起眼的屬性
2024-07-21 02:45:12
供稿：網友
話說前陣子姜敏兄對Array.Sort和Enumerable.OrderBy方法進行了一次足夠嚴密的性能測試?？山Y論似乎與理論和預期不符，但這個結論卻是在一個相對嚴謹的環境下測出，也勾起了各位大牛的興趣。偶也在偶的機器上測試了一把，當然偶先把一些無關的代碼整理了一下：
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一定有性能優勢。
