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》