循环优化

编译器会对代码做很多优化，根据统计，应用百分之八十的时间落在循环体中，因此循环优化变得尤为重要。

循环优化的目的

• 移动非必要的计算到循环体外
• 使用最廉价的指令
• 使用SIMD来优化代码
• 循环体内的指令应该充分利用CPU的PIPELINE，减少停顿的时间
• 使用更优的访存方式

循环优化的手段

Inline

循环体内的函数调用被转换为inline后，会让编译器做更多的优化

代码片段：

inline int mul(int x, int y) {
    return x*y;
}

int main() {
    int a = 4, b=2;
    cout<< mul(a, b);
    return 0;
}

mul函数经过inline后，会把代码转变为 a*b，然后发现a和b是常熟，编译器就可以直接得到答案8

保持变量在寄存器

编译器会尽量保持变量在寄存器中

因为它的访问速度是最快的

有两个情况会妨碍变量持续保存在寄存器中

• 太多的变量，因为寄存器有限
• 变量存在指针引用，因为有可能变量被引用改变

去掉死代码

代码有可能存在某些片段，是程序无法运行到的

编译器通过判定条件，来发现这些死代码，并去掉，从而得到占用更少内存的应用

void add(int* a, int* b) {
    (*a)++;
    if(b) (*b)++;
}

for(int i=0; i<n; ++i) {
    add(&a[i], nullptr);
}

编译器通过内联函数 add ，发现 b 为 nullptr，可以判定代码第三行为死代码

可以剔除

移动不必要计算到循环外

for (int i=0; i<n; ++i) {
    switch (i%2) {
        case 0: a[i] += x*x; break;
        case 1: a[i] -= x*x; break;
    }
}

x*x会在循环中不断用到，如果在每次循环都去计算，会浪费计算资源

编译器通过把x*x的计算移动到循环体外，来减少循环体的计算量

auto x2 = x*x;
for (int i=0; i<n; ++i) {
    switch (i%2) {
        case 0: a[i] += x2; break;
        case 1: a[i] -= x2; break;
    }
}

使用更廉价的计算指令

for (int i=0; i<n; ++i) {
    a[i] = i*3;
}

通过分析，上面的乘法指令可以使用累加来代替

int tmp = 0;
for (int i=0; i<n; ++i) {
    a[i] = tmp;
    tmp += 3;
}

循环展开

对循环体展开后，可以让循环体更大，有可能得到更大的优化空间

for (int i=0; i<n; ++i){
    index = i/2;
    a[i] = b[index];
}

进行循环展开

for (int i=0; i<n;){
    index = i/2;
    a[i] = b[index];
    
    ++i
    index = i/2;
    a[i] = b[index];
    
    ++i;
}

展开后发现 index在两次计算得到的值是一样的

所以再优化后代码得

for (int i=0; i<n;){
    index = i/2;
    a[i] = b[index];
    
    ++i
    a[i] = b[index];
    
    ++i;
}

CPU Pipelining

为了更好得利用CPU Pipeline，需要让指令间经量减少CPU的停顿

思考下面代码

for (int i=0; i<n; ++i) {
    c[i] = a[i] + b[i];
}

转化成指令如下：

for (int i=0; i<n; ++i){
    val_a = load(a + i);
    val_b = load(b + i);
    val_c = add(val_a, val_b);
    store(val_c, c+i);
}

line 4依赖 line 2 和 line 3

line 5依赖 line 4

这会导致CPU需要等待依赖的完成而发生停顿

编译器通过修改顺序，代码如下，来减少停顿

val_a = load(a + 0);
val_b = load(b + 0);
val_c = add(val_a, val_b);

val_a = load(a + 1);
val_b = load(b + 1);
for (int i = 0; i < n - 2; i++) {
    store(val_c, c + i);
    val_c = add(val_a, val_b);
    val_a = load(a + i + 2);
    val_b = load(b + i + 2);
}

store(val_c, n - 2);

val_c = add(val_a, val_b);
store(val_c, n - 1);

转化后，循环体就有任何依赖了

可以通过pipeline并行执行

向量化

CPU simd操作，可以成倍提高代码的运行效率

double sum = 0.0;
for(int i=0; i<n; i++){
    sum += a[i];
}

使用simd转换后

double<4> vec_sum = {0, 0, 0, 0};
for(int i=0; i<n; i+=4) {
    double<4> a_val = load<4>(a + i);
    vec_sum += a_val;
}
double sum = 0;
for(int i=0; i<4; ++i){
    sum += vec_sum[i];
}

循环交换

循环体又包含循环体

那么以row优先的循环，性能会更优

for(int i=0; i<n; ++i){
    for(int j=0; j<n; ++j){
        b[j][i] = a[j][i] + 1;
    }
}

交换循环

for(int j=0; j<n; ++j){
    for(int i=0; i<n; ++i){
        b[j][i] = a[j][i] + 1;
    }
}

分裂循环

循环体可以分成很多部分

某些部分可以通过向量化来优化

某些部分由于出现数据依赖，导致不能使用向量化来优化

通过把循环分裂

可以把可以向量化的代码抽离出来

并使用simd来优化

for(int i=0; i<n; ++i) {
    a[i] = a[i-1]*b[i];
    c[i] = a[i] + b[i];
}

通过分析发现line 2出现了数据依赖

line 3没有数据依赖，可以向量化

for(int i=0; i<n; ++i) {
    a[i] = a[i-1]*b[i];
}

for(int i=0; i<n; ++i){
    c[i] = a[i] + b[i];
}

循环合并

两个循环体如果遍历的是用一个对象

把这两个循环体合并成一个，会更好的利用CPU cache

auto min = a[0];
for(int i=1; i<n; ++i){
    if(a[i]<min) min = a[i];
}

auto max = a[0];
for(int i=1; i<n; ++i){
    if(a[i]>max) max = a[i];
}

合并后

auto min = a[0];
auto max = a[0];
for(int i=1; i<n; ++i){
    if(a[i]<min) min = a[i];
    if(a[i]>max) max = a[i];
}

编译优化的杀手

• 函数调用
• 指针别名