設計代碼以適應CPU緩存？

Question

寫模擬時，我的好友說他喜歡嘗試編寫足夠小的程序以適應緩存。這有什麼真正的意義？我知道緩存比RAM和主內存更快。是否可以指定您希望程序從緩存運行或至少將變量加載到緩存中？我們正在編寫模擬程序，因此任何性能/優化增益都是巨大的優勢。

如果您知道任何解釋CPU緩存的好鏈接，請指出該方向。

Answer 1

至少在典型的臺式機CPU中，您不能直接指定有關緩存使用情況的信息。儘管如此，您仍然可以嘗試編寫緩存友好的代碼。在代碼方面，這通常意味着展開循環（僅用於一個明顯的示例）很少有用 - 它擴展了代碼，現代CPU通常會最小化循環開銷。您通常可以在數據方面做更多的工作，以改善參考的局部性，防止錯誤共享（例如，兩個常用的數據片段將嘗試使用高速緩存的相同部分，而其他部分仍未使用）。

編輯（使一些點位更清楚了）：

一個典型的CPU有許多不同的緩存。現代臺式機處理器通常至少具有2級並且通常3級緩存。通過（至少接近）普遍認同，「1級」是與處理元件「最接近」的高速緩存，並且數字從那裏上升（2級是下一級，3級之後等）。

大多數情況下（至少）1級高速緩存分爲兩部分：指令高速緩存和數據高速緩存（英特爾486幾乎是我意識到的唯一例外，其中一個高速緩存用於指令和數據 - - 但它是如此徹底的過時，可能不值得思考）。

在大多數情況下，緩存被組織爲一組「行」。緩存的內容通常是一次讀取，寫入和跟蹤一行。換句話說，如果CPU要使用來自緩存行的任何部分的數據，那麼將從下一個較低級別的存儲中讀取整個緩存行。靠近CPU的緩存通常較小，緩存線較小。

這個基本的體系結構導致了高速緩存的大部分編寫代碼的特性。儘可能地，你想要將某些內容讀入緩存中，然後用它去做所有事情，然後轉向其他的東西。

這意味着當您處理數據時，通常讀取較少量的數據（足夠小以適應緩存），儘可能多地處理該數據，然後轉到下一塊數據。像Quicksort這樣的算法可以快速將大量輸入分解爲逐漸變小的數據，這或多或少會自動執行，因此它們往往相當緩存友好，幾乎不考慮緩存的精確細節。

這也會影響您如何編寫代碼。如果你有這樣一個循環：

for i = 0 to whatever 
    step1(data); 
    step2(data); 
    step3(data); 
end for 

你通常會更好串儘可能多的措施一起，你可以最多，將適合在高速緩存中的量。一旦你溢出緩存，性能可能會急劇下降。如果上述步驟3中的代碼是足夠大，它不適合到緩存中，你通常會更好斷開回路成兩片這樣的（如果可能）：

for i = 0 to whatever 
    step1(data); 
    step2(data); 
end for 

for i = 0 to whatever 
    step3(data); 
end for 

循環展開是一個頗受爭議的話題。一方面，它可以導致代碼的更多的CPU友好，減少了循環本身執行的指令的開銷。同時，它可以（並且通常會）增加代碼大小，所以它相對緩存不友好。我自己的經驗是，在合成基準測試中，往往對真正的大量數據進行非常少量的處理，從循環展開中獲得很多。在更實用的代碼中，如果您傾向於對單個數據片進行更多處理，您的獲益就會少得多 - 並且導致嚴重性能損失的緩存溢出並不是特別罕見。

數據緩存也被限制在尺寸。這意味着您通常希望您的數據儘可能密集地包裝，以便儘可能多的數據適合緩存。僅舉一個明顯的例子，用指針連接在一起的數據結構需要在計算複雜性方面獲得相當多的補償，以彌補這些指針所使用的數據緩存空間的數量。如果您要使用鏈接的數據結構，通常至少要確保您將相對較大的數據鏈接在一起。然而，在很多情況下，我發現我最初學習的用於將數據適配到微小處理器中的小技巧已經學會了幾十年（大部分）已經過時了幾十年的技巧，在現代處理器上效果不錯。目的是讓更多的數據放入緩存而不是主內存中，但效果幾乎相同。在相當多的情況下，你能想到的CPU指令，近免費的，並且執行的整體速度是由帶寬，緩存（或主存儲器），所以額外的處理解壓數據治理從密集的格式，作品出來你的青睞。當你處理的數據足夠多時，這種情況尤其會發生，因爲總體速度將受到主內存帶寬的控制。在這種情況下，您可以執行lot指令來節省一些內存讀取，並且仍然會提前。

