昨天我們比較了Array.Sort方法與LINQ排序的性能，知道了LINQ排序的性能以較大幅度落后于Array.Sort方法。而對(duì)于Array.Sort來(lái)說(shuō)，性能最高的是其中使用Comparer.Default作為比較器的重載方法。在前文的末尾我們做出了推測(cè)：由于排序算法已經(jīng)近乎一個(gè)標(biāo)準(zhǔn)了（快速排序），因此從算法角度來(lái)說(shuō)，Array.Sort方法和LINQ排序上不應(yīng)該有那么大的差距，因此造成兩者性能差異的原因，應(yīng)該是具體實(shí)現(xiàn)方式上的問(wèn)題。

　　下載.NET框架的代碼

　　既然是比較實(shí)現(xiàn)的區(qū)別，那么閱讀代碼是很直接的選擇。談到閱讀.NET代碼，我們往往會(huì)使用.NET Reflector將框架的程序集反編譯為C#代碼——不排除有朋友喜歡觀察IL，并認(rèn)為它們更直接，更底層。不過(guò)我倒覺(jué)得在絕大部分情況下，IL能看出的東西從C#也能看出，而C#無(wú)法了解的IL也幫不上忙，因此許多“由IL發(fā)現(xiàn)問(wèn)題”的文章其實(shí)只是自己和自己在爽。

　　不過(guò)，雖然.NET Reflector將程序集反編譯成非常優(yōu)秀的C#代碼，但是還是無(wú)法恢復(fù)之前的不少信息。例如，局部變量名無(wú)法得知，這就給理解代碼意圖造成了困難。再例如，為了可讀性我們可能會(huì)將一些條件語(yǔ)句分開(kāi)寫(xiě)，而C#編譯器則可能把它們連做一塊兒。至于注釋等明顯會(huì)被去除的東西就更不用說(shuō)了。因此，在能直接讀到代碼的情況下，我并不傾向于使用.NET Reflector。

　　您可能會(huì)說(shuō)：這不是廢話么，不過(guò)有些類(lèi)庫(kù)——如.NET框架并沒(méi)有提供源代碼，這又有什么辦法呢？其實(shí)微軟也已經(jīng)公布了.NET框架相當(dāng)部分程序集的源代碼（幾乎所有v2.0的程序集，如mscrolib，System，System.Web等等），而且它們其實(shí)都可以使用NETMassDownloader直接下載到本地。隨員代碼發(fā)布的還有方便調(diào)試的pdb文件，不過(guò)這是另一個(gè)話題了，我們現(xiàn)在只關(guān)心源代碼。

　　因此，我建議您將所有微軟提供的源代碼都下載到本地。在看不懂.NET Reflector的反編譯結(jié)果時(shí)，不妨參考一下源代碼——還是包含注釋的源代碼。

　　Array.Sort方法實(shí)現(xiàn)

　　各Array.Sort方法的重載最終都會(huì)委托給下面這個(gè)重載來(lái)執(zhí)行：

public static void Sort(T[] array, int index, int length, IComparer comparer){    ...    if (length > 1)    {        //         // TrySZSort is still faster than the generic implementation.        // The reason is Int32.CompareTo is still expensive than just using "<" or ">".         //         if (comparer == null || comparer == Comparer.Default)        {            if (TrySZSort(array, null, index, index + length - 1))            {                return;            }        }        ArraySortHelper.Default.Sort(array, index, length, comparer);    }}

　　我們知道，從邏輯上說(shuō)，Array.Sort方法會(huì)使用IComparer類(lèi)型的比較器來(lái)判斷兩個(gè)元素的大小。不過(guò)在這里，.NET框架作了一個(gè)“特例”，它在用戶(hù)沒(méi)有提供比較器，或是直接使用默認(rèn)比較器的時(shí)候利用TrySZSort方法進(jìn)行排序。如果TrySZSort方法如果返回true，則表示排序完成，直接返回。如果它返回false，則繼續(xù)使用內(nèi)置的排序方法進(jìn)行處理。那么TrySZSort又是如何實(shí)現(xiàn)的呢？

private static extern bool TrySZSort(Array keys, Array items, int left, int right);

　　這是一個(gè)extern方法，說(shuō)明它是由CLR直接實(shí)現(xiàn)的，我們無(wú)法得知它的具體算法或是意圖。不夠從注釋中可以得知，這個(gè)做法的目的是提高性能（明白注釋的優(yōu)勢(shì)了吧）。每次使用IComparer的Compare方法進(jìn)行比較的時(shí)候相當(dāng)于是一次虛方法的調(diào)用，CLR需要計(jì)算它的偏移量，也無(wú)法將其內(nèi)聯(lián)。這個(gè)細(xì)節(jié)相對(duì)于直接進(jìn)行int的大小比較來(lái)說(shuō)，也是有較大開(kāi)銷(xiāo)的。使用TrySZSort這種外部方法進(jìn)行排序，有助于提高在特定情況下的執(zhí)行效率。

　　因此，我們應(yīng)該可以有足夠信心來(lái)推斷出TrySZSort的作用。TrySZSort方法的作用是對(duì)一些可以直接進(jìn)行比較的原生類(lèi)型（如int等）進(jìn)行排序，如果它發(fā)現(xiàn)自己無(wú)法支持?jǐn)?shù)組中元素的類(lèi)型，那么就返回false，否則便排序后并返回true。如果TrySZSort返回false，便會(huì)使用ArraySortHelper進(jìn)行排序。而其中的實(shí)現(xiàn)便是標(biāo)準(zhǔn)（真的很標(biāo)準(zhǔn)）的快速排序，如果您感興趣的話可以自行閱讀其中的代碼。

