GCC編譯器高效利用cache的原理和引數

作者：由 fujx 發表于詩詞時間：2022-04-11

cache簡介

cache作為承接CPU計算單元和記憶體的重要通道，能夠避免cpu頻繁進行效率不高的讀寫記憶體操作。然後由於成本和物理空間的關係，cache的大小不能做的很大，差不多是記憶體千分之一的容量。如何高效利用cache就成為了一個重要的任務。

區域性性原理

是指CPU訪問儲存器時，無論是存取指令還是存取資料，所訪問的儲存單元都趨於聚集在一個較小的連續區域中。

時間區域性性（Temporal Locality）：如果一個資訊項正在被訪問，那麼在近期它很可能還會被再次訪問。程式迴圈、堆疊等是產生時間區域性性的原因。

空間區域性性（Spatial Locality）：在最近的將來將用到的資訊很可能與正在使用的資訊在空間地址上是臨近的。

順序區域性性（Order Locality）：在典型程式中，除轉移類指令外，大部分指令是順序進行的。順序執行和非順序執行的比例大致是5：1。此外，對大型陣列訪問也是順序的。指令的順序執行、陣列的連續存放等是產生順序區域性性的原因。

由於區域性性原理，cache的利用率實際上還是挺高的。但是由於程式碼是人工編寫的，難免能夠充分的利用好區域性性原理。因此編譯器主動承擔了這樣一項重要的任務，基本上在開啟了-O2或-O3的最佳化級別後，編譯器能夠儘可能的使得可執行程式的區域性性更好。

本文將介紹gcc編譯器中絕大部分為了提高cache命中率而提供了最佳化選項，並介紹其最佳化的細節。

這些最佳化選項基本可以分為三大類：

調整資料的訪問順序

一般是由於迴圈結構，導致有多個數據（如陣列，連續分佈）在一個很短的時間內都想去佔有cache。如訪問一個數據的的元素，由於沒在cache裡面，就從記憶體中取，但是可能就會把另一個數據剛剛放入cache的部分資料又給擠出去了。這樣多個數組都在搶佔cache，導致cache頻繁的進行更新，cache的命中率也不會很高。這時候應該調整這些資料的訪問流程進行調整，包括多個數據訪問的拆分和迴圈邏輯的調整。

二進位制檔案中程式碼段對齊

因為在程式執行中，cpu得從程式碼段取出指令，再執行該指令，所以程式碼段的cache命中率也一樣重要。對齊是為了儘量使得部分程式碼段能集中在一個cache中。當前L1 cache一個單元為64B，即每次可以將64B的記憶體資料給搬運到cache中。假設有一個程式碼段（一個函式）的大小正好為64B，如果沒有對齊的話，它的資料基本上會放到兩個cache中，但是有了對齊後，就只需要佔用一個cache。因此gcc透過新增padding的方法，用空間成本換取了時間成本。

調整程式碼塊的佈局

這裡的程式碼塊主要分為兩類，一類是函式級別的程式碼塊，這樣的程式碼塊相對比較獨立，位置可以自由調整，因此根據區域性性原理，可以將一些熱點函式的程式碼塊放到臨近的位置。另一類是函式內的程式碼塊，應該主要指的是以label為分界的程式碼塊，可以在不影響函式正常功能的前提下，進行空間上的調整。在一個更細粒度的程度進行熱點程式碼的聚合。

這裡再抽象一個場景，讓大家感受一下上面這樣做可能帶來的好處

假設一個cache的最小分隔單元是64B，有100個這樣的單元，而記憶體大小為64B*100000，這樣的話每個cache實際會有1000個記憶體的單元去搶佔它。這裡做一個簡單的對映 cachePos = memPos % 100；以第0個cache為例，記憶體中的第0，100，200。。。的位置是對映的這個位置。對於第一種最佳化情況，由於同時訪問的幾個資料在分別記憶體中連續，因此有可能會存在都去競爭相同cache的情況。第二種最佳化情況，是讓程式碼段對cache的利用率更高，減少對cache的訪問次數，並且降低和其他程式碼塊衝突的機率，如我只佔有一個cache單元，衝突肯定小於佔有兩個的時候。第三種最佳化的情況，由上述的對映關係可以得知，如果本身程式碼塊之間距離很進，如記憶體中的100，101，102號位置，那他們對映到cache中也是0，1，2，這些程式碼塊之間不會發生競爭的關係。

調整資料的訪問順序

-ftree-loop-distribution

Perform loop distribution。 This flag can improve cache performance on big loop bodies and allow further loop optimizations， like parallelization or vectorization， to take place。 For example， the loop執行迴圈分佈。

這個標誌可以改善大迴圈體的快取效能，並允許進一步的迴圈最佳化，如並行化或向量化。例如，迴圈中的

DO I = 1， N

