編寫快取友好型程式技巧

• 2022 年 3 月 20 日
• 筆記
• C++, 程式碼底層優化

通過使用數據快取加速程式

譯者註：本文原始鏈接為<Make your programs run faster by better using the data cache>，翻譯獲得作者同意。本文中的一些策略只對大量數據處理有優化的可能，小量數據很可能帶來性能下降。

通過使用數據快取加速程式

開發者時刻面臨著如何加速程式，其中最明顯的是通過花哨的演算法來降低複雜度。比如說將\(O(n^2)\) 複雜度的演算法，使用 \(O(nlogn)\) 替換等等。這是很好的方法，但是並不是所有的程式都有更好的演算法來優化。那麼應該怎麼辦？是否存在一種方法來優化我們已存在的演算法。事實上是存在的，它叫：底層優化(low-level optimizations)。

首先，先來了解一下底層優化的情況。底層優化關注於如何最好地利用底層架構的特殊性來獲得更好的性能。這是這個系列的第一篇，將會涉及到底層優化。我們將在如何更好地利用記憶體快取子系統上探索一系列的方法。對於熟悉現代多進程系統記憶體快取原理的讀者，可以調過 數據快取 章節。

數據快取

電腦系統通常包含處理器和記憶體。在現代電腦系是中記憶體是比處理器慢百倍的，因此處理器通常都要等待記憶體傳輸數據。聰明的硬體工程師想出了一個解決方案來抵消速度上差異：他們添加了一個很小的快速記憶體被稱為快取的東西，用以彌補不同的速度。當程式需要訪問主存中的數據，它首先會檢查數據是否已經在快取中，如果在，它可以很快的獲取數據。否則，電腦會犧牲一些處理器周期，等待主記憶體提供數據。

通常情況下，快取存儲器分為指令快取存儲器和數據快取存儲器。指令快取器的目的是加速對指令的訪問，數據緩衝器的目的是加快對指令所使用的數據的訪問。這篇文章主要關注如何使用數據快取器來加速程式。

為什麼記憶體快取可以使程式運行的更快?

那麼，為什麼增加快取記憶體能起作用呢？ 畢竟，程式可以在任何時候都可以訪問任何記憶體位置，因此，這些數據不應該在快取中。理論上是這樣的，但在實踐中，真正的程式幾乎不會以隨機方式訪問記憶體。

有兩個原則制約著現實世界的程式行為。第一條被稱為時間局部性，即如果處理器目前正在訪問某個記憶體地址，就很有可能在不久的將來訪問這個記憶體地址(例如：循環中的計數器)。第二種被稱為空間局部性，其含義是如果處理器目前正在訪問某個記憶體地址，那麼它很有可能會在不久的將來訪問鄰近的記憶體地址（例如：處理數組中的數據）。

數據快取內部組織形式

現在讓我們來看看快取的內部情況。在現代電腦處理器中被分解為 Cache line，每個 Cache line 通常情況下是 64bytes 的大小。一個 Cache line 對應主存中 64byte 的記憶體塊。獲取 64byte 中的任意 1byte 數據，意味著需要載入整個 64byte 記憶體塊到快取中來。當 cache line 長時間沒有使用或需要使用新的數據去替換，快取將返回修改後的塊到主存中去。這整個過程程式並不知道。

讓程式運行更快的一些技巧

對數據快取有了一定的了解後，讓我們來看看如何將數據快取相關的原理應用到你的程式中，從而使你的程式擁有更好的性能。

注意：下面每小節，我使用 C 寫法的數組和 C++ 寫法的數組(vector、array),以及 C 寫法(struct)和 C++ 寫法(class)的類。

當獲取線性數據時，盡量使用vector和array

