C＃存儲數組大小超過512長（4096字節）是否不同？

Question

我做了一些在.NET Framework中實現集合類型的基準測試。

從參考源我知道List<T>使用數組來存儲內容。爲了避免每次插入調整陣列的大小，每次可用空間用完時都會調用array length gets doubled。現在

我的基準會插入隨機long值成List（見上面的尺寸圖 - 時間 - 曲線）。在像128或256這樣的列表大小存在明顯的「滯後尖峯」時，內部陣列必須重新分配。但是，在512的大小（128，儘管？），似乎有一個非常大的滯後和插入一個項目所需的時間是持久增加。

在我的理解中，除了需要重新分配內部數組的場合外，圖形應該是嚴格恆定的。這種行爲是否有任何原因，可能與CLR或Windows內存管理/內存碎片有關？

基準測試是在Windows 10/i7-3630QM機器上執行64位應用程序（源代碼如下所示）。由於單個添加操作不可測量，我創建了1000個列表，併爲每個列表大小添加一個項目。

for (int i = 1; i <= MaxCollectionSize; i++) 
{ 
    // Reset time measurement 
    TestContainer.ResetSnapshot(); 

    // Enable time measurement 
    TestContainer.BeginSnapshot(); 
    // Execute one add operation on 1000 lists each 
    ProfileAction.Invoke(TestContainer); 
    TestContainer.EndSnapShot(); 

    double elapsedMilliseconds = (TestContainer.GetElapsedMilliSeconds()/(double)Stopwatch.Frequency) * 1000; 
    // ... 
} 

編輯：我仔細檢查了我的結果，是的，他們是可重複的。我將測試的數量從1000個增加到10000個，結果現在更加流暢（請參閱下圖）。調整內部陣列的尖峯現在清晰可見。然而，圖表中的步驟仍然存在 - 這與預期的O（1）複雜性存在分歧，即如果忽略調整大小，數組插入應該是。

我也嘗試在每個Add操作之前觸發GC集合，並且圖保持完全相同。

至於關於創建委託對象的問題：我所有的代表（如ProfileAction）都是在一個完整的測試周期內保持分配的實例屬性，在這種情況下，10000個列表各有1000個添加操作。

Answer 1

好的，讓我們先看看圖片的簡單部分。峯值是由重新分配，複製和垃圾回收引起的 - 在那裏沒有什麼大驚喜。少數第一次添加到列表中的異常低時間很容易通過緩存局部性來解釋 - 儘管堆仍然適合整個內存，但內存訪問可以是隨機的，而仍然是非常低的延遲。一旦堆足夠大，並且數組長度值（以及列表計數值）與插入的值相距足夠遠，緩存局部性就會變得明顯 - 在我的計算機上使用32位x86代碼進行測試時，針對緩存局部性進行優化將使整個測試的性能提高四倍。然而，儘管這些效應很好地解釋了峯值本身以及每次峯值之後的操作需要比峯值之前花費更多時間的事實，但它們並沒有真正解釋隨後的趨勢 - 沒有明顯的理由說明爲什麼插入第600個峯值元素應該比插入第550個元素花費更長的時間（假設最後一個調整大小在512左右）。性能分析很好地表明，不斷的成本相當高，但並沒有顯示隨着時間的推移顯着增加的東西。

我的測試代碼被砍倒在非常基礎：

var collections = new List<int>[100000]; 

for (var i = 0; i < collections.Length; i++) 
{ 
    collections[i] = new List<int>();  
} 

for (var i = 0; i < 1024; i++) 
{ 
    for (var j = 0; j < collections.Length; j++) 
    { 
    collections[j].Add(i); 
    } 
} 

儘管這仍然是唯一的抽象是Add本身的走勢仍處於測試數據可見，雖然我必須指出，我的曲線遠沒有你的曲線那麼平滑，偏差也很大。典型的週期可能需要20毫秒左右，而尖峯高達5秒。

好的，有時間看看反彙編。我的測試代碼很簡單（只是內部循環體）：

002D0532 mov   eax,dword ptr [ebp-18h] 
002D0535 mov   ecx,dword ptr [eax+esi*4+8] 
002D0539 mov   edx,ebx 
002D053B cmp   dword ptr [ecx],ecx 
002D053D call  7311D5F0 

collections引用存儲在堆棧中。如預期的那樣，i和j都在寄存器中，事實上，j在esi中，這非常方便。所以，我們首先參考collections，加上j * 4 + 8以獲得實際的列表引用，並將其存儲在ecx（我們即將調用的方法中的this）中。 i存儲在ebx中，但必須移動到edx才能調用Add - 在兩個通用寄存器之間沒有大的轉移值，但是:)然後是簡單的樂觀空檢查，最後是調用本身。

