目錄
Part2. Source Code Tuning For CPU
數據驅動優化
7 CPU Front-End Optimizations
7.1 Machine code layout ? ?//機器碼布局
7.2 Basic Block
7.3 Basic block placement
7.4 Basic block alignment
7.5 Function splitting ? ?//函數拆分
7.6 Function grouping ? ?//函數分組
7.7 Profile Guided Optimizations ? ?//基于性能分析的優化
7.8 Optimizing for ITLB
7.9 Chapter Summary
8 CPU Back-End Optimizations
8.1 Memory Bound ? ?//內存受限
8.2 Core Bound ? ?//核心受限
8.3 Chapter Summary
9 Optimizing Bad Speculation
9.1 Replace branches with lookup ? ?//將分支替換為查找表
9.2 Replace branches with predication
9.3 Chapter Summary
10 Other Tuning Areas
10.1 Compile-Time Computations ? ?//編譯時計算
10.2 Compiler Intrinsics ? ?//編譯器內置函數
10.3 Cache Warming ? ?//緩存預熱
10.4 Detecting Slow FP Arithmetic
10.5 System Tuning
11 Optimizing Multithreaded Applications
11.1 Performance Scaling And Overhead ? ?//性能擴展和開銷
11.2 Parallel Efficiency Metrics ? ?//并行效率指標
11.3 Analysis With Intel VTune Profiler
11.4 Analysis with Linux Perf
11.5 Analysis with Coz
11.6 Analysis with eBPF and GAPP
11.7 Detecting Coherence Issues
11.8 Chapter Summary
Epilog
Appendix A. Reducing Measurement Noise
Appendix B. The LLVM Vectorizer
Part2. Source Code Tuning For CPU
在第二部分中，我們將了解如何使用CPU監測功能（參見第6節）來找到可以針對CPU執行調優的代碼部分。對于像大型分布式云服務、科學高性能計算軟件、AAA游戲等性能關鍵應用程序來說，了解底層硬件如何工作非常重要。如果在開發過程中沒有關注硬件，那將是一次從一開始就失敗的嘗試。
在對性能至關重要的工作負載進行處理時，傳統的算法和數據結構并不總是表現良好。例如，鏈表在大多數情況下已經被“扁平”數據結構所取代。傳統上，鏈表的每個新節點都是動態分配的。除了涉及許多昂貴的內存分配操作外，這可能導致列表的所有元素在內存中分散存儲。遍歷這樣的數據結構需要為每個元素進行隨機內存訪問。盡管算法復雜度仍然是O(N)，但實際上，執行時間比普通數組要差得多。某些數據結構（如二叉樹）具有天然的鏈表表示形式，因此可能會誘使我們以指針追蹤的方式實現它們。然而，更高效的“扁平”版本的這些數據結構也存在，比如boost::flat_map、boost::flat_set。
鏈表優于數組的原因：
鏈表相對于數組具有一些優點，這些優點使得它在某些情況下比數組更加有效或適用：
1. 動態大小：鏈表的大小可以動態地增長或縮小，不需要提前分配固定大小的存儲空間。這使得鏈表對于處理需要頻繁插入或刪除操作的情況更加靈活和高效。
2. 插入和刪除操作：在鏈表中進行插入和刪除元素的操作較為高效。相比之下，對于數組而言，在插入或刪除元素時通常需要移動其他元素，這可能會導致較高的時間復雜度。
3. 內存管理：鏈表的節點可以根據需要進行動態分配和釋放，因此可以更好地管理內存。相比之下，數組需要一次性分配固定大小的連續內存塊。
4. 靈活性：鏈表可以具有不同的結構，如單向鏈表、雙向鏈表、循環鏈表等。這使得鏈表在某些問題的解決方案中更加靈活和多樣化。
盡管鏈表有以上優點，但也存在一些缺點。鏈表的缺點包括無法通過索引直接訪問元素、占用更多的內存空間（由于存儲了指向下一個節點的指針）和遍歷時需要更多的時間（需要通過指針逐個訪問節點）。因此，在選擇數據結構時，需要根據具體情況和需求權衡利弊。
即使您選擇的算法在特定問題上表現最好，但對于您特定的情況可能并非最佳選擇。例如，二分查找在已排序數組中查找元素是最優的。然而，該算法通常受到分支預測錯誤的影響，因為每次測試元素值時，有50%的機會為真。這就是為什么在小型（少于20個元素）整數數組中，線性搜索通常更好的原因。
性能工程是一門藝術，就像任何藝術一樣，可行的場景是無窮無盡的。本章試圖解決與CPU微架構相關的優化問題，而不試圖覆蓋所有可能的優化機會。然而，我認為至少需要提到一些高級優化方法：
? 如果程序使用解釋型語言編寫（如Python、JavaScript等），可以將其性能關鍵部分重寫為開銷較小的語言。
? 分析程序中使用的算法和數據結構，看看是否可以找到更好的替代方案。
? 調整編譯器選項。檢查是否至少使用了以下三個編譯器標志：-O3（啟用與機器無關的優化）、-march（針對特定CPU代數啟用優化）、-flto（啟用程序間優化）。
? 如果問題可以高度并行化計算，可以使用線程，或者考慮在GPU上運行。
? 使用異步IO來避免在等待IO操作時發生阻塞。
? 利用更多的RAM來減少CPU和IO的使用量（記憶化、查找表、數據緩存、壓縮等）。
以上是一些高級的性能優化方法，但請注意，在優化代碼性能時并非適用于所有情況。具體的優化策略應該根據實際情況和需求進行權衡和選擇。
數據驅動優化
“數據驅動”優化是調優中最重要的技術之一，它基于對程序正在處理的數據進行內省。該方法側重于數據的布局以及在程序中如何進行轉換。一個經典的例子是Structure-Of-Array到Array-Of-Structures (SOA-to-AOS)的轉換，如圖14所示。
Listing 14 SOA to AOS transformation.
//SOA
struct S {
int a[N];
int b[N];
int c[N];
// many other fields
};
<=>
//AOS
struct S {
int a;
int b;
int c;
// many other fields
};
S s[N];對于哪種布局更好的問題的答案取決于代碼如何訪問數據。如果程序在數據結構上進行迭代并且僅訪問字段b，則SOA更好，因為所有內存訪問都是順序的（空間局部性）。然而，如果程序在數據結構上進行迭代并且對對象的所有字段（即a、b、c）執行過多的操作，則AOS更好，因為結構的所有成員很可能位于同一緩存行中。它還能更好地利用內存帶寬，因為需要讀取的緩存行數量更少。
這類優化基于對程序所操作的數據、數據的布局以及相應的修改進行了解。
個人經驗：事實上，我們可以說，在某種程度上，所有的優化都是數據驅動的。即使在下一節中我們將要介紹的轉換也是基于對程序執行的一些反饋信息：函數調用計數、性能分析數據、性能計數器等。
另一個非常重要的數據驅動優化例子是"小尺寸優化"。其思想是預先分配一定量的內存給容器，以避免動態內存分配。這在小型和中型容器中特別有用，當元素的上限可以被很好預測時。這種方法已成功應用于整個LLVM基礎設施，并提供了顯著的性能優勢（例如搜索SmallVector）。相同的概念也在boost::static_vector中實現。
顯然，這并不是完整的數據驅動優化列表，但正如之前所述，沒有試圖列出所有的優化。讀者可以在easyperf博客上找到更多的示例。
現代CPU是非常復雜的設備，幾乎不可能預測某些代碼片段的性能。CPU對指令的執行取決于許多因素，而涉及的部件數量對人類來說太大了，無法完全了解。幸運的是，通過我們在第6節中討論的所有性能監控功能，我們可以知道從CPU的角度看，你的代碼是什么樣子。
請注意，你實施的優化可能對每個平臺都不一定有益。例如，循環阻塞非常依賴于系統中內存層次結構的特性，尤其是L2和L3緩存的大小。因此，針對具有特定L2和L3緩存大小的CPU進行調優的算法可能對具有較小緩存的CPU效果不好。重要的是要在將應用程序運行的平臺上進行測試更改。
接下來的三章以最便于與TMA（參見第6.1節）一起使用的方式組織。這種分類背后的思想是提供一種檢查清單，工程師可以使用它來有效地消除TMA揭示的低效率。再次強調，這并不是一個完整的轉換列表，因為人們可以提出更多的轉換。然而，這是一個試圖描述典型轉換的嘗試。
7 CPU Front-End Optimizations
?CPU前端（FE）組件在第3.8.1節中進行了討論。大多數情況下，CPU FE的低效率可以描述為后端等待執行指令，但FE無法提供指令的情況。結果是，在沒有執行任何實際有用工作的情況下浪費了CPU周期。由于現代處理器是4寬度（即，它們每個周期可以提供四個微操作），可能出現未填充所有四個可用槽的情況。這也可能是執行效率低下的來源。實際上，IDQ_UOPS_NOT_DELIVERED性能事件記錄了由于前端停頓而未利用的可用槽位數。TMA使用此性能計數器的值來計算其“前端邊界”指標。
FE無法向執行單元傳遞指令的原因有很多。但通常歸結為緩存利用和無法從內存中提取指令的問題。只有當TMA指向較高的“前端邊界”指標時，才建議開始優化針對CPU FE的代碼。
個人經驗：大多數實際應用程序將會出現一個非零的“前端邊界”指標，這意味著一定比例的運行時間將會在次優的指令獲取和解碼上浪費。幸運的是，這通常低于10%。如果你看到“前端邊界”指標在20%左右，那么一定值得花時間進行優化。
7.1 Machine code layout ? ?//機器碼布局
當編譯器將您的源代碼轉換為機器代碼（二進制編碼）時，它會生成一系列的字節序列。例如，對于以下的C代碼：
if (a <= b)
c = 1;編譯器會產生如下的匯編代碼:
; a is in rax
; b is in rdx
; c is in rcx
cmp rax, rdx
jg .label
mov rcx, 1
.label:匯編指令將按順序進行編碼，并在內存中進行布局：
400510 cmp rax, rdx
400512 jg 40051a
400514 mov rcx, 1
40051a ...這就是所謂的機器碼布局。請注意，對于同一個程序，可以以許多不同的方式進行代碼布局。例如，給定兩個函數：foo和bar，我們可以將bar放在二進制文件中先于foo，或者反過來改變它們的順序。這會影響指令在內存中的偏移位置，進而影響生成的二進制代碼的性能。在本章的其余部分，我們將研究一些常見的機器碼布局優化技巧。
7.2 Basic Block
基本塊（Basic Block）是一系列指令的序列，具有單一入口和單一出口。圖40展示了一個簡單的基本塊示例，其中MOV指令是入口指令，而JA是出口指令。雖然基本塊可以有一個或多個前驅和后繼，但是在中間的指令不能退出該塊。
保證基本塊中的每條指令將被執行一次。這是一個非常重要的屬性，被許多編譯器轉換所利用。例如，它極大地減少了控制流圖分析和轉換的問題，因為對于某些問題類別，我們可以將基本塊中的所有指令視為一個實體處理。
7.3 Basic block placement
假設程序中存在一個熱路徑，該路徑在某些錯誤處理代碼（coldFunc）之間：
// hot path
if (cond)
coldFunc();
// hot path again圖41展示了該代碼片段的兩種可能的物理布局。圖41a是大多數編譯器在沒有提供提示的情況下默認生成的布局。圖41b所展示的布局可以通過反轉條件cond并將熱代碼作為默認執行路徑來實現。在一般情況下，哪種布局更好主要取決于cond是否通常為真。如果cond通常為真，則最好選擇默認布局，否則我們將執行兩次跳轉而不是一次。而且，在一般情況下，我們希望內聯受到cond保護的函數。然而，在這個特定的例子中，我們知道coldFunc是一個處理錯誤的函數，并且可能不經常被執行。通過選擇41b的布局，我們保持了代碼熱點之間的順序執行，并將已執行的分支轉換為未執行的分支。
對于前面在本節中呈現的代碼，布局41b表現更好有幾個原因。首先，未執行的分支基本上比已執行的分支更便宜。一般情況下，現代英特爾CPU每個周期可以執行兩個未執行的分支，但每兩個周期才能執行一個已執行的分支。
其次，布局41b更好地利用了指令和uop高速緩存（DSB，請參見第3.8.1節）。由于所有熱代碼都是連續的，不存在緩存行碎片化問題：L1I緩存中的所有緩存行都被熱代碼使用。對于uop高速緩存也是如此，因為它也是基于底層代碼布局進行緩存的。
最后，對于取指單元來說，已執行的分支也更昂貴。它會獲取連續的16字節塊，因此每個已執行的跳轉意味著跳轉后的字節是無用的。這降低了最大有效的取指吞吐量。
為了建議編譯器生成改進的機器碼布局版本，可以使用__builtin_expect161結構提供提示：
// hot path
if (__builtin_expect(cond, 0)) // NOT likely to be taken
coldFunc();
// hot path again開發人員通常會編寫LIKELY輔助宏來使代碼更易讀，因此經常可以找到類似下面所示的代碼。自C++20起，有一個標準的[[likely]]屬性，應該優先使用。
#define LIKELY(EXPR) __builtin_expect((bool)(EXPR), true)
#define UNLIKELY(EXPR) __builtin_expect((bool)(EXPR), false)
if (LIKELY(ptr != nullptr))
// do something with ptr優化編譯器在遇到LIKELY/UNLIKELY提示時不僅會改進代碼布局，還會在其他地方利用這些信息。例如，當將UNLIKELY提示應用于本節中的原始示例時，編譯器會阻止對coldFunc的內聯，因為現在它知道coldFunc不太可能經常執行，而優化其大小更有益，即只保留對該函數的調用。在switch語句中插入__builtin_expect提示也是可能的，如清單15所示。
Listing 15 Built-in expect hint for switch statement
for (;;) {
switch (__builtin_expect(instruction, ADD)) {
// handle different instructions
}
}使用這個提示，編譯器將能夠稍微不同地重新排列代碼，并優化熱門的switch語句以更快地處理ADD指令。有關這種轉換的更多詳細信息可以在easyperf163博客上找到。
7.4 Basic block alignment
有時性能可能會根據指令在內存中的布局偏移而發生顯著變化。考慮一下清單16中呈現的簡單函數。
Listing 16 Basic block alignment
void benchmark_func(int* a) {
for (int i = 0; i < 32; ++i)
a[i] += 1;
}一款良好的優化編譯器可能會生成適用于Skylake架構的機器碼，示例如下：
00000000004046a0 <_Z14benchmark_funcPi>:
4046a0: mov rax,0xffffffffffffff80
4046a7: vpcmpeqd ymm0,ymm0,ymm0
4046ab: nop DWORD PTR [rax+rax*1+0x0]
4046b0: vmovdqu ymm1,YMMWORD PTR [rdi+rax*1+0x80] # loop begins
4046b9: vpsubd ymm1,ymm1,ymm0
4046bd: vmovdqu YMMWORD PTR [rdi+rax*1+0x80],ymm1
4046c6: add rax,0x20
4046ca: jne 4046b0
# loop ends
4046cc: vzeroupper
4046cf: ret代碼本身對于Skylake架構來說是相當合理的，但其布局并不完美（參見圖42a）。與數據緩存一樣，指令緩存行通常是64字節長。在圖42中，粗框表示緩存行邊界。請注意，循環跨越多個緩存行：它從緩存行0x80 - 0xBF開始，結束于緩存行0xC0 - 0xFF。這類情況通常會導致CPU前端的性能問題，特別是對于像上面例子中的小循環而言。
為了解決這個問題，我們可以使用NOP指令將循環指令向前移動16字節，使整個循環位于一個緩存行中。圖42b顯示了使用NOP指令執行此操作的效果，其中用藍色突出顯示了NOP指令。需要注意的是，由于基準測試僅運行該熱門循環，因此可以確保這兩個緩存行都留在L1I緩存中。關于布局42b性能更好的原因并不容易解釋，涉及大量的微架構細節，本書將避免詳細介紹這些。
?盡管CPU架構師努力在設計中隱藏這種瓶頸，但在某些情況下，代碼布局（對齊）確實會對性能產生影響。如圖42a所示，默認情況下，LLVM編譯器會識別循環并將它們對齊到16字節邊界。為了達到我們示例中所示的期望代碼布局（圖42b），可以使用-mllvm -align-all-blocks選項。然而，要小心使用此選項，因為它可能會降低性能。插入將被執行的NOP指令可能會給程序增加開銷，特別是如果它們處于關鍵路徑上。NOP指令不需要執行，但仍然需要從內存中獲取、解碼和退休。后者還會消耗FE數據結構和緩沖區中的空間，類似于所有其他指令。
為了對對齊進行細粒度控制，還可以使用ALIGN匯編指令。為了進行實驗，開發人員可以發出匯編清單，然后插入ALIGN指令：
; will place the .loop at the beginning of 256 bytes boundary
ALIGN 256
.loop
dec rdi
jnz rdi7.5 Function splitting ? ?//函數拆分
函數拆分的思想是將熱點代碼與冷卻代碼分離。這種優化對于具有復雜控制流圖（CFG）且在熱路徑中包含大量冷卻代碼的相對較大函數非常有益。下面是一個可能會受益于這種轉換的代碼示例（見清單17）。為了從熱路徑中刪除冷卻基本塊，我們可以將其剪切并放入自己的新函數中，并創建對它的調用（見清單18）。
Listing 17 Function splitting: baseline version.
void foo(bool cond1, bool cond2) {
// hot path
if (cond1) {
// large amount of cold code (1)
}
// hot path
if (cond2) {
// large amount of cold code (2)
}
}Listing 18 Function splitting: cold code outlined.
void foo(bool cond1, bool cond2) {
// hot path
if (cond1)
cold1();
// hot path
if (cond2)
cold2();
}
void cold1() __attribute__((noinline)) { // cold code (1) }
void cold2() __attribute__((noinline)) { // cold code (2) }
圖43對該轉換進行了圖形化表示。由于我們在熱路徑中只留下了CALL指令，下一個熱指令很可能位于同一緩存行中。這提高了CPU前端數據結構（如I-cache和DSB）的利用率。
這種轉換包含另一個重要的思想：禁用冷卻函數的內聯。即使我們為冷卻代碼創建一個新函數，編譯器仍然可能決定將其內聯，從而有效地撤消我們的轉換。這就是為什么我們想要使用noinline函數屬性來防止內聯。另外，我們還可以在cond1和cond2分支上應用UNLIKELY宏（參見7.3節），以向編譯器傳達不希望內聯cold1和cold2函數的意圖。
最后，新函數應該在.text段之外創建，例如在.text.cold中。如果函數從未被調用，這可能會改善內存占用，因為它不會在運行時加載到內存中。
7.6 Function grouping ? ?//函數分組
根據前面章節中描述的原則，可以將熱函數分組在一起，以進一步提高CPU前端緩存的利用率。當熱函數被分組在一起時，它們可能共享同一緩存行，從而減少CPU需要獲取的緩存行數量。
圖44以圖形方式表示了對foo、bar和zoo進行分組。默認布局（見圖44a）需要讀取四個緩存行，而在改進版本中（見圖44b），foo、bar和zoo的代碼只適用于三個緩存行。此外，當我們從foo調用zoo時，由于我們已經獲取了那個緩存行，zoo的開頭已經在I-cache中。
類似于之前的優化，函數分組提高了I-cache和DSB-cache的利用率。當存在許多小型熱函數時，這種優化效果最佳。
?鏈接器負責將程序中的所有函數按照指定的方式布局到生成的二進制輸出中。盡管開發人員可以嘗試自行重新排序程序中的函數，但不能保證所期望的物理布局。多年來，人們一直在使用鏈接器腳本來實現這個目標。如果使用GNU鏈接器，這仍然是一種可行的方法。
Gold鏈接器（ld.gold）對于解決這個問題有一個更簡單的方法。為了在二進制文件中獲得所需的函數順序，可以首先使用"-ffunction-sections"標志編譯代碼，這將把每個函數放入單獨的節中。然后，應該使用"--section-ordering-file=order.txt"選項提供一個包含按所需最終布局排序的函數名稱的文件。LLD鏈接器也具有相同的功能，它是LLVM編譯器基礎設施的一部分，并通過"--symbol-ordering-file"選項進行調用。
HFSort169是一種解決將熱函數分組在一起問題的有趣方法，它是一種基于分析數據自動生成節順序文件的工具[Ottoni and Maher, 2017]。使用此工具，Facebook工程師在大型分布式云應用程序（如Facebook、百度和維基百科）中獲得了2%的性能改進。目前，HFSort已集成到Facebook的HHVM項目中，不作為獨立工具提供。LLD鏈接器采用HFSort算法的實現170，它根據分析數據對節進行排序。
7.7 Profile Guided Optimizations ? ?//基于性能分析的優化
編譯程序并生成優化的匯編代碼是基于啟發式算法的過程。代碼轉換算法包含許多針對特定情況下最佳性能的邊界條件。在編譯器做出許多決策時，它會根據一些典型案例來猜測最佳選擇。例如，在決定是否將特定函數內聯時，編譯器可以考慮到該函數將被調用的次數。問題在于編譯器事先并不知道這些信息。
這就是為什么性能分析信息非常有用。有了性能分析信息，編譯器可以做出更好的優化決策。大多數編譯器都有一組基于反饋的轉換，可以根據反饋的分析數據調整其算法。這組轉換被稱為Profile Guided Optimizations（PGO）。有時在文獻中還可以找到Feedback Directed Optimizations（FDO）這個術語，實質上它指的是與PGO相同的內容。當可用時，編譯器通常會依賴于性能分析數據。否則，它將回退到使用標準算法和啟發式規則。
使用Profile Guided Optimizations往往可以使真實工作負載的性能提高多達15%。PGO不僅改善了內聯和代碼布局，還改善了寄存器分配等方面的優化。
生成性能分析數據可以基于兩種不同的方式：代碼插裝（參見第5.1節）和基于采樣的性能分析（參見第5.4節）。這兩種方式相對容易使用，并且在第5.8節中討論了與之相關的優缺點。
在LLVM編譯器中，可以通過使用"-fprofile-instr-generate"選項構建程序來利用第一種方法。這將指示編譯器對代碼進行插裝，在運行時收集性能分析信息。然后，LLVM編譯器可以使用"-fprofile-instr-use"選項消耗性能分析數據，重新編譯程序并輸出經過PGO調優的二進制文件。有關在clang中使用PGO的指南在文檔中有描述。
GCC編譯器使用不同的選項組合"-fprofile-generate"和"-fprofile-use"，如GCC文檔所述。
第二種方法是基于采樣生成用于編譯器的性能分析數據輸入，可以借助于AutoFDO工具。該工具將Linux perf生成的采樣數據轉換為GCC和LLVM等編譯器可以理解的格式。請注意，編譯器會"盲目"地使用您提供的性能分析數據。編譯器假設所有工作負載的行為都相同，因此它只針對單個工作負載對您的應用程序進行優化。使用PGO的用戶應該在選擇要進行性能分析的工作負載時要小心，因為雖然改善了應用程序的一個用例，但其他用例可能會受到影響。幸運的是，它不一定要完全是單個工作負載，因為可以將來自不同工作負載的性能分析數據合并在一起，代表應用程序的一組用例。
在2018年中期，Facebook開源了其二進制重鏈接工具BOLT。BOLT適用于已編譯的二進制文件。它首先對代碼進行反匯編，然后利用性能分析信息進行各種布局變換（包括基本塊重新排序、函數拆分和分組），最后生成優化的二進制文件。Google也開發了一個類似的工具，名為Propeller，它與BOLT具有類似的目的，但聲稱在某些方面具有優勢。可以將優化重鏈接器集成到構建系統中，并從優化的代碼布局中獲得額外5-10%的性能提升。唯一需要擔心的是獲取具有代表性和有意義的工作負載以收集性能分析信息。
7.8 Optimizing for ITLB
在優化前端（FE）效率時，虛擬地址到物理地址的轉換對于內存地址非常重要。主要是通過TLB（參見第3節）來提供這些轉換，它在專用條目中緩存最近使用的內存頁轉換。當TLB無法滿足轉換請求時，會進行耗時的內核頁表頁面訪問，以計算每個引用的虛擬地址的正確物理地址。當TMA指向高ITLB開銷174時，本節中的建議可能會派上用場。
通過將應用程序的性能關鍵代碼部分映射到大頁面，可以減少ITLB壓力。這需要重新鏈接二進制文件，以便將文本段調整到適當的頁面邊界，為大頁面映射做準備（請參閱libhugetlbfs的指南175）。有關大頁面的一般討論，請參見第8.1.3節。
除了使用大頁面外，還可以使用標準的技術來優化I-cache性能，從而改善ITLB性能。例如，通過重新排序函數使熱函數更加相鄰，通過LTO/IPO176減少熱區域的大小，使用基于配置文件的優化，以及減少過度的內聯。
7.9 Chapter Summary
CPU前端優化的摘要總結如表6所示。
個人經驗：我認為代碼布局的改進經常被低估，最終被省略和遺忘。我同意你可能會從一些低 hanging 的優化措施開始，比如循環展開和矢量化機會。但是知道你可以通過更好地布局機器代碼來獲得額外的5-10%的性能提升仍然是有用的。如果你能為你的應用程序找到一組典型的用例，通常使用PGO是最好的選擇。
8 CPU Back-End Optimizations
?CPU后端（BE）組件在第3.8.2節中進行了討論。大部分情況下，CPU后端的低效率可以描述為FE已經獲取和解碼指令，但是BE負載過重，無法處理新指令。從技術上講，這是一種FE無法傳遞uops的情況，因為后端缺乏接受新uops所需的資源。其中一個例子是由于數據緩存未命中或除法器負載過重而導致的停頓。
我想強調給讀者的建議是，只有當TMA指向較高的“后端限制”指標時，才建議開始優化針對CPU后端的代碼。TMA進一步將后端限制指標分為兩個主要類別：內存限制和核心限制，我們將在接下來進行討論。
8.1 Memory Bound ? ?//內存受限
當一個應用程序執行大量的內存訪問并花費大量時間等待它們完成時，這樣的應用程序被稱為受內存限制。這意味著要進一步提高其性能，我們可能需要改進內存訪問方式、減少此類訪問次數或升級內存子系統本身。
內存層次結構性能非常重要的說法得到了圖45的支持。該圖顯示了內存和處理器之間性能差距的增長。垂直軸采用對數刻度，顯示了CPU-DRAM性能差距的增長。內存基線是1980年64KB DRAM芯片的內存訪問延遲。典型的DRAM性能改進每年為7%，而CPU每年可以享受20-50%的改進。[Hennessy和Patterson，2011]
在TMA中，內存受限（Memory Bound）估計了CPU流水線由于需求加載或存儲指令而可能停頓的插槽比例。解決這類性能問題的第一步是找出導致高內存受限指標的內存訪問（請參閱第6.1.4節）。一旦確定了具有問題的內存訪問，就可以應用多種優化策略。下面我們將討論幾種典型情況。
8.1.1 Cache-Friendly Data Structures
如果變量在緩存中可以在幾個時鐘周期內獲取，但如果不在緩存中，則從RAM內存中獲取該變量可能需要超過一百個時鐘周期。關于編寫有利于緩存的算法和數據結構的重要性有很多信息，因為這是一個高性能應用程序的關鍵因素之一。緩存友好代碼的關鍵支柱是時間和空間局部性（請參見第3.5節）的原則，其目標是允許有效地從緩存中獲取所需的數據。在設計緩存友好代碼時，將變量及其在內存中的位置視為緩存行，而不僅僅是個別變量，這將會很有幫助。
8.1.1.1 Access data sequentially.
利用空間局部性最佳的方法是進行連續的內存訪問。通過這樣做，我們可以允許硬件預取器（請參見第3.5.1.5.1節）識別內存訪問模式，并提前獲取下一塊數據。在清單19中展示了一個實現這種緩存友好訪問的C代碼示例。該代碼之所以“緩存友好”，是因為它按照內存中的排布順序（行優先遍歷）訪問矩陣的元素。如果調換數組索引的順序（例如，matrix[column][row]），將會導致按列優先遍歷矩陣，這不利用空間局部性并且降低性能。
Listing 19 Cache-friendly memory accesses.
for (row = 0; row < NUMROWS; row++)
for (column = 0; column < NUMCOLUMNS; column++)
matrix[row][column] = row + column;清單19中呈現的示例是經典的，但通常實際應用程序比這復雜得多。有時候，為了編寫緩存友好的代碼，你需要更加深入一些。例如，在一個排序的大數組中，標準的二分查找實現并不利用空間局部性，因為它測試位于彼此相距很遠且不共享同一緩存行的不同位置的元素。解決這個問題最著名的方法是使用Eytzinger布局[Khuong和Morin，2015]來存儲數組的元素。其思想是使用類似廣度優先搜索（BFS）的布局，在一個數組中維護一個隱式的二叉搜索樹，通常在二叉堆中可見。如果代碼在數組中執行大量的二分查找，將其轉換為Eytzinger布局可能會有益處。
8.1.1.2 Use appropriate containers.
幾乎每種編程語言都有各種準備好的容器可供使用。但了解它們的底層存儲和性能影響是很重要的。選擇適當的C++容器的一個很好的逐步指南可以在[Fog, 2004，第9.7章 數據結構和容器類]中找到。
此外，在選擇數據存儲方式時，要考慮代碼對數據的處理方式。考慮這樣一種情況：在對象大小較大時，需要在數組中存儲對象還是存儲指向這些對象的指針之間進行選擇。存儲指針的數組需要更少的內存。這對于修改數組的操作有益，因為指針數組需要傳輸的內存較少。然而，如果保留對象本身，則通過數組進行線性掃描將更快，因為它更加緩存友好并且不需要間接內存訪問。
8.1.1.3 Packing the data. ? ?//使數據更緊湊
通過使數據更緊湊，可以提高內存層次結構的利用率。有許多方法可以壓縮數據。其中一個經典示例是使用位域（bitfields）。在清單20中展示了一個可能受益于數據壓縮的代碼示例。如果我們知道a、b和c表示的是占用一定位數進行編碼的枚舉值，我們可以減小結構體S的存儲空間（參見清單21）。
Listing 20 Packing Data: baseline struct.
struct S {
unsigned a;
unsigned b;
unsigned c;
}; // S is sizeof(unsigned int) * 3Listing 21 Packing Data: packed struct.
struct S {
unsigned a:4;
unsigned b:2;
unsigned c:2;
}; // S is only 1 byte這樣做大大減少了來回傳輸的內存量，并節省了緩存空間。但需要牢記的是，這樣做會增加訪問每個壓縮元素的成本。由于b的位與a和c共享同一機器字（machine word），編譯器需要執行右移（>>）和按位與（AND）操作來加載它。類似地，存儲值時需要執行左移（<<）和按位或（OR）操作。在計算效率低下的內存傳輸引起延遲的情況下，數據壓縮是有益的。
此外，程序員可以通過重新排列結構體或類中的字段來減少內存使用，以避免編譯器添加的填充字節（padding）。編譯器插入未使用的內存字節（填充）的原因是為了實現對結構體的各個成員進行有效存儲和提取。在示例中，如果按照成員大小遞減的順序聲明S1的成員，則可以減小其大小。
8.1.1.4 Aligning and padding.
另一種提高內存子系統利用率的技術是對數據進行對齊。可能會出現這樣的情況：一個占據16字節的對象跨越了兩個緩存行，即它在一個緩存行上開始，在下一個緩存行上結束。獲取這樣的對象需要讀取兩個緩存行，如果對象正確對齊，可以避免這種情況。清單23展示了如何使用C++11的alignas關鍵字來對齊內存對象。
最有效地訪問變量的方式是將其存儲在可被變量大小整除的內存地址上。例如，double類型占用8字節的存儲空間。因此，最好將其存儲在可以被8整除的地址上。大小應始終為2的冪次方。大于16字節的對象應存儲在可以被16整除的地址上。
Listing 22 Avoid compiler padding.
struct S1 {
bool b;
int i;
short s;
}; // S1 is sizeof(int) * 3
struct S2 {
int i;
short s;
bool b;
}; // S2 is sizeof(int) * 2Listing 23 Aligning data using the “alignas” keyword.
// Make an aligned array
alignas(16) int16_t a[N];
// Objects of struct S are aligned at cache line boundaries
#define CACHELINE_ALIGN alignas(64)
struct CACHELINE_ALIGN S {
//...
};因此，最好將其存儲在可以被8整除的地址上。大小應始終為2的冪次方。大于16字節的對象應存儲在可以被16整除的地址上。這樣做有助于減少內存帶寬的利用，并提高性能。
對齊可能會導致未使用字節的空洞，從而降低內存帶寬的利用率。在上面的示例中，如果結構體S只有40字節，那么下一個S對象將從下一個緩存行的開頭開始，這意味著每個包含S結構體對象的緩存行將有64 - 40 = 24個未使用的字節。
有時需要填充數據結構成員以避免緩存爭用（詳見[Fog, 2004, 第9.10章 緩存爭用]）和偽共享（見第11.7.3節）。例如，在多線程應用程序中，當兩個線程A和B訪問同一結構體的不同字段時，可能會發生偽共享問題。當成員a和b有可能占用同一緩存行時，緩存一致性問題可能會嚴重降低程序的速度。為了解決這個問題，可以填充S，使得成員a和b不共享同一緩存行，如清單25所示。
Listing 24 Padding data: baseline version.
struct S {
int a; // written by thread A
int b; // written by thread B
};Listing 25 Padding data: improved version.
#define CACHELINE_ALIGN alignas(64)
struct S {
int a; // written by thread A
CACHELINE_ALIGN int b; // written by thread B
};對于通過malloc進行的動態分配，返回的內存地址保證滿足目標平臺的最小對齊要求。有些應用程序可能會受益于更嚴格的對齊要求。例如，使用64字節對齊而不是默認的16字節對齊來動態分配16字節。為了利用這一點，POSIX系統的用戶可以使用memalign API。其他用戶可以按照這里的描述自行實現。
在對齊考慮中最重要的領域之一是SIMD代碼。當依賴編譯器自動向量化時，開發人員不需要做任何特殊處理。然而，當您使用編譯器矢量內置函數（參見第10.2節）編寫代碼時，很常見它們要求地址可以被16、32或64整除。編譯器內置頭文件提供的矢量類型已經進行了注釋，以確保適當的對齊。
// ptr will be aligned by alignof(__m512) if using C++17
__m512 * ptr = new __m512[N];8.1.1.5 Dynamic memory allocation.
首先，有許多可以替代malloc的內存分配器，它們更快、更具可伸縮性，并且更好地解決了地址碎片問題。只需使用非標準的內存分配器，就可以獲得幾個百分點的性能提升。其中一些流行的內存分配庫包括jemalloc和tcmalloc。
其次，可以使用自定義分配器來加速分配過程，例如，使用arena分配器。其主要優點之一是開銷較低，因為此類分配器不會為每個內存分配執行系統調用。另一個優點是其高度靈活性。開發人員可以基于操作系統提供的內存區域實現自己的分配策略。一個簡單的策略是維護兩個不同的分配器，每個分配器都有自己的arena（內存區域）：一個用于熱數據，一個用于冷數據。將熱數據放在一起可以提供共享緩存行的機會，從而改善內存帶寬利用率和空間局部性。它還改善了TLB利用率，因為熱數據占用的內存頁面較少。此外，自定義內存分配器可以使用線程本地存儲來實現每個線程的分配，并消除線程之間的任何同步。當應用程序基于線程池并且不會生成大量線程時，這將非常有用。
8.1.1.6 Tune the code for memory hierarchy.
對于某些應用程序，性能取決于特定級別緩存的大小。其中最著名的例子是使用循環分塊（tiling）改進矩陣乘法的性能。其思想是將矩陣的工作大小分成較小的片段（塊），以便每個塊都適應L2緩存。
大多數體系結構都提供類似于CPUID的指令，允許我們查詢緩存的大小。另外，可以使用緩存無關算法，其目標是在任何緩存大小下都能夠良好地工作。
英特爾的CPU具有數據線性地址硬件（見第6.3.3節），支持如easyperf博客文章所描述的緩存分塊技術。
通過合理利用緩存結構和緩存相關的特性，可以顯著提高應用程序的性能。
8.1.2 Explicit Memory Prefetching ? ?//顯示內存預取
在通用工作負載中，常常存在數據訪問沒有明確模式或是隨機的情況，因此硬件無法提前有效預取數據（請參考第3.5.1.5.1節中有關硬件預取器的信息）。這些情況下，緩存未命中無法通過選擇更好的數據結構來消除。例如，在第26個代碼清單中展示了這種情況的一個例子。假設calcNextIndex返回彼此差異顯著的隨機值。在這種情況下，后續加載arr[j]會指向內存中的完全新位置，并且很可能導致緩存未命中。當arr數組足夠大時，硬件預取器將無法捕捉到模式并未能提前獲取所需的數據。在第26個示例中，計算索引j和請求元素arr[j]之間存在一段時間窗口。由于這一點，我們可以使用__builtin_prefetch等顯式預取指令，如第27個代碼清單所示。
使用顯式預取指令可以在計算索引和訪問該索引對應元素之間的時間窗口中，提前將需要的數據加載到緩存中，從而減少緩存未命中的次數。這樣可以顯著改善訪存性能，在數據訪問無明顯模式或隨機的情況下尤為有效。
Listing 26 Memory Prefetching: baseline version.
for (int i = 0; i < N; ++i) {
int j = calcNextIndex();
// ...
doSomeExtensiveComputation();
// ...
x = arr[j]; // this load misses in L3 cache a lot
}為了讓預取提示生效，請確保提前將其插入到適當的位置，以便在加載的值在其他計算中使用之前，它已經存在于緩存中。同時，也不要插入得太早，因為這樣可能會污染緩存，使得一段時間內沒有使用的數據占據了緩存空間。為了估計預取窗口，可以使用第6.2.5節中描述的方法。
工程師最常使用顯式內存預取的場景是獲取下一次循環迭代所需的數據。然而，線性函數預取也可以非常有幫助，例如，當您事先知道數據的地址，但在一定延遲（預取窗口）后請求該數據時。這種情況下，線性函數預取能起到很好的作用。
Listing 27 Memory Prefetching: using built-in prefetch hints.
for (int i = 0; i < N; ++i) {
int j = calcNextIndex();
__builtin_prefetch(a + j, 0, 1); // well before the load
// ...
doSomeExtensiveComputation();
// ...
x = arr[j];
}確實，顯式內存預取并不可移植，這意味著在一個平臺上可以獲得性能提升，并不保證在另一個平臺上也能獲得類似的加速效果。更糟糕的是，當不正確使用時，它可能會惡化緩存的性能。如果使用錯誤大小的內存塊或者過于頻繁地請求預取，可能會迫使其他有用的數據從緩存中被驅逐出去。
雖然軟件預取能夠讓程序員具備控制和靈活性，但要正確使用并不總是容易。考慮一種情況，我們想要將預取指令插入到平均IPC為2的代碼片段中，每次DRAM訪問需要100個周期。為了達到最佳效果，我們需要在加載之前的200個指令處插入預取指令。但這并不總是可能的，特別是當加載地址就在加載本身之前計算時。指針追蹤問題可以是顯式預取無法解決的一個很好的例子。
最后，顯式預取指令會增加代碼大小并增加CPU前端的壓力。預取指令就像其他任何指令一樣，會消耗CPU資源，當使用不當時，可能會降低程序的性能。
8.1.3 Optimizing For DTLB
正如第3節所描述的，TLB是一個快速但有限的核心緩存，用于內存地址的虛擬地址到物理地址的轉換。如果沒有TLB，每個應用程序的內存訪問都需要耗時的內核頁表頁行走來計算每個引用的虛擬地址的正確物理地址。
TLB層次結構通常包括L1 ITLB（指令）、L1 DTLB（數據）和L2 STLB（指令和數據的統一緩存）。L1 ITLB的缺失通常只會導致非常小的懲罰，通常可以通過亂序執行來隱藏。STLB的缺失將導致調用頁行走器。在運行時，這個懲罰可能是明顯的，因為在此過程中，CPU會停頓[Suresh Srinivas, 2019]。假設Linux內核中默認的頁面大小為4KB，現代的L1級別的TLB緩存只能保存最近使用的幾百個頁面表項，覆蓋大約1MB的地址空間，而L2 STLB則可以保存多達幾千個頁面表項。具體的數字可以在https://ark.intel.com上找到特定處理器的信息。
在Linux和Windows系統上，應用程序被加載到內存中的是以4KB頁面為單位的，默認情況下大多數系統都是這樣的。分配許多小頁面是昂貴的。如果一個應用程序活躍地引用了數十GB或數百GB的內存，那么就需要很多4KB大小的頁面，每個頁面都會爭奪有限的TLB條目。使用大的2MB頁面，可以用只有十個頁面就映射20MB的內存，而使用4KB頁面則需要5120個頁面。這意味著需要更少的TLB條目，從而減少了TLB缺失的次數。無論是Windows還是Linux，都允許應用程序建立大頁內存區域。HugeTLB子系統的支持取決于體系結構，而AMD64和Intel 64體系結構均支持2MB（huge）和1GB（gigantic）頁面。
正如我們剛剛學到的那樣，減少ITLB缺失的一種方法是使用更大的頁面大小。值得慶幸的是，TLB也能夠緩存2MB和1GB頁面的條目。如果前面提到的應用程序使用了2MB頁面而不是默認的4KB頁面，它將使TLB的壓力減少512倍。同樣地，如果它從使用2MB頁面更新為使用1GB頁面，它將再次將TLB的壓力減少512倍。這是一個很大的改進！對于某些應用程序來說，使用較大的頁面大小可能有益，因為在緩存中用于存儲轉換的空間較少，可以為應用程序代碼提供更多的可用空間。巨大的頁面通常會導致更少的頁行走，并且由于表本身更緊湊，所以在發生TLB缺失時，在內核頁表中進行頁行走的懲罰也會降低。
大頁面可以用于代碼、數據或兩者兼而有之。如果您的工作負載有一個大的堆，那么對數據使用大頁面是值得嘗試的。像關系型數據庫系統（如MySQL、PostgreSQL、Oracle等）和配置有大堆區域的Java應用程序這樣的大內存應用程序經常受益于使用大頁面。在[Suresh Srinivas, 2019]中，有一個使用巨大頁面優化運行時的示例，展示了這個功能如何在三個環境中的三個應用程序中提高性能并減少ITLB缺失（最多50％）。
然而，就像其他許多功能一樣，大頁面并不適用于每個應用程序。如果一個應用程序只想分配一個字節的數據，那么使用4KB頁面而不是巨大頁面會更好；這樣可以更有效地使用內存。
在Linux操作系統上，有兩種在應用程序中使用大頁面的方式：顯式和透明巨大頁面。
8.1.3.1 Explicit Hugepages.
作為系統內存的一部分，巨大頁面可以作為巨大頁面文件系統（hugetlbfs）提供，應用程序可以使用系統調用（例如mmap）來訪問它。可以通過cat /proc/meminfo命令和HugePages_Total條目來檢查系統上適當配置的巨大頁面。巨大頁面可以在啟動時或運行時進行預留。在啟動時進行預留增加了成功的可能性，因為內存尚未被顯著碎片化。有關預留巨大頁面的詳細說明，請參考Red Hat性能調優指南。
還有一種選項是使用libhugetlbfs庫，在大型頁面之上動態分配內存，該庫覆蓋了現有動態鏈接二進制可執行文件中使用的malloc調用。它不需要修改代碼甚至重新鏈接二進制文件；最終用戶只需配置幾個環境變量即可。它可以同時使用顯式預留的巨大頁面和透明頁面。有關更多詳細信息，請參閱libhugetlbfs的操作文檔。
對于從代碼中對大頁面的訪問需要更精細控制的情況（即不影響每個內存分配），開發人員有以下替代方案：
? 使用MAP_HUGETLB標志的mmap（示例代碼197）。
? 使用掛載的hugetlbfs文件系統中的文件的mmap（示例代碼198）。
? 使用SHM_HUGETLB標志的shmget（示例代碼199）。
8.1.3.2 Transparent Hugepages.
Linux還提供透明巨大頁面支持（THP），它可以自動管理大頁面，并對應用程序透明。在Linux下，您可以啟用THP，在需要大塊內存時動態切換到巨大頁面。THP功能有兩種操作模式：系統級和進程級。當啟用系統級THP時，內核會嘗試在可能分配巨大頁面的情況下為任何進程分配巨大頁面，因此不需要手動預留巨大頁面。如果按進程啟用了THP，內核僅將巨大頁面分配給通過madvise系統調用歸屬的各個進程的內存區域。您可以使用以下命令檢查系統中是否已啟用THP：
$ cat /sys/kernel/mm/transparent_hugepage/enabled
always [madvise] never如果值始終為"always"（系統級）或"madvise"（進程級），則THP對您的應用程序可用。使用"madvise"選項，只有通過madvise系統調用標記為MADV_HUGEPAGE的內存區域內啟用了THP。有關每個選項的完整規范，可以在Linux內核文檔中找到有關THP的文檔。
8.1.3.3 Explicit vs. Transparent Hugepages.
與顯式巨大頁面（EHP）需要提前在虛擬內存中保留不同，THP并不需要。內核在后臺嘗試分配一個THP，如果失敗，將默認使用標準的4k頁面。這一切對用戶來說都是透明的。分配過程可能涉及多個內核進程，負責為未來的THP在虛擬內存中騰出空間（可能包括將內存交換到磁盤、碎片化或壓縮頁面）。透明巨大頁面的后臺維護會帶來非確定性的內核延遲開銷，因為它管理著不可避免的碎片化和交換問題。而EHP則不會受到內存碎片化的影響，也無法被交換到磁盤上。
其次，EHP可用于應用程序的所有段，包括文本段（即同時受益于DTLB和ITLB），而THP僅適用于動態分配的內存區域。
THP的一個優點是相比EHP需要較少的操作系統配置工作，這有助于加快實驗速度。
8.2 Core Bound ? ?//核心受限
第二類CPU后端瓶頸是核心限制（Core Bound）。一般來說，該指標表示CPU亂序執行引擎內的所有停頓，并且這些停頓不是由于內存問題引起的。核心限制指標有兩個主要類別：
? 硬件計算資源短缺。這表明某些執行單元過載（執行端口爭用）。當工作負載頻繁執行大量的重型指令時，就會出現這種情況。例如，除法和平方根運算由Divider單元處理，其延遲時間可能比其他指令要長很多。
? 軟件指令之間的依賴關系。這表示程序數據流或指令流中的依賴關系限制了性能。例如，依賴浮點運算的高延遲算術操作會導致指令級并行性（ILP）較低。
在本小節中，我們將介紹最常見的優化技術，如函數內聯、矢量化和循環優化。這些優化旨在減少執行的指令總數，在工作負載經歷高的Retiring指標時也會有所幫助。但作者認為在這里討論它們是合適的。
8.2.1 Inlining Functions
函數內聯是將對函數F的調用替換為針對該調用實際參數進行特化的F代碼。內聯是最重要的編譯器優化之一，不僅可以消除函數調用的開銷，還可以啟用其他優化。這是因為當編譯器內聯一個函數時，編譯器分析的范圍擴大到了更大的代碼塊。然而，內聯也有一些缺點：可能會增加代碼大小和編譯時間。
在很多編譯器中，函數內聯的主要機制依賴于某種成本模型。例如，對于LLVM編譯器，它基于計算每個函數調用（調用點）的成本和閾值來進行內聯。只有當成本小于閾值時才會進行內聯。通常，內聯一個函數調用的成本基于該函數中指令的數量和類型。閾值通常是固定的，但在某些情況下可以變化。
在這個普遍成本模型周圍存在許多啟發式規則。例如：
- 微小的函數（包裝器）幾乎總是會被內聯。
- 僅有一個調用點的函數是內聯的首選候選對象。
- 大型函數通常不會被內聯，因為它們會使調用者函數的代碼膨脹。
此外，也存在一些內聯存在問題的情況：
- 遞歸函數無法內聯到其自身。
- 通過指針引用的函數可以在直接調用的位置進行內聯，但必須保留在二進制文件中，即不能完全內聯和消除。對于具有外部鏈接的函數也是如此。
如前所述，編譯器在判斷是否內聯一個函數時通常采用成本模型方法，這在實踐中通常效果良好。一般來說，依靠編譯器來做出所有內聯決策并在需要時進行調整是一個不錯的策略。成本模型無法考慮到每種可能的情況，這給改進留下了空間。有時編譯器需要開發人員提供特殊提示。一種找到程序中潛在內聯候選的方法是查看分析數據，特別是函數的前導部分和尾聲部分的熱度。下面是一個函數剖面的示例，其中前導和尾聲部分消耗了函數時間的約50%：
這可能是一個強有力的指標，表明如果我們內聯該函數，前導和尾聲部分的運行時間可能會被節省下來。需要注意的是，即使前導和尾聲部分是熱點代碼，也不一定意味著內聯該函數就會有利可圖。內聯觸發了許多不同的變化，因此很難預測結果。始終通過測量改變后的代碼的性能來確認是否需要強制內聯。
對于GCC和Clang編譯器，可以使用C++11的[[gnu::always_inline]]屬性來給內聯 foo 函數提供提示，如下所示的代碼示例。對于MSVC編譯器，可以使用__forceinline關鍵字。
[[gnu::always_inline]] int foo() {
// foo body
}8.2.2 Loop Optimizations
循環是幾乎所有高性能（HPC）程序的核心。由于循環代表著需要執行大量次數的代碼片段，因此執行時間的大部分都花費在循環中。對于這樣一個關鍵的代碼片段來說，微小的改變可能會對程序的性能產生很大的影響。因此，仔細分析程序中熱門循環的性能并了解改進它們的可能選項非常重要。
要有效優化一個循環，關鍵是了解循環的瓶頸所在。一旦找到了耗時最長的循環，嘗試確定其瓶頸。通常情況下，循環的性能受限于以下一個或多個方面：內存延遲、內存帶寬或計算機的計算能力。屋頂線性模型（Roofline Performance Model）（第5.5節）是評估不同循環性能與硬件理論極限之間關系的良好起點。自頂向下的微架構分析（Top-Down Microarchitecture Analysis）（第6.1節）也是了解瓶頸信息的另一個良好來源。
通過使用這些工具和方法，可以更好地了解循環的性能問題，并確定如何改進循環以提高程序性能。這包括利用合適的算法、優化數據布局、使用矢量化指令、循環展開、循環分塊等技術來減少內存延遲、提高內存帶寬和充分利用計算能力。此外，根據具體的硬件架構和應用場景，調整循環的執行策略也非常重要。
在本節中，我們將介紹一些最常見的循環優化方法，以解決前面提到的各種瓶頸類型。首先，我們將討論低級優化，這些優化只在單個循環內部對代碼進行移動。這類優化通常有助于使循環內的計算更加有效。接下來，我們將介紹高級優化，它們對循環進行重構，通常涉及多個循環。第二類優化的目標通常是改善內存訪問，消除內存帶寬和內存延遲問題。需要注意的是，這里列舉的并不是所有已發現的循環變換的完整列表。讀者可以參考[Cooper and Torczon，2012]以獲取有關每種變換的更詳細信息。
編譯器可以自動識別執行某種循環變換的機會。然而，有時候需要開發人員的干預才能達到預期的結果。在本節的第二部分，我們將探討在循環中發現性能改進機會的可能方式。了解對給定循環執行了哪些變換，以及編譯器無法做到哪些優化，是成功進行性能調優的關鍵之一。最后，我們將考慮使用多面體框架優化循環的另一種替代方式。
8.2.2.1 Low-level optimizations.
首先，我們將考慮簡單的循環優化，這些優化會轉換單個循環內部的代碼：循環不變式代碼移動（Loop Invariant Code Motion）、循環展開（Loop Unrolling）、循環強度降低（Loop Strength Reduction）和循環不交換（Loop Unswitching）。這些優化通常有助于改善具有高算術密集度的循環的性能（參見第5.5節），即當循環受到CPU計算能力限制時。一般來說，編譯器在執行這些轉換時表現良好；然而，仍然存在一些情況，編譯器可能需要開發人員的支持。我們將在后續章節中討論這個問題。
Loop Invariant Code Motion (LICM).
在循環中永遠不會改變的表達式被稱為循環不變式（loop invariants）。由于它們的值在循環迭代過程中保持不變，我們可以將循環不變式表達式移到循環外部。我們可以通過將結果存儲在一個臨時變量中，并在循環內部使用臨時變量來實現這一操作（參見清單28）。
Loop Unrolling.
歸納變量（induction variable）是循環中的一個變量，其值是循環迭代次數的函數。例如，v = f(i)，其中i是迭代次數。在每次迭代中修改歸納變量可能很昂貴。相反，我們可以展開循環，并為每個歸納變量的增量執行多次迭代（參見清單29）。循環展開的主要好處是每次迭代可以執行更多的計算。在每次迭代結束時，需要增加索引值、進行測試，并且如果還有更多迭代需要處理，則跳轉回循環的頂部。這個工作可以被看作是循環的“稅”，可以減少。通過將清單29中的循環展開2倍，我們將執行的比較和分支指令數量減少了一半。
循環展開是一個眾所周知的優化方法，但仍然有很多人對此感到困惑，并嘗試手動展開循環。我建議開發人員不應該手動展開任何循環。首先，編譯器在進行循環展開時表現非常出色，通常能夠實現很優化的展開方式。第二個原因是處理器具有“內置展開器”，這得益于其亂序推測執行引擎（參見第3節）。當處理器等待第一次迭代的加載完成時，它可以推測性地開始執行第二次迭代的加載操作。這可以向前跨越多次迭代，在指令重排序緩沖區（ROB）中有效地展開循環。
所以，由于編譯器和處理器都能夠自動處理循環展開，開發人員無需手動展開循環。這樣做更容易導致代碼復雜性增加、易錯和可讀性下降。如果開發人員嘗試手動展開循環，可能會產生不必要的代碼冗余和維護成本。相反，應該將精力放在編寫清晰、簡潔且易于理解的代碼上，讓編譯器和處理器負責優化循環展開以提高性能。
Loop Strength Reduction (LSR).
LSR（循環強度降低）的思想是用廉價的指令替換昂貴的指令。這種轉換可以應用于所有使用歸納變量的表達式。強度降低通常應用于數組索引。編譯器通過分析變量在循環迭代中的演變方式來執行LSR（見清單30）。
Loop Unswitching.
如果一個循環內部包含一個不變的條件判斷語句，我們可以將其移到循環外部。這可以通過復制循環體，并將其放置在條件判斷語句的if和else子句中的各個版本中來實現（見清單31）。雖然循環拆分可能會使代碼量增加一倍，但現在每個新的循環都可以單獨進行優化。
循環拆分是一種優化技術，它的目標是減少循環內部的條件判斷次數，以提高執行效率。當循環中的條件在每次迭代中都保持不變時，這種優化可以提供更好的性能。
通過將循環體復制到條件判斷語句的if和else子句中，我們可以在每個版本的循環中單獨進行優化。這樣，編譯器可以針對不同的條件進行優化，并生成更有效的代碼。
雖然循環拆分會導致代碼量增加，但這種優化可以提高程序的執行效率。通過分別對每個拆分后的循環進行優化，可以針對不同的條件進行更精細的控制流優化和計算優化，從而獲得更好的性能。
8.2.2.2 High-level optimizations.
還有一類循環變換可以改變循環的結構，通常會影響到多個嵌套循環。我們將介紹循環交換、循環分塊（瓦片化）以及循環融合和分布（分裂）。這組變換旨在改進內存訪問方式，消除內存帶寬和內存延遲的瓶頸。從編譯器的角度來看，合法且自動地進行高級循環變換非常困難。往往很難證明所做的任何優化的益處。在這種意義上，開發人員處于更好的位置，因為他們只需關注在特定代碼段中變換的合法性，而不必考慮可能發生的每種情況。不幸的是，這也意味著我們經常需要手動進行這樣的變換。
循環交換、循環分塊和循環融合與分布是用于優化內存訪問、消除內存帶寬和內存延遲瓶頸的重要循環變換技術。循環交換可以改變循環的執行順序，以優化數據的局部性，并提高緩存效率。循環分塊通過將大循環分割成小的塊，可以減少對主存的訪問次數，以及提高數據重用和并行性。循環融合和分布可以將多個循環合并或拆分，以減少內存訪問次數，并提高數據的局部性。
由于進行高級循環變換是非常困難的，因此開發人員通常需要手動進行這些變換，以在特定代碼段中實現性能優化。他們需要評估和驗證變換的合法性，并權衡所帶來的性能提升是否值得投入。編譯器很難在所有情況下自動進行這些變換，因此開發人員的角色仍然非常重要。
Loop Interchange.
循環交換是指交換嵌套循環的循環順序。內部循環中使用的歸納變量切換到外部循環，反之亦然。清單32展示了一個關于i和j的嵌套循環交換的示例。循環交換的主要目的是對多維數組的元素進行順序內存訪問。通過按照內存中元素布局的順序進行訪問，我們可以提高內存訪問的空間局部性，并使我們的代碼更加緩存友好（見第8.1.1節）。這種轉換有助于消除內存帶寬和內存延遲的瓶頸。
Loop Blocking (Tiling).
循環分塊（瓦片化）的思想是將多維執行范圍分割成較小的塊（塊或瓦片），以便每個塊都適合CPU緩存210。如果算法使用大型多維數組，并對其元素進行跨步訪問，那么緩存利用率可能很低。每次這樣的訪問都可能將未來訪問所需的數據推出緩存（緩存驅逐）。通過將算法劃分為較小的多維塊，我們可以確保在循環中使用的數據保持在緩存中直到被重復使用。
在清單33所示的例子中，算法對數組a的元素進行行主序遍歷，同時對數組b進行列主序遍歷。循環嵌套可以分割為較小的塊，以最大程度地重用數組b的元素。
循環分塊是一種廣為人知的優化一般矩陣乘法（General Matrix Multiplication，GEMM）算法的方法。它增強了內存訪問的緩存重用，并改善算法的內存帶寬和內存延遲。
Loop Fusion and Distribution (Fission).
當兩個循環迭代相同范圍并且彼此不引用對方的數據時，可以將它們合并為一個循環。循環融合是將兩個獨立的循環合并為一個循環的過程。在第34段代碼示例中展示了循環融合的例子。另一種相反的操作稱為循環分配（分裂），即將循環拆分成多個獨立的循環。
循環融合有助于減少循環開銷（參見循環展開討論），因為兩個循環可以使用相同的歸納變量。此外，循環融合可以提高內存訪問的時間局部性。在第34段代碼示例中，如果結構體的 x 和 y 成員恰好位于同一緩存行上，最好將兩個循環融合起來，因為我們可以避免重復加載同一緩存行。這將減少緩存占用，并提高內存帶寬利用率。
然而，并非總是循環融合能夠提高性能。有時候將一個循環拆分為多個階段、預先過濾數據、排序和重組數據等操作會更好。通過將大循環分割成多個較小的循環，可以限制每次循環迭代所需的數據量，從而有效地增加內存訪問的時間局部性。這對于存在高緩存爭用的情況特別有幫助，而這通常發生在大型循環中。循環分配還可以減少寄存器壓力，因為在每次循環迭代中執行的操作更少。此外，將大循環拆分為多個較小的循環還有助于CPU前端的性能，因為可以更好地利用指令緩存（參見第7節）。最后，分布式后，編譯器可以單獨對每個小循環進行進一步優化。
8.2.2.3 Discovering loop optimization opportunities.
正如我們在本節開頭討論的那樣，編譯器將承擔優化循環的繁重工作。您可以依靠它們來對循環代碼進行所有明顯的改進，比如消除不必要的工作、進行各種peephole優化等。有時候編譯器足夠聰明，可以默認生成快速版本的循環，而其他情況下我們需要自己進行一些重寫來幫助編譯器。正如之前所說，從編譯器的角度來看，合法且自動地進行循環轉換是非常困難的。通常，當編譯器無法證明變換的合法性時，它必須保守處理。
考慮列表35中的代碼。編譯器無法將表達式strlen(a)移出循環體。因此，循環在每次迭代中檢查字符串是否到達末尾，這顯然是慢速的。編譯器不能提升這個調用的原因是，數組a和b的內存區域可能重疊。在這種情況下，將strlen(a)移出循環體是不合法的。如果開發者確信內存區域不會重疊，他們可以在foo函數的兩個參數上使用restrict關鍵字聲明，即char* __restrict__ a。
有時候，編譯器可以通過編譯優化備注（參見第5.7節）告知我們轉換失敗的情況。然而，在這種情況下，無論是Clang 10.0.1還是GCC 10.2都無法明確告知表達式strlen(a)未被提升出循環。唯一的方法是根據應用程序的配置文件查看生成的匯編代碼的熱點部分。分析機器代碼需要基本的匯編語言閱讀能力，但這是一項非常有價值的活動。
首先嘗試獲取最容易的優化是一個合理的策略。開發者可以使用編譯器優化報告或檢查循環的機器代碼以尋找簡單的改進方法。有時候，我們可以通過使用用戶指令來調整編譯器的轉換。例如，當我們發現編譯器將我們的循環展開了4倍時，我們可以檢查是否使用更高的展開系數會提高性能。大多數編譯器都支持#pragma unroll(8)，它會指示編譯器使用用戶指定的展開系數。還有其他的指令來控制特定的轉換，比如循環向量化、循環分布等。有關完整的用戶指令列表，請查閱編譯器的手冊。
接下來，開發者應該確定循環中的瓶頸，并根據硬件的理論最大性能進行評估。可以首先使用Roofline性能模型（第5.5節），它將揭示開發者應該嘗試解決的瓶頸。循環的性能受以下因素之一或多個因素的限制：內存延遲、內存帶寬或機器的計算能力。一旦確定了循環的瓶頸，開發者可以嘗試應用本節前面討論過的轉換技術之一。
個人經驗：盡管針對特定的計算問題有眾所周知的優化技術，但在很大程度上，循環優化是一種需要經驗的“黑魔法”。我建議您依靠編譯器，只有在必要時才進行必要的轉換。最后，保持代碼盡可能簡單，如果性能提升微不足道，不要引入過于復雜的改變。
8.2.2.4 Use Loop Optimization Frameworks
在過去的幾年中，研究人員們開發了一些技術來確定循環轉換的合法性并自動對循環進行轉換。其中一個創新是多面體框架（polyhedral framework）。GRAPHITE是最早集成到生產編譯器中的多面體工具之一。GRAPHITE基于從GCC的低級中間表示GIMPLE中提取的多面體信息，執行一系列經典的循環優化。GRAPHITE證明了該方法的可行性。
基于LLVM的編譯器使用自己的多面體框架：Polly。Polly是一個面向LLVM的高級循環和數據局部性優化器及優化基礎設施。它使用基于整數多面體的抽象數學表示來分析和優化程序的內存訪問模式。Polly執行經典的循環轉換，特別是瓦片化和循環合并，以改善數據局部性。該框架在許多著名基準測試中實現了顯著的加速（Grosser等人，2012年）。下面是一個示例，展示了Polly如何將Polybench 2.0基準套件中的GEneral Matrix-Multiply（GEMM）核心的速度提升近30倍：
$ clang -O3 gemm.c -o gemm.clang
$ time ./gemm.clang
real 0m6.574s
$ clang -O3 gemm.c -o gemm.polly -mllvm -polly
$ time ./gemm.polly
real 0m0.227sPolly是一個強大的循環優化框架，然而它仍然無法處理一些常見且重要的情況。在LLVM基礎設施的標準優化流程中，Polly并未啟用，并且需要用戶顯式地提供編譯器選項來使用它（-mllvm -polly）。當尋找加速循環的方法時，使用多面體框架是一個可行的選擇。
8.2.3 Vectorization ? ?//向量化
在現代處理器上，使用SIMD指令可以比常規的非矢量化（標量）代碼實現顯著加速。在進行性能分析時，軟件工程師最重要的任務之一是確保熱點代碼由編譯器進行向量化處理。本節旨在引導工程師發現向量化的機會。回顧一下關于現代CPU的SIMD能力的一般信息，讀者可以參考第3.7節。
大多數向量化都是自動完成的，無需用戶干預（自動向量化）。也就是說，編譯器會自動識別源代碼中產生SIMD機器代碼的機會。依賴自動向量化是一個很好的策略，因為現代編譯器可以為各種源代碼輸入生成快速的向量化代碼。正如前面給出的建議一樣，作者建議讓編譯器完成其工作，只有在必要時才進行干預。
在一些罕見的情況下，軟件工程師需要根據從編譯器或分析數據中獲得的反饋來調整自動向量化。在這種情況下，程序員需要告訴編譯器某個代碼區域是可向量化的，或者向量化是有益的。現代編譯器具有擴展功能，允許高級用戶直接控制向量化器，并確保代碼的某些部分得到高效的向量化處理。后續章節將提供使用編譯器提示的幾個示例。
需要注意的是，在一些問題中，SIMD具有無可替代的價值，而自動向量化并不起作用，并且在不久的將來也不太可能起作用（可以參考[Mu?a和Lemire, 2019]中的一個示例）。如果編譯器無法生成所需的匯編指令，可以借助編譯器內置函數來重寫代碼片段。在大多數情況下，編譯器內置函數提供了與匯編指令的一對一映射（請參見第10.2節）。
個人意見：盡管在某些情況下開發人員需要使用編譯器內置函數，但我建議主要依賴編譯器的自動向量化，只有在必要時才使用內置函數。使用編譯器內置函數的代碼類似于內聯匯編，很快就會變得難以理解。編譯器的自動向量化通常可以通過pragma和其他提示進行調整。
一般來說，編譯器會進行三種類型的向量化：內部循環向量化、外部循環向量化和SLP（超級字級并行）向量化。本節主要討論內部循環向量化，因為這是最常見的情況。關于外部循環和SLP向量化，我們在附錄B中提供了一般信息。
8.2.3.1 Compiler Autovectorization.
許多因素可能阻礙自動向量化，其中一些因素與編程語言的語義相關。例如，編譯器必須假設無符號循環索引可能會溢出，這可能會阻止某些循環轉換。另一個例子是C語言的假設：程序中的指針可以指向重疊的內存區域，這會使程序的分析變得非常困難。另一個主要障礙是處理器本身的設計。在某些情況下，處理器對于某些操作沒有高效的向量指令。例如，在大多數處理器上不支持執行受位掩碼控制的加載和存儲操作。另一個例子是有符號整數到雙精度浮點數的向量寬度格式轉換，因為結果涉及不同大小的向量寄存器。
盡管存在所有這些挑戰，軟件開發人員可以解決其中許多問題并啟用向量化。在本節的后面部分，我們將提供如何與編譯器合作并確保熱點代碼由編譯器進行向量化的指導。
向量化器通常分為三個階段：合法性檢查、盈利性檢查和轉換本身：
- 合法性檢查：在此階段，編譯器檢查是否可以將循環（或其他代碼區域）轉換為使用向量。循環向量化器檢查循環的迭代是否連續，即循環按線性方式進行。向量化器還確保循環中的所有內存和算術操作可以擴展為連續操作，循環的控制流在所有通道上都是統一的，并且內存訪問模式是統一的。編譯器必須檢查或確保生成的代碼不會觸及不應該觸及的內存，并且操作的順序將被保留。編譯器需要分析指針的可能范圍，如果有一些缺失的信息，它必須假設轉換是非法的。合法性階段收集了一系列必須滿足的要求，以使循環向量化合法。
- 盈利性檢查：然后，向量化器檢查轉換是否具有盈利性。它比較不同的向量化因素，并確定哪個向量化因素執行速度最快。向量化器使用成本模型來預測不同操作（例如標量加法或向量加載）的成本。它需要考慮將數據洗牌到寄存器中的附加指令，預測寄存器壓力，并估算確保滿足允許向量化的前提條件的循環保護的成本。檢查盈利性的算法很簡單：1）累加代碼中所有操作的成本，2）比較每個代碼版本的成本，3）將成本除以預期執行計數。例如，如果標量代碼花費8個周期，而向量化代碼花費12個周期，但一次執行4個循環迭代，則向量化版本的循環可能更快。
- 轉換：最后，在向量化器確定轉換是合法且具有盈利性之后，它們會轉換代碼。這個過程還包括插入啟用向量化的保護。例如，大多數循環使用未知的迭代計數，因此編譯器必須生成循環的標量版本以及向量化的版本，以處理最后幾次迭代。編譯器還必須檢查指針是否重疊等。所有這些轉換都使用在合法性檢查階段收集的信息進行。
8.2.3.2 Discovering vectorization opportunities.
Amdahl定律告訴我們，在程序執行過程中，我們應該花時間僅分析那些最常使用的代碼部分。因此，性能工程師應該專注于通過分析工具（見5.4節）突出顯示的熱點代碼部分。正如前面提到的，向量化最常用于循環。
發現改進向量化的機會應該從分析程序中的熱點循環開始，并檢查編譯器對它們進行了哪些優化。檢查編譯器的向量化備注（見5.7節）是了解這一點的最簡單方法。現代編譯器可以報告一個特定循環是否被向量化，并提供額外的細節，例如向量化因子（VF）。如果編譯器無法將一個循環向量化，它也能告訴失敗的原因。
使用編譯器優化報告的另一種方法是檢查匯編輸出。最好分析來自性能分析工具的輸出，該工具顯示給定循環的源代碼與生成的匯編指令之間的對應關系。然而，這種方法需要具備讀取和理解匯編語言的能力。想要弄清楚編譯器生成的指令的語義可能需要一些時間218。但是這種技能是非常有價值的，并且通常可以提供額外的見解。例如，我們可以發現生成的代碼存在不夠優化的問題，比如缺乏向量化、向量化因子不夠優化、執行不必要的計算等。
在嘗試加速可向量化代碼時，開發人員經常遇到幾種常見情況。下面我們介紹四個典型場景，并給出在每種情況下的一般指導。
8.2.3.3 Vectorization is illegal.
在某些情況下，遍歷數組元素的代碼可能無法進行向量化。向量化備注非常有效地解釋了出現問題的原因，以及編譯器無法對代碼進行向量化的原因。第36條示例展示了一個循環內的依賴關系，阻止了向量化。
Listing 36 Vectorization: read-after-write dependence.
void vectorDependence(int *A, int n) {
for (int i = 1; i < n; i++)
A[i] = A[i-1] * 2;
}雖然由于上述的硬性限制，有些循環無法進行向量化，但在某些約束條件放寬的情況下，其他循環可能是可以進行向量化的。有些情況下，編譯器無法對循環進行向量化，是因為它無法證明向量化是合法的。編譯器通常非常保守，只有在確保不會破壞代碼的情況下才進行轉換。通過向編譯器提供額外的提示，可以放寬這種軟性限制。例如，在轉換執行浮點算術運算的代碼時，向量化可能會改變程序的行為。浮點加法和乘法是可交換的，也就是說，可以交換左操作數和右操作數而不改變結果：(a + b == b + a)。然而，這些操作不是可結合的，因為舍入發生的時間不同：((a + b) + c) != (a + (b + c))。第37條示例中的代碼無法通過編譯器自動進行向量化。原因是向量化會將變量sum轉換為向量累加器，這會改變操作的順序，并可能導致不同的舍入決策和不同的結果。
Listing 37 Vectorization: flfloating-point arithmetic.
1 // a.cpp
2 float calcSum(float* a, unsigned N) {
3 float sum = 0.0f;
4 for (unsigned i = 0; i < N; i++) {
5 sum += a[i];
6 }
7 return sum;
8 }然而，如果程序在最終結果上可以容忍一點不準確性（通常是這種情況），我們可以將這個信息傳遞給編譯器以啟用向量化。Clang和GCC編譯器提供了一個標志 -ffast-math220，允許進行此類轉換：
$ clang++ -c a.cpp -O3 -march=core-avx2 -Rpass-analysis=.*
...
a.cpp:5:9: remark: loop not vectorized: cannot prove it is safe to reorder
floating-point operations; allow reordering by specifying '#pragma clang
loop vectorize(enable)' before the loop or by providing the compiler
option '-ffast-math'. [-Rpass-analysis=loop-vectorize]
...
$ clang++ -c a.cpp -O3 -ffast-math -Rpass=.*
...
a.cpp:4:3: remark: vectorized loop (vectorization width: 4, interleaved
count: 2) [-Rpass=loop-vectorize]
...讓我們再來看另一個典型情況，當編譯器無法證明循環在非重疊內存區域上操作時，它通常選擇保守一點。讓我們回顧一下第5.7節中提供的第9條示例。當編譯器嘗試對第38條示例中的代碼進行向量化時，通常無法做到這一點，因為數組a、b和c的內存區域可能重疊。
Listing 38 a.c
1 void foo(float* a, float* b, float* c, unsigned N) {
2 for (unsigned i = 1; i < N; i++) {
3 c[i] = b[i];
4 a[i] = c[i-1];
5 }
6 }這是由GCC 10.2提供的優化報告（使用-fopt-info啟用）：
$ gcc -O3 -march=core-avx2 -fopt-info
a.cpp:2:26: optimized: loop vectorized using 32 byte vectors
a.cpp:2:26: optimized: loop versioned for vectorization because of possible
aliasingGCC已經識別出數組a、b和c的內存區域可能存在重疊，并創建了同一個循環的多個版本。編譯器插入了運行時檢查來檢測內存區域是否重疊。根據這些檢查，它在向量化和標量化版本之間進行調度。在這種情況下，向量化帶來了插入潛在昂貴的運行時檢查的成本。如果開發人員知道數組a、b和c的內存區域不重疊，可以在循環前面插入#pragma GCC ivdep或使用__restrict__關鍵字，如第10條示例中所示。這樣的編譯器提示將消除GCC編譯器插入之前提到的運行時檢查的需要。
由于編譯器的本質是靜態工具，它們只根據它們處理的代碼進行推理。例如，一些動態工具（如Intel Advisor）可以檢測給定循環中是否實際發生了跨迭代依賴或對具有重疊內存區域的數組的訪問等問題。但請注意，這類工具只提供建議。輕率地插入編譯器提示可能會引起真正的問題。
8.2.3.4 Vectorization is not beneficial.
在某些情況下，編譯器可以對循環進行向量化，但認為這樣做并不劃算。在第39條示例中的代碼中，編譯器可以對數組A的內存訪問進行向量化，但需要將對數組B的訪問拆分為多個標量加載。散射/聚集模式相對昂貴，而能夠模擬操作成本的編譯器通常決定避免向具有這種模式的代碼進行向量化。
Listing 39 Vectorization: not benefificial.
1 // a.cpp
2 void stridedLoads(int *A, int *B, int n) {
3 for (int i = 0; i < n; i++)
4 A[i] += B[i * 3];
5 }以下是第39條代碼的編譯器優化報告：
$ clang -c -O3 -march=core-avx2 a.cpp -Rpass-missed=loop-vectorize
a.cpp:3:3: remark: the cost-model indicates that vectorization is not
beneficial [-Rpass-missed=loop-vectorize]
for (int i = 0; i < n; i++)
^用戶可以使用#pragma hint指令來強制Clang編譯器對循環進行向量化，如第40條示例所示。然而，請記住，向量化是否具有盈利性在很大程度上取決于運行時數據，例如循環的迭代次數。編譯器沒有這些信息可用，因此它們通常傾向于保守處理。開發人員可以在尋找性能提升空間時使用這類提示。
Listing 40 Vectorization: not benefificial.
1 // a.cpp
2 void stridedLoads(int *A, int *B, int n) {
3 #pragma clang loop vectorize(enable)
4 for (int i = 0; i < n; i++)
5 A[i] += B[i * 3];
6 }開發人員應該意識到使用向量化代碼的隱藏成本。使用AVX和尤其是AVX512向量指令會導致頻率大幅降低。代碼的向量化部分應該足夠熱門，以證明使用AVX512是合理的。
8.2.3.5 Loop vectorized but scalar version used. ? ?//循環被向量化，但使用了標量版本。
在某些情況下，編譯器可以成功地對代碼進行向量化，但向量化代碼在分析器中不可見。當檢查循環的相應匯編代碼時，通常很容易找到循環主體的向量化版本，因為它使用了向量寄存器，這在程序的其他部分通常不常見，并且代碼被展開并填充了檢查和多個版本，以適應不同的邊緣情況。
如果生成的代碼沒有被執行，可能的原因之一是編譯器生成的代碼假設循環的迭代次數比程序實際使用的要高。例如，在現代CPU上有效地進行向量化，程序員需要使用AVX2進行向量化，并將循環展開4-5次，以便為流水線化的FMA單元生成足夠的工作。這意味著每次循環迭代需要處理大約40個元素。許多循環的迭代次數可能低于此值，并且可能回退到使用標量的剩余循環。通過分析器可以輕松發現這些情況，標量的剩余循環會變得明顯，而向量化代碼則保持不活躍。
解決這個問題的方法是強制向量化器使用較低的向量化因子或展開次數，以減少循環處理的元素數量，并使更多迭代次數較低的循環訪問快速向量化的循環主體。開發人員可以通過#pragma hints指令來實現這一點。對于Clang編譯器，可以使用#pragma clang loop vectorize_width(N)，如easyperf博客中所示。
8.2.3.6 Loop vectorized in a suboptimal way
當你看到一個循環被向量化并在運行時執行時，通常意味著程序的這部分已經表現良好。然而，也有例外情況。有時候人工專家可以提出比編譯器生成的代碼更高效的代碼。
最優的向量化因子可能不直觀，原因有幾個。首先，對于人類來說，想象CPU內部的操作是困難的，除了實際嘗試多種配置外別無選擇。涉及多個向量通道的向量重組操作可能比預期的更加昂貴，這取決于許多因素。其次，在運行時，程序可能以不可預測的方式行為，這取決于端口壓力和許多其他因素。建議是嘗試強制向量化器選擇特定的向量化因子和展開因子，并測量結果。向量化指令可以幫助用戶枚舉不同的向量化因子，并找出最高性能的一種。
對于每個循環來說，可能的配置相對較少，而在典型輸入上運行循環是人類能做到而編譯器無法做到的。
最后，有些情況下，標量的未向量化版本的循環性能比向量化版本好。這可能是因為向量操作（如gather/scatter加載、掩碼、重組等）很耗費資源，而編譯器為了實現向量化必須使用這些操作。性能工程師也可以嘗試以不同的方式禁用向量化。對于Clang編譯器，可以通過編譯選項-fno-vectorize和-fno-slp-vectorize來禁用，或者使用特定于特定循環的提示，例如#pragma clang loop vectorize(enable)。
8.2.3.7 Use languages with explicit vectorization.
向量化也可以通過使用專門用于并行計算的編程語言重寫程序的部分來實現。這些語言使用特殊的結構和對程序數據的了解，將代碼高效地編譯成并行程序。最初，這些語言主要用于將工作轉移到特定的處理單元，例如圖形處理單元（GPU）、數字信號處理器（DSP）或可編程門陣列（FPGA）。然而，一些編程模型也可以針對CPU進行優化（例如OpenCL和OpenMP）。
其中一種并行語言是Intel? Implicit SPMD Program Compiler（ISPC），我們將在本節中介紹一些。ISPC語言基于C編程語言，并使用LLVM編譯器基礎架構為許多不同的體系結構生成優化代碼。ISPC的關鍵特性是"接近底層"的編程模型和在SIMD體系結構上的性能可移植性。它要求從傳統的編程思維方式轉變，但給程序員更多控制CPU資源利用的權力。
ISPC的另一個優點是其互操作性和易用性。ISPC編譯器生成的是標準的目標文件，可以與傳統的C/C++編譯器生成的代碼鏈接。由于使用ISPC編寫的函數可以像使用C代碼一樣調用，因此ISPC代碼可以輕松地插入任何本地項目中。
在 ISPC 中，我們可以使用類似于程序清單 37 中展示的簡單函數的示例來重寫代碼。ISPC將程序視為基于目標指令集的并行實例運行。例如，當使用 SSE 和浮點數時，它可以同時計算 4 個操作。每個程序實例將對向量值 i 進行操作，如 (0,1,2,3)，然后是 (4,5,6,7)，以此類推，從而一次有效地計算出 4 個和。正如您所看到的，使用了一些不典型于 C 和 C++ 的關鍵字：
? export 關鍵字表示該函數可以從與 C 兼容的語言中調用。
? uniform 關鍵字表示變量在程序實例之間共享。
? varying 關鍵字表示每個程序實例都有自己的變量副本。
? foreach 關鍵字與經典的 for 循環相同，只是它將工作分布在不同的程序實例之間。
Listing 41 ISPC version of summing elements of an array.
export uniform float calcSum(const uniform float array[],
uniform ptrdiff_t count)
{
varying float sum = 0;
foreach (i = 0 ... count)
sum += array[i];
return reduce_add(sum);
}由于函數 calcSum 必須返回一個單一值（一個 uniform 變量），而我們的 sum 變量是 varying 類型的，因此我們需要使用 reduce_add 函數來收集每個程序實例的值。ISPC還會根據需要生成 peeled 循環和余數循環，以考慮那些沒有正確對齊或不是向量寬度的倍數的數據。
“貼近底層”的編程模型。傳統的 C 和 C++ 語言存在一個問題，即編譯器并不總是對代碼的關鍵部分進行向量化優化。通常情況下，程序員會使用編譯器內置函數（參見第10.2節），這繞過了編譯器的自動向量化，但一般而言比較困難，并且需要在新的指令集出現時進行更新。ISPC通過默認將每個操作都視為SIMD操作來幫助解決這個問題。例如，ISPC 語句 sum += array[i] 在隱式中被視為一個并行進行多次相加的SIMD操作。ISPC不是一個自動向量化的編譯器，它不會自動發現向量化的機會。由于 ISPC 語言與 C 和 C++ 非常相似，相比使用內置函數，ISPC 更好地允許您專注于算法而不是低級指令。此外，據報道，在性能方面，ISPC 的性能與手寫的內置函數代碼相媲美[Pharr 和 Mark 2012]或超越[228]。
性能可移植性。ISPC 可以自動檢測 CPU 的特性，以充分利用所有可用的資源。程序員可以編寫一次 ISPC 代碼，然后編譯為許多矢量指令集，如 SSE4、AVX 和 AVX2。ISPC 還可以為不同的架構生成代碼，如 x86 CPU、ARM NEON，并且還具有實驗性的對 GPU 卸載的支持。
8.3 Chapter Summary
? 大多數實際應用程序經歷的性能瓶頸與 CPU 后端相關。這并不奇怪，因為與內存相關的問題以及低效的計算都屬于這個類別。
? 內存子系統的性能增長速度不及 CPU 的性能增長速度。然而，在許多應用程序中，內存訪問是性能問題的常見來源。加速這類程序需要重新審查它們訪問內存的方式。
? 在第8.1節中，我們討論了一些常見的緩存友好數據結構、內存預取和利用大內存頁面來改善 DTLB 性能的技巧。
? 低效的計算也在實際應用程序的性能瓶頸中占據重要部分。現代編譯器非常擅長通過執行許多不同的代碼轉換來消除不必要的計算開銷。然而，我們有很大機會比編譯器提供的優化效果更好。
? 在第8.2節中，我們展示了如何通過強制進行某些代碼優化來搜索程序中的性能潛力。我們討論了諸如函數內聯、循環優化和向量化等常見的轉換方法。
9 Optimizing Bad Speculation
?現代CPU中的預測功能在第3.3.3節中有描述。當分支預測錯誤時，會導致顯著的速度懲罰。當這種情況經常發生時，CPU需要清除之前提前完成的所有推測工作，并重新開始填充正確路徑的指令。通常，由于分支預測錯誤，現代CPU會經歷15-20個時鐘周期的懲罰。
如今，處理器在預測分支結果方面非常出色。它們不僅可以遵循靜態預測規則，還可以檢測動態模式。通常，分支預測器會保存先前分支結果的歷史記錄，并試圖猜測下一個結果。然而，當模式變得難以跟隨對CPU分支預測器來說，它可能會影響性能。通過查看TMA Bad Speculation指標，可以了解程序因分支預測錯誤而受到的影響程度。
個人經驗：程序總是會發生一定數量的分支預測錯誤。普通應用程序的“Bad Speculation”率在5-10%的范圍內是正常的。如果這個指標超過了10%，我建議注意一下。
由于分支預測器擅長尋找模式，因此以往優化分支預測的建議已不再適用。過去可以通過在分支指令前添加一個預測提示（0x2E：分支不被采取，0x3E：分支被采取）來提高性能。盡管這種技術可以改善舊平臺上的性能，但在新平臺上并不會產生收益。
也許，擺脫分支預測錯誤的唯一直接方法就是擺脫分支本身。在接下來的兩節中，我們將了解如何使用查找表和條件執行來替代分支。
9.1 Replace branches with lookup ? ?//將分支替換為查找表
使用查找表可以避免分支語句，從而提高性能。在代碼示例中，函數mapToBucket將值映射到相應的桶中。對于均勻分布的值v，它們被映射到各個桶的概率是相等的。在基準版本生成的匯編代碼中，通常會看到很多分支語句，這可能導致高錯誤預測率。希望能夠通過使用單個數組查找來重寫mapToBucket函數，如Listing 43所示。
Listing 43中的mapToBucket函數的匯編代碼應該只使用一條分支語句，而不是多條。對于典型的熱路徑，該函數將執行未使用的分支和一條加載指令。由于我們預計大多數輸入值將落入buckets數組覆蓋的范圍內，用于保護越界訪問的分支將被CPU正確預測。此外，buckets數組相對較小，因此我們可以期待它位于CPU緩存中，這將確保對它的快速訪問。[Lemire, 2020]
Listing 42 Replacing branches: baseline version.
int mapToBucket(unsigned v) {
if (v >= 0 && v < 10) return 0;
if (v >= 10 && v < 20) return 1;
if (v >= 20 && v < 30) return 2;
if (v >= 30 && v < 40) return 3;
if (v >= 40 && v < 50) return 4;
return -1;
}Listing 43 Replacing branches: lookup version.
int buckets[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
... };
int mapToBucket(unsigned v) {
if (v < (sizeof (buckets) / sizeof (int)))
return buckets[v];
return -1;
}當需要映射一個更大范圍的值時，分配一個非常大的數組是不切實際的。在這種情況下，我們可以使用區間映射數據結構來實現這一目標，它可以使用較少的內存但具有對數級的查找復雜度。讀者可以在Boost和LLVM中找到現有的區間映射容器的實現。
9.2 Replace branches with predication
有些分支語句可以通過執行分支的兩個部分并選擇正確的結果來有效地消除（條件執行）。當存在這種情況時，可能會嘗試使用轉換來消除if條件判斷語句，如Listing 44所示。
對于Listing 45中的代碼版本，編譯器可以消除分支并生成CMOV指令234。CMOVcc指令檢查EFLAGS寄存器中一個或多個狀態標志（CF、OF、PF、SF和ZF）的狀態，并在標志處于指定狀態（或條件）時執行移動操作。[Int, 2020, Volume 2]下面是基準版本和改進版本的兩個匯編清單：
修改后的匯編代碼序列不再包含原始的分支指令。然而，在第二個版本中，x和y都是獨立計算的，然后只選擇一個值。雖然這種轉換消除了分支預測錯誤的成本，但它可能比原始代碼執行更多的工作。性能改進在很大程度上取決于computeX和computeY函數的特性。如果這些函數很小且編譯器能夠內聯它們，那么可能會帶來明顯的性能優勢。如果這些函數很大，那么承受分支預測錯誤的代價可能比執行兩個函數更低廉。
需要注意的是，條件執行并不總是對應用程序的性能有益。條件執行的問題在于它限制了CPU的并行執行能力。對于Listing 44中的代碼片段，CPU可以選擇if條件的true分支，并繼續以a = computeX()的值進行代碼的推測執行。例如，如果后續存在使用a索引數組元素的加載操作，這個加載可以在我們得知if分支的真實結果之前就發出。對于Listing 45中的代碼，這種推測是不可能的，因為CPU不能在CMOVNE指令完成之前發出使用a的加載指令。
因此，是否使用條件執行（predication）取決于具體情況。在某些情況下，消除分支預測錯誤的成本可能超過了通過條件執行帶來的性能改進。在進行優化時，需要權衡條件執行和并行執行之間的平衡，以獲得最佳性能。
二分查找（binary search）是一個很好的例子，可以展示在選擇標準版本和無分支版本代碼之間進行權衡時所涉及的折衷。下面是兩種情況的描述：
1. 對于一個大數組的搜索，該數組不適合存儲在CPU緩存中，基于分支的二分查找版本表現更好，因為與內存訪問的延遲相比（由于緩存未命中而較高），分支預測錯誤的代價較低。由于存在分支，CPU能夠推測它們的結果，這允許同時從當前迭代和下一迭代加載數組元素。推測還會繼續進行，可能會同時存在多個加載操作。
2. 對于適合存儲在CPU緩存中的小數組，情況則相反。無分支的二分查找仍然需要將所有的內存訪問串行化，正如前面解釋的那樣。但是，這次加載操作的延遲很小（只有幾個周期），因為數組適合CPU緩存。基于分支的二分查找會遭受持續的預測錯誤，其代價約為20個周期。在這種情況下，預測錯誤的代價遠大于內存訪問的代價，因此無法獲得推測執行帶來的好處。在這種情況下，無分支版本通常會更快。
二分查找是一個很好的例子，可以說明在選擇標準版本和無分支版本實現時如何進行推理。現實世界中的場景可能更難分析，因此建議測量數據，判斷是否有必要在你的情況下替換分支語句。
9.3 Chapter Summary
? 現代處理器在預測分支結果方面表現非常出色。因此，我建議只有在TMA報告指出存在高不良預測度量時才開始修復分支預測錯誤的工作。
? 當分支預測器難以跟蹤分支結果模式時，應用程序的性能可能會受到影響。在這種情況下，無分支版本的算法可能更好。在本章中，我們展示了如何使用查找表和條件執行來替換分支語句。在某些情況下，還可以使用編譯器內置函數來消除分支，就像[Kapoor, 2009]所示。
? 無分支算法并不是普遍適用的。始終進行測量，以確定在你的情況下哪種方式更好。
10 Other Tuning Areas
在本章中，我們將介紹一些與前三章中討論的類別沒有明確關聯但仍然非常重要的優化主題。這些主題雖然不屬于特定的類別，但在本書中找到它們的位置是非常有意義的。
10.1 Compile-Time Computations ? ?//編譯時計算
如果程序的一部分執行的計算與輸入無關，可以提前進行預計算，而不是在運行時執行。現代優化編譯器已經將很多計算移到編譯時，特別是像 int x = 2 * 10 這樣的簡單情況轉換為 int x = 20。然而，如果涉及到分支、循環和函數調用等更復雜的計算，在編譯時處理可能會有困難。C++語言提供了一些功能，可以確保某些計算在編譯時發生。
在C++中，可以使用各種元編程技術將計算轉移到編譯時。在C++11/14之前，開發人員使用模板來實現這一目標。理論上，可以使用模板元編程來表示任何算法，但這種方法往往語法復雜，編譯速度較慢。然而，這是一種成功的方法，它開啟了一類新的優化方式。幸運的是，隨著每個新的C++標準推出，元編程變得更加簡單。C++14標準允許使用constexpr函數，而C++17標準則提供了if constexpr關鍵字來實現編譯時分支。這種新的元編程方式允許在編譯時進行許多計算，同時不影響代碼的可讀性。[Fog, 2004, 第15章 元編程]
以下是通過將計算轉移到編譯時來優化應用程序的示例46。假設程序涉及對一個數是否為質數的測試。如果我們知道大部分被測試的數字都小于1024，我們可以預先計算結果，并將它們保存在一個constexpr數組primes中。在運行時，大部分isPrime函數的調用只需要從primes數組中加載一次數據，這比在運行時計算要快得多。
10.2 Compiler Intrinsics ? ?//編譯器內置函數
有些應用程序很少有需要大量調優的熱點部分。然而，編譯器在這些熱點位置生成的代碼并不總是符合我們的期望。例如，一個程序在循環中進行一些計算，但編譯器以次優的方式進行了向量化。這通常涉及一些棘手或特殊的算法，我們可以想出更好的指令序列來實現。使用C和C++語言的標準結構很難甚至不可能讓編譯器生成所需的匯編代碼。
幸運的是，有辦法在不編寫低級匯編語言的情況下，強制編譯器生成特定的匯編指令。為了實現這一點，可以使用編譯器內置函數（compiler intrinsics），它們會被轉換成具體的匯編指令。內置函數具有與內聯匯編相同的好處，但同時提高了代碼的可讀性，允許編譯器類型檢查，幫助指令調度，并有助于減少調試工作。示例中的代碼清單47展示了如何使用編譯器內置函數（函數bar）重寫函數foo中的同樣循環的例子。
在代碼清單47中，兩個函數生成了類似的匯編指令。然而，還有幾個注意事項。首先，當依賴自動向量化時，編譯器會插入所有必要的運行時檢查。例如，它會確保有足夠的元素供應給向量執行單元。其次，函數foo將為處理循環剩余部分生成一個回退的標量版本。最后，大多數向量內置函數假設數據是對齊的，因此bar使用了movaps（對齊加載），而foo使用了movups（非對齊加載）。在使用編譯器內置函數時，開發人員必須自行處理安全方面的問題。
當使用非可移植的平臺特定內置函數編寫代碼時，開發人員還應為其他架構提供備選方案。可以在該參考文檔中找到適用于Intel平臺的所有可用內置函數的列表。
10.3 Cache Warming ? ?//緩存預熱
第7節和第8.1.1節詳細介紹了指令緩存和數據緩存，以及它們各自的性能影響，并提供了具體的技術來最大化利益。然而，在某些應用負載中，對延遲最敏感的代碼部分往往是最不經常執行的。這導致函數塊和相關數據隨著時間推移從指令緩存(I-cache)和數據緩存(D-cache)中被淘汰出去。然后，就在我們需要執行那個關鍵但很少執行的代碼片段時，我們遇到了I-cache和D-cache的缺失懲罰，這可能超過我們的目標性能預算。
這樣的負載示例可以是一個高頻交易應用程序，它持續從股票交易所讀取市場數據信號，并在檢測到有利的市場信號時向交易所發送買入訂單。在上述負載中，涉及讀取市場數據的代碼路徑最常執行，而執行買入訂單的代碼路徑很少執行。如果我們希望我們的買入訂單盡快達到交易所，并利用市場數據中檢測到的有利信號，則在決定執行關鍵代碼時不希望出現緩存缺失。這就是緩存預熱技術的幫助之處。緩存預熱包括定期運行延遲敏感的代碼，以使其保持在緩存中，同時確保不會完全執行任何不需要的操作。運行延遲敏感的代碼還可以“熱身”數據緩存，將延遲敏感的數據引入其中。事實上，這種技術經常用于像CppCon 2018 lightning演講中描述的交易應用程序中。
10.4 Detecting Slow FP Arithmetic
對于使用浮點數值的應用程序，存在一定的概率會出現異常情況，即浮點數變為非規格化數。對非規格化數進行操作可能會變得慢10倍甚至更多。當CPU處理嘗試對非規格化浮點數進行算術操作的指令時，需要對這種情況進行特殊處理。由于這是異常情況，CPU會請求微碼輔助。微碼序列器（MSROM）將向流水線提供大量微操作（參見4.4節），以處理這種情況。
TMA方法將這類瓶頸歸類為“Retiring”（退休）類別。這是“高Retiring”并不意味著好事情的情況之一。由于對非規格化數進行的操作通常代表程序的不良行為，可以只收集FP_ASSIST.ANY性能計數器的值。該值應該接近零。Blog easyperf中介紹了一個進行非規格化浮點運算并因此遇到許多FP assist的示例。C++開發人員可以通過使用std::isnormal()函數來防止其應用程序陷入與次正常值的操作。或者，可以更改SIMD浮點運算的模式，在CPU控制寄存器中啟用“flush-to-zero”（FTZ）和“denormals-are-zero”（DAZ）標志，以防止SIMD指令生成非規格化數。在代碼級別禁用次正常浮點數可以使用專用宏來完成，這可能因編譯器而異。
10.5 System Tuning
在調優應用程序以充分利用CPU微架構的各種復雜功能之后，我們最不希望的就是系統固件、操作系統或內核破壞我們的努力。即使是經過高度調優的應用程序，如果遭遇系統管理中斷（SMI），即整個操作系統被停止以執行固件代碼的BIOS中斷，那么它的意義也將變得微乎其微。這種中斷可能每次運行10到100毫秒。
可以說，開發人員通常對應用程序執行的環境幾乎沒有任何控制權。當我們發布產品時，不太可能調整每個客戶可能擁有的設置。通常，足夠大的組織會有專門的運維團隊來處理此類問題。然而，當與這些團隊的成員進行溝通時，了解其他可能限制應用程序性能的因素非常重要。
如第2.1節所示，現代系統有許多需要調整的地方，避免受到系統干擾并不容易。一份針對基于x86服務器部署的性能調優手冊的示例是Red Hat的指南。在那里，您將找到消除或顯著減少來自系統BIOS、Linux內核和設備驅動程序等應用程序干擾源的緩存中斷的提示，以及許多其他應用程序干擾源。在將任何應用程序部署到生產環境之前，這些指南應作為所有新服務器構建的基準鏡像。
對于調整特定的系統設置，往往并不總是一個簡單的“是”或“否”的答案。例如，您的應用程序是否會受益于啟用了環境中的Simultaneous Multi-Threading (SMT)功能，事先并不清楚。一般的指導方針是只為展示相對較低IPC的異構工作負載啟用SMT。另一方面，如今CPU制造商提供的處理器核心數量如此之高，以至于SMT遠不像過去那樣必要。然而，這只是一個一般的指導方針，正如本書中所強調的一切，最好根據自己的實際情況進行測量。
大多數開箱即用的平臺都配置為在盡可能節省電力的同時實現最佳吞吐量。但是有些行業對實時性要求更高，比其他一切更關心較低的延遲。例如，汽車組裝線上運行的機器人就是這樣一個行業的例子。這些機器人執行的動作是由外部事件觸發的，通常有事先確定的時間預算，因為下一個中斷即將到來（通常稱為“控制循環”）。滿足此類平臺的實時目標可能需要犧牲機器的總吞吐量，或者允許它消耗更多能源。在這個領域中，一個流行的技術是禁用處理器的睡眠狀態，以保持其隨時準備作出反應。另一種有趣的方法被稱為Cache Locking，它為特定數據集保留了CPU緩存的部分空間，有助于優化應用程序內的內存延遲。
11 Optimizing Multithreaded Applications
?現代CPU每年都在不斷增加核心數量。截至2020年，您可以購買一款具有50個以上核心的x86服務器處理器！甚至一個中檔臺式機通常也會配置8個執行線程。由于每個CPU都擁有如此強大的處理能力，如何有效利用所有的硬件線程成為一個挑戰。為了應用程序未來的成功，準備軟件以適應日益增長的CPU核心數量非常重要。
多線程應用程序有其特殊性。在處理多個線程時，某些單線程執行的假設將被否定。例如，我們不能再通過查看單個線程來確定熱點，因為每個線程可能有自己的熱點。在常見的生產者-消費者設計中，生產者線程可能在大部分時間都處于休眠狀態。對這樣的線程進行分析無法揭示為什么我們的多線程應用程序無法良好擴展的原因。
11.1 Performance Scaling And Overhead ? ?//性能擴展和開銷
在處理單線程應用程序時，對程序的某一部分進行優化通常會對性能產生積極影響。然而，在多線程應用程序中，情況并非一定如此。有些應用程序中，線程A執行一些非常耗時的操作，而線程B則很早就完成了任務，只是在等待線程A完成。無論我們如何改進線程B，應用程序的延遲都不會減少，因為它將受到運行時間較長的線程A的限制。
?這種效果被廣泛稱為阿姆達爾定律，它規定了并行程序的加速比受到其串行部分的限制。圖46展示了理論上加速限制與處理器數量的關系。對于一個75%并行的程序，加速因子趨于4。
Figure 47a展示了Starbench并行基準套件中h264dec基準測試的性能擴展情況。我在擁有4個核心/8個線程的Intel Core i5-8259U上進行了測試。請注意，在使用了4個線程之后，性能的擴展并不明顯。很可能，獲取一個擁有更多核心的CPU也無法提高性能。
實際上，進一步增加計算節點到系統中可能會導致性能的倒退。這種效應可以通過Neil Gunther提出的通用可伸縮性定律（Universal Scalability Law，USL）來解釋，該定律是阿姆達爾定律的一個擴展。USL描述了計算節點（線程）之間的通信作為另一個限制性能的因素。隨著系統的擴展，開銷開始阻礙性能的提升。超過臨界點后，系統的能力開始下降（參見圖48）。USL被廣泛用于建模系統的容量和可伸縮性。
USL描述的性能下降由幾個因素驅動。首先，隨著計算節點數量的增加，它們開始競爭資源（爭用）。這導致額外的時間用于同步這些訪問。另一個問題出現在多個工作線程之間共享的資源上。我們需要在多個工作線程之間保持共享資源的一致狀態（一致性）。例如，當多個工作線程頻繁更改某個全局可見對象時，這些更改需要廣播到使用該對象的所有節點。由于額外的一致性維護需求，通常操作開始花費更多時間完成。在Intel Core i5-8259U上的h264dec基準測試中，通信開銷可以在圖47b中觀察到。請注意，隨著我們為該任務分配超過4個線程，基準測試在執行的指令和核心周期方面都遇到了更多的開銷。
優化多線程應用程序不僅涉及到本書中描述的所有技術，還需要檢測和緩解爭用和一致性帶來的影響。下面的小節將介紹用于解決這些額外挑戰以調優多線程程序的技術。
11.2 Parallel Efficiency Metrics ? ?//并行效率指標
在處理多線程應用程序時，工程師應該小心地分析基本指標，如CPU利用率和IPC（參見第4節）。其中一個線程可能顯示出高CPU利用率和高IPC，但實際上它可能只是在一個鎖上自旋。這就是為什么在評估應用程序的并行效率時，建議使用有效的CPU利用率，它只基于有效時間。
11.2.1 Effective CPU Utilization
表示應用程序有效利用可用的CPU的效率。它顯示系統上所有邏輯CPU的平均CPU利用率的百分比。CPU利用率指標僅基于有效時間，不包括并行運行時系統和自旋時間引入的開銷255。100%的CPU利用率意味著您的應用程序在運行的整個時間內保持所有邏輯CPU核心繁忙。[Int, 2020]
對于指定的時間間隔T，可以計算出有效CPU利用率的公式如下：
?
11.2.2 Thread Count
應用程序通常具有可配置的線程數量，這使它們能夠在具有不同核心數量的平臺上高效運行。顯然，如果使用的線程數低于系統可用的線程數，則會浪費其資源。另一方面，運行過多的線程可能會導致CPU時間增加，因為某些線程可能正在等待其他線程完成，或者時間可能浪費在上下文切換上。除了實際的工作線程，多線程應用程序通常還有輔助線程：主線程、輸入和輸出線程等。如果這些線程占用了大量時間，它們就需要專用的硬件線程。這就是為什么知道總線程數并正確配置工作線程數非常重要。
為了避免線程創建和銷毀的開銷，工程師通常會分配一個線程池，其中包含多個線程等待任務由監督程序分配并進行并發執行。這對于執行短期任務尤其有益。
11.2.3 Wait Time
等待時間發生在軟件線程由于阻塞或導致同步的API而等待時。等待時間是每個線程的時間；因此，總等待時間可以超過應用程序的經過時間。[Int, 2020]
由于同步或搶占，操作系統調度程序可以將線程從執行中切換出來。因此，等待時間可以進一步分為同步等待時間和搶占等待時間。大量的同步等待時間可能意味著應用程序具有高度競爭的同步對象。我們將在以下部分探討如何找到它們。顯著的搶占等待時間可以表示線程過多的問題，可能是由于應用程序線程數量過多或與操作系統線程或系統上的其他應用程序沖突。在這種情況下，開發人員應考慮減少總線程數或增加每個工作線程的任務粒度。
11.2.4 Spin Time
自旋時間是CPU繁忙的等待時間。這通常發生在同步API導致軟件線程等待時，CPU需要進行輪詢。[Int, 2020]。
實際上，內核同步原語的實現更傾向于在鎖定期間進行一段時間的自旋，而不是立即進行線程上下文切換（這是昂貴的）。然而，過多的自旋時間可能反映了無法進行有效工作的機會的喪失。
11.3 Analysis With Intel VTune Profiler
Intel VTune Profiler使用專門針對多線程應用程序的分析類型，稱為線程分析。它的摘要窗口（見圖49）顯示了關于整個應用程序執行的統計信息，識別了我們在第11.2節中描述的所有指標。通過有效CPU利用率直方圖，我們可以了解捕獲到的應用程序行為的幾個有趣事實。首先，平均而言，同一時間只有5個硬件線程（圖表上的邏輯核心）被利用。其次，幾乎從未同時激活所有8個硬件線程。
11.3.1 Find Expensive Locks
接下來，工作流程建議我們識別最有爭議的同步對象。圖50顯示了這些對象的列表。我們可以看到__pthread_cond_wait明顯突出，但由于程序中可能有數十個條件變量，我們需要知道哪個是CPU利用率低下的原因。
為了知道這一點，我們可以簡單地點擊__pthread_cond_wait，這將讓我們進入底部向上視圖，如圖51所示。我們可以看到導致線程在條件變量上等待的最常見路徑（等待時間的47%）：__pthread_cond_wait <- x264_8_frame_cond_wait <- mb_analyse_init。
接下來，我們可以通過在分析中雙擊相應的行，跳轉到x264_8_frame_cond_wait的源代碼（參見圖52）。然后，我們可以研究鎖的原因，以及使該位置的線程通信更高效的可能方法。
11.3.2 Platform View
Intel VTune Profiler的另一個非常有用的功能是平臺視圖（參見圖53），它允許我們觀察程序執行的任何時刻每個線程在做什么。這對于理解應用程序的行為并找到潛在的性能空間非常有幫助。例如，我們可以看到在從1秒到3秒的時間間隔內，只有兩個線程持續地利用了相應的CPU核心的約100%（TID為7675和7678的線程）。在該時間間隔內，其他線程的CPU利用率是突發性的。
平臺視圖還具有縮放和過濾功能。這使我們能夠了解每個線程在指定的時間范圍內執行的操作。要查看此內容，選擇時間線上的范圍，右鍵單擊并選擇“放大”和“通過選擇進行過濾”。Intel VTune Profiler將顯示在此時間范圍內使用的函數或同步對象。
11.4 Analysis with Linux Perf
Linux perf工具可以對應用程序可能創建的所有線程進行性能分析。它具有-s選項，可以記錄每個線程的事件計數。使用此選項，在報告的末尾，perf會列出所有線程的線程ID以及每個線程收集的樣本數：
要過濾特定軟件線程的樣本，可以使用--tid選項：
Linux perf還自動提供了我們在11.2節中討論的一些指標：
11.4.1 Find Expensive Locks
要使用Linux perf找到最具爭用的同步對象，需要對調度器上下文切換（sched:sched_switch）進行采樣，這是一個內核事件，因此需要root權限：
上面的輸出顯示了哪些線程最頻繁地被切換出執行。請注意，我們還收集調用堆棧（--call-graph dwarf，參見第5.4.3節），因為我們需要它來分析導致昂貴的同步事件的路徑：
上面的列表顯示了導致等待條件變量（__pthread_cond_wait）和后續的上下文切換最頻繁的路徑。這個路徑是x264_8_macroblock_analyse -> mb_analyse_init -> x264_8_frame_cond_wait。從這個輸出中，我們可以得知84%的所有上下文切換是由于在x264_8_frame_cond_wait內的線程等待條件變量引起的。
11.5 Analysis with Coz
在11.1節中，我們定義了識別影響多線程程序整體性能的代碼部分的挑戰。由于各種原因，優化多線程程序的某個部分并不總是會產生明顯的結果。Coz259是一種新型的分析器，它解決了這個問題，并填補了傳統軟件分析器留下的空白。它使用一種稱為“因果分析”的新技術，在應用程序運行時通過虛擬加速代碼段來預測某些優化的總體效果。它通過插入減慢所有其他并發運行代碼的暫停來實現這些“虛擬加速”。[Curtsinger和Berger，2015]
?
將Coz分析器應用于Phoronix測試套件中的C-Ray基準的示例顯示在第54頁上。根據圖表，如果我們將c-ray-mt.c中的第540行的性能提高20％，Coz預計C-Ray基準整體應用程序性能會相應增加約17％。一旦我們在該行上達到約45％的改進，按照Coz的估計，對應的應用程序的影響開始趨于平穩。有關此示例的更多詳細信息，請參閱easyperf博客上的文章。
11.6 Analysis with eBPF and GAPP
Linux支持各種線程同步原語，包括互斥鎖、信號量、條件變量等。內核通過futex系統調用支持這些線程原語。因此，通過在內核中跟蹤futex系統調用的執行，并收集涉及的線程的有用元數據，可以更容易地識別爭用瓶頸。Linux提供了內核跟蹤/分析工具來實現這一點，其中最強大的是Extended Berkeley Packet Filter（eBPF）。
eBPF是基于一個在內核中運行的沙盒化虛擬機，它允許在內核內安全高效地執行用戶定義的程序。這些用戶定義的程序可以用C語言編寫，并通過BCC編譯器262編譯成BPF字節碼，以便加載到內核虛擬機中。這些BPF程序可以在特定的內核事件執行時啟動，并通過各種方式將原始或處理后的數據返回給用戶空間。
開源社區提供了許多用于通用目的的eBPF程序。其中一個工具是通用自動并行分析器(GAPP)，它幫助跟蹤多線程爭用問題。GAPP使用eBPF來跟蹤多線程應用程序的爭用開銷，通過對已識別的串行化瓶頸的重要性進行排名，收集被阻塞的線程和導致阻塞的線程的堆棧跟蹤信息。GAPP最好的一點是它不需要代碼更改、昂貴的插裝或重新編譯。GAPP分析器的創建者能夠確認已知的瓶頸，并且在Parsec 3.0基準套件263和一些大型開源項目上揭示了新的、以前未報告的瓶頸。[Nair和Field，2020]
11.7 Detecting Coherence Issues
11.7.1 Cache Coherency Protocols
多處理器系統采用緩存一致性協議來確保在每個含有獨立緩存實體的核心共享使用內存時的數據一致性。如果沒有這樣的協議，如果CPU A和CPU B都將內存位置L讀入其各自的緩存中，并且處理器B隨后修改了其緩存中L的值，那么這兩個CPU會對相同內存位置L擁有不一致的值。緩存一致性協議確保任何對緩存條目的更新都會被及時地更新到相同位置的任何其他緩存條目中。
最著名的緩存一致性協議之一是MESI（Modified Exclusive Shared Invalid），它用于支持類似于現代CPU中使用的寫回緩存。它的首字母縮寫表示緩存行可能被標記的四種狀態（見圖55）：
? Modified - 緩存行僅存在于當前緩存中，并且已被修改，與RAM中的值不同。
? Exclusive - 緩存行僅存在于當前緩存中，并且與RAM中的值相匹配。
? Shared - 緩存行既存在于此處，也存在于其他緩存行中，并且與RAM中的值相匹配。
? Invalid - 緩存行未使用（即不包含任何RAM位置）。
當從內存中獲取時，每個緩存行都有一個編碼的狀態標記。然后，緩存行的狀態會從一個狀態轉換到另一個264。實際上，CPU廠商通常會實現稍微改進的MESI變體。例如，Intel使用MESIF265，它添加了一個Forwarding（F）狀態，而AMD使用MOESI266，則添加了Owning（O）狀態。但是這些協議仍然保持了基本MESI協議的核心。
正如前面的例子所示，緩存一致性問題可能會導致程序的順序不一致。通過使用偵聽式緩存來監視所有內存事務并相互協作以維護內存一致性，可以減輕這個問題。不幸的是，這種方法會帶來一些成本，因為一個處理器對緩存線的修改會使另一個處理器的相應緩存行無效。這會導致內存停頓并浪費系統帶寬。與只能限制應用程序性能的串行化和鎖定問題不同，一致性問題可能會導致USL在第11.1節中所描述的逆向效果。兩種廣為人知的一致性問題類型是“真共享”和“假共享”，接下來我們將探討這兩種問題。
11.7.2 True Sharing
真共享是指兩個不同的處理器訪問同一個變量時發生的情況（見列表48）。
首先，真共享意味著可能難以檢測的數據競爭。幸運的是，有一些工具可以幫助識別此類問題。Clang的Thread Sanitizer和helgrind就是其中的一些工具。為了避免列表48中的數據競爭，應將sum變量聲明為std::atomic<unsigned int> sum。
使用C++原子操作可以幫助解決真共享時的數據競爭問題。然而，這實際上會對原子變量的訪問進行串行化，可能會影響性能。解決真共享問題的另一種方式是使用線程本地存儲（TLS）。TLS是在給定的多線程進程中，每個線程都可以分配內存來存儲線程特定數據的方法。通過這樣做，線程修改它們的本地副本，而不是爭用全局可用內存位置。在列表48中，可以通過使用TLS類說明符來修復示例：thread_local unsigned int sum（自C++11起）。主線程然后應該合并所有工作線程的本地副本的結果。
11.7.3 False Sharing
錯誤共享（False Sharing）是指兩個不同的處理器修改不同的變量，這些變量恰好位于同一個緩存行上（見列表49）。圖56說明了錯誤共享問題。對于多線程應用程序來說，錯誤共享經常是性能問題的來源。因此，現代分析工具內置了檢測此類情況的支持。TMA將經歷真/假共享的應用程序描述為內存受限。通常，在這種情況下，您會看到爭用訪問度量指標（Contested Accesses）的高值。
在使用Intel VTune Profiler時，用戶需要進行兩種類型的分析來查找和消除錯誤共享問題。首先，運行微架構探索（Microarchitecture Exploration）分析，該分析實施了TMA方法來檢測應用程序中是否存在錯誤共享。正如前面所提到的，爭用訪問度量指標的高值促使我們深入挖掘并運行Memory Access分析，并啟用“分析動態內存對象”選項。該分析有助于找出導致爭用問題的數據結構的訪問。通常，這種內存訪問具有較高的延遲，這將由分析揭示。在Intel開發者社區中有使用Intel VTune Profiler解決錯誤共享問題的示例。
Linux perf也支持查找錯誤共享。與Intel VTune Profiler類似，首先運行TMA（參見章節6.1.2）以了解程序是否存在錯誤共享問題。如果是這種情況，可以使用perf c2c工具來檢測具有高緩存一致性成本的內存訪問。perf c2c會匹配不同線程的存儲和加載地址，看看是否發生了修改緩存行的命中。讀者可以在專門的博客文章中找到關于該過程和如何使用工具的詳細解釋。
可以通過對齊/填充內存對象來消除錯誤共享。在第11.7.2節的示例中，可以通過確保sumA和sumB不共享同一個緩存行來解決問題（詳見第8.1.1.4節）。
從性能的一般角度考慮，最重要的是考慮可能的狀態轉換的成本。在所有緩存狀態中，唯一不涉及昂貴的跨緩存子系統通信和數據傳輸的是Modified (M)和Exclusive (E)狀態。因此，緩存行保持M或E狀態的時間越長（即跨緩存的數據共享越少），多線程應用程序所產生的一致性開銷就越低。在Nitsan Wakart的博客文章《深入研究緩存一致性》中可以找到一個展示這個屬性如何被應用的示例。
11.8 Chapter Summary
? 不充分利用現代多核CPU的應用程序將落后于競爭對手。為了未來應用程序的成功，準備軟件以適應日益增長的CPU核心數量非常重要。
? 處理單線程應用程序時，優化程序的一部分通常會對性能產生積極影響。然而，對于多線程應用程序，情況并非總是如此。這種效應被廣泛稱為阿姆達爾定律，它規定并行程序的加速比受限于其串行部分。
? 線程間通信可能導致速度變慢，這可以通過通用可擴展性定律解釋。這給調優多線程程序帶來了額外的挑戰。優化多線程應用程序的性能還涉及檢測和減輕爭用和一致性效應。
? Intel VTune Profiler是分析多線程應用程序的“首選”工具。但在過去幾年中，還出現了其他具有獨特功能的工具，例如Coz和GAPP。
Epilog
//后記
感謝您閱讀整本書。我希望您喜歡并且覺得有用。如果這本書能幫助您解決實際問題，我將更加開心。在這種情況下，我會認為這是一次成功，證明我的努力沒有白費。在您繼續努力之前，讓我簡要總結一下本書的要點，并給出最后的建議：
? 硬件性能增長的速度不如過去幾年快。性能調優比過去40年更為關鍵。在不久的將來，它將是性能提升的關鍵驅動因素之一。
? 軟件默認情況下并不具備最佳性能。存在某些限制，阻止應用程序充分發揮其性能潛力。硬件和軟件組件都有這樣的限制。
? “過早優化是萬惡之源”。但相反的情況也經常發生。推遲性能工程可能為時已晚，并且可能會造成與過早優化同樣的問題。設計未來產品時不要忽視性能方面的考慮。
? 現代系統的性能是不確定的，取決于許多因素。有意義的性能分析應考慮噪聲，并使用統計方法分析性能測量數據。
? 理解CPU微架構可以幫助您理解進行的實驗結果。然而，在對代碼進行具體更改時不要過于依賴這種知識。您的心理模型永遠無法像CPU內部的實際設計一樣準確。幾乎不可能預測特定代碼片段的性能。始終進行測量！
? 性能優化很困難，因為沒有預先確定的步驟或算法可供遵循。工程師需要從不同角度解決問題。了解可用的性能分析方法和工具（包括硬件和軟件）。如果您的平臺支持，我強烈建議采用Roofline模型和TMA方法。它將幫助您正確引導工作方向。此外，了解何時可以利用其他硬件性能監控功能，例如LBR、PEBS和PT。
? 理解應用程序性能的限制因素以及修復的可能方式。第2部分介紹了針對每種類型的CPU性能瓶頸的一些基本優化方法：前端瓶頸、后端瓶頸、退出和錯誤推測。當您的應用程序屬于上述四種類別之一時，請參閱第7-10章了解可用的選項。
? 如果修改的效益微乎其微，應保持代碼的簡潔和清晰。
? 有時，改進一個系統上的性能可能會減慢另一個系統上的執行速度。確保在您關心的所有平臺上測試您的更改。
這些要點提供了對開發人員在改善應用程序性能方面的寶貴指導。
希望這本書能幫助您更好地理解您的應用程序性能和CPU性能的一般情況。當然，它并沒有涵蓋您在進行性能優化工作時可能遇到的所有可能場景。我的目標是給您一個起點，并向您展示在現代CPU上處理性能分析和調優的潛在選擇和策略。
如果您喜歡閱讀這本書，請務必將其傳給您的朋友和同事。我會感激您在社交媒體平臺上推廣這本書的幫助。
我很愿意聽取您對這本書的反饋意見，您可以通過我的電子郵件dendibakh@gmail.com與我聯系。請讓我知道您的想法、意見和對這本書的建議。我將在我的博客easyperf.net上發布有關這本書的所有更新和未來信息。
祝您進行性能調優時順利愉快！
Appendix A. Reducing Measurement Noise
以下是可能導致性能測量中增加不確定性的一些特征示例。請參閱第2.1節中的完整討論。
Dynamic Frequency Scaling
動態頻率調整（Dynamic Frequency Scaling，DFS）是一種通過在運行要求高的任務時自動提高CPU工作頻率來增加系統性能的技術。舉個DFS實施的例子，Intel CPU具有Turbo Boost功能，而AMD CPU則采用Turbo Core功能。
以下是在Intel? Core? i5-8259U上運行單線程工作負載時，Turbo Boost可能產生的影響示例：
當啟用Turbo Boost時，平均頻率要高得多。
DFS可以在BIOS中永久禁用。在Linux系統上以編程方式禁用DFS功能，您需要root訪問權限。下面是實現此目的的方法：
Simultaneous Multithreading ? ? //同時多線程?
現代CPU核心通常采用同時多線程（Simultaneous Multithreading，SMT）的方式制造。這意味著在一個物理核心中，可以同時執行兩個線程。通常，架構狀態會被復制，但執行資源（ALU、緩存等）不會被復制。這意味著如果我們在同一個核心上以“同時”的方式運行兩個獨立的進程（在不同的線程中），它們可以相互競爭資源，例如緩存空間。
SMT可以在BIOS中永久禁用。在Linux系統上以編程方式禁用SMT，您需要root訪問權限。下面是如何關閉每個核心的兄弟線程的方法：
echo 0 > /sys/devices/system/cpu/cpuX/onlineCPU線程的兄弟對可以在以下文件中找到：
/sys/devices/system/cpu/cpuN/topology/thread_siblings_list例如，在具有4個核心和8個線程的Intel? Core? i5-8259U上：
Scaling Governor ? ?//頻率調整策略
Linux內核能夠控制CPU頻率以實現不同的目的。其中之一是為了節省功耗，在這種情況下，Linux內核中的頻率調整策略（Scaling Governor）可以決定降低CPU運行頻率。為了進行性能測量，建議將頻率調整策略設置為performance，以避免出現非標頻率。以下是如何為所有核心設置頻率調整策略的方法：
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > $i
doneCPU Affinity
處理器親和力（Processor affinity）使得進程可以綁定到特定的CPU核心。在Linux中，可以使用taskset工具來實現這一點。這是如何使用taskset工具的方法：
請注意，cpu遷移的次數降至0，即該進程永遠不會離開core0。另外，您還可以使用cset工具，為您要進行基準測試的程序保留特定的CPU。如果使用Linux perf工具，請至少保留兩個核心，這樣perf會在一個核心上運行，而您的程序會在另一個核心上運行。下面的命令將所有線程移出N1和N2（-k選項表示連內核線程也一同移出）：
$ cset shield -c N1,N2 -k on下面的命令將在隔離的CPU上運行在 -- 后的命令：
$ cset shield --exec -- perf stat -r 10 <cmd>Process Priority
在Linux中，可以使用nice工具來提高進程優先級。通過增加優先級，進程將獲得更多的CPU時間，并且Linux調度器將更傾向于優先處理該進程，而不是普通優先級的進程。niceness的取值范圍為-20（最高優先級）到19（最低優先級），默認值為0。
請注意，在前面的示例中，基準測試的進程被操作系統中斷了100多次。如果我們通過以sudo nice -n -N方式運行基準測試來提高進程優先級，效果如下：
$ perf stat -r 10 -- sudo nice -n -5 taskset -c 1 a.exe
0 context-switches
0 cpu-migrations請注意，上下文切換的次數變為0，因此該進程獲得了連續的計算時間，沒有被中斷。
Filesystem Cache
通常，一部分主內存被用于緩存文件系統的內容，包括各種數據。這樣可以減少應用程序需要直接訪問磁盤的次數。
下面是一個示例，展示了文件系統緩存如何影響簡單的git status命令的運行時間：
# clean fs cache
$ echo 3 | sudo tee /proc/sys/vm/drop_caches && sync && time -p git status
real 2,57
# warmed fs cache
$ time -p git status
real 0,40可以通過運行以下兩個命令來清空當前的文件系統緩存：
$ echo 3 | sudo tee /proc/sys/vm/drop_caches
$ sync或者，你可以進行一次干燥運行，只是為了預熱文件系統緩存，并將其排除在測量范圍之外。這個干燥的迭代可以與基準測試輸出的驗證結合起來。
Appendix B. The LLVM Vectorizer
該段描述了截至2020年的Clang編譯器中LLVM循環向量化器的狀態。內層循環向量化是將內部循環中的代碼轉換為在多個循環迭代中使用向量的代碼的過程。SIMD向量中的每個通道在連續的循環迭代上執行獨立的算術操作。通常情況下，循環并不處于干凈的狀態，向量化器需要猜測和假設缺失的信息，并在運行時檢查細節。如果這些假設被證明是錯誤的，向量化器將退回到執行標量循環。下面的示例突出顯示了LLVM向量化器支持的一些代碼模式。
Loops with unknown trip count
LLVM循環向量化器支持具有未知迭代次數的循環。在下面的循環中，迭代的起始點和結束點未知，而向量化器有一種機制可以對不從零開始的循環進行向量化。在這個示例中，n可能不是向量寬度的整數倍，因此向量化器需要將最后幾次迭代作為標量代碼執行。保留循環的標量副本會增加代碼大小。
void bar(float A, float B, float K, int start, int end) {
for (int i = start; i < end; ++i)
A[i] *= B[i] + K;
}Runtime Checks of Pointers
在下面的示例中，如果指針A和B指向連續的地址，則對代碼進行向量化是不允許的，因為一些A的元素會在從數組B讀取之前被寫入。
一些程序員使用restrict關鍵字來通知編譯器指針是不相交的，但在我們的例子中，LLVM循環向量化器無法知道指針A和B是唯一的。循環向量化器通過在運行時插入代碼來處理此循環，檢查數組A和B是否指向不相交的內存位置。如果數組A和B重疊，則執行標量版本的循環。
void bar(float A, float B, float K, int n) {
for (int i = 0; i < n; ++i)
A[i] *= B[i] + K;
}Reductions
在這個例子中，sum變量被循環的連續迭代使用。通常情況下，這會阻止向量化，但是向量化器可以檢測到sum是一個約簡變量。sum變量會變成一個整數向量，在循環結束時，將數組的元素相加以得到正確的結果。LLVM向量化器支持多種不同的約簡運算，例如加法、乘法、異或、與和或運算。這些約簡操作使得向量化可以更高效地處理這類循環，提高程序的性能。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
sum += A[i] + 5;
return sum;
}當使用 `-ffast-math` 參數時，LLVM向量化器支持浮點數約簡操作。
Inductions ? ?//歸納變量
在這個例子中，循環的歸納變量 i 的值被保存到一個數組中。LLVM循環向量化器知道如何對歸納變量進行向量化處理。當循環向量化時，向量化器會自動處理歸納變量的更新和傳播，以提高代碼的運行效率。這樣可以將歸納變量的操作擴展為向量操作，從而充分利用SIMD指令并加速循環的執行。
void bar(float A, float B, float K, int n) {
for (int i = 0; i < n; ++i)
A[i] = i;
}If Conversion
LLVM循環向量化器能夠“展開”代碼中的IF語句，并生成一條指令流。向量化器支持內層循環中的任何控制流程。內層循環可以包含復雜的IF嵌套、ELSE以及GOTO語句。向量化器能夠處理這些控制流程，使得循環的操作可以以向量化的方式執行，從而提高代碼的效率和性能。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
if (A[i] > B[i])
sum += A[i] + 5;
return sum;
}Pointer Induction Variables
這個例子使用了標準C++庫中的std::accumulate函數。這個循環使用了C++迭代器，它們是指針，而不是整數索引。LLVM循環向量化器可以檢測到指針歸納變量，并對該循環進行向量化處理。這個功能非常重要，因為許多C++程序使用迭代器來遍歷容器或集合。通過支持指針歸納變量的向量化，向量化器可以更高效地處理這類循環，提高程序的性能和效率。
int baz(int *A, int n) {
return std::accumulate(A, A + n, 0);
}Reverse Iterators
LLVM循環向量化器可以對逆向計數的循環進行向量化處理。
int foo(int *A, int *B, int n) {
for (int i = n; i > 0; --i)
A[i] +=1;
}Scatter / Gather
LLVM循環向量化器可以對代碼進行向量化處理，使其成為一系列散布/收集內存的標量指令序列。
int foo(int * A, int * B, int n) {
for (intptr_t i = 0; i < n; ++i)
A[i] += B[i * 4];
}在許多情況下，成本模型會判斷這種轉換不具備盈利性。
Vectorization of Mixed Types
LLVM循環向量化器可以對包含混合類型的程序進行向量化處理。向量化器的成本模型可以估計類型轉換的成本，并決定是否進行向量化處理是有利可圖的。這意味著即使循環中存在不同類型的變量，向量化器也可以根據類型轉換的代價來判斷是否對其進行向量化處理。通過在向量化時考慮類型轉換的成本，向量化器可以更加精確地評估優化的收益，以提高代碼的性能和效率。
int foo(int *A, char *B, int n, int k) {
for (int i = 0; i < n; ++i)
A[i] += 4 * B[i];
}Vectorization of function calls
LLVM循環向量化器可以對內部數學函數進行向量化處理。請參考下表列出的這些函數：
- fabs: 絕對值（浮點數）
- sqrt: 平方根
- cbrt: 立方根
- sin: 正弦
- cos: 余弦
- exp: 指數函數
- log: 自然對數函數
- log10: 以10為底的對數函數
- pow: 冪函數
- ceil: 向上取整
- floor: 向下取整
- round: 四舍五入
- trunc: 截斷小數部分
LLVM循環向量化器可以檢測到這些內部數學函數，并將其轉化為相應的向量指令，以在向量級別上執行計算，提高代碼的執行效率和性能。
Partial unrolling during vectorization
現代處理器具有多個執行單元，只有包含高度并行性的程序才能充分利用機器的全部寬度。LLVM循環向量化器通過對循環進行部分展開來增加指令級并行性（ILP）。
在下面的示例中，整個數組被累加到變量sum中。這種做法是低效的，因為處理器只能使用一個執行端口。通過展開代碼，循環向量化器可以同時使用兩個或更多的執行端口，從而提高程序的并行性。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
sum += A[i];
return sum;
}LLVM循環向量化器使用成本模型來決定何時對循環進行展開是劃算的。
展開循環的決策取決于寄存器壓力和生成的代碼大小。
SLP vectorization
SLP（超級字級并行性）向量化器嘗試將多個標量操作組合成向量操作。它從底向上地處理代碼，跨越基本塊，尋找可組合的標量操作。SLP向量化的目標是將類似的獨立指令組合成向量指令。使用這種技術可以對內存訪問、算術操作和比較操作進行向量化。例如，下面的函數對其輸入（a1、b1）和（a2、b2）執行非常相似的操作。基本塊向量化器可以將以下函數組合為向量操作。
void foo(int a1, int a2, int b1, int b2, int *A) {
A[0] = a1*(a1 + b1);
A[1] = a2*(a2 + b2);
A[2] = a1*(a1 + b1);
A[3] = a2*(a2 + b2);
}Outer loop vectorization. ? ?//外部循環向量化
外部循環向量化是發生在數據并行應用程序中最外層循環的一種向量化形式。例如，OpenCL和CUDA依賴于外部循環向量化，因為它們指定了在循環的外部維度上的迭代之間是相互獨立的。換句話說，這種向量化技術可以同時處理多個迭代，利用數據并行性來提高程序的執行效率。通過將外部循環中的迭代打包成向量操作，可以在單個指令中處理多個數據元素，從而充分利用SIMD（單指令多數據）指令集并行性，提高程序的并行性和性能。
