代码性能优化

在开发C代码时，需要注意以下几点：

1. 能用整型计算就不用浮点数计算
2. 能用左移右移，就不用乘除
3. 在循环内部，多次使用的值不变的计算表达式，一定要提前计算好。如果是常数，就放到循环外
4. 能不用if就不用if，比如MAX(a,b,c)和MIN(a,b,c)
5. 多层循环尽量外小内大
6. 选择合适的且空间更小的数据类型
7. 函数参数不要超过6个，超过了就放在一个结构体中。

1 编译优化

1.1 编译优化选项

1. 内联优化 为了进行函数调用，程序需要将调用参数放到栈或寄存器中，同时还需要保存一些寄存器到栈上，以免 callee 会覆盖到。函数执行的切换，对于代码局部性、寄存器使用、运行性能都会有不少的影响。 使用内联优化需要用inline关键字以及开启编译优化'-O2'等级或'-finline-functions'。 一些实例
2. 自动向量化 使用编译选项-ftree-vectorize即可开启自动向量化。使用编译选项-fopt-info-vec-optimized查看自动向量化优化信息。 自动向量化的限制： 1）循环中有较多条件语句，函数调用等，复杂的cfg。这样做不了向量化优化 2）嵌套循环中，外层循环的索引参与内部循环计算，导致无法向量化优化 3）其他一些特性 也就是不能有依赖。
3. 自动并行化 通过OpenMP的编译指导语句，可实现自动并行化。使用编译选项-fopenmp即可使用OpenMP的功能。OpenMP有哪些能力需要学习。第一个链接，第二个链接
4. 浮点优化 通过编译选项-ffast-math，即可开启浮点优化，提高浮点运算速度。
5. 循环优化 1） 循环展开 实例

//展开前for(int i =0; i < n; i++){
    a[i]+= b[i];
    c[i]+= d[i];}//展开后for(int i =0; i < n; i +=2){
    a[i]+= b[i];
    c[i]+= d[i];
    a[i+1]+= b[i+1];
    c[i+1]+= d[i+1];}

循环展开可以

提高CPU的利用率

和

减少分支预测失败的次数

。但是也会增大代码的体积，降低缓存命中率。
使用编译选项

-funroll-loops

，即可开启循环展开优化。
建议在手写向量化代码后再考虑循环展开优化。
2） 循环分布

//分布前for(int i =0; i < n; i++){
    A[i]= i;
    B[i]=2+ B[i];
    C[i]=3+ C[i -1];}//分布后for(int i =0; i < n; i++){
    A[i]= i;
    B[i]=2+ B[i];}for(int i =0; i < n; i++){
    C[i]=3+ C[i -1];}

循环分布将有依赖和没有依赖的语句分开，从而进行自动向量化。
llvm可以用编译选项

-mllvm -enable-loop-distribute

开启循环分布，gcc没查到。

3） 循环剥离
将循环的头和尾剥离处理，对中间的部分进行自动向量化。

//剥离前for(int i =0; i < N-2; i++){
    c[i]= a[i]+ b[i];}//剥离后for(int i =0; i <2; i++){
    c[i]= a[i]+ b[i];}for(int i =2; i < N-2; i++){
    c[i]= a[i]+ b[i];}

1. 编译指示优化

#pragmaGCC optimize(1)#pragmaGCC optimize(2)#pragmaGCC optimize(3)#pragmaGCC optimize("Ofast")#pragmaGCC optimize("inline")//内联#pragmaGCC optimize("-fgcse")#pragmaGCC optimize("-fgcse-lm")#pragmaGCC optimize("-fipa-sra")#pragmaGCC optimize("-ftree-pre")#pragmaGCC optimize("-ftree-vrp")#pragmaGCC optimize("-fpeephole2")#pragmaGCC optimize("-ffast-math")//浮点优化#pragmaGCC optimize("-fsched-spec")#pragmaGCC optimize("unroll-loops")//循环展开#pragmaGCC optimize("-falign-jumps")#pragmaGCC optimize("-falign-loops")#pragmaGCC optimize("-falign-labels")#pragmaGCC optimize("-fdevirtualize")#pragmaGCC optimize("-fcaller-saves")#pragmaGCC optimize("-fcrossjumping")#pragmaGCC optimize("-fthread-jumps")#pragmaGCC optimize("-funroll-loops")//循环展开#pragmaGCC optimize("-fwhole-program")#pragmaGCC optimize("-freorder-blocks")#pragmaGCC optimize("-fschedule-insns")#pragmaGCC optimize("inline-functions")//内联#pragmaGCC optimize("-ftree-tail-merge")#pragmaGCC optimize("-fschedule-insns2")#pragmaGCC optimize("-fstrict-aliasing")#pragmaGCC optimize("-fstrict-overflow")#pragmaGCC optimize("-falign-functions")#pragmaGCC optimize("-fcse-skip-blocks")#pragmaGCC optimize("-fcse-follow-jumps")#pragmaGCC optimize("-fsched-interblock")#pragmaGCC optimize("-fpartial-inlining")#pragmaGCC optimize("no-stack-protector")//栈保护#pragmaGCC optimize("-freorder-functions")#pragmaGCC optimize("-findirect-inlining")#pragmaGCC optimize("-frerun-cse-after-loop")#pragmaGCC optimize("inline-small-functions")#pragmaGCC optimize("-finline-small-functions")#pragmaGCC optimize("-ftree-switch-conversion")#pragmaGCC optimize("-foptimize-sibling-calls")#pragmaGCC optimize("-fexpensive-optimizations")#pragmaGCC optimize("-funsafe-loop-optimizations")#pragmaGCC optimize("inline-functions-called-once")#pragmaGCC optimize("-fdelete-null-pointer-checks")