鏈表，hash maps,字典等，都是十分有用的數據結構，但是，它們都不是快取優化的。在這些數據結構中遍歷，將會帶來很大的快取丟失。如果，當前程式性能是最重要的因素，那麼將這些數據結構轉為數組。 如果這是不可能的，嘗試將數組的快取效率和其他數據的靈活性結合起來。Gap_buffer 是這種結合的很好例子。它將鏈表結構和數組結構結合，這使得其具有卓越的快取效率和較低代價的元素添加和刪除。另一個例子是 Judy_array ，稀疏數組的樹形實現，同樣的擁有很低代價的元素插入和刪除並且快取友好。

經常訪問的數據，在記憶體中應當是相鄰的

如果有幾個變數被一起訪問，它們應該被逐一聲明。這就增加了另一個變數在處理器訪問後已經在快取中的可能性。因為在處理器訪問了第一個變數之後，另一個變數已經在快取中了。從而避免了緩衝區的缺失。

考慮下面的類：

 class free_memory_list {
    void* head; /// Pointer to the beginning of the list
    Statistics statistics; /// Statistics about list usage
    int count; /// Number of elements in the list
    Allocator* base_allocator; /// Pointer to the class used for memory
/// allocation and deallocation
};

這個類實現了一個鏈接指針列表。如果我們的程式以這樣的方式使用該類，即把變數 head 和 count 作為一個包來訪問，那麼它們應該一個接一個地放在類定義中。在這種情況下我們增加了它們實際在同一快取行中的概率。

使用數據數組替換指針數組

當談到類或結構的數組時，人們想到的第一個想法是使用指針而不是值。這種解決方案與數組相比有很多優點，包括運行時的多態性和在數組中未分配元素的情況下，對記憶體的使用更少，但會有一個性能缺陷。 使用指針訪問該變數時，必然會涉及到高速快取的缺失。 因此，為了快速訪問數組，可以不使用指針而使用值。

因此，現在當把類的數組作為值時，我們將獲得一些好處。每當我們訪問數組中的一個元素時，快取預取器就會獲取更多與我們當前訪問的元素接近的元素。 如果，我們訪問的是數組中彼此相鄰的元素，數據快取被最大限度地利用了。

優化對類或結構數組的訪問

如果我們以隨機的方式訪問數組中的元素，就會出現一些快取丟失的情況。但是我們會有更多或者更少的丟失取決於我們在類中如何組織數據。例如：

假設我們有一個類my_class 並且該類的大小為 48btyes。陣列的第一個元素從偏移量 0 開始，第二個元素從偏移量 48 開始，第三個元素從偏移量 96 開始，第四個元素從偏移量 96 開始。如果我們的cache line是64bytes，那麼意味著第一個類元素在第一個 cache line 中，第二個元素將被分別存在第一個和第二個cache line中，第三個元素也將被分別存在兩個 cache line 中…

在對類的元素進行隨機訪問的情況下，將一個元素分割在兩個高速快取線之間，從數據快取利用率的角度來說是不好的。快取存儲器需要兩次訪問主存儲器才能讀取一個元素。那麼如何避免呢？如何使每個元素適合最小數量的cache line？下面是一些規則：

• 類的大小需要是cache line大小的倍數。
• 數組的起始地址需要是cache line大小的倍數。

要使類的大小是快取行大小的倍數，我們可以手動的填充使其滿足cache line 或者告訴編譯器自動幫我們填充，在C++11中允許使用alignas(64) 來指定。當然 GCC/CLANG 編譯器提供了 __attribute__((aligned (64))) 實現相同功能。更好的解決方案是讓編譯器和庫來幫助我們；我們可以用 posix_memalign 去分配對齊的記憶體在堆中，或者使用alignas(64) 和 __attribute__((aligned (64))) 在棧或者全局記憶體中分配記憶體。下面是一個使用posix_memalign分配類數組的例子:

my_class* array_of_my_class;
posix_memalign((void**)array_of_my_class, 64, SIZE * sizeof(my_class));
for (size_t i = 0; i < SIZE; i++) {
 ::new (&array_of_my_class[i]) my_class(i);
}

