|
|
昨天我們比較了Array.Sort方法與LINQ排序的性能，知道了LINQ排序的性能以較大幅度落后于Array.Sort方法。而對于Array.Sort來說，性能最高的是其中使用Comparer.Default作為比較器的重載方法。在前文的末尾我們做出了推測：由于排序算法已經近乎一個標準了（快速排序），因此從算法角度來說，Array.Sort方法和LINQ排序上不應該有那么大的差距，因此造成兩者性能差異的原因，應該是具體實現方式上的問題。
下載.NET框架的代碼
既然是比較實現的區別，那么閱讀代碼是很直接的選擇。談到閱讀.NET代碼，我們往往會使用.NET Reflector將框架的程序集反編譯為C#代碼——不排除有朋友喜歡觀察IL，并認為它們更直接，更底層。不過我倒覺得在絕大部分情況下，IL能看出的東西從C#也能看出，而C#無法了解的IL也幫不上忙，因此許多“由IL發現問題”的文章其實只是自己和自己在爽。
不過，雖然.NET Reflector將程序集反編譯成非常優秀的C#代碼，但是還是無法恢復之前的不少信息。例如，局部變量名無法得知，這就給理解代碼意圖造成了困難。再例如，為了可讀性我們可能會將一些條件語句分開寫，而C#編譯器則可能把它們連做一塊兒。至于注釋等明顯會被去除的東西就更不用說了。因此，在能直接讀到代碼的情況下，我并不傾向于使用.NET Reflector。
您可能會說：這不是廢話么，不過有些類庫——如.NET框架并沒有提供源代碼，這又有什么辦法呢？其實微軟也已經公布了.NET框架相當部分程序集的源代碼（幾乎所有v2.0的程序集，如mscrolib，System，System.Web等等），而且它們其實都可以使用NETMassDownloader直接下載到本地。隨員代碼發布的還有方便調試的pdb文件，不過這是另一個話題了，我們現在只關心源代碼。
因此，我建議您將所有微軟提供的源代碼都下載到本地。在看不懂.NET Reflector的反編譯結果時，不妨參考一下源代碼——還是包含注釋的源代碼。
Array.Sort方法實現
各Array.Sort方法的重載最終都會委托給下面這個重載來執行：
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，則繼續使用內置的排序方法進行處理。那么TrySZSort又是如何實現的呢？
private static extern bool TrySZSort(Array keys, Array items, int left, int right);
這是一個extern方法，說明它是由CLR直接實現的，我們無法得知它的具體算法或是意圖。不夠從注釋中可以得知，這個做法的目的是提高性能（明白注釋的優勢了吧）。每次使用IComparer的Compare方法進行比較的時候相當于是一次虛方法的調用，CLR需要計算它的偏移量，也無法將其內聯。這個細節相對于直接進行int的大小比較來說，也是有較大開銷的。使用TrySZSort這種外部方法進行排序，有助于提高在特定情況下的執行效率。
因此，我們應該可以有足夠信心來推斷出TrySZSort的作用。TrySZSort方法的作用是對一些可以直接進行比較的原生類型（如int等）進行排序，如果它發現自己無法支持數組中元素的類型，那么就返回false，否則便排序后并返回true。如果TrySZSort返回false，便會使用ArraySortHelper進行排序。而其中的實現便是標準（真的很標準）的快速排序，如果您感興趣的話可以自行閱讀其中的代碼。
值得注意的是，Array是定義在System命名空間下的類型，而ArraySortHelper則定義在System.Collections.Generic命名空間下。在閱讀微軟提供的源代碼時有個麻煩之處便是不容易導航，例如ArraySortHelper類便讓我一頓好找。不過，其實我們也可以配合.NET Reflector中強大的導航功能來快速定位到某個類的位置，然后直接去查找它對應的文件。當然，如果您索引了文件內容，也可以查找類似“class ArraySortHelper”這樣的關鍵字，也可以很快找到特定文件。
Array.Sort其他重載的性能
以上，我們已經知道為什么使用Comparer.Default作為比較器時性能最高了，因為對于int類型來說，Array.Sort方法會使用最快的TrySZSort方法進行排序。而如果我們使用自定義的Int32Comparer進行比較的話，Compare方法調用的開銷是無可避免的，根據實驗結果，使用Int32Comparer的執行時間比前者有80%的增加也可以接受。
那么使用委托進行排序的時候為什么比Int32Comparer更慢一些呢？且看其代碼：
public static void Sort(T[] array, Comparison comparison){ ... IComparer comparer = new FunctorComparer(comparison); Sort(array, comparer);}
其實原因很簡單，因為.NET框架使用了FunctorComparer封裝了comparison委托。這樣在每次比較時，它相對于Int32Comparer來說還增加了委托執行的開銷——這又相當于一次虛方法的調用：需要尋址，無法內聯。
至此，我們已經分析了Array.Sort各重載的實現方式，也了解了三種Array.Sort重載性能有別的原因。剛好，不久前姜敏兄又回應了我的文章，認為使用Person類，而不是int類型進行比較的時候，仍舊是LINQ排序比較快——由此他認為兩種做法的性能和類型也有關系。您認為這個說法正確嗎？其實從實現上看，Array.Sort幾乎已經是最優的做法了。相反，LINQ排序由于會生成額外的序列，性能想要超過Array.Sort幾乎是件不可能的事情。但事實真是如此嗎？
那這測試結果……我也寫了一個Person類的測試（http://gist.github.com/282796），還是Array.Sort比較快。那么為什么兩個結果會有所不同呢？這是一個值得探討的問題。
相關文章
NET技術：數組排序方法的性能比較（中）：Array.Sort 實現分析，轉載需保留來源！
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。
