使用GCC優化C/C++循環中的嵌套if語句

我使用GCC編譯器在C/C++中測試各種優化。我目前有一個循環與多個嵌套if語句。條件是在程序執行開始時計算的。它看起來有點像這樣：使用GCC優化C/C++循環中的嵌套if語句

bool conditionA = getA(); 
bool conditionB = getB(); 
bool conditionC = getC(); 
//Etc. 

startTiming(); 

do { 
    if(conditionA) { 
     doATrueStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } else { 
     doAFalseStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } 
} while (testCondition()); 

endTiming();

哪裏doATrueStuff()是做一些簡單的數值計算所以在調用它沒有開銷的內聯函數。

不幸的是，這些條件不能事先定義，它們必須在運行時計算。我們甚至無法可靠地預測它們是真的還是錯的機會。 getA()不妨是rand()%2。但一旦計算出來，它們的價值從不改變。

有兩個解決方案，我認爲，其中之一是用於調用循環內的相應功能全局函數指針，就像這樣：

void (*ptrA)(void); 
//Etc. 

int main(int argc, char **argv) { 
    //... 
    if (conditionA) { 
     ptrA=&aTrueFunc; 
    } else { 
     ptrA=&aFalseFunc; 
    } 
    //... 
    do { 
     (*ptrA)(); 
    } while (testCondition()); 
    //... 
}

這樣我可以消除從所有分支循環，然後我會有多個函數調用的開銷放緩我。

或者我可以簡單地對條件的每個組合不同的循環，這樣的事情：

if(conditionA) { 
    if(conditionB) { 
     do { 
      //Do A == true B == true stuff 
     } while (testCondition()); 
    } else { 
     do { 
      //Do A == true B == false stuff 
     } while (testCondition()); 
    } 
} else { 
    //Etc. 
}

不過是少了很多優雅，並得到不可能一個如此高效地完成，一旦一個人開始有太多許多條件，因爲在X條件下需要編寫2^X個循環。

有沒有更優雅/更快的方式來優化？

這裏甚至還有什麼意思嗎？或者編譯器是否會明白，在循環過程中條件不會改變並優化它本身？

出於好奇，是否還有另一種編程語言可以使編寫這樣的代碼更容易/可能？或者只有在程序加載到內存後才能使用程序集來更改程序的指令？

來源

2015-05-15 Parisbre56

第一個想法似乎沒有比原來的更多的函數調用。 –

如果條件在循環內部沒有改變，那麼CPU可能會很好地進行分支預測。 – Carlton

看來你已經有了2^X個不同的塊。 – Jarod42

理論：

試圖通過一些古怪的重寫優化你的代碼可能很難讓編譯器作出其一貫的優化。編譯器和還使處理器能夠優化使用2項技術的代碼：

分支預測：編譯器可以做到這一點，通過使用profile guided optimizations，主要通過估計每個分支的概率。除了計算每個目標的統計數據之外，CPU還具有分支目標緩衝區，用於檢測分支模式。
分支預測：編譯器或CPU將使代碼並行執行兩個分支（因爲時下處理器是超標量）和基於所述條件的結果，它會只是忽略不正確的路徑的結果（例如CMOV指令）。您可以嘗試使用以下命令禁用分支預測：：-fno-if-conversion和-fno-if-conversion2。如果每個分支上有很多計算，並且執行所有路徑將導致浪費指令解碼器和執行端口，這可能會有所幫助。

舉一個簡單的開發，使用gcc，你還可以幫助分支預測或代碼生成使用「可能」與「不可能」編譯提示。查詢here瞭解更多詳情。如果你知道例如一種情況比另一種情況更可能發生，這可能會起作用。

要查看分支預測效率，請使用perf stat ./binary並查看分支未命中率以及每次優化的分支未命中次數。

在你的代碼的情況：

如果conditionA，conditionB和conditionC在循環之前計算，並且不改變，那麼很容易在分支預測來檢測模式。 CPU的預測器通過跟蹤最後一個分支的採集/未採集，並使用記錄的歷史來預測後續分支。所以我實際上期望由於代碼中的分支導致的性能損失很小，您可以像上面那樣驗證它。

來源

2015-05-15 20:34:51 VAndrei

你的回答非常有幫助和正確。我做了一些測試，看看分支機構花了多少時間，這並不是很多，所以我嘗試的任何優化都不應該顯着改善。再次感謝您帶來了許多我不知道的事情。 – Parisbre56

考慮模板。挑戰在於將運行時值映射到編譯時模板參數。下面的樣板是每個參數的一個分派功能，編譯器會爲你創建組合樹。不完全優雅，但比開放編碼多參數開關場更好。

您也可以直接在您的計算中使用模板參數（或它們的函數），並且這些參數也將進行優化，例如根據模板參數選擇常數，或者將0乘以表達式項你不想貢獻。

template <bool B0, bool B1, bool B2> 
void doStuffStage3() 
{ 
    // Once you get here, you can use B0, B1, and B2 in 
    // any expressions you want, in the inner loop, and the compiler 
    // will optimize everything out since they're known compile-time. Basically, 
    // the compiler will create separate versions of this function 
    // for all required combinations of the input 
    do { 
     if(B0) { 

     } else { 

     } 
    } while(testCondition()); 
} 

template <bool B0, bool B1> 
void doStuffStage2(bool b2) 
{ 
    if(b2) doStuffStage3<B0,B1,true>(); 
    else doStuffStage3<B0,B1,false>(); 
} 

template <bool B0> 
void doStuffStage1(bool b1, bool b2) 
{ 
    if(b1) doStuffStage2<B0,true> (b2); 
    else doStuffStage2<B0,false>(b2); 
} 

void doStuff(bool b0, bool b1, bool b2) 
{ 
    if(b0) doStuffStage1<true> (b1, b2); 
    else doStuffStage1<false>(b1, b2); 
} 

int main() 
{ 
    doStuff(getA(), getB(), getC()); 
}

來源

2015-05-15 20:12:36 Peter

儘管你的回答是正確的，但我會和VAndrei一起去，只是因爲我發現它提供的信息更有幫助。儘管如此，感謝您花時間回答並將此技術引入我的注意。 – Parisbre56

使用GCC優化C/C++循環中的嵌套if語句

回答

相關問題