語法看起來非常的複雜，其實很簡單。我們聲明了my_class 類型的指針，該指針用來保存類數組。接下來我們使用posix_memalign 去為數組分配記憶體。同時指定了對其參數為64。最後，在循環中，我們為數組中的每個元素調用構造函數。注意，我們使用的是::new操作符，這個操作符不做記憶體分配，而是它在作為參數提供的記憶體上執行構造函數（簡單的說，就是執行 array_of_my_class[i] 構造函數，而不進行記憶體分配）。

有效地訪問你的矩陣中的數據

如果你的程式需要處理矩陣，你需要了解矩陣是如何存儲在記憶體中的。矩陣被定義為二維的，但是記憶體是一維的。C 和 C+ 編譯器將矩陣逐行排列。這就意味著如果我們獲取矩陣中的某個元素，和這個元素在相同行的一些元素也已經被載入到數據快取中。

這看起來微不足道，但它會對性能產生深遠的影響。考慮一下簡單的矩陣乘法演算法：

void multiply_matrices(int in_matrix1[][N], int in_matrix[][N], int result[][N])
{
    int i, j, k;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
          result[i][j] = 0;
             for (k = 0; k < N; k++) {
             result[i][j] += in_matrix1[i][k] * in_matrix[k][j];
             }
         }
    }
}

矩陣相乘就是對in_matrix1 的行，和對in_matrix2 的列做運算，按照這個計算規律結合上文的內容，我們可知in_matrix1 是符合快取規律的，但是，in_matrix2 將會是緩衝的災難。在in_matrix2 中每訪問下一個元素都會導致 cache 丟失，因此上面的程式碼具有很大的性能缺陷。

那麼如何解決上述問題？其實很簡單。進行一種叫做循環互換的轉換。 將j上的循環移到最裡面的位置。這個解決方案的具體實現如下：

