如何讓編譯器用std :: map實現循環不變代碼運動？

Question

這裏是我的代碼部分：（注意M是一個大的數字）

void myFunc(std::map<int, int>& myMap, int** arr) { 

    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = myMap[i] * j + i; 
     } 
    } 

} 

myMap[i]是在內部循環的循環不變。所以我認爲當我使用-O1時，gcc會自動將它移出內部循環。但它不起作用。因爲當我手動移動如下：

void myFunc(std::map<int, int>& myMap, int** arr) { 

    for (int i = 0; i < N; i++) { 
     int tmp = myMap[i]; 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = tmp * j + i; 
     } 
    } 

} 

運行時比第一個版本好得多。

也許編譯器認爲myMap會修改地圖，因此它選擇不進行優化。但我確定我只想讀取myMap的值，並且不會修改它。我如何讓編譯器理解？

Answer 1

你是對的，因爲地圖operator[]總是返回一個可修改的值的引用，所以編譯器不能認爲將它移到內部循環之外是安全的。這是因爲如果不存在，操作員會插入值。這可能是而不是你想要什麼。

通過僅使用const方法反覆遍歷地圖，很容易修復。您可以將地圖作爲const&傳遞給myFunc，然後使用cbegin()和cend()成員函數來獲取對存儲在其中的值的引用。

例如爲：

void myFunc(const std::map<int, int>& m, int** arr) { 
    int i = 0; 
    auto it = m.cbegin(); 
    while (it != m.cend()) { // assumes m.size() == N 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = (*it).second * j + i; 
     } 
     it++; 
     i++; 
    } 
} 

這裏是我的機器上的幾個簡單的基準，N=10和M=1000000。 （我每跑了幾次，這些都是在中間的某個地方。）

您的原始版本：

real 0m0.449s 
user 0m0.434s 
sys 0m0.012s 

你的第二個版本：

real 0m0.162s 
user 0m0.148s 
sys 0m0.012s 

我的解決辦法：

real 0m0.176s 
user 0m0.162s 
sys 0m0.012s 

你的第二個解決方案實際上似乎一致地快10％左右，所以如果你關心速度的每一點，ju st hoist that assign off out yourself。