什麼原因導致這種奇怪的性能下降，中等數量的項目？

我剛剛閱讀了由Rico Mariani提供的article，它考慮到不同的局部性，體系結構，對齊和密度對內存訪問性能的影響。什麼原因導致這種奇怪的性能下降，中等數量的項目？

作者構建了一個不同大小的數組，其中包含一個帶有int有效載荷的雙向鏈表，該數據被混洗到一定比例。他試驗了這個清單，並在他的機器上發現了一些一致的結果。

引用的結果表的一個：

Pointer implementation with no changes 
sizeof(int*)=4 sizeof(T)=12 
    shuffle 0% 1% 10% 25% 50% 100% 
    1000 1.99 1.99 1.99 1.99 1.99 1.99 
    2000 1.99 1.85 1.99 1.99 1.99 1.99 
    4000 1.99 2.28 2.77 2.92 3.06 3.34 
    8000 1.96 2.03 2.49 3.27 4.05 4.59 
    16000 1.97 2.04 2.67 3.57 4.57 5.16 
    32000 1.97 2.18 3.74 5.93 8.76 10.64 
    64000 1.99 2.24 3.99 5.99 6.78 7.35 
    128000 2.01 2.13 3.64 4.44 4.72 4.80 
    256000 1.98 2.27 3.14 3.35 3.30 3.31 
    512000 2.06 2.21 2.93 2.74 2.90 2.99 
1024000 2.27 3.02 2.92 2.97 2.95 3.02 
2048000 2.45 2.91 3.00 3.10 3.09 3.10 
4096000 2.56 2.84 2.83 2.83 2.84 2.85 
8192000 2.54 2.68 2.69 2.69 2.69 2.68 
16384000 2.55 2.62 2.63 2.61 2.62 2.62 
32768000 2.54 2.58 2.58 2.58 2.59 2.60 
65536000 2.55 2.56 2.58 2.57 2.56 2.56

作者解釋：

這是基線測量。你可以看到這個結構是一個不錯的圓12字節，它將在x86上很好地對齊。看着第一列，沒有任何洗牌，不出所料，事情越來越糟，因爲數組越來越大，直到最後緩存沒有什麼幫助，而且你有最糟糕的情況發生，這大概是2.55ns平均每個項目。

可是，我很奇怪，可以看到周圍的32K項目：

洗牌的結果是不正是我的預期。在小尺寸時，它沒有區別。我期待這一點，因爲基本上整個表都在緩存中保持熱點，所以局部性並不重要。然後，隨着桌子的增長，你會發現洗牌對大約32000個元素有很大的影響。這是384k的數據。可能是因爲我們已經超過了256k的限制。

現在奇怪的是：在這之後，洗牌成本實際上下降了，直到後來它幾乎沒什麼問題。現在我可以理解，在某種程度上洗牌或不洗牌真的應該沒有什麼區別，因爲陣列非常龐大，運行時很大程度上受內存帶寬的限制，無論順序如何。但是......中間有些地方非地方性的成本實際上比最終的成本要差得多。

我期望看到的是，洗牌導致我們儘快達到最大程度的惡劣程度並留在那裏。實際上發生的事情是，在中等大小的非地區似乎會導致事情變得非常糟糕......我不知道爲什麼:)

所以問題是：什麼可能導致這種意外的行爲？

我已經想了一段時間，但沒有找到好的解釋。測試代碼對我來說看起來很好。我不認爲CPU分支預測是這種情況下的罪魁禍首，因爲它應該比32k項目早得多，並且顯示出更小的峯值。

我已經在我的盒子上確認了這種行爲，它看起來非常完全一樣。

我想這可能是由CPU狀態的轉發引起的，所以我改變了行和/或列的生成順序 - 幾乎沒有輸出差異。爲了確保，我爲更大的連續樣本生成了數據。爲了方便觀看，我把它轉換爲Excel：

enter image description here