並行處理會加劇這個問題。在許多情況下，重寫代碼以允許並行處理可能導致性能上的增益，甚至有時甚至會導致性能損失。如果總體速度受CPU到內存帶寬的控制，擁有更多核心競爭該帶寬不太可能產生任何好處（並且可能造成實質性傷害）。在這種情況下，使用多個內核來提高速度往往歸結爲更緊密地打包數據，並利用更多的處理能力來分解數據，所以真正的速度增益來自減少消耗的帶寬，而額外的核心不會浪費時間從密集格式解壓縮數據。

可以並行編碼產生的另一個基於高速緩存的問題的共享變量（和僞共享）。如果兩個（或更多）內核需要寫入內存中的相同位置，則保存該數據的高速緩存行最終可能會在內核之間來回穿梭，從而使每個內核都能訪問共享數據。結果通常是並行運行速度慢於串行運行（即單個內核）的代碼。這種被稱爲「虛假共享」的變體，其中不同核心上的代碼正在寫入單獨的數據，但是不同核心的數據最終在同一緩存行中。由於緩存控制數據完全依據整行數據，因此數據在覈心之間來回移動，導致完全相同的問題。

Answer 2

如果我是你，我會確保我知道這部分代碼是熱點，我定義爲

• 緊密循環不包含任何函數調用，因爲如果它調用的任何函數，那麼PC將花費大部分時間在該功能上，該功能佔據了執行時間的很大一部分（例如> = 10％），您可以從分析器中確定該時間的大部分時間（
• ）。 （我只是手動採樣堆棧。）

如果你有這樣一個熱點，那麼它應該適合緩存。我不確定你如何告訴它這樣做，但我懷疑它是自動的。

Answer 3

下面是一個非常好的paper鏈路上通過的Christer愛立信（戰爭I/II的神/ III名望）高速緩存/內存優化。這已經有幾年了，但仍然非常相關。

Answer 4

大多數C/C++編譯器傾向於以優化尺寸，而不是爲「速度」。也就是說，由於緩存效應，較小的代碼通常比展開的代碼執行得更快。

Answer 5

一個有用的文件，會告訴你，比你曾經想知道的高速緩存是由What Every Programmer Should Know About Memory烏利齊·德雷珀。 Hennessey涵蓋了非常徹底。克里斯特和麥克阿克頓也寫了一些關於這方面的好東西。

我覺得你應該比我的經驗更關心數據緩存，比指令緩存—，dcache錯過更頻繁，更痛苦，更有用的修復。

Answer 6

晴這將作爲一個佔位符，直到我的時間做這個專題公正，但我想和大家分享我認爲是一個真正的突破性里程碑 - 引入新的英特爾Hazwell微處理器專用的位操作指令。

它變得非常明顯，當我寫到這裏的一些代碼在計算器上扭轉位在4096位陣列，引入個人電腦後30+年，微處理器只是不要投入太多的關注或資源位，我希望會改變。特別是，我很想看看，對於初學者來說，bool類型在C/C++中變成了實際的位數據類型，而不是當前浪費的浪費字節。

UPDATE：2013年12月29日

我最近有機會，以優化其在毫秒粒度跟蹤512個不同資源用戶的需求的系統上的環形緩衝器。有一個計時器每隔幾毫秒觸發一次，它添加了最新切片的資源請求的總和，並減去了第1,000時間片的請求，包括現在1,000毫秒的資源請求。

頭，尾巴矢量在內存中彼此相鄰，除非首先是頭部，然後是尾部包裹並重新開始在數組的開頭。然而，（滾動式）摘要片卻處於一個固定的，靜態分配的數組中，與其中的任何一個都不是特別接近，甚至沒有從堆中分配。

思考這個問題，研究代碼幾個細節引起了我的注意。

1. 該被進入的需求的代碼相鄰行被添加到頭部，並在同一時間的摘要切片，右邊彼此相鄰。

2. 當計時器所觸發，尾巴被減去摘要片的，結果被留在總結片，如你所期望

3. 調用的時候，計時器所觸發的所有先進的第2個功能服務於戒指的指針。特別.... 團長覆蓋了尾部，從而佔據相同的存儲器位置 新尾佔用的下一個512個存儲位置，或纏繞

4. 用戶希望在要求的數量更多的靈活性被管理，從512到4098，或者更多。我覺得最強大，最笨的方法就是將1000個時間片和摘要片一起作爲一個連續的內存塊分配，這樣對於摘要片最終會成爲一個不同的長度將是不可能的比其他1,000個時間片。

5. 鑑於上述情況，我開始懷疑，如果我能，如果獲得更高的性能，而不必摘要切片保持在一個位置，我有頭和尾之間爲「漫遊」，所以總是對的在頭部旁邊添加新的需求，並在計時器開啓時​​尾部旁邊，並且必須從摘要中減去尾部值。

