串行代码优化

《并行算法设计与性能优化》(刘文志)读书笔记

应用级别

编译选项

优化选项,指令集选项,循环展开,openMP

1
2
3
4
5
6
7
-OX: X级优化,如-O2 -O3

-ffast-math: 对超越函数使用精度低但速度快的版本

-funroll-all-loops: 展开所有循环

-mavx: 使用avx指令集向量化

使用高性能运算库

如 Intel的MKL、BLAS以及Nvidia的cuda加速库

少使用全局变量

全局变量会影响编译器优化,尤其是跨文件的全局变量(编译器需要在多文件中分析其状态),除此之外,在开发过程,优化全局变量也是个很困难的事情。

受限指针 __restrict__

对于存在别名的存储器,编译器很难去做优化,通常是不优化,因此使用restrict指针可以允许编译器做更多优化

条件编译

宏条件在编译确定,编译器可以忽略不成立分支,而条件分支是在运行时求值,能在编译时确定的东西尽量使用宏条件。

算法

查表法

对于数值计算,可以使用查表方法进行优化计算,比如计算10万次的exp计算,如果直接通过程序循环计算逼近精确值,时间上的损失特别大,如果利用查表法和线性插值可以节省很多时间。

索引顺序

访问数组或者多维数组时,尽量按行访问数据,若是Fortran,尽量按列访问数据。

预取

在数据使用之前,将数据加载到缓存中,可由编译器和人工通过添加预取指令完成。

函数级别

调用参数

函数参数优化先通过寄存器传递,超量之后才会通过栈传递。

若函数参数为比较大的结构体或者数组或者类,应当选择使用指针或者引用来减少复制和返回的开销,指针在这种情况下比值复制好。

使用内联(inline)函数

inline函数可以减小函数调用的开销,在循环中调用inline函数优势更加明显。但设计inline函数,注意复杂性,内联函数过于复杂,寄存器压力也会变大,可能并没有什么优势。

循环级别

循环展开

展开较小的循环可以获得优化(减少了循环变量和循环计数的开销)

1
2
3
4
float sum = 0.0;
for(int i = 0; i < 1000; i ++) {
sum += nums[i];
}

进行循环展开后

1
2
3
4
5
6
7
8
9
float sum = 0.0, sum1 = 0.0, sum2 = 0.0, sum3 = 0.0;
for(int i = 0; i < 1000; i = i + 4) {
sum += nums[i];
sum1 += nums[i+1];
sum2 += nums[i+2];
sum3 += nums[i+3];
}

sum += sum1 + sum2 + sum3;

通过展开部分可以有效减少循环次数,并且充分利用了寄存器。

循环合并

多个相似且条件相同的小循环如果寄存器的使用没有超量,可以考虑合并循环来提升性能。循环合并可以有效减少多个循环的开销。

未合并

1
2
3
4
5
6
for(int i = 0; i < 1000; i ++) {
a += arr1[i];
}
for(int i = 0; i < 1000; i ++) {
b += arr2[i];
}

合并后

1
2
3
4
for(int i = 0; i < 1000; i ++) {
a += arr1[i];
b += arr2[i];
}

循环拆分

大循环如果出现寄存器超量或溢出,可以将大循环拆分成多个小循环。此外,对于循环中,存在很强的依赖时,可以将循环拆开后,移除依赖。

1
2
3
4
for(int i = 0; i < 1000; i ++) {
a[i+1] = b[i]*2;
c[i] = a[i]/3;
}

其中计算c[i]会依赖a[i]并行化会存在依赖问题。
可以将循环串行

1
2
3
4
5
6
7
for(int i = 0; i < 1000; i ++) {
a[i+1] = b[i]*2;
}

for(int i = 0; i < 1000; i ++) {
c[i] = a[i]/3;
}

语句级别

对齐结构体

大数据类型在前,小数据类型在后。

或者使用编译器原语 __attribute__((aligned(x)))__attribute__((packed()))

选择小的数据类型

有些时候,使用int类型可能开销过大,使用short就已经绰绰有有余了。

减少内存读写

读写内存远比读写寄存器慢,合理使用寄存器和CPU缓存

简化代码

移除多余冗杂的计算

尽量避免在循环内部判断

分支预测失误会影响流水线

总结

串行代码有很多优化方式,虽然都只是小tricks,但在应用中,可以改善我们的编程习惯,性能也是一点一点提升的。所以,学习这个很有必要,也是为之后并行化做准备。