第6章循环优化

课程目录第6章循环优化

6. 循环优化：循环展开、循环合并、循环交换、减少循环内的分支预测失败

循环，说白了就是程序里最耗时的「热区」。我做过不少性能分析，十次有八次，瓶颈都卡在某个循环里。你想想看，一条指令执行一次可能只要几纳秒，但如果循环一千万次，那累积起来就是几十毫秒的延迟。所以优化循环，是性价比最高的手段之一。

今天咱们聊四个最实用的循环优化技巧：循环展开、循环合并、循环交换，以及减少分支预测失败。每个我都踩过坑，也尝过甜头。

6.1 循环展开：用空间换时间

循环展开，就是把循环体复制多份，减少循环控制的开销。说白了，少跳几次，多干点活。

举个例子，一个简单的累加循环：

// 原始循环
int sum = 0;
for (int i = 0; i < 1000; ++i) {
    sum += arr[i];
}

// 展开4次
int sum = 0;
for (int i = 0; i < 1000; i += 4) {
    sum += arr[i];
    sum += arr[i+1];
    sum += arr[i+2];
    sum += arr[i+3];
}
// 处理剩余元素
for (int i = 1000 - (1000 % 4); i < 1000; ++i) {
    sum += arr[i];
}

展开之后，循环次数从1000次降到了250次。每次循环少了一次条件判断和一次跳转。别小看这点开销，在百万级循环里，差别很明显。

我的经验：展开因子不是越大越好。我试过展开8次、16次，结果代码体积暴涨，指令缓存（I-cache）命中率下降，反而变慢了。一般展开2到4次比较稳妥。具体多少，建议用perf跑一下看看。

6.2 循环合并：减少缓存污染

循环合并，就是把两个或多个遍历相同数据范围的循环，合并成一个。好处是：数据只需要加载一次，减少缓存缺失。

看个例子：

// 两个独立循环
for (int i = 0; i < N; ++i) {
    a[i] = b[i] * 2;
}
for (int i = 0; i < N; ++i) {
    c[i] = a[i] + 1;
}

// 合并成一个循环
for (int i = 0; i < N; ++i) {
    a[i] = b[i] * 2;
    c[i] = a[i] + 1;
}

合并之后，a[i] 刚算完就被用上了，还在缓存里热乎着。两个循环分开写的话，第一个循环把 a 写进缓存，第二个循环又要重新加载——如果数据量很大，缓存早就被冲掉了。

注意：循环合并不是万能的。如果两个循环访问的数据集完全不同，合并反而会让缓存压力变大。我曾经在一个图像处理项目里强行合并，结果L1缓存命中率掉了15%，得不偿失。合并前先想想：这些数据是不是「邻居」？

6.3 循环交换：让内存访问更连续

C++里二维数组是按行存储的。如果你按列遍历，每次访问都跳到下一行的不同位置，缓存行利用率极低。循环交换就是调整内外层循环的顺序，让内存访问模式更连续。

看这个反面教材：

// 按列遍历（坏）
for (int j = 0; j < COLS; ++j) {
    for (int i = 0; i < ROWS; ++i) {
        matrix[i][j] = 0;
    }
}

// 按行遍历（好）
for (int i = 0; i < ROWS; ++i) {
    for (int j = 0; j < COLS; ++j) {
        matrix[i][j] = 0;
    }
}

按列遍历时，每次 matrix[i][j] 都跳到下一行的不同列，缓存行里只取了一个元素就废了。按行遍历的话，连续访问同一行的相邻元素，一个缓存行64字节，能装16个int，利用率高得多。

我做过一个矩阵乘法优化，光是把循环顺序从 i-k-j 改成 i-j-k，性能就提升了3倍。嗯，你没看错，就是3倍。

    核心原则：最内层循环的索引，应该对应内存中变化最快的维度。对于C++二维数组，就是最右边的索引。

6.4 减少分支预测失败

现代CPU有分支预测器，它会猜测条件跳转的结果。猜对了，流水线继续跑；猜错了，就要清空流水线，重新加载，损失十几个时钟周期。循环里的分支，如果预测失败率很高，性能会大打折扣。

常见的优化手段有几种：

消除分支：用算术运算代替条件判断
数据驱动：用查表代替if-else
分支排序：把大概率发生的分支放在前面

看个消除分支的例子：

// 有分支的版本
for (int i = 0; i < N; ++i) {
    if (arr[i] > 0) {
        sum += arr[i];
    }
}

// 无分支的版本
for (int i = 0; i < N; ++i) {
    int mask = (arr[i] > 0) - 1;  // 正数时mask为0，否则为-1
    sum += arr[i] & ~mask;
}

第二个版本用位运算代替了分支。虽然指令多了几条，但流水线不会被清空。在数据随机分布时，这个优化效果很明显。

避坑指南：我曾经在一个排序后的数组上做条件累加，分支预测成功率高达99%，这时候用位运算反而更慢。因为分支预测几乎不失败，而位运算多了几条指令。所以优化前一定要先分析数据分布。

知识体系总览

下面这张图总结了循环优化的四个方向及其核心思想：

总结一下

循环优化没有银弹。展开、合并、交换、去分支，每个都有适用场景。我的建议是：

先用perf定位热点循环
分析数据访问模式和分支规律
选一个最对症的策略下手
改完一定要测，别想当然

我曾经在一个排序算法里同时用了展开和交换，结果两个优化互相干扰，性能反而下降了。所以，一次只改一个，对比验证，才是靠谱的做法。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

6. 循环优化：循环展开、循环合并、循环交换、减少循环内的分支预测失败

6.1 循环展开：用空间换时间

6.2 循环合并：减少缓存污染

6.3 循环交换：让内存访问更连续

6.4 减少分支预测失败

知识体系总览

总结一下