|
|
昨天有朋友寫了一篇文章，其中比較了List的Sort方法與LINQ中排序方法的性能，而最終得到的結(jié)果是“LINQ排序方法性能高于List.Sort方法”。這個結(jié)果不禁讓我很疑惑。因為List.Sort方法是改變?nèi)萜鲀?nèi)部元素的順序，而LINQ排序后得到的是一個新的序列。假如兩個排序方法的算法完全一致，LINQ排序也比對方多出元素復(fù)制的開銷，為什么性能反而會高？如果LINQ排序的算法/實現(xiàn)更為優(yōu)秀，那為什么.NET Fx不將List.Sort也一并優(yōu)化一下呢？于是今天我也對這個問題進(jìn)行了簡單的試驗。
注意事項
在后面的評論中有人說，List.Sort是“內(nèi)部排序”，而LINQ排序是“外部排序”。但是根據(jù)外部排序的定義，這個說法是不正確的。“外部排序”是指在排序目標(biāo)規(guī)模太大，導(dǎo)致主存相對太?。ㄈ鐑?nèi)存）而不夠放，不得不利用外部存儲（如硬盤）做一些“過渡”的排序方式。因此，LINQ排序雖然生成了新的序列，但還是內(nèi)部排序。事實上，從定義中我們也可以很容易推斷出，如果數(shù)據(jù)規(guī)模相同，外部排序的性能一般總是比內(nèi)部排序要差——不過事實上我們不太好做這樣的比較，因為如果是能夠進(jìn)行內(nèi)部排序的情況下，誰會利用麻煩的外部排序呢？
那篇文章中得到的結(jié)果是不對的，那么問題究竟出在什么地方呢？在我看來，問題主要出在以下兩點。
首先，原文作者使用了ASP.NET作為測試環(huán)境。值得注意的是，ASP.NET執(zhí)行.NET代碼的時候，使用的是IIS進(jìn)程中托管的CLR，它的配置和直接運行.NET應(yīng)用程序時不同（不同的CLR托管方式配置很可能不一樣——例如SQL Server里托管的CLR）。例如，ASP.NET中每個線程的調(diào)用棧為250K，而直接運行.NET應(yīng)用程序時這個大小為1M。根據(jù)我的經(jīng)驗（也就是說我無法確切地“證明”這個說法），在ASP.NET中執(zhí)行此類性能測試得到的結(jié)果可能很不穩(wěn)定。因此，一般我建議使用一個最普通的Console應(yīng)用程序來進(jìn)行性能測試。
其次，也是更重要的原因，便是原作者只測試了一次排序的性能。這是性能測試中的大忌諱，因為這么做的話誤差實在太大。例如，會不會在進(jìn)行某一個方法的測試時，忽然系統(tǒng)起了一個后臺進(jìn)程進(jìn)行維護(hù)，動用了一部分CPU和內(nèi)存資源，從而導(dǎo)致測試消耗的時間很冤枉地增加。而且，.NET程序是有一個“預(yù)熱”過程的，這導(dǎo)致代碼在第一次執(zhí)行時需要有一個生成本機代碼的過程（俗稱“預(yù)熱”）。這個過程和代碼的執(zhí)行效率是無關(guān)的，因為它無論如何只會產(chǎn)生一次消耗，而代碼是會被執(zhí)行無數(shù)次的。因此，在進(jìn)行測試的時候，一定要將測試目標(biāo)反復(fù)執(zhí)行N次，至少要讓執(zhí)行耗時到達(dá)“秒”級別，這樣的結(jié)果才有一定參考價值。如果執(zhí)行時間太少的話測試也可能不準(zhǔn)確——要知道“計時器”也是有開銷，也是有誤差的，我們要得到盡量準(zhǔn)確的結(jié)果。
最后，我強烈建議使用CodeTimer進(jìn)行計時，因為在它的Initialize方法中會將當(dāng)前進(jìn)程及線程的優(yōu)先級設(shè)置到最高，以此減少其他無關(guān)因素所造成的干擾。如果可以的話，其實也應(yīng)該盡量關(guān)閉系統(tǒng)中其他應(yīng)用程序或服務(wù)，并且最好可以斷開網(wǎng)絡(luò)（也是一個道理）。當(dāng)然Release編譯也是一定需要的。而且，如果您一定需要使用ASP.NET進(jìn)行性能測試的話，也千萬記得要在web.config中將節(jié)點的debug屬性設(shè)為false——考慮到原作者忽略了之前犯了很明顯的忌諱，我強烈懷疑這點也沒有滿足。:)
因此，我認(rèn)為那篇文章中的測試結(jié)果是不準(zhǔn)確的，參考價值很低。
重新測試
既然如此，我們來重新進(jìn)行一次試驗吧。不過我現(xiàn)在來比較的是Array.Sort方法與LINQ排序的性能。這么做的主要原因是，由于我們要執(zhí)行多次排序操作，因此每次都應(yīng)該使用亂序的序列。但是，每次生成新的序列也會帶來開銷，如果使用List的話，填充元素的開銷會很大，但如果是普通數(shù)組的話，就可以用性能很高的Array.Copy方法了：
static T[] CloneArray(T[] source){ var dest = new T[source.Length]; Array.Copy(source, dest, source.Length); return dest;}
從試驗結(jié)果上看，數(shù)組的復(fù)制操作應(yīng)該并沒有造成顯著影響。還有便是，經(jīng)過閱讀List.Sort方法的代碼，我們可以發(fā)現(xiàn)它只是將實現(xiàn)簡單地委托給Array.Sort方法，因此我們可以認(rèn)為它們的性能完全一致。
Array.Sort方法其實有兩“類”重載，一類是使用IComparer對象進(jìn)行比較，而另一類則使用了Comparison這個委托對象進(jìn)行比較。為此，我們構(gòu)造一個Int32Comparer類來實現(xiàn)IComparer接口：
private class Int32Comparer : IComparer<int>{ #region IComparer 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的方法性能更高一些，我還是想盡可能將關(guān)注點放在“排序”而不是其他方面。
比較代碼如下：
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萬個隨機元素的數(shù)組，以此進(jìn)行排序方法的性能比較。每次比較的時候我們都使用CloneArray方法來生成一個新的數(shù)組。
試驗結(jié)果
試驗結(jié)果如下：
SortWithDefaultComparer Time Elapsed: 7,662ms Gen 0: 49 Gen 1: 49 Gen 2: 49SortWithCustomComparer Time Elapsed: 13,847ms Gen 0: 49 Gen 1: 49 Gen 2: 49SortWithDelegate Time Elapsed: 19,625ms Gen 0: 49 Gen 1: 49 Gen 2: 49SortWithLinq Time Elapsed: 31,785ms Gen 0: 99 Gen 1: 99 Gen 2: 99
從結(jié)果上來，四種做法的性能區(qū)別還是非常明顯的：使用Comparer.Default進(jìn)行排序的耗時只有LINQ排序的1/4。有趣的是，從GC次數(shù)上來看，LINQ排序也剛好是其他三種的一倍，和“理論值”幾乎完全吻合。
經(jīng)過測試后發(fā)現(xiàn)，其實LINQ排序的性能并不會比Array.Sort要高，甚至還有明顯的劣勢。由于排序算法都已經(jīng)被用到濫了，而且?guī)缀跻呀?jīng)成為了一個“標(biāo)準(zhǔn)”，因此從算法上來看它們不應(yīng)該會有那么大的差距。所以，我們這里應(yīng)該可以得出一個比較靠譜的推測：這幾種排序方法的性能差距，完全是由于具體實現(xiàn)上的細(xì)節(jié)引起的。
至于其中的原因，我們下次再來進(jìn)行分析——這些方法的實現(xiàn)，尤其是LINQ排序的實現(xiàn)，似乎還是挺有趣的。
本文代碼：http://gist.github.com/281857
相關(guān)文章
- 數(shù)組排序方法的性能比較（1）：注意事項及試驗
- 數(shù)組排序方法的性能比較（2）：Array.Sort實現(xiàn)分析
- 數(shù)組排序方法的性能比較（3）：LINQ排序?qū)崿F(xiàn)分析
NET技術(shù)：數(shù)組排序方法的性能比較（上）：注意事項及試驗，轉(zhuǎn)載需保留來源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。
