爲什麼處理排序後的數組要比未排序的數組慢？

Question

我有500000名隨機生成Tuple<long,long,string>對象列表上我執行一個簡單的搜索「之間」時：

var data = new List<Tuple<long,long,string>>(500000); 
... 
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x); 

當我生成我隨機陣列和運行我爲x 100個隨機生成的值的搜索，所述大約四秒鐘完成搜索。然而，在知道great wonders that sorting does to searching後，我決定對我的數據進行排序 - 首先按Item1，然後按Item2，最後按Item3 - 在運行我的100次搜索之前。由於分支預測，我預計排序後的版本會執行得更快一些：我的想法是，一旦我們達到Item1 == x的所有進一步檢查將正確預測分支爲「不帶」，加快尾部的搜索。令我驚訝的是，搜索花費了兩倍於排序陣列！

我試着開關周圍，我跑我的實驗，並用不同的種子隨機數發生器的順序，但效果一直不變：在排序的數組的搜索跑了近兩倍的速度在搜查相同的數組，但排序！

有沒有人有這個奇怪的效果很好的解釋？我的測試源代碼如下;我正在使用.NET 4.0。

---

private const int TotalCount = 500000; 
private const int TotalQueries = 100; 
private static long NextLong(Random r) { 
    var data = new byte[8]; 
    r.NextBytes(data); 
    return BitConverter.ToInt64(data, 0); 
} 
private class TupleComparer : IComparer<Tuple<long,long,string>> { 
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) { 
     var res = x.Item1.CompareTo(y.Item1); 
     if (res != 0) return res; 
     res = x.Item2.CompareTo(y.Item2); 
     return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3); 
    } 
} 
static void Test(bool doSort) { 
    var data = new List<Tuple<long,long,string>>(TotalCount); 
    var random = new Random(1000000007); 
    var sw = new Stopwatch(); 
    sw.Start(); 
    for (var i = 0 ; i != TotalCount ; i++) { 
     var a = NextLong(random); 
     var b = NextLong(random); 
     if (a > b) { 
      var tmp = a; 
      a = b; 
      b = tmp; 
     } 
     var s = string.Format("{0}-{1}", a, b); 
     data.Add(Tuple.Create(a, b, s)); 
    } 
    sw.Stop(); 
    if (doSort) { 
     data.Sort(new TupleComparer()); 
    } 
    Console.WriteLine("Populated in {0}", sw.Elapsed); 
    sw.Reset(); 
    var total = 0L; 
    sw.Start(); 
    for (var i = 0 ; i != TotalQueries ; i++) { 
     var x = NextLong(random); 
     var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x); 
     total += cnt; 
    } 
    sw.Stop(); 
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted"); 
} 
static void Main() { 
    Test(false); 
    Test(true); 
    Test(false); 
    Test(true); 
} 

---

Populated in 00:00:01.3176257 
Found 15614281 matches in 00:00:04.2463478 (Unsorted) 
Populated in 00:00:01.3345087 
Found 15614281 matches in 00:00:08.5393730 (Sorted) 
Populated in 00:00:01.3665681 
Found 15614281 matches in 00:00:04.1796578 (Unsorted) 
Populated in 00:00:01.3326378 
Found 15614281 matches in 00:00:08.6027886 (Sorted) 

Answer 1

當您使用未排序列表中的所有元組在內存階訪問。它們已經在RAM中連續分配。 CPU喜歡順序訪問內存，因爲它們可以推測性地請求下一個緩存行，以便在需要時始終存在。

當你整理列表時，你把它放入隨機順序因爲你的排序鍵是隨機生成的。這意味着訪問元組成員的內存是不可預知的。 CPU不能預取內存，幾乎每個對元組的訪問都是緩存未命中。

這是GC內存管理特定優勢的一個很好的例子：已經分配在一起並且一起使用的數據結構表現得非常好。他們有很好的地點參考。

從緩存中的點球偏出勝過在這種情況下，保存的分支預測點球。

嘗試切換到struct -tuple。這將恢復性能，因爲在運行時不需要使用指針取消引用來訪問元組成員。

Chris Sinclair在評論中指出「對於TotalCount大約10,000或更少，排序後的版本確實執行得更快」。這是因爲一個小列表完全適合CPU高速緩存。內存訪問可能是不可預測的，但目標總是在緩存中。我相信還是有一點小小的損失，因爲即使是來自緩存的負載也需要一些週期。但這似乎不成問題，因爲CPU可以處理多個未完成的負載，從而提高吞吐量。無論CPU何時等待內存，它都會在指令流中加速前進，以儘可能地排隊儘可能多的內存操作。該技術用於隱藏延遲。

這種行爲表明它是如何很難預測在現代CPU的性能。事實上，我們是只有兩倍慢從順序訪問隨機內存訪問告訴我有多少事情在封面下隱藏內存延遲。內存訪問可能會使CPU停止50-200個週期。在引入隨機存儲器訪問的情況下，預計該程序的速度會降低10倍以上。

Answer 2

LINQ不知道你是否列表進行排序或沒有。

由於伯爵與謂詞參數是所有IEnumerables擴展方法，我認爲它甚至不知道它是否運行在高效隨機存取集合。所以，它只是檢查每個元素，並解釋爲什麼性能降低。

要利用有序陣列（例如二進制搜索）的性能優勢，你就必須做一點點的編碼。