通過優秀的設計減少緩存未命中數

Question

如何在設計C++程序時減少可能的緩存未命中數？

內聯函數是否每次都有幫助？或者只有當程序是CPU有界的時候（即程序是面向計算的而不是面向I/O的）纔是好的？

Answer 1

以下是我在處理這類代碼時需要考慮的一些事情。

• 考慮您是否想要「結構的數組」或「結構數組」。你想要使用的將取決於數據的每一部分。
• 嘗試將結構保持爲32個字節的倍數，以便均勻地打包緩存行。
• 在冷熱元素中對數據進行分區。如果你有一組o類的對象，並且你經常一起使用ox，oy，oz，但偶爾需要訪問oi，oj，那麼請考慮將ox，oy和oz放在一起，然後移動i，j和k部分到平行的腋窩數據結構。
• 如果您有多維數據數組，然後使用通常的行順序佈局，則沿着首選維度掃描時訪問速度會非常快，而在其他位置掃描時會非常緩慢。沿着任何維度遍歷時，沿着space-fillingcurve映射它將有助於平衡訪問速度。 （阻塞技術是相似的 - 它們只是具有較大基數的Z階。）
• 如果您必須導致緩存未命中，請嘗試儘可能多地使用該數據來分攤成本。
• 你在做什麼多線程？注意緩存一致性協議的減速。填充標誌和小計數器，以便它們位於單獨的緩存行中。
• 英特爾的SSE提供了一些預取內在函數，前提是您知道提前訪問的內容。

Answer 2

允許CPU有效地預取數據。例如，您可以減少按行處理多維數組的數量緩存未命中，而不是按列，展開循環等。

這種優化取決於硬件架構，因此您最好使用某種平臺特定的分析器，如英特爾VTune檢測緩存可能存在的問題。

Answer 3

有一個非常不錯的視頻由Herb薩特說提到這個話題here

對於數據綁定操作

1. 使用數組&載體在列表，地圖由&套

2. 過程列上的行

Answer 4

避免在沒有必要時使用動態內存。使用新的，刪除，智能指針等，往往會將你的程序數據傳播到內存中。這不好。如果您可以將大部分數據保存在一起（例如通過在堆棧中聲明對象），緩存肯定會更好。

Answer 5

內聯函數運行會危害指令緩存。如果內存沒有被綁定，那麼就不太可能產生太多（如果有）差異。

與往常一樣，任何優化都應該通過分析而不是直覺告知。更不用說，您需要了解剖析器告訴您的內容，這意味着熟悉彙編語言以及您正在優化的plaftorm的特定特性。

現在有點老了，但邁克Abrash的「圖形編程黑皮書」仍然有很多很好的一般建議。

Answer 6

另外，如果你在做C++和多線程，你需要考慮每個處理器的緩存上的虛假共享，局部性和數據的熱度。這可以造成很大的差異。尤其在多線程計算中，採用LIFO方式的計算比以FIFO方式進行計算更有效，但它在單處理器體系結構中也是有效的。