A（I） = B（I） + C

D（I） = E（I） * F

ENDDO

is transformed to

被轉化為

DO I = 1， N

A（I） = B（I） + C

ENDDO

DO I = 1， N

D（I） = E（I） * F

ENDDO

This flag is enabled by default at -O3。 It is also enabled by -fprofile-use and -fauto-profile。

這個標誌在預設情況下由-O3啟用。它也可以由 -fprofile-use 和 -fauto-profile 啟用。

-ftree-loop-distribute-patterns

Perform loop distribution of patterns that can be code generated with calls to a library。 This flag is enabled by default at -O2 and higher， and by -fprofile-use and -fauto-profile。

對可以透過呼叫庫生成程式碼的模式進行迴圈分佈。這個標誌在-O2和更高版本時預設啟用，並由-fprofile-use和-fauto-profile啟用。

This pass distributes the initialization loops and generates a call to memset zero。 For example， the loop

這個通道分配了初始化迴圈，併產生了對memset zero的呼叫。例如，迴圈中的

DO I = 1， N

A（I） = 0

B（I） = A（I） + I

ENDDO

is transformed to

被轉換為

DO I = 1， N

A（I） = 0

ENDDO

DO I = 1， N

B（I） = A（I） + I

ENDDO

and the initialization loop is transformed into a call to memset zero。 This flag is enabled by default at -O3。 It is also enabled by -fprofile-use and -fauto-profile。

並且初始化迴圈被轉化為對memset zero的呼叫。這個標誌在預設情況下由-O3啟用。它也被-fprofile-use和-fauto-profile所啟用。

-floop-interchange

Perform loop interchange outside of graphite。 This flag can improve cache performance on loop nest and allow further loop optimizations， like vectorization， to take place。 For example， the loop

在graphite之外執行迴圈互換。這個標誌可以提高迴圈巢狀的快取效能，並允許進一步的迴圈最佳化，如向量化，發生。例如，迴圈中的

for

（

int

；

）

for

（

int

；

）

for

（

int

；

）

［

］［

］

［

］［

］

［

］［

］

［

］［

］；

is transformed to

被轉化為

for

（

int

；

）

for

（

int

；

）

for

（

int

；

）

［

］［

］

［

］［

］

［

］［

］

［

］［

］；

This flag is enabled by default at -O3。 It is also enabled by -fprofile-use and -fauto-profile。

這個標誌在預設情況下由-O3啟用。它也被-fprofile-use和-fauto-profile所啟用。

-floop-unroll-and-jam

Apply unroll and jam transformations on feasible loops。 In a loop nest this unrolls the outer loop by some factor and fuses the resulting multiple inner loops。 This flag is enabled by default at -O3。 It is also enabled by -fprofile-use and -fauto-profile。

在可行的迴圈上應用解卷和堵塞轉換。在一個迴圈巢狀中，它將外迴圈按某種係數展開，並將產生的多個內迴圈融合。這個標誌在預設情況下是在-O3下啟用的。它也可以由-fprofile-use和-fauto-profile啟用。

調整二進位制檔案中程式碼段的佈局

-falign-functions

-falign-functions=n

-falign-functions=n：m

-falign-functions=n：m：n2

-falign-functions=n：m：n2：m2

Align the start of functions to the next power-of-two greater than or equal to n， skipping up to m-1 bytes。 This ensures that at least the first m bytes of the function can be fetched by the CPU without crossing an n-byte alignment boundary。

將函式的開始部分與大於或等於n的下一個2次方對齊，最多跳過m-1位元組。這可以確保CPU至少可以獲取函式的前m個位元組而不跨越n位元組的對齊邊界。

If m is not specified， it defaults to n。

如果沒有指定m，它預設為n。

Examples： -falign-functions=32 aligns functions to the next 32-byte boundary， -falign-functions=24 aligns to the next 32-byte boundary only if this can be done by skipping 23 bytes or less， -falign-functions=32：7 aligns to the next 32-byte boundary only if this can be done by skipping 6 bytes or less。

例子。-falign-functions=32將函式對齊到下一個32位元組的邊界，-falign-functions=24只有在跳過23個位元組或更少時才會對齊到下一個32位元組的邊界，-falign-functions=32：7只有在跳過6個位元組或更少時才會對齊到下一個32位元組邊界。

The second pair of n2：m2 values allows you to specify a secondary alignment： -falign-functions=64：7：32：3 aligns to the next 64-byte boundary if this can be done by skipping 6 bytes or less， otherwise aligns to the next 32-byte boundary if this can be done by skipping 2 bytes or less。 If m2 is not specified， it defaults to n2。

第二對n2：m2值允許你指定二級對齊：-falign-functions=64：7：32：3如果可以跳過6個位元組或更少，則對齊到下一個64位元組邊界，否則如果可以跳過2個位元組或更少，則對齊到下一個32位元組邊界。如果沒有指定m2，它預設為n2。