void multiply_matrices(int in_matrix1[][N], int in_matrix[][N], int result[][N]) 
{ 
    int i, j, k; 
    for (i = 0; i < N; i++) { 
        for (j = 0; j < N; j++) { 
            result[i][j] = 0; 
        }
        for (k = 0; k < N; k++) {
            for (j = 0; j < N; j++) {
                result[i][j] += in_matrix1[i][k] * in_matrix[k][j]; 
        } 
    } 
}

通過這種轉換，逐行運行in_matrix，也要逐行運行result。這對性能有很大的影響。

在你的類和結構體中避免填充

關於數據對齊的一個小說明， 適用於所有原始數據類型，如果數據類型為4位元組大小，其起始地址需要能被 4 整除。如果數據類型為8位元組大小，其起始地址需要能被 8 整除。以此類推對於N位元組大小的數據類型，它的起始地址應當能被 N 整除，我們說變數是正確對齊的，或是對齊的，此外都是未對齊。對齊要求通常是由硬體提出的，並由編譯器儘可能地強制執行。

為了確保你的類和結構中的數據能正確對齊，C 和 C++ 編譯器可以添加填充：這些是在類的成員之間添加的未使用的位元組，以確保所有成員都正確對齊。請看下面的例子：

class my_class {
  int my_int;
  double my_double;
  int my_second_int;
};

人們期望這個結構體的大小是sizeof(int) + sizeof(double) + sizeof(int) = 16 ，然而，double需要8位元組對其。因此在my_int 之後，編譯器添加了 4bytes 的填充，此時my_double 記憶體對齊了。因此，當前的結構體需要20bytes。

此外，為了使類的數據在數組中正確對齊，類採取了根據其最大成員大小來對齊。而且類的大小是其最大成員大小的整數倍。在上面的例子中，整型是 4 位元組對齊，雙精度浮點型是 8 位元組對齊，因此我們的類應當 8 位元組對齊。由於類的大小需要是其對齊方式的倍數，編譯器在類的末尾增加了 4 位元組的填充。因此，類的大小從原來的 20 位元組增加到 24 位元組。填充物是如何影響快取效率的？比方說，我們的高速快取存儲器有一個 64 位元組的 cache line。在我們的例子中，只有2.7個my_class 類可以填充到 cache line 中，而不是我們所期望的四個類實例。另外，填充位元組被載入到高速快取中，但是你的程式是不會用這些填充位元組的。這保證了編譯器不會插入任何填充物，程式將更好地使用數據快取。下面對上面類進行了修改的類，其類成員的順序略有修改，從而避免編譯器填充。

class my_class {
  double my_double;
  int my_int;
  int my_second_int;
};

這個類的大小現在是 16 位元組，四個類實例符合一個 cache line 大小。

在linux中有個叫做 pahole工具可以查找你類的填充，它需要從源碼構建。並且不支援 C++11。

儘可能的使用最小的類型

儘可能的使用位元組數少的類型也是避免編譯器填充的一種方法。有時short 可以滿足需求的，我們卻習慣性的用int 。或者說在你的類的定義中有幾個bool變數，你用它來保持各種flag。你可以用chars或bool位域來代替使用bool。

class my_class {
public:
    bool my_bool1:1;
    bool my_bool2:1;
    bool my_bool3:1;
    bool my_bool4:1;
    int my_int:1;
};

在上面的例子中，每個 bool 佔了 1 bit。但是，編譯器為了和 my_int 對齊會在 my_bool4 後面自動填充。這可以通過重新安排my_class成員的順序來避免。

另外的例子：一個64位元組的cache line可以存儲8個整型或者4個長整型。 如果你有一個 1M 元素的數組，若該數組元素是整型那麼將佔 4MB，若為長整型就是 8MB。顯而易見的是，載入 8MB 到緩衝中，比載入 4MB 慢。

但要注意！處理器在內部以原生位元組數（例如：8位元組對於現代64位電腦，或者在嵌入式系統的結構中，可能適用更小的位元組數）為最佳工作方式。 使用較小的數據類型甚至可能降低速度。因此，你將需要測量以獲得確定的性能差異。

儘可能避免堆分配

由於下面幾個原因，堆的效率很低：

• 調用 malloc 和 free 是很慢的。
• 對這些位置的訪問是間接(通過指針)的，這種方式將導致更多的高速快取不命中的情況。

另一方面，棧頂幾乎總是在快取中，分配和刪除的速度超快。你可以用下面幾個技巧來加速。如果，你的程式需要分配可變大小的數組，可以考慮在棧而不是堆上分配數組（ GCC 支援但是有些編譯器不支援）。如果，你的程式需要使用malloc分配大量的小記憶體塊，可以考慮分配一個大的記憶體塊，然後根據你的需要把它分成小的。如果，你的程式需要頻繁的分配和釋放同一類型的對象，那麼我們可以考慮快取記憶體塊，而不是直接釋放，如果我們重新需要時，可以很快的重新分配。

儘可能的重複使用緩衝中的數據

理想情況下，我們希望從記憶體中載入數據到快取中，對其進行一些修改，然後再把它們返回到操作記憶體中。如果你需要兩次獲取相同的數據，你就沒有最佳地使用快取。

以查找一個數組中的最大元素和最小元素為例。

int * a = initialize_array(size);
int min = find_min(a, size);
int max = find_max(a, size);

我們在這裡調用了兩個函數，一個是找到最大值，一個是找到數組中的最小值。每個函數都有自己的循環，並在循環中遍曆數組中的元素。

假設數組足夠大，數組中的元素將被載入到快取中兩次。

解決辦法很簡單：在一個循環中完成對數組的所有工作。下面是更正後的版本。

int * a = initialize_array(size);
int min = a[0];
int max = a[0];
for (int i = 0; i < size; i++) {
  min = std::min(a[i], min);
  max = std::max(a[i], max);
}

這裡我們只對數組進行一次迭代。數組數據只被載入到數據快取中一次，這樣可以更好地利用數據快取。

盡量避免寫記憶體

所有對記憶體的寫入都要經過數據高速快取。當進行寫操作時，快取將該 cache line 標記為 “dirty”。若一個 cache line 是 dirty 的，這就意味著他和記憶體中的數據不同，它的內容遲早會被寫回記憶體中。這導致了速度的減慢。請看這兩個演算法:

void sort_fast(int* a, int len) {
    for (int i = 0; i < len; i++) {
        int min = a[i];
        int min_index = i;
        for (int j = i+1; j < len; j++) {
            if (a[j] < min) {
                min = a[j];
                min_index = j;
            }
        }
        std::swap(a[i], a[min_index]);
    }
}
void sort_slow(int* a, int len) {
    for (int i = 0; i < len; i++) {
        for (int j = i+1; j < len; j++) {
            if (a[j] < a[i]) {
                std::swap(a[j], a[i]);
            }
        }
    }
}

上面的程式碼顯示了兩個類似的數字排序的函數。兩者的工作方式相同。找到最小的元素並把它放在 0 的位置，然後找到下一個最小的元素並把它放在 1 的位置，以此類推。

方法 sort_slow 尋找比 a[i] 小的數組元素，如果找到就立即交換。 每當發現一個比 a[i] 小的元素時，它就會繼續交換元素。方法sort_fast 尋找數組中比a[i]小的元素，但它不做交換，而是將新的最小元素保存在臨時變數min和min_index中（編譯器為這些臨時變數使用一個暫存器）。 當函數完成對數組的運行並找到最終最小的元素時，才會替換a[i]和a[min_index]的內容。 在我的系統上，函數sort_fast比sort_slow快 2 倍。

正確對齊你的數據

你的變數需要正確對齊。這樣可以確保整個變數位於一個快取行中，而不是被分割在兩個快取行中。如果你的系統不支援對錯位變數的訪問，獲取數據會變得非常慢，因為你的作業系統可能會模擬對錯位記憶體地址的訪問。大多數時候，編譯器會確保數據正確對齊，但不細心開發者可能會創造出記憶體訪問錯位的地方。這種情況經常發生在將指針從一種類型轉換為另一種類型指針的時侯。錯誤示範：

unsigned char serialized_data[1024];
read_data(serialized_data);
int* header_pointer = (int*) (serialized_data + 3);
int header = *header_pointer; 

在這個例子中，我們將 char 指針轉換為 int 指針，從而使 header_pointer 錯位。解除對header_pointer的引用會產生錯位的記憶體訪問。在某些架構上，程式會崩潰，在其他架構上，程式會變慢。正確示例：

unsigned char serialized_data[1024];
read_data(serialized_data);
int* header_pointer = (int*) (serialized_data + 3);
int header;
memcpy(&header, header_pointer, sizeof(int));

在這裡，我們使用memcpy將輸入數組中的值複製到 header 變數中。函數memcpy不需要適當的對齊，這段程式碼更好地利用了數據快取，而且它是可移植的。

使用軟體預取

如果你的演算法不是一個一個地訪問數據，而是以隨機的方式在記憶體中跳躍，你可以使用軟體預取來告訴處理器你將訪問哪些數據，這樣它就有時間在需要它們之前將它們載入到快取中。例如，GCC 和 CLANG 編譯器提供了__builtin_prefetch內置，允許軟體預取。這裡我們舉一個二分搜索演算法的例子：

int binarySearch(int *array, int number_of_elements, int key) {
    int low = 0, high = number_of_elements-1, mid;
    while(low <= high) {
        mid = (low + high)/2;
#ifdef DO_PREFETCH
        // low path
        __builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1);
        // high path
        __builtin_prefetch (&array[(low + mid - 1)/2], 0, 1);
#endif
        if(array[mid] < key)
            low = mid + 1; 
        else if(array[mid] == key)
             return mid;
        else if(array[mid] > key)
             high = mid-1;
        }
}