　　值得注意的是，Array是定義在System命名空間下的類(lèi)型，而ArraySortHelper則定義在System.Collections.Generic命名空間下。在閱讀微軟提供的源代碼時(shí)有個(gè)麻煩之處便是不容易導(dǎo)航，例如ArraySortHelper類(lèi)便讓我一頓好找。不過(guò)，其實(shí)我們也可以配合.NET Reflector中強(qiáng)大的導(dǎo)航功能來(lái)快速定位到某個(gè)類(lèi)的位置，然后直接去查找它對(duì)應(yīng)的文件。當(dāng)然，如果您索引了文件內(nèi)容，也可以查找類(lèi)似“class ArraySortHelper”這樣的關(guān)鍵字，也可以很快找到特定文件。

　　Array.Sort其他重載的性能

　　以上，我們已經(jīng)知道為什么使用Comparer.Default作為比較器時(shí)性能最高了，因?yàn)閷?duì)于int類(lèi)型來(lái)說(shuō)，Array.Sort方法會(huì)使用最快的TrySZSort方法進(jìn)行排序。而如果我們使用自定義的Int32Comparer進(jìn)行比較的話，Compare方法調(diào)用的開(kāi)銷(xiāo)是無(wú)可避免的，根據(jù)實(shí)驗(yàn)結(jié)果，使用Int32Comparer的執(zhí)行時(shí)間比前者有80%的增加也可以接受。

　　那么使用委托進(jìn)行排序的時(shí)候?yàn)槭裁幢菼nt32Comparer更慢一些呢？且看其代碼：

public static void Sort(T[] array, Comparison comparison){    ...    IComparer comparer = new FunctorComparer(comparison);    Sort(array, comparer);}

　　其實(shí)原因很簡(jiǎn)單，因?yàn)?NET框架使用了FunctorComparer封裝了comparison委托。這樣在每次比較時(shí)，它相對(duì)于Int32Comparer來(lái)說(shuō)還增加了委托執(zhí)行的開(kāi)銷(xiāo)——這又相當(dāng)于一次虛方法的調(diào)用：需要尋址，無(wú)法內(nèi)聯(lián)。

　　至此，我們已經(jīng)分析了Array.Sort各重載的實(shí)現(xiàn)方式，也了解了三種Array.Sort重載性能有別的原因。剛好，不久前姜敏兄又回應(yīng)了我的文章，認(rèn)為使用Person類(lèi)，而不是int類(lèi)型進(jìn)行比較的時(shí)候，仍舊是LINQ排序比較快——由此他認(rèn)為兩種做法的性能和類(lèi)型也有關(guān)系。您認(rèn)為這個(gè)說(shuō)法正確嗎？其實(shí)從實(shí)現(xiàn)上看，Array.Sort幾乎已經(jīng)是最優(yōu)的做法了。相反，LINQ排序由于會(huì)生成額外的序列，性能想要超過(guò)Array.Sort幾乎是件不可能的事情。但事實(shí)真是如此嗎？

　　那這測(cè)試結(jié)果……我也寫(xiě)了一個(gè)Person類(lèi)的測(cè)試（http://gist.github.com/282796），還是Array.Sort比較快。那么為什么兩個(gè)結(jié)果會(huì)有所不同呢？這是一個(gè)值得探討的問(wèn)題。

相關(guān)文章

1. 數(shù)組排序方法的性能比較（1）：注意事項(xiàng)及試驗(yàn)
2. 數(shù)組排序方法的性能比較（2）：Array.Sort實(shí)現(xiàn)分析
3. 數(shù)組排序方法的性能比較（3）：LINQ排序?qū)崿F(xiàn)分析

NET技術(shù)：數(shù)組排序方法的性能比較（中）：Array.Sort 實(shí)現(xiàn)分析，轉(zhuǎn)載需保留來(lái)源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。