我這樣做了，但後來在這個過程中發現了一些額外的優化。我更改了計算滾動摘要的代碼，以便將結果留在尾部，而不是摘要片段。爲什麼？因爲下一個函數正在執行memcpy（）來將摘要切片移入剛剛由尾部佔據的內存中。 （怪異但真實，尾巴領先頭部直到環繞它結束時）。通過將總和的結果留在Tail中，我不必執行memcpy（），我只需將pTail分配給pSummary。

以類似的方式，新的頭部佔據了已經陳舊摘要片的老內存的位置，如此反覆，我剛分配到pSummary PHEAD，並清零所有的值與memset的零。尾部是引導環到達尾部的方式（實際上是一個鼓，512個音軌寬），但我只需要將其指針與一個常量pEndOfRing指針進行比較以檢測該條件。所有其他指針都可以被賦值爲它之前的向量的指針值。 IE：我只需要1：3指針的條件測試來正確包裝它們。

初步設計已經使用字節整數最大化緩存使用，但是，我可以放寬這個限制 - 滿足用戶要求，以每毫秒處理每用戶更高的資源數 - 使用無符號的短褲和STILL 雙重性能 ，因爲即使有3個512個無符號短路的相鄰向量，L1緩存的32K數據緩存也可以容易地保存所需的3,720個字節，其中2/3個字節位於剛纔使用的位置。只有尾部，摘要或頭部包裝的三個中的任何一個在8MB L3cache中的任何重要「步驟」之間分開時纔是其中之一。

此代碼的總運行時內存佔用量小於2MB，因此它完全從片上高速緩存運行，甚至在具有4個內核的i7芯片上，該進程的4個實例可以運行而不會發生任何降級在性能方面，5個進程運行時總吞吐量略有提高。這是關於緩存使用情況的Opus Magnum。

Answer 7

更新：2014年1月13日 根據這一高級芯片設計，高速緩存未命中現在是在代碼的性能絕對主導地位的因素，所以我們基本上所有的方式回到了80年代中期，快速286芯片在加載，存儲，整數運算和緩存未命中的相對性能瓶頸方面。

A Crash Course In Modern Hardware by Cliff Click @ Azul 。 。 。 。 。

---我們現在返回到你的定期節目---

有時候一個例子是比如何做一個更好的描述。本着這種精神，我特別成功地舉例說明了如何更改一些代碼以更好地使用芯片緩存。一段時間以前，這是在486 CPU上完成的，後者被遷移到第一代奔騰CPU。對性能的影響是相似的。

實施例：下標映射

下面是我用於將數據裝配到芯片的高速緩存，其具有通用效用的技術的一個例子。

我有一個雙浮動向量爲1,250元件長，這與非常長尾巴的流行病學曲線。曲線中「有趣」的部分只有大約200個獨特的值，但我不希望用雙面if（）測試來弄亂CPU的管道（因此長尾巴可以用作下標，值的蒙特卡羅代碼將吐出），並且我需要在代碼中的「熱點」內的十幾個其他條件測試的分支預測邏輯。

我定居在哪裏使用8位整數的向量作爲下標到雙載體，其餘縮短至256種元素的方案。小的整數在128之前都有相同的值，在零之前128，在零之後有128，因此除了中間的256值之外，它們都指向雙向量中的第一個或最後一個值。

這縮水存儲需求至2k雙打，而對於8位標1250個字節。這將10000個字節縮減到3,298。由於該程序花費了90％以上的時間在這個內部循環中，因此2個向量永遠不會從8k數據緩存中排出。該計劃立即使其性能翻倍。這個代碼在計算100萬按揭貸款的OAS價值的過程中已經達到了1000億次。由於很少涉及曲線的尾部，所以很有可能只有微小的int向量中的中間200-300個元素實際上保存在緩存中，而160-240箇中間的雙元代表1/8的百分比利益。這是一個顯着的性能提高，在一個下午完成了一個我花了一年時間優化的項目。

我同意傑裏，因爲它一直是我的經驗也，謂傾斜代碼對指令緩存是幾乎沒有對數據高速緩存/ s的優化成功。這是我認爲AMD的普通緩存不如英特爾獨立的數據和指令緩存有用的原因之一。 IE：你不希望指令佔用緩存，因爲它不是很有用。部分原因是因爲CISC指令集最初是爲了彌補CPU和內存速度之間的巨大差異而創建的，除了80年代後期出現畸變以外，這幾乎總是如此。

另一個我喜歡使用數據緩存和野蠻指令緩存的最受歡迎的技術是在結構定義中使用了大量的位元，並且通常使用最小的可能數據大小。爲了屏蔽4位整數來保存一年的月份，或9位來保存一年中的某一天，等等，要求CPU使用掩碼來屏蔽這些位正在使用的主機整數，這會縮小數據，有效地增加了緩存和總線的大小，但需要更多指令。雖然這種技術產生的代碼在綜合基準測試中表現不佳，但在繁忙的系統上，用戶和進程正在爭奪資源，它的功能奇妙。