二分搜索演算法不按順序運行數組，硬體快取預置器面臨大量的快取缺失。在上面的二分搜索演算法中，我們在進行數據查找之前就預取了記憶體中 high 的新值和 low 的新值。而當我們真正需要這些數據時，它已經存在於快取中了。

這個特定演算法的缺點是，我們獲取兩個值。而其中一個值我們將永遠不會被使用。這可能會對性能產生影響，因為一些 cache line 現在需要離開快取，以便為未使用的值騰出位置。如果另一個程式在另一個使用相同快取的核心上運行，可能會導致兩個程式的性能下降。

實驗

讓我們看看這些技巧對我們的實際問題有何幫助。在測試中，我們使用一個普通的通用系統AMD A8-4500M CPU，有四個核心，每個核心有16KB的L1數據快取，每個核心有2MB的L2數據快取（兩個核心共享2MB的L2數據快取）。這個系統有12GB的記憶體。

矩陣乘法

這裡有一篇由 Ulrich Drepper 寫的關於快取優化的文章，非常好，但也很冗長。他從簡單的矩陣乘法演算法開始，不斷完善，直到得到一個優化的版本，速度幾乎快了十倍。在他的實驗中，他使用了一個1000×1000的雙精度浮點矩陣。 他做的第一個優化是在乘法前對矩陣進行轉置，僅此一項就帶來了76.6%的性能提升！