Some assemblers only support this flag when n is a power of two； in that case， it is rounded up。

有些彙編程式只支援n是2的冪時的這個標誌；在這種情況下，它被四捨五入。

-fno-align-functions and -falign-functions=1 are equivalent and mean that functions are not aligned。

-fno-align-functions和-falign-functions=1是等同的，意味著函式不被對齊。

If n is not specified or is zero， use a machine-dependent default。 The maximum allowed n option value is 65536。

如果沒有指定n或為0，則使用與機器相關的預設值。允許的最大n選項值是65536。

Enabled at levels -O2， -O3。

在級別-O2、-O3時啟用。

example

// align。c

int

（

void

）

{

return

；

}

int

（

void

）

{

return

；

}

使用gcc 4。4。5使用預設設定編譯時：

align。o： file format elf64-x86-64

Disassembly of section 。text：

0000000000000000 ：

0： 55 push %rbp

1： 48 89 e5 mov %rsp，%rbp

4： b8 00 00 00 00 mov $0x0，%eax

9： c9 leaveq

a： c3 retq

000000000000000b ：

b： 55 push %rbp

c： 48 89 e5 mov %rsp，%rbp

f： b8 00 00 00 00 mov $0x0，%eax

14： c9 leaveq

15： c3 retq

指定

-falign-functions

給出：

align。o： file format elf64-x86-64

Disassembly of section 。text：

0000000000000000 ：

0： 55 push %rbp

1： 48 89 e5 mov %rsp，%rbp

4： b8 00 00 00 00 mov $0x0，%eax

9： c9 leaveq

a： c3 retq

b： eb 03 jmp 10

d： 90 nop

e： 90 nop

f： 90 nop

0000000000000010 ：

10： 55 push %rbp

11： 48 89 e5 mov %rsp，%rbp

14： b8 00 00 00 00 mov $0x0，%eax

19： c9 leaveq

1a： c3 retq

-flimit-function-alignment

If this option is enabled， the compiler tries to avoid unnecessarily overaligning functions。 It attempts to instruct the assembler to align by the amount specified by -falign-functions， but not to skip more bytes than the size of the function。

如果這個選項被啟用，編譯器會試圖避免不必要地過度對齊函式。它試圖指示彙編器按-falign-functions指定的數量對齊，但不會跳過比函式大小更多的位元組。

-falign-labels

-falign-labels

-falign-labels=n

-falign-labels=n：m

-falign-labels=n：m：n2

-falign-labels=n：m：n2：m2-

Align all branch targets to a power-of-two boundary。

將所有的分支目標對準一個2次方的邊界。

Parameters of this option are analogous to the -falign-functions option。 -fno-align-labels and -falign-labels=1 are equivalent and mean that labels are not aligned。

這個選項的引數與-falign-functions選項類似。-fno-align-labels和-falign-labels=1是等同的，意味著標籤不被對齊。

If -falign-loops or -falign-jumps are applicable and are greater than this value， then their values are used instead。

如果-falign-loops或-falign-jumps適用並且大於這個值，那麼它們的值將被替代使用。

If n is not specified or is zero， use a machine-dependent default which is very likely to be ‘1’， meaning no alignment。 The maximum allowed n option value is 65536。

如果沒有指定n或者是0，則使用與機器有關的預設值，很可能是‘1’，意味著不對齊。允許的最大n選項值是65536。

Enabled at levels -O2， -O3。

在級別-O2、-O3中啟用。

-falign-loops

-falign-loops

-falign-loops=n

-falign-loops=n：m

-falign-loops=n：m：n2

-falign-loops=n：m：n2：m2

Align loops to a power-of-two boundary。 If the loops are executed many times， this makes up for any execution of the dummy padding instructions。

迴圈與2的冪的邊界對齊。如果迴圈被多次執行，這就彌補了任何假的填充指令的執行。

If -falign-labels is greater than this value， then its value is used instead。

如果-falign-labels大於這個值，那麼就用其值代替。

Parameters of this option are analogous to the -falign-functions option。 -fno-align-loops and -falign-loops=1 are equivalent and mean that loops are not aligned。 The maximum allowed n option value is 65536。

這個選項的引數與-falign-functions選項類似。-fno-align-loops和-falign-loops=1是等同的，意味著迴圈不被對齊。允許的最大n選項值是65536。

If n is not specified or is zero， use a machine-dependent default。

如果沒有指定n或者為0，則使用與機器有關的預設值。

Enabled at levels -O2， -O3。

在級別-O2、-O3中啟用。

-falign-jumps

-falign-jumps

-falign-jumps=n

-falign-jumps=n：m

-falign-jumps=n：m：n2

