C++性能榨汁機之局部性原理

來自專欄 C++性能榨汁機

前言

《CSAPP》講到了局部性原理：一個編寫良好的計算機程序常常具有良好的局部性（locality）。也就是說，它們傾向於引用鄰近於其他最近引用過的數據項，或者最近引用過的數據項本身。這種傾向性，被稱為局部性原理（principle of locality），是一個持久的概念，對硬體和軟體系統的設計和性能都有著極大的影響。

局部性原理代碼示例

為了讓大家更加直觀的感受到局部性原理對我們程序性能的影響，我們先看一段代碼：

#include <iostream>#include <chrono>#include <vector>using namespace std;//求和函數，行優先int sum_row_first(const vector<vector<int>> &data){ int sum = 0; for(int i = 0; i < 1024; i++){ for(int j = 0; j < 1024; j++){ sum += data[i][j]; } } return sum;}//求和函數，列優先int sum_col_first(const vector<vector<int>> &data){ int sum = 0; for(int j = 0; j < 1024; j++){ for(int i = 0; i < 1024; i++){ sum += data[i][j]; } } return sum;}int main(){ vector<vector<int>> data(1024,vector<int>(1024,0)); //初始化二維數組 for(int i=0;i < 1024; i++){ for(int j=0; j < 1024; j++){ data[i][j] = rand() % 10; } } chrono::steady_clock::time_point start_time = chrono::steady_clock::now(); sum_row_first(data); // 計算行優先求和函數耗時 chrono::steady_clock::time_point stop_time = chrono::steady_clock::now(); chrono::duration<double> time_span = chrono::duration_cast<chrono::microseconds>(stop_time - start_time); std::cout << "行優先耗時："<< time_span.count() << " ms" << endl; start_time = chrono::steady_clock::now(); sum_col_first(data); //計算列優先求和函數耗時 stop_time = chrono::steady_clock::now(); time_span = chrono::duration_cast<chrono::microseconds>(stop_time - start_time); std::cout << "列優先耗時："<< time_span.count() << " ms" << endl;}

上面這段代碼我們主要定義了兩個二維數組求和函數，其中sum_row_first函數按照二維數組的行求和（先訪問第一行的所有元素，然後第二行……直到最後一行），而sum_col_first函數按照二維數組的列求和（先訪問第一列的所有元素，然後第二列……直到最後一列）。邏輯上來講，無論行優先訪問還是列優先訪問對函數運行的時間應該不會造成影響，畢竟，兩個函數都是遍歷了整個二維數組，但是實際運行結果如何呢？

從上圖運行結果我們發現，行優先求和函數的總運行時間為0.004661ms，列優先求和函數的總運行時間為0.007287ms，列優先求和函數運行時間幾乎是行優先求和函數運行時間的兩倍，造成這兩個函數運行速度相差巨大的原因就是局部性原理。

局部性原理

介紹局部性原理之前，我們需要先了解一下緩存的概念：在偽共享這篇博客中，我們提到了CPU中的緩存行的概念，CPU使用高速緩存以提高訪問數據的速度，每次CPU取數據都首先檢查高速緩存中是否已有所取數據，如果沒有則從內存中取到數據（包括相鄰的數據），緩存到CPU高速緩存中以供下次使用。緩存的概念充斥在現代操作系統的各個層次，從硬體到操作系統、再到用戶軟體，很多項目架構也使用到了緩存的思想，如使用訪問速度快的內存資料庫（如Redis）作為訪問速度慢的關係型資料庫（如Mysql）的緩存，以降低整個系統的訪問時間。

CSAPP中定義了空間局部性：在一個良好空間局部性的程序中，如果一個存儲器位置被引用了一次，那麼程序很可能在不遠的將來引用附近的一個存儲器位置。

在C/C++編譯系統中，二維數組的數據是按行存放的，所以每一行的數據在內存中是連續的，每一列的數據在內存中是相距較遠的，上面代碼中的行優先求和函數按行訪問數據，當某個數據被緩存的時候，它附近跟它同一行的數據也被同時緩存進了高速緩存，所以當程序繼續運行訪問下一個數據時，由於該數據已經被緩存了，所以CPU可以很快的從高速緩存獲取到該數據，而不用重新從內存中讀取。但是列優先求和函數訪問某一個數據時，把跟它同行的數據緩存進了高速緩存，但程序下一步卻是訪問下一行的對應列數據，所以導致緩存不命中，所以程序每一次訪問數據都需要重新從內存中訪問，所以速度相比於行優先程序有所降低。所以說行優先求和函數比列優先求和函數有更好的空間局部性。

總結

我們已經明白了局部性原理對我們程序性能的影響，在以後的代碼編寫時應盡量保證程序有較好的局部性，局部性比較好的程序更容易有較高的緩存命中率，而緩存命中率高的程序往往比緩存命中率低的程序運行速度更快。

最後請大家思考一個問題：堆排序平均複雜度和最差複雜度都為O(NlogN)，而快速排序平均複雜度O(NlogN)，最差複雜度會到O(N*N)，理論上講堆排序是優於快速排序的，但為何快速排序應用反而遠比堆排序應用廣泛？

……

答案之一：快速排序的每一步訪問的數據在內存中都是連續的，而堆排序中需要不停比較父子節點，如果父節點時N，則子節點是2N+1，兩者在內存中相距較遠。快速排序相比堆排序有更好的局部性，所以雖然兩種排序方法的理論平均複雜度相同，但在計算機上運行時往往快速排序的表現大幅優於堆排序。

推薦閱讀：