帶軟體預取的二分搜索演算法

我們實現了一個使用前一章中的軟體預取的二進位搜索演算法，我們用它來測試當程式設計師明確使用預取時，記憶體快取子系統是如何工作的。我們使用的程式源碼放在了 github 中。只需要輸入make binary_search_runtimes 和 make binary_search_cache_misses 就可分別生成帶預取和不帶預取的程式。

我們生成了一個排序的隨機整數數組，長度為 10K, 100K, 1M, 10M 和 100M。我們用這些數組來進行二分搜索。我們稱其為 input_array 。我們使用幾種不同的方法來生成 index_array 的索引。並使用隨機的方法來生成 index_array 的元素， 但我們也使用了一種基於非隨機步長的方法。 如果步長是 N，index_array 的第一個元素是 0，第二是 N，第三是 2N 等等，直到我們到達數組的末端，然後繞過。

因此，程式碼實現如下：

 for (int i = 0; i < len; i++) {
    binarySearch(inputArray, len, inputArray[indexArray[i]]);
 }

我們對隨機 index_array 和步長為 1、100 和 10K 的 index_array 都進行了測試。 我們將 index_array 的大小固定為 10M ，這意味著我們正在進行 10M 的搜索。 對於隨機訪問的 index_array，下面是結果。

上表表示了在隨機訪問的情況下二分搜索的運行時間和工作集大小的關係。

對於隨機訪問，軟體預取對最小的10K數據集來說是負優化。隨著工作集的增加，帶軟預取的演算法也會變得比普通演算法快。對於大的工作集來說，速度上的差異大約是20%，而且即使工作集的大小進一步增加，它也會保持這種狀態。如果我們不是在訪問隨機元素，而是在以恆定的步長訪問元素，會發生什麼？由於這是一個合成測試，我們正在尋找一個我們事先知道位置的元素。例如：如果步長是 100，我們知道第一個元素的位置是 0，我們正在尋找 input_array[0] 這個值。在下一次迭代中，我們要尋找一個元素 input_array[100] 等等。 在這種情況下，快取是如何表現的？下面是結果。

上表是 步長=1 的情況下二分搜索的運行時間和工作集大小的關係。

上表是 步長=100 的情況下二分搜索的運行時間和工作集大小的關係。