-falign-jumps=n：m：n2：m2

Align branch targets to a power-of-two boundary， for branch targets where the targets can only be reached by jumping。 In this case， no dummy operations need be executed。

對於那些只能透過跳轉達到目標的分支目標，將分支目標對準2次方的邊界。在這種情況下，不需要執行假操作。

If -falign-labels is greater than this value， then its value is used instead。

如果-falign-labels大於這個值，那麼就用它的值代替。

Parameters of this option are analogous to the -falign-functions option。 -fno-align-jumps and -falign-jumps=1 are equivalent and mean that loops are not aligned。

這個選項的引數與-falign-functions選項類似。-fno-align-jumps和-falign-jumps=1是等同的，意味著迴圈不被對齊。

If n is not specified or is zero， use a machine-dependent default。 The maximum allowed n option value is 65536。

如果沒有指定n或者為0，則使用與機器有關的預設值。允許的最大n選項值是65536。

Enabled at levels -O2， -O3。

在級別-O2， -O3中啟用。

調整程式碼塊的佈局

-freorder-blocks

Reorder basic blocks in the compiled function in order to reduce number of taken branches and improve code locality。

對編譯後的函式中的基本塊進行重新排序，以減少所採取的分支數量，提高程式碼的定位性。

Enabled at levels -O1， -O2， -O3， -Os。

在級別-O1、-O2、-O3、-Os時啟用。

-freorder-blocks-algorithm=algorithm

Use the specified algorithm for basic block reordering。 The algorithm argument can be ‘simple’， which does not increase code size （except sometimes due to secondary effects like alignment）， or ‘stc’， the “software trace cache” algorithm， which tries to put all often executed code together， minimizing the number of branches executed by making extra copies of code。

使用指定的演算法進行基本塊重排。演算法引數可以是 “simple”，它不增加程式碼大小（除了有時由於對齊等次要影響），或者是 “stc”，即 “軟體跟蹤快取 ”演算法，它試圖將所有經常執行的程式碼放在一起，透過製作額外的程式碼副本來最小化執行的分支數量。

The default is ‘simple’ at levels -O1， -Os， and ‘stc’ at levels -O2， -O3。

預設情況下，在-O1、-O級別上為‘simple’，在-O2、-O3級別上為‘stc’。

-freorder-blocks-and-partition

In addition to reordering basic blocks in the compiled function， in order to reduce number of taken branches， partitions hot and cold basic blocks into separate sections of the assembly and 。o files， to improve paging and cache locality performance。

除了在編譯的函式中重新排序基本塊，以減少所採取的分支數量，將熱的和冷的基本塊劃分到彙編和。o檔案的不同部分，以改善分頁和快取定位的效能。

This optimization is automatically turned off in the presence of exception handling or unwind tables （on targets using setjump/longjump or target specific scheme）， for linkonce sections， for functions with a user-defined section attribute and on any architecture that does not support named sections。 When -fsplit-stack is used this option is not enabled by default （to avoid linker errors）， but may be enabled explicitly （if using a working linker）。

在存在異常處理或解卷表的情況下（在使用setjump/longjump或目標特定方案的目標上），對於linkonce部分，對於具有使用者定義的部分屬性的函式，以及在任何不支援命名部分的架構上，這種最佳化會自動關閉。當使用-fsplit-stack時，該選項預設不啟用（以避免連結器錯誤），但可以顯式啟用（如果使用工作連結器）。

Enabled for x86 at levels -O2， -O3， -Os。

對於x86來說，在-O2、-O3、-Os級別上啟用。

-freorder-functions

Reorder functions in the object file in order to improve code locality。 This is implemented by using special subsections

。text。hot

for most frequently executed functions and

。text。unlikely

for unlikely executed functions。 Reordering is done by the linker so object file format must support named sections and linker must place them in a reasonable way。

在物件檔案中重新排列函式，以提高程式碼的定位性。這是透過使用特殊的子段。text。hot和。text。unlikely來實現的，前者用於最常執行的函式，後者用於不常執行的函式。重新排序是由連結器完成的，所以物件檔案格式必須支援命名的部分，連結器必須以合理的方式放置它們。

This option isn’t effective unless you either provide profile feedback （see -fprofile-arcs for details） or manually annotate functions with

hot

cold

attributes （see Common Function Attributes）。

這個選項是無效的，除非你提供配置檔案反饋（詳見-fprofile-arcs）或用熱或冷屬性手動註釋函式（詳見常用函式屬性）。

Enabled at levels -O2， -O3， -Os。

在級別-O2、-O3、-Os時啟用。

others

-fprefetch-loop-arrays

If supported by the target machine， generate instructions to prefetch memory to improve the performance of loops that access large arrays。

如果目標機器支援，生成預取記憶體的指令，以提高訪問大陣列的迴圈的效能。