首先要注意的是，沒有涉及分支，所以沒有分支錯誤預測。其次，我們有兩個內存訪問 - 第一個是在堆棧上，這是非常保證總是在緩存中。第二種情況更糟 - 這是我們獲取緩存局部性問題的地方。然而，這種延遲完全取決於數組的長度（和數量），所以應該（並且確實）與數組大小相關。

查看Add方法本身的時間:)請記住，ecx包含列表實例，而edx包含我們要添加的項目。

首先，有通常的方法序言，沒有什麼特別的。接下來，我們檢查陣列大小：

8bf1 mov esi, ecx 
8bfa mov edi, edx 
8b460c mov eax, DWORD PTR [esi+0xc] ; Get the list size 
8b5604 mov edx, DWORD PTR [esi+0x4] ; Get the array reference 
3bf204 cmp eax, DWORD PTR [edx+0x4] ; size == array.Length? 
741c je HandleResize ; Not important for us 

我們在這裏還有三個內存訪問。前兩個基本相同，因爲加載的值足夠緊密。該陣列只會在第一個陣列調整大小之前共置，這樣可以進一步提高前幾個插入的緩存性能。請注意，CPU並不能在這裏並行執行，但三次內存訪問仍應該只支付一次延遲成本。分支幾乎總是可以正確預測 - 只有在達到數組大小後纔會採用，之後我們爲每個列表執行一次相同的分支。

兩件保留：將項目本身，並更新列表的內部版本（失敗名單上的任何正在進行枚舉）：

_items[_size++] = item; 
_version++; 

它在裝配:)

有點wordier

8b5604 mov edx, DWORD PTR [esi+0x4] ; get the array reference again 
8b4e0c mov ecx, DWORD PTR [esi+0xc] ; ... and the list size 
8d4101 lea eax, [ecx+0x1] ; Funny, but the best way to get size + 1 :) 
89460c mov DWORD PTR [esi+0xc], eax ; ... and store the new size back in the list object 
3b4a04 cmp ecx, DWORD PTR [edx+0x4] ; Array length check 
7318 jae ThrowOutOfRangeException ; If array is shorter than size, throw 
897c8a08 mov DWORD PTR [edx+ecx*4+0x8], edi ; Store item in the array 
ff4610 inc DWORD PTR [esi+0x10] ; Increase the version 
; ... and the epilogue, not important 

就是這樣。我們有永遠不會被採用的分支（假設單線程;我們已經檢查過數組大小）。我們有很多訪問：四個與列表本身相關（包括兩個更新），另外兩個（包括一個更新）。現在，雖然列表中沒有緩存未命中的原因（它幾乎總是已經加載），但由於更新而導致失效。相比之下，在我們的場景中，數組訪問總是會導致緩存未命中，唯一的例外是在第一個數組調整之前。事實上，你可以首先看到沒有緩存未命中（數組和對象同時存在，很小），然後有一個未命中（仍然並置，但超出緩存行的項），然後是兩個（超出緩存行的長度和項訪問）。

這當然是有趣的（並且可以從微小的位受益於手動優化：P），但它再次只給我們分析數據上的「階梯」。重要的是，不涉及分配，所以沒有GC。

所有這一切，我會得出結論，List.Add確實是O（1）時，不需要數組調整大小。對於非常小的數組（以及與它們的引用同名的數組），還有一些額外的優化使事情變得更快，但這並不重要。

因此，您在概要分析數據中看到的趨勢必須是環境或與概要分析本身直接相關，或者只是一種嚴格選擇的平均方法。例如，如果我100個000列表運行以下命令：

1. 添加第一個550個項目
2. 添加其他100個項目
3. 而另一家100個項目

有時間2之間的變化和3取決於，但沒有趨勢 - 2的速度越快越好，3越快越快（在約400ms的時間跨度上約2ms的差異，大約0.5％的偏差）。然而，如果我用2100件產品進行「熱身」，隨後的步驟幾乎只需要一半的時間。更改列表數量並不會對每個集合產生明顯影響（只要所有內容都適合您的物理內存，當然:)）。

好的，即使在發佈模式下運行在調試器外部，只需一個簡單的Stopwatch即可看到，而且結果數據採樣簡單。所以我們可以排除分析效果和統計錯誤。

但是這可能是環保事業？