指定代码段使用指定的优化级别

#pragmaGCC push_options#pragmaGCC optimize("O3")//your code optimize ("O3") specially#pragmaGCC pop_options

2 代码编写优化

2.1 算法优化

2.2 数据结构优化

各种数据结构对比

2.3 函数级优化

2.3.1 指针别名消除

当一个程序中两个及以上的指针引用相同的存储地址时，就会有指针别名的问题。别名会影响程序的自动向量化和并行化。
若确定两个指针指向的是不同的地址，则可以用restrict关键字修饰。

voidadd(int*a,int*b){...}//restrict修饰后voidadd(int* restrict a,int* restrict b){...}

2.4 循环级优化

1 循环展开
2 循环合并
3 循环分段
4 循环分块
5 循环交换
6 循环分布
7 循环分裂
8 循环倾斜

2.5 语句级优化

2.5.1 删除冗余语句

一些没有使用的变量或没有意义的语句都可以删除。

2.5.2 去除相关性

1. 标量扩展

for(int i =0; i < N; i++){
    T = A{i];
    A[i]= B[i];
    B[i]= T;}//将标量T改为数组T[i],打破了依赖就可以进行自动向量化for(int i =0; i < N; i++){
    T[i]= A[i];
    A[i]= B[i];
    B[i]= T[i];}

1. 标量重命名

T =2；
y = T + T;
T = a - b;
z = T * T;//不要一直用T当临时变量，重新申请一个，打破依赖
T =2；
y = T + T;
T1 = a - b;
z = T1 * T1;

1. 数组重命名 与标量重命名类似，不要一直拿一个数组当中间变量。

2.5.3 分支语句优化

1优化判断条件

if((a1 !=0)&&(a2 !=0)&&(a3 !=0)){...}//简化判断条件，可以提高分支预测的效率
temp =(a1 & a2 & a3);if(temp !=0){...}

2 用#ifdef代替if
因为#ifdef在编译时就知道结果，不需要在运行时判断，节省运行时间。

3 移除分支语句
用查表法代替分支判断，将分支跳转运算转为访问表中元素。

4 平衡分支判断
相当于结合二分法进行判断。在switch判断次数比较多时可以使用。

3 单核优化

3.1 指令级并行

指令之间的控制相关(就是if判断)会影响指令流水线的执行。现代CPU都是采取分支预测的方式处理分支判断。若预测正常则流水线顺利执行，若预测错误，则需要清空流水线并丢弃已经执行的结果，并重新执行正确的分支。所以分支预测准确率直接影响CPU的性能。目前Intel极大的优化了分支预测器的性能，而ARM和GPU都没有太关注分支预测，所以在ARM和GPU上尽量少用if。

3.1.1 循环不变量外提

当循环内有分支判断，并且判断条件还是常量时，就将分支判断提到循环外。

for(int i =0; i < N; i++){if(an >10){
        a[i]= c[i];}else{
        a[i]= d[i];}
    m[i]= n[i];}//外提后if(an >10){for(int i =0; i < N; i++){
        a[i]= c[i];
        a[i]= d[i];}}else{for(int i =0; i < N; i++){
        a[i]= c[i];
        a[i]= d[i];}}

3.1.2 控制转换

就是用顺序执行语句代替if条件选择语句。

//if(r < 0) {//   r = 0;//}
r = r &~(r>>31);//if(r > 255) {//   r = 255;//}
r =(r |((255-r)>>31))&0xFF;//if(g < 0) {//   g = 0;//}
g = g &~(g>>31);//if(g > 255) {//   g = 255;//}
g =(g |((255-g)>>31))&0xFF;//if(b < 0) {//   b = 0;//}
b = b &~(b>>31);//if(b > 255) {//   b = 255;//}
b =(b |((255-b)>>31))&0xFF;

3.2 数据级并行

就是手写SIMD向量化代码。

4 访存优化

4.1 寄存器优化

4.1.1 寄存器分配

寄存器分配优化，是指将程序中的有用变量尽可能的分配到寄存器。

1. 减少全局变量 全局变量会独占一个寄存器，导致寄存器数量减少。
2. 直接读取寄存器 由于数组是保存在内存中，标量保存在寄存器中，因此能用标量的地方都用标量，不用数组。 如果有对数组的反复访问，就先把数组的内容赋值给一个标量，后面使用该标量进行计算。
3. 寄存器分配溢出 要尽量避免寄存器溢出。

4.2 内存优化

4.2.1 减少内存读写

4.2.2 数据对齐

1. 数据对齐访问 对于2Byte的变量，应尽量使其起始地址为2的整数倍。 对于4Byte的变量，应尽量使其起始地址为4的整数倍。 对于8Byte的变量，应尽量使其起始地址为8的整数倍。
2. 结构体对齐 由于结构体占用内存越大，读取一次耗时越久。而结构体占用内存大小与其成员变量的顺序有关。因此在设计结构体时，尽量按照成员变量大小从大到小的顺序依次定义。