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

　　下載.NET框架的代碼

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

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

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

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

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

　　各Array.Sort方法的重載最終都會委托給下面這個重載來執(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);    }}

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

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

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

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

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

　　Array.Sort其他重載的性能

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

　　那么使用委托進行排序的時候為什么比Int32Comparer更慢一些呢？且看其代碼：

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

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

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

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

相關(guān)文章

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

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

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