上表是 步長=10K 的情況下二分搜索的運行時間和工作集大小的關係。

對於stride=1，普通演算法每次都能擊敗軟體預取演算法。不過這並不奇怪，因為前一次迭代的所有數據都已經在快取中了。

對於stride=100，正如預期的那樣，對於小的工作集，一般的演算法勝過軟體預取演算法。但是隨著工作集的增加，軟體預取演算法平均快6%。為什麼在這種情況下，與完全隨機的情況下的20%相比，平均快6%？如果我們的工作集是10M，平均來說，該演算法在20步左右完成。在這20步中，有14步的數據已經在之前搜索的快取中了。因此，只有在最後的6步中，軟體預取才有意義。

對於stride = 10K，我們看到一個非常奇怪的行為，即一般演算法比軟體預取演算法快。為什麼呢？答案是，在步長為10K時對於輸入的10M的工作集，這相當於將其減少到只有10K的工作集。因此，即使是最大的工作集大小（10M），通用演算法也更快，與隨機索引和工作集10K的通用演算法的百分比幾乎相同。

快取性能如何？預取對快取性能有什麼樣的影響。讓我們比較一下有預取和無預取的pref指令的結果。

兩個版本的二分搜索的快取性能、周期和指令數據。結果是有趣的。與普通版本相比，軟體預取版本有更多的快取引用，更多的快取丟失和更多的指令執行。這意味著，軟體預取版本實際上做了更多的工作。但它還是更快，因為它在較少的周期內做了更多的工作。現代處理器每個周期可以執行一條以上的指令，但如果處理器需要等待從主存儲器中獲取數據，這個數字就會下降。如果我們計算每個周期的指令數，軟體預取版本為0.42，普通版本為0.21。這是一個巨大的差異。

快取友好的鏈表

第二個實驗是一個有利於快取的鏈表（這些列表也被稱為 unrolled 鏈表）。普通的鏈表對快取非常不友好，在這樣的結構中迭代會導致很多快取丟失。我們怎樣才能做得更好呢？

常規的鏈接列表通常由鏈接列表節點組成，每個節點持有一個值和指向下一個節點的指針。在我們的實現中，鏈表節點可以持有一個以上的值，值的數量被指定為 linked_list 類的一個模板參數。我們測試了可以容納 1、2、4和 8 個值的鏈接列表節點，節點中值的數量越大，快取失誤就越少。我們用來測試的程式的源程式碼可以在 github 上找到。要運行它，只需執行 make linked_list_runtimes 和 make linked_list_cache_misses 即可。

我們唯一感興趣的是測試在鏈表中的進行插入、刪除等。我們的實現也比簡單的鏈錶快，但大部分的性能改進來自於更少的記憶體分配，而不是更好地使用數據快取。下面是一個單一列表節點的源程式碼。

    class linked_list_node {
    public:
        char used_elems[count];
        linked_list_node* next;
        char values[count * sizeof(Type)];
        ...
};

常量 count 保存單個列表節點中的值的數量，模板常量 Type 是我們在節點中保存的類型。由於一個節點有不止一個值，我們在數組 used_elems 中標記哪些值是實際使用的。注意，我們使用字元來保存使用的值，而不是bool。在我的機器上，bool需要四個位元組，而char需要一個位元組。這個選擇確實提高了列表的性能，因為更多來自節點的其他數據將被預取到快取中。

現在讓我們開始測量。下面的圖表測量了迭代鏈表所需的時間，這取決於節點中的值的數量（1、2、4和8）和鏈表的值的類型大小。

結果看起來非常好! 對於最小的類型大小，遍歷一個節點中有兩個值的鏈表比遍歷一個值的鏈表要少花43%的時間，而且這個數字對於所有類型大小都大致相同。還要注意的是，列表中的類型大小越大，在單個鏈表節點中擁有更多的值就越有意義。對於4位元組的類型大小，有兩個值的節點和有四個值的節點之間的差異很小，但對於32位元組的類型大小，這種差異是明顯的。