• GC根本不參與，在數組之外調整大小。沒有分配，並且分析器非常清楚在調整大小之間沒有GC發生的事實（儘管這對於併發GC來說是有限的價值:)）。調整GC設置會使速度變慢，但同樣只會影響調整大小尖峯及其周圍環境。最重要的是，列表的數量（以及堆大小）對趨勢沒有任何影響，如果GC是原因，這將是相當令人驚訝的。
• 堆是零散的，但非常有序。這使得重定位在內存壓力下具有較少的開銷，但同樣只會影響數組的大小調整。無論如何，這並不令人感到意外，事實上也是有據可查的。

因此，看着這一切...我不知道爲什麼這個趨勢存在。但是，請注意，趨勢絕對不是線性的 - 隨着您增加列表大小，增加速度會迅速下降。從大約15k項目開始，趨勢完全消失，所以Add確實是O（1），不包括數組大小調整 - 它只是在某些大小下有些怪異行爲:)在這種情況下，結果與僅基於緩存局部性的預測100％一致。這似乎表明調整大小和GCing模式對通常緩存算法的效率有很大的影響（至少在我的CPU上 - 這會有很大的變化，我會重新考慮）。還記得我們談到整個Add操作過程中發生的緩存未命中嗎？有一個技巧 - 如果我們可以在兩個循環之間保持足夠的高速緩存行，緩存缺失將會經常避免;如果我們假設64字節的緩存行和最佳的緩存失效算法，那麼您將在List成員訪問和數組長度訪問中沒有錯過，每個數組只有一次錯過16次添加。我們根本不需要陣列的其餘部分！還有一些你需要的其他緩存行（例如列表實例），但這些數組是迄今爲止最重要的。

現在，讓我們做數學題。十萬個集合，2 * 64B高速緩存的每一在最壞的情況下增加了12個MIB和我有緩存的10 MIB對我 - 我可以幾乎適合在高速緩存中的所有相關陣列數據！當然，我並不是唯一使用該緩存的應用程序（和線程），所以我們可以預期翻轉點會低於理想值 - 讓我們看看改變收集量會如何改變我們的結果。

列出預先分配給8000項（32 KB），增加2000項，100，100

Lists A  B C 
400  18  1 1 
800  52  2 2 
1600 120  6 6 
3200 250  12 12 
6400 506  25 25 
12800 1046 52 53 
25600 5821 270 270 

哈！非常好看。時序很好地隨着列表數量的增加而線性增加，直到最後一項 - 這就是我們的緩存用完的時間。這是某處大約緩存使用總量的3-8 MIB - 最有可能忽略的是還需要在操作系統或CPU的一部分緩存，或一些優化，以防止我霸佔了整個高速緩存或某事的一些重要的事情了我的結果:)

的在非常小的列表計數的輕微未線性度是最有可能與下級緩存的緩慢溢出 - 400舒適適合在我的L2高速緩存，800已經溢出了一下，1600相當多的和當我們達到3200時，L2緩存幾乎可以完全忽略。

而對於我們最後的檢查，同樣的場景，但增加4000項，而不是2000：

Lists A  B C 
400  42  1 1 
800  110  3 2 
1600 253  6 6 
3200 502  12 12 
6400 1011 25 25 
12800 2091 52 53 
25600 10395 250 250 

正如你所看到的，項目數有（每件）的插入時間沒有任何作用，整個趨勢就消失了。

所以，你有它。這種趨勢是由GC間接引起的（通過代碼中的次優分配和GC中壓縮模式來破壞緩存局部性）以及直接緩存溢出。如果產品數量較少，則更有可能現在任何給定的所需內存都將保存在緩存中。當數組需要調整大小時，大部分緩存的內存幾乎毫無價值，並且會慢慢失效並替換爲更有用的內存 - 但整個內存使用模式與CPU的優化內容相距甚遠。相比之下，通過保持數組的預先分配，我們確保一旦我們在內存中擁有列表，我們也會看到數組長度（獎金1），並且已經指向數組末尾的高速緩存行對於一些循環很有用（獎金2）。由於沒有數組大小調整，這些對象都不需要在內存中移動，並且有很好的託管。

Answer 2

不C＃存儲陣列超過512個多頭（4096個字節）不同更大？

不會。當總大小爲（IIRC）84kB或更多時，會出現這種情況：使用大對象堆（不是壓縮或分代）。

但是：

創建1000名列表和添加每一個項目，每列表的大小。

給予每次測試〜5ms左右的時間。 Windows調度器增量大於此值（根據版本和版本，實際值從40ms到100ms不等）。你能看到調度程序執行線程切換嗎？

建議您嘗試將每個尺寸至少運行250ms以平衡這些效果。

編輯另外，正如Lasse對問題的評論所指出的：這可能是GC。爲了消除你的時間，在大小循環的開始，但在開始時鐘之前，強制GC。還要監視GC性能計數器。