C++性能優化筆記-6-C++元素的效率差異-9-循環

C++元素的效率差異

• 循環
• • 循環展開
  • 循環控制條件
  • 拷貝或清零數組

循環

循環的效率依賴于微處理器可以多好地預測循環控制分支。分支預測參考前面的章節以及《Intel，AMD與VIA CPU微架構》。具有小且固定重複計數以及不包含分支的循環可以被完美預測。可以被預測的最大循環計數取決于處理器。僅某些具有特殊循環預測器的處理器可以預測嵌套循環。在其他處理器上，僅最裡層循環可以良好預測。具有高重複計數的循環僅在退出時被誤預測。例如，如果一個循環重複1000次，在1000次裡循環控制分支僅誤預測一次，是以對總體執行時間，誤預測懲罰微不足道。

循環展開

在某些情形裡，展開一個循環是有好處的。例如：

// Example 7.30a
int i;
for (i = 0; i < 20; i++) {
     if (i % 2 == 0) {
          FuncA(i);
     }
     else {
          FuncB(i);
     }
     FuncC(i);
}
           

這個循環重複20次，交替調用FuncA與FuncB，然後FuncC。展開該循環得到：

// Example 7.30b
int i;
for (i = 0; i < 20; i += 2) {
     FuncA(i);
     FuncC(i);
     FuncB(i+1);
     FuncC(i+1);
}
           

這有3個好處：

• I < 20循環控制分支執行10次而不是20次。
• 重複計數從20降到10的事實意味着在大多數CPU上可以被完美預測。
• 消除了if分支。

循環展開也有缺點：

• 展開的循環在代碼緩存或微操作緩存中占據更多空間。
• 許多CPU有回環緩沖區，以提高很小的循環的性能。展開循環不大可能适合回環緩沖。
• 如果重複計數是奇數且以2展開，那麼有一次必須在循環外完成的額外疊代。一般來說，在重複計數不确定能被展開因子整除時，有這個問題。

循環展開僅應該在可以獲得特定好處時才使用。如果循環包含浮點計算或向量指令且循環計數器是整數，那麼通常可以假設總體執行時間由浮點代碼确定，而不是循環控制分支。在這個情形裡，展開循環沒有好處。

循環展開在存在循環執行依賴鍊的情況下是有用的。

在帶有微操作緩存的處理器上，最好避免循環展開，因為有效地使用微操作緩存是重要的。這也适用于有回環緩沖的處理器。

編譯器将通常自動展開一個循環，如果這看起來有利可圖。程式員不需要手動展開循環，除非可以獲得特定的好處，比如消除例子7.30b中的if分支。

循環控制條件

最高效循環控制條件是一個簡單的整數計數器。具有亂序能力的微處理器将能夠提前幾次疊代對循環控制語句求值。

如果循環控制分支依賴于循環内的計算，它的效率下降。下面的例子将一個零結尾的ASCII字元串轉換到小寫：

// Example 7.31a
char string[100], *p = string;
while (*p != 0) *(p++) |= 0x20;
           

如果該字元串的長度已知，那麼使用一個循環計數器更高效：

// Example 7.31b
char string[100], *p = string; int i, StringLength;
for (i = StringLength; i > 0; i--) *(p++) |= 0x20;
           

循環控制分支依賴循環内計算的一個常見情形是在數學疊代裡，比如泰勒展開與Newton-Raphson疊代。這裡，疊代被重複，直到殘留誤差低于特定的。計算殘留誤差以及将它與容許值比較所需的時間可能很高，以至于确定最壞情形的最大重複次數并總是疊代這個次數的方式效率會更高。這個方法的好處是，微處理器可以提前執行循環控制分支，并早在循環内浮點計算完成前，解決分支誤預測。如果典型的重複計數接近最大重複計數，且每次疊代殘留誤差的計算對總體計算時間貢獻顯著時，這個方法是有優勢的。

循環計數器最好應該是一個整數。如果循環需要浮點計數器，那麼添加一個額外整數計數器。例如：

// Example 7.32a
double x, n, factorial = 1.0;
for (x = 2.0; x <= n; x++) factorial *= x;
           

通過增加一個整數計數器并在循環控制條件中使用整數，可以改善：

// Example 7.32b
double x, n, factorial = 1.0; int i;
for (i = (int)n - 2, x = 2.0; i >= 0; i--, x++) factorial *= x;
           

在具有多個計數器的循環裡注意逗号與分号間的差别。

将整數與零比較有時比與其他數比較更高效。是以，使循環計數遞減為零比遞增到某個正數n要稍微高效一些。但如果循環計數器用作一個數組的索引，就不成立。資料緩存是對前向通路數組優化的，而不是後向。

拷貝或清零數組

拷貝數組或将數組置零，使用循環可能不是最優的。例如：

// Example 7.33a
const int size = 1000; int i;
float a[size], b[size];

// set a to zero
for (i = 0; i < size; i++) a[i] = 0.0;

// copy a to b
for (i = 0; i < size; i++) b[i] = a[i];
           

使用函數memset與memcpy通常更快：

// Example 7.33b
const int size = 1000;
float a[size], b[size];

// set a to zero
memset(a, 0, sizeof(a));

// copy a to b
memcpy(b, a, sizeof(b));
           

大多數編譯器将自動使用對memset與memcpy調用替換這樣的循環，至少在簡單的情形中如此。memset與memcpy的顯式使用是不安全的，因為如果size參數比目标數組更大，會出現嚴重的錯誤。但如果循環計數超過數組大小，相同的錯誤也會發生。

《optimizing cpp》