快取性能如何？在我們的測試中，記憶體讀取次數和數據快取失誤率是多少？首先讓我們測量一下我們的程式有多少次記憶體讀取。

正如你所看到的，單個節點中存儲的數值越多，讀取的記憶體總量就越少。這是可以預期的，因為涉及的指針算術較少。請注意，在我們的例子中，記憶體讀取的數量並不取決於類型大小。

快取缺失情況如何？我們使用了 cachegrind 工具來測量高速快取失誤率。它可以提供關於每個函數或每行的快取缺失的資訊。下面是結果。

一般的趨勢是：如果一個鏈接列表中的值越多，快取缺失的次數就越少。對於最小的類型，節點中8個值的快取丟失率為3%，而節點中1個值的快取丟失率為10%。對於較大的類型也觀察到類似的比率。另一個趨勢是：在一個鏈接列表節點中，類型大小越大，快取缺失率就越大。對於4位元組的類型大小，最壞的情況下快取丟失率為10%，最好的情況下為3%。對於32位元組的類型大小，最壞的情況下快取缺失率為20%，最好的情況下為13.6%。沒有什麼意外。當我們訪問節點中的第一個值時，快取預置器會在周圍的記憶體地址中載入值，所以當我們以後需要它們時，它們已經在快取中了。如果類型越大，預置器載入有用數據的機會就越少，所以這也是造成額外的緩衝區失誤的原因。

總結

那麼結論是什麼呢？無論是在我們的實驗中還是在一般情況下，關於數據快取的優化肯定有一些有趣的說法。

關於實驗的總結

那麼結論是什麼呢？我們先談談我們的實驗：這三個實驗都表明，更好地利用數據快取，會取得性能上的提升。與非優化版本相比，優化後的矩陣乘法有很好的性能提升，但是除了矩陣之外，我們很少能在數據結構上做一個簡單的操作來使我們的結構更適合快取。而在我的專業經驗中，我也很少看到矩陣作為數據結構使用。

第二個實驗是關於軟體預取的。我們確實看到了軟體預取在二分搜索上的性能提升，但性能提升只與不合適數據快取的工作集有關。需要注意，軟體預取是有代價的：我們的系統執行了更多的指令，並將更多的數據載入到快取中，這在某些情況下可能會導致其他方面的性能下降。軟體預取的好處是，它很容易實現，可以用來加快各種結構的迭代速度：鏈表、樹、堆等。然而，需要仔細測量以確保性能的提高是值得的。

我們的第三個實驗是關於快取友好的鏈表。我們再次看到速度有了很大的提高。改進來自幾個方面：更少的記憶體分配，更小的數據緩衝區失誤率和更少的指針運算指令。唯一的缺點是實現更複雜，而且記憶體消耗增加，因為可能會出現單個節點沒有被最佳填充的情況。但一般來說，我認為這些缺點是值得努力的。

對於數據快取優化的總結

正如我們的實驗所顯示的，以及我之前的經驗，優化確實帶來了性能的提升，而且有許多應用都需要這樣做。性能的提高取決於許多因素，範圍可以從百分之幾到百分之百甚至更多。

然而，這裡提出的一些建議會使你的程式更難理解，更難調試。而開發人員一直認為要避免的正是這一點，原因很充分。為了最大限度地從這些優化中獲益，你需要仔細地對你的程式進行剖析，找到瓶頸，並專註於加速這些瓶頸，而不是在你的程式碼中到處應用這些技巧。首先，應當保持你的介面乾淨，避免模組間的依賴，然後用更快的程式碼替換你的慢程式碼就很簡單了，你可以在不犧牲可維護性的情況下享受性能的提升。

參考

Ulrich Drepper 「What every programmer should know about memory」

What is cache memory – Gary explains

Agner.org – Software Optimization Resources