昨天有朋友寫了一篇文章，其中比較了List<T>的Sort方法與LINQ中排序方法的性能，而最終得到的結果是“LINQ排序方法性能高於List<T>.Sort方法”。這個結果不禁讓我很疑惑。因為List<T>.Sort方法是改變容器內部元素的順序，而LINQ排序後得到的是一個新的序列。假如兩個排序方法的算法完全一致，LINQ排序也比對方多出元素復制的開銷，為什麼性能反而會高？如果LINQ排序的算法/實現更為優秀，那為什麼.Net Fx不將List<T>.Sort也一並優化一下呢？於是今天我也對這個問題進行了簡單的試驗。
注意事項
在後面的評論中有人說，List<T>.Sort是“內部排序”，而LINQ排序是“外部排序”。但是根據外部排序的定義，這個說法是不正確的。“外部排序”是指在排序目標規模太大，導致主存相對太小（如內存）而不夠放，不得不利用外部存儲（如硬盤）做一些“過渡”的排序方式。因此，LINQ排序雖然生成了新的序列，但還是內部排序。事實上，從定義中我們也可以很容易推斷出，如果數據規模相同，外部排序的性能一般總是比內部排序要差——不過事實上我們不太好做這樣的比較，因為如果是能夠進行內部排序的情況下，誰會利用麻煩的外部排序呢？
那篇文章中得到的結果是不對的，那麼問題究竟出在什麼地方呢？在我看來，問題主要出在以下兩點。
首先，原文作者使用了asp.net作為測試環境。值得注意的是，ASP.NET執行.NET代碼的時候，使用的是IIS進程中托管的CLR，它的配置和直接運行.NET應用程序時不同（不同的CLR托管方式配置很可能不一樣——例如SQL Server裡托管的CLR）。例如，ASP.NET中每個線程的調用棧為250K，而直接運行.NET應用程序時這個大小為1M。根據我的經驗（也就是說我無法確切地“證明”這個說法），在ASP.Net中執行此類性能測試得到的結果可能很不穩定。因此，一般我建議使用一個最普通的Console應用程序來進行性能測試。
其次，也是更重要的原因，便是原作者只測試了一次排序的性能。這是性能測試中的大忌諱，因為這麼做的話誤差實在太大。例如，會不會在進行某一個方法的測試時，忽然系統起了一個後台進程進行維護，動用了一部分CPU和內存資源，從而導致測試消耗的時間很冤枉地增加。而且，.Net程序是有一個“預熱”過程的，這導致代碼在第一次執行時需要有一個生成本機代碼的過程（俗稱“預熱”）。這個過程和代碼的執行效率是無關的，因為它無論如何只會產生一次消耗，而代碼是會被執行無數次的。因此，在進行測試的時候，一定要將測試目標反復執行N次，至少要讓執行耗時到達“秒”級別，這樣的結果才有一定參考價值。如果執行時間太少的話測試也可能不准確——要知道“計時器”也是有開銷，也是有誤差的，我們要得到盡量准確的結果。
最後，我強烈建議使用CodeTimer進行計時，因為在它的Initialize方法中會將當前進程及線程的優先級設置到最高，以此減少其他無關因素所造成的干擾。如果可以的話，其實也應該盡量關閉系統中其他應用程序或服務，並且最好可以斷開網絡（也是一個道理）。當然Release編譯也是一定需要的。而且，如果您一定需要使用ASP.Net進行性能測試的話，也千萬記得要在web.config中將<compilation />節點的debug屬性設為false——考慮到原作者忽略了之前犯了很明顯的忌諱，我強烈懷疑這點也沒有滿足。:)
因此，我認為那篇文章中的測試結果是不准確的，參考價值很低。
重新測試
既然如此，我們來重新進行一次試驗吧。不過我現在來比較的是Array.Sort<T>方法與LINQ排序的性能。這麼做的主要原因是，由於我們要執行多次排序操作，因此每次都應該使用亂序的序列。但是，每次生成新的序列也會帶來開銷，如果使用List<T>的話，填充元素的開銷會很大，但如果是普通數組的話，就可以用性能很高的Array.Copy方法了：
static T[] CloneArray<T>(T[] source)
{
var dest = new T[source.Length];
Array.Copy(source, dest, source.Length);
return dest;
}從試驗結果上看，數組的復制操作應該並沒有造成顯著影響。還有便是，經過閱讀List<T>.Sort方法的代碼，我們可以發現它只是將實現簡單地委托給Array.Sort<T>方法，因此我們可以認為它們的性能完全一致。
Array.Sort<T>方法其實有兩“類”重載，一類是使用IComparer<T>對象進行比較，而另一類則使用了Comparison<T>這個委托對象進行比較。為此，我們構造一個Int32Comparer類來實現IComparer<int>接口：
PRivate class Int32Comparer : IComparer<int>
{
#region IComparer<int> Members
public int Compare(int x, int y)
{
return x - y;
}
#endregion
}於是，兩“類”重載的測試方法分別為：
static void SortWithCustomComparer(int[] array)
{
Array.Sort(array, new Int32Comparer());
}
static void SortWithDelegate(int[] array)
{
Array.Sort(array, (x, y) => x - y);
}但是，我在這裡還是再補充一個排序“方法”（原因以後再談）。因為int類型是框架知道該如何比較的類型，因此我們其實也可以這麼寫：
static void SortWithDefaultComparer(int[] array)
{
Array.Sort(array, Comparer<int>.Default);
}最後，參加活動的自然還有LINQ排序：
static void SortWithLinq(int[] array)
{
var sorted =
(from i in array
orderby i
select i).ToList();
}這裡我使用的是ToList方法而不是ToArray方法來生成新序列，這是因為ToList的方法性能更高一些，我還是想盡可能將關注點放在“排序”而不是其他方面。
比較代碼如下：
static void Main(string[] args)
{
var random = new Random(DateTime.Now.Millisecond);
var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();
CodeTimer.Initialize();
CodeTimer.Time("SortWithDefaultComparer", 100,
() => SortWithDefaultComparer(CloneArray(array)));
CodeTimer.Time("SortWithCustomComparer", 100,
() => SortWithCustomComparer(CloneArray(array)));
CodeTimer.Time("SortWithDelegate", 100,
() => SortWithDelegate(CloneArray(array)));
CodeTimer.Time("SortWithLinq", 100,
() => SortWithLinq(CloneArray(array)));
Console.ReadLine();
}首先，我們生成一個擁有50萬個隨機元素的數組，以此進行排序方法的性能比較。每次比較的時候我們都使用CloneArray方法來生成一個新的數組。
試驗結果
試驗結果如下：
SortWithDefaultComparer
Time Elapsed: 7,662ms
Gen 0: 49
Gen 1: 49
Gen 2: 49
SortWithCustomComparer
Time Elapsed: 13,847ms
Gen 0: 49
Gen 1: 49
Gen 2: 49
SortWithDelegate
Time Elapsed: 19,625ms
Gen 0: 49
Gen 1: 49
Gen 2: 49
SortWithLinq
Time Elapsed: 31,785ms
Gen 0: 99
Gen 1: 99
Gen 2: 99從結果上來，四種做法的性能區別還是非常明顯的：使用Comparer<int>.Default進行排序的耗時只有LINQ排序的1/4。有趣的是，從GC次數上來看，LINQ排序也剛好是其他三種的一倍，和“理論值”幾乎完全吻合。
經過測試後發現，其實LINQ排序的性能並不會比Array.Sort<T>要高，甚至還有明顯的劣勢。由於排序算法都已經被用到濫了，而且幾乎已經成為了一個“標准”，因此從算法上來看它們不應該會有那麼大的差距。所以，我們這裡應該可以得出一個比較靠譜的推測：這幾種排序方法的性能差距，完全是由於具體實現上的細節引起的。
至於其中的原因，我們下次再來進行分析——這些方法的實現，尤其是LINQ排序的實現，似乎還是挺有趣的。
