串行代码性能优化

标签：int 代码 ++ 编译器 循环 串行 优化 分支

串行代码的优化层次

层次	作用
系统级别	要求找出程序的性能控制因素以做针对性的优化
应用级别	在程序编写前就要确定应用级别的配置
算法级别	选择不同的数据组织方式，或者选择不同的算法
函数级别	函数级别的优化通常用来减少函数调用的开销或者减少函数调用带来的编译器性能优化阻碍
循环级别	通常循环级别的优化能够发掘循环的并行性，减少循环内多余的运算
语句级别	不同的语句产生的指令数量并不相同，应尽量使用产生指令条数少的语句
指令级别	应优先使用吞吐量大、延迟小的指令

---

系统级别

优化程序的性能，首先需要在系统级别找出程序的性能控制因素，然后再做有针对性的优化。

如果处理器的利用率一直是100%，那么限制因素就是处理器，需要减少计算。而如果处理器使用率不高但很平稳，此时就需要测试程序的内存带宽，比较程序的带宽和内存能够提供的带宽，以估计程序还有多少优化余地，此时优化应注意减少存储器访问。

1. 网络速度、利用率及负载均衡
2. 处理器利用率
   处理器的利用率在两种情况下可能存在性能问题：
   • 处理器空闲较多：如果处理器大部分时间空闲，很明显程序不是最优的，因为程序无法发挥硬件的计算能力。
   • 处理器利用率过高：如果核心的使用率为100%，或者单核程序中某个核的使用率为100%，这就意味着处理器成为了性能限制因素，通常也称为“计算限制”。
3. 存储器带宽利用率
   • 提高存储器访问的局部性以增加缓存利用。
   • 将数据保存在临时变量中以减少存储器读写。
   • 减少读写依赖。读写依赖会导致流水线指令等待，减弱了流水线效率。
   • 同时读写多个数据以提高系统的指令级并行和向量化能力。
4. 去阻塞处理器运算的因素
   可以通过观察处理器的使用率来估计处理器有多少比例的运算时间是在等待IO操作完成，如果两者差别非常大就没有优化的必要了。如果IO操作和处理器计算时间比较接近，那么优化最多可使性能提升2倍。通常的解决方法是使用非阻塞的函数调用，如Linux或glibc的异步IO操作，或使用独立的线程来处理IO操作以使得IO和计算同时进行。

---

应用级别

应用级别的优化通常应当最先采用，一方面因为它可能关系到程序的各个部分，另一方面也因为软件开发越到后面，越不容易采用应用级别的优化。

1. 编译器选项
   如GCC就有O0（编译器不对程序做优化）、O1、O2、O3（编译器会为了性能做极致的优化）等优化选项。还有很多其他选项，如指定处理器架构、是否使用循环展开、是否使用SSE指令等，绝大多数程序使用O2优化选项

-O3 -ffast-math -funroll-all-loops -maaxv -mtune=native

• fast-math: 对超越函数使用更快但精度低一些的版本
• funroll-all-loops表示使用循环展开
• avx表示使用avx指令集向量化
• tune=native表示为当前编译的处理器做优化

2. 调用高性能库
   直接调用高性能库，如优化的BLAS（BasicLinear Algebra Subprograms，基本线性代数子程序）和快速傅立叶变换自由软件库FFTW（Fastest Fourier Transform）等，可以减少大量工作。

3. 去掉全局变量
   全局变量尤其是多个文件共享的全局数据结构会阻碍编译器的优化，因为编译器需要在多个文件间分析其使用状态。对于并行程序来说，全局变量（除非是不可变的）应当是绝对禁止的。

4. 受限的指针
   C99为了减少存储器别名对性能的影响而引入了“受限的指针”这一特性，受限的指令表示该指针不会和其他指针存在存储器别名。存储器别名是指多个指针指向同一个内存地址或指向的内存地址有重叠，它会阻碍编译器对程序进行指令重排、表达式移除等优化。

int f(int *a, int *b) {
    *a += *b;
    *a += *b;
}

下面分别介绍上面代码可能存在的有存储器别名和没有存储器别名两种情况：
第1种：如果指针a、b指向不同的内存地址，也就是说a、b之间不存在存储器别名，那么函数f可简化为：

int f(int *a, int *b){
    int temp = *b;
    *a += 2 * temp;
}

第2种：如果指针a、b指向同一个内存地址，即a、b之间存在存储器别名，那么函数f将变成：

int f(int *a, int *b){
    int temp = *b;
    temp += temp;
    temp += temp;
    *a = temp;
}

进一步简化就变成了如下所示的代码：

int f(int *a, int *b) {
    int temp = *b;
    *a = 4 * temp;
}

因此在a、b之间存在存储器别名的情况下，第1种情况的结果是错误的。

C99标准对受限的指针使用的标识符是restrict，但是它没有被C++标准接受，不过G++编译器支持__restrict__限定符，其含义和restrict一样。

5. 条件编译
   通常使用条件编译以满足可移植性。相比运行时检测，条件编译生成的代码更短，因此效率更高。C语言提供了#if #else #elif #endif #ifdef等指令来支持条件编译。

由于宏条件在编译时就已经确定，故编译器可直接忽略不成立的分支；而分支判别的条件是在运行时求值的，故编译后的代码要长。不过如果要支持多个条件编译分支版本，条件编译的方式只能使用多个程序，而运行时分支版本却只需要一个

switch(mode){
    case ON_ARM_CPU:
        arm_f(); break;
    case ON_X86_CPU:
        x86_f(); break;
    default:
        /*…*/
}

#ifdef ON_ARM_CPU
    arm_f();
#elif ON_X86_CPU
    x86_f();
#endif

---

算法级别

1. 索引顺序
   访问多维数据时的局部性直接与各维数据在内存中存放的先后顺序相关，如C语言中数组是以行为主序存放的，在计算时尽量按行访问数据。而对于Fortran代码，则应当按列访问数据。

2. 缓存分块
   以矩阵乘法为例，简单的基于缓存分块的代码如代码清单4-4所示：

for(i=0; i<N; i+=NB)
    for(j=0; j<M; j+=NB)
            for(k=0; k<K; k+=NB)
                    for(i0=i; i0<(i + NB); i0++)
                            for(j0=j; j0<(j + NB); j0++)
                                    for(k0=k; k0<(k + NB); k0++)｛
                                        C[i0][j0] += A[i0][k0] + B[k0][j0];
                                    ｝

3. 软件预取
   预取通常有硬件和软件两种方式，软件预取指由编译器或软件开发人员将预取指令插入到代码的适当地方。指令集通常会提供预取指令供编译器优化时使用。编译器分析代码，并把预取指令适当地插入代码中。这类指令直接把目标预取数据载入缓存。

4. 查表法
   查表法是这样一类方法：这类方法提前把数据组织成表格（一维、二维或多维），在真正需要使用数据时，只需要访问表格即可。

在一些科学计算中，需要多次计算一些复杂函数的结果，此时也可利用查表法减少计算。比如在某个应用中需要计算十万次exp（x），其中x范围为[0，1]，那么可查区间[0，1]不均匀分成1000份，靠近1时密，靠近0时稀，然后保存这1000个exp（x）的值来做查表。如果不采用查表法，那么需要计算十万次exp，使用查表法后，计算exp的次数减少为1000，不过在此例中使用查表法会导致结果精度的降低。

void buildTable(int num, float *table){
    table[0] = 1.0f;
    for(int i = 0; i < num; i++){
        table[i] = i*1.0f/num;
    }
}
float computExp(float x, int num, const float *table){
    int index = (int)(x*num);
    return table[index];
}

在需要大量计算exp值的程序中，代码清单4-5所示的查表法能够极大地减少计算数量。它将不固定的exp计算转化成了固定数量（num）的exp计算和不固定数量的访存。

在实际项目中，通常将查表法和线性插值结合使用以减少计算精度的降低：对于每个要求值的元素，其返回值为多个结果（一维为2个：称为线性插值；二维为4个：称为双线性插值；三维为8个：称为三线性插值）的线性插值。以一维查表为例，索引1.5的返回值等于索引1的返回值和索引2的返回值的和的一半；索引1.3的返回值等于索引1的返回值和0.7的积与索引2的返回值和0.3的积的和。

函数级别

函数调用时，需要将调用参数通过寄存器或栈传递，且将函数返回地址入栈。函数级别的优化通常用于减少这部分的消耗及其导致的优化障碍。建议函数只访问自己的局部变量和通过参数传入的值，这样编译器能够只依据函数内的信息就可以分析变量使用情况。

1. 函数调用参数
   在64位X86处理器上，函数的参数优先通过寄存器传递，超量之后才会通过栈传递。另外，如果一个函数的参数少，那么这个函数就更容易被记住和使用。如果函数的参数是大结构体或类，应当通过传指针或引用以减少调用时复制和返回时销毁的开销，因为函数可能只会使用大的结构体中的一部分域。

函数getYByPtr就比getYByValue要好

struct BigStruct{
    int x[30];
    float y;
    float z;
}
float getYByValue(BigStruct bs){
    return bs.y;
}
float getYByPtr(const BigStruct *bs){
    return bs->y;
}

在调用getYByValue函数前，处理器会将结构体bs入栈，这意味着要复制128字节；而调用getYByPtr函数前，处理器只需要入栈一个指针。实际上，解决getYByValue函数调用时的入栈开销的一个有效办法是：内联函数。

因此要尽量不使用全局变量，就算要使用全局变量，也要通过参数传递

2. 内联小函数
   内联（inline）小函数能够消除函数调用的开销，且可能会提供更多的指令级并行、表达式移除等优化机会，进而增加指令流水线的性能。另外函数调用也可能阻止编译器优化，如果循环内有函数调用，则编译器很难进行向量化。对于这些情况，内联可以解决问题。

如果内联后的函数比较长，就可能会增加寄存器的压力。如果函数内有分支，内联后会对指令流水线产生不利的影响，因此通常对少于10行且其中代码没有分支的函数内联。

循环级别(important)

循环如果执行次数多，更易成为性能瓶颈。通常循环级别的优化以发掘循环的并行性、减少寄存器和缓存的使用为主，以更好地利用硬件的资源。

循环展开

展开循环不但减少了每次的判断数量和循环变量改变的计算次数，更能够增加处理器流水线执行的性能。
通常展开小循环且内部没有判断的会获益，展开大循环则可能会因为导致寄存器溢出而导致性能下降，而展开内部有判断的循环会增加分支预测的开销也可能会导致性能下降。

下面是用来给15000个数求和的代码

float sum = 0.0f;
for(int i = 0; i < num; i++){
    sum += a[i];
}

循环展开4次后

float sum = 0.0f, sum1 = 0.0f, sum2 = 0.0f, sum3 = 0.0f;
for(int i = 0; i < num; i += 4){
    sum1 +=  a[i];
    sum2 +=  a[i+1];
    sum3 +=  a[i+2];
    sum +=  a[i+3];
}
sum += sum1+sum2+sum3;

对于二层循环来说，通常建议优先展开外层循环，但是这不是一个普适的准则。循环展开时需要注意处理末尾的数据，如代码中的num大小不是4的倍数，则最后num%4次循环需要单独处理。许多编译器可以自动展开循环，也有些编译器提供了控制循环展开的伪指令，开发人员可优先选择它们，在必要时再采取手动展开。

循环累积

循环累积主要和循环展开同时使用，在减少寄存器的使用量的同时保证平行度。

float sum = 0.0f, sum1 = 0.0f, sum2=0.0f;
for(int i = 0; i < num; i +=6){
    sum1 +=  a[i]+a[i+1]
    sum +=  a[i+2]+a[i+3];
    sum2 += a[i+4]+a[i+5];
}
sum += sum1+sum2;

如果直接使用循环展开6次，则总共需要至少6个临时变量，而现在只要3个，潜在地减少了寄存器的使用。在寄存器总量一定的前提下，减少寄存器的使用，就可以将循环展开更多次。

循环合并

如果多个小循环使用的寄存器数量没有超过处理器的限制，那么合并这几个小循环可能会带来性能好处（增加了乱序执行能力）。循环合并不但可以减少判断次数，还能够增加指令级并行能力（能够合并的两个循环内代码通常没有依赖）。

合并前

for(int i = 0; i < len; i++){
    x1 += a[i];
}
for(int i = 0; i < len; i++){
    x2 *= b[i];
}

合并后

for(int i = 0; i < len; i++){
    x1 += a[i];
    x2 *= b[i];
}

循环合并的另一个常用场景是并行化，由于能够增加每个控制流的计算量，因此将多个循环合并再并行化能够更好地隐藏线程建立开销，获得更好的效果。

循环拆分

如果大循环（循环体内代码比较多、执行时间长）存在寄存器溢出的情况，那么将大循环拆分为几个小循环，就能够提高寄存器的使用，而且能够为循环展开等技术的使用提供条件。循环拆分和循环合并是相对的技术，只是它们应用的对象类型不同。何时进行循环拆分必须就事论事，不能一概而论，通常与处理器的缓存容量、寄存器数量等相关。

for(int i = 0; i < len; i++){
    doA();
    doB();
}

for(int i = 0; i < len; i++){
    doA();
}
for(int i = 0; i < len; i++){
    doB();
}

从表面上看，循环拆分增加了循环条件的执行次数，如果循环条件的计算量相比循环内代码计算量小的话（即大循环），那么循环拆分所导致的循环条件执行代价即可忽略。

语句级别

实现同一功能的不同语句系列编译后的指令数量不同、指令类型也不同，必然导致性能也不相同。从本质上来说，语句级别的优化和指令级别的优化比较相似，因为两者的粒度都非常小，而且没有本质的区别（从指令级别分析语句的结果就是指令级别的优化）。

减少内存读写

应当优先使用数值（重用数据）而不是解引用。如果需要多次访问函数参数指针指向的值，应当先将其保存到寄存器中
大多数情况下，编译器能够很好地解决这个问题，但是在具有存储器别名情况或读写依赖情况下，就需要开发人员手动处理。

优化前的前缀和

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

优化后的前缀和

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

在某些情况下，可以重复计算某些值而不是计算后保存到内存中再读取，此时需要权衡计算的代价和读写内存的延迟。

选用尽量小的数据类型

由于能够在缓存中放更多的数据，小尺寸类型数据的访问速度比大尺寸类型数据要快（指以数据的个数统计，而非传输带宽）。在使用SSE/AVX指令时，一个SSE/AVX寄存器能够存放更多的小尺寸类型数据，这也能够提升某些程序的性能。

代码是将RGB图像转换成灰度图像，但是代码使用了int来保存中间结果

for( int i = 0; i < n; i++){
    int r = r_buf[i]; // load red
    int g = g_buf[i]; // load green
    int b = b_buf[i]; // load blue
    int r_ratio = 77;
    int g_ratio = 151;
    int b_ratio = 28;
    int y = r * r_ratio;
    y += g*g_ratio;
    y += (b*b_ratio);
    dest[i] = (y>>8);
}

而由于图像像素每通道大小为1字节，权重也可以使用1字节来表示，故使用short来保存就已经足够，优化后的代码

for( int i = 0; i < n; i++){
    short int r = r_buf[i]; // load red
    short int g = g_buf[i]; // load green
    short int b = b_buf[i]; // load blue
    short int r_ratio = 77;
    short int g_ratio = 151;
    short int b_ratio = 28;
    short int y = r * r_ratio;
    y += g*g_ratio;
    y += (b*b_ratio);
    dest[i] = (y>>8);
}

以ARM NEON 128位向量指令集为例，其寄存器为128位，若使用int型，则每个向量只能保存4个数据，但是使用short的话，每个向量可保存8个数据，这意味着使用short时潜在的性能是使用int时的两倍。

结构体对齐

声明结构体时，尽量大数据类型在前，小数据类型在后，一方面这样会节省一些空间，另一方面可以更好地满足处理器的对齐要求。

• 结构体占用总字节数尽量是2的幂；
• 每个域的开始地址是它的大小的整数倍；
• 编译器提供了按字节对齐的编译原语，如GCC的__attribute__((aligned(x)))和__attribute__((packed()))。

如下面的两个结构体，其元素相同，但是大小不同。

struct s{
   char x;
   double y;
   int z;
   short w;
}

struct t{
   double y;
   int z;
   short w;
   char x;
}

处理器和编译器对齐的要求导致结构体s占用24字节（浪费了9字节），而结构体t占用16字节（浪费了1字节）。无论是在32位还是64位系统上，无论是Windows还是Linux，它们占用的字节数不会变。

本质上来说，结构体s和t可用来保存相同的数据，但是由于域声明顺序导致结构体s占用的空间是结构体t的1.5倍，这意味着访问相同数量的结构体s和t，s对存储器的带宽要求更多。

有些结构体声明使得它们在不同的硬件上或不同的操作系统上大小并不一致，基于这一点，软件开发人员要记住永远都使用sizeof运算符，而不是确切的字节数。

数据占用的字节越小，在同样大小的缓存线中存放的数据数量就越多，缓存线的利用就越好。但是轻易不要使用编译器的packed选项将结构体的存储空间压缩到最小，因为这可能会导致不对齐的读写存储器。

表达式移除

前者每次循环都需要比较索引以检查访存是否越界，而后者只比较一次即可

void readVI(VI *vi, int id){
    int len = vi->size();
    if(id < len) return vi[id];
    else return ERROR;
}

for(int i = 0; i < len; i++)｛
    readVI(a, i);
}

if(len >= a->size) return ERROR;
for(int i = 0; i < len; i++)｛
    a[i];
}

分支优化

1. 尽量避免把判断放到循环里面:
   由于分支预测失误会对流水线产生非常不利的影响，因此要避免循环里面有判断语句，此时尽量改成判断里面有循环
   （这要求循环和判断之间没有依赖）。

for(int i = 0; i < len; i++){
   if(x > y) dosomething();
}

在不考虑编译器优化的前提下，下方只需要计算一次分支，而上方要计算len次

if(x > y){
   for(int i = 0; i < len; i++){
       dosomething();
   }
}

2. 拆分循环
   某些循环中分支非常多，这可能会导致处理器分支预测失败率增加，把它拆分成几个小循环有可能改善处理器的分支预测正确率；在另外一些循环代码中，循环内分支条件依赖循环变量，这种情况可通过拆分循环去掉分支，如常见的奇偶分支模式：

for(int i = 0; i < len; ++i){
    if (i&1 == 0) do0();
    else do1();
}

此时可以将循环展开两次，一次处理奇数循环，一次处理偶数循环，自然就不需要分支判断。

for(int i = 0; i < len-1; i += 2){
    do0();
    do1();
}
if(0 != len%2) do0();

如果do0和do1使用的临时变量比较多的话，下方的性能可能更好（因为每个循环使用的寄存器可能更少）。

for(int i = 0; i < len; i += 2){
    do0();
}
for(int i = 1; i < len; i += 2){
    do1();
}
if(0 != len%2) do0();

使用循环拆分去掉分支时，由于去掉了分支路径执行的先后顺序，故要求分支路径之间没有相关性；而使用循环展开去掉分支则无此要求。

3. 合并多个条件
   一些分支条件是包含多个比较操作的复杂表达式，编译器通常将它们编译成嵌套的多个if语句代码，如果能够将其修改成一个运算，那么只需要一个分支，就可以提高分支预测成功率。比如：

if((a0==0) && (a1==0) && (a2==0)){
......
}

某些编译器将生成3个条件跳转指令，而使分支可预测性降低，可以改写为：

if(a > 0){
    x = a;
}else{
    x = b;
}

从而同时改进代码质量和分支预测率。合并分支条件要求在分支执行前计算出分支的结果，在某些分支条件计算量非常大的情况下（如函数调用），并不应当使用这一技术。

4. 使用条件状态值生成掩码来移除条件分支

if(a > 0){
    x = a;
}else{
    x = b;
}

x = a > 0;
a = a*x + b*(1-x);

由于增加了计算量，在分支预测失败概率很小或编译器能够将其优化为条件复制指令的情况下，可能会导致程序性能更差。因此此优化应当只在分支预测失败率比较高的情况下使用。

5. 使用条件复制指令以移除分支
   在64位的X86 CPU上，可以使用条件复制指令（cmov）来移除分支。编译器会将C语言中简单的三目运算符编译成条件复制指令。移除分支条件中的第一段代码也可优化为：

x = (a>0 ? a : b);

由于64位X86处理器都支持条件复制指令，因此推荐使用。

6. 查表法移除分支
   查表法是指提前计算一些结果，将结果放到一张具有索引的表中（如C++stl标准库中的map），在实际使用时，只需要依据索引从表中取得计算好的结果即可。如果能够将各分支路径的计算结果放到一张表中，并将分支条件转化为表中值对应的索引，那么就可以将分支跳转转化为访问表中元素，这是查表法移除分支的主要思想。实际上编译器在优化一些分支模式代码时也使用了类似的想法。

if(score >= 90)  //score属于[0...100]
    return 'A';
else if (score >= 80)
    return 'B';
else if (score >= 70)
    return 'C';
else
    return 'D';

char s[] = {'D', 'D', 'D', 'D', 'D', 'D', 'D', 'C', 'B', 'A'};
return s[score/10];

使用查表法去除分支有两点要求：①分支路径很容易转化成索引；②分支结果能够提前计算出来。

7. 分支顺序
   C中判断式求值是短路的，也就是说如果现在的信息已经能够决定整体的结果，后面的就不用算了。如if（a&&b），如果a为假，那么if语句就一定不能执行，故b不用再求值。例如，a、b中a是计算量相当大的，就应当将它放在后面，即（b&&a），如果计算量差不多，就把a、b中为假概率大的放在前面。对||运算可以类推。

优化交换性能

在实际使用排序类算法代码中，经常发现如下交换模式代码：

unsigned char tmp = a[ji];
a[ji] = a[jj];
a[jj] = tmp;

优化：

unsigned char aji = a[ji];
unsigned char ajj = a[jj];
a[ji] = ajj;
a[jj] = aji

前一段代码只需要使用一个临时变量，而后一段代码需要使用2个，但是后一段代码两次读之间和两次写之间都没有依赖关系，因此并行性要高。

指令级别

不同的指令具有不同的吞吐量，在实现相同功能的前提下，使用高吞吐量的指令能够明显提升程序的性能。例如，计算某个数的平方采用自己写或pow2函数而不是pow，在可能的情况下使用移位运算计算乘除法。

1. 减少数据依赖
   数据依赖会减弱处理器的乱序访问性能，另外读写依赖会极大地减弱内存性能。
   寄存器依赖

float tmp = 0.0f;
for(int i = 0; i < len; i++){
    tmp += a[i];
    a[i] = tmp;
}

数据依赖

for(int i = 1; i < len; i++){
    a[i] += a[i-1];
}

减少数据依赖能够提升代码的指令级和向量级并行能力。

2. 注意处理器的多发射能力
   在很多处理器上，单指令发射能力不能保证所有的执行单元都可同时运行，因此引入了双发射和多发射能力。但是实际上一些指令系列即使不存在依赖也不能多发射，因此应尽量将能够同时发射的指令安排在一起，不过这可能要求使用内置函数或汇编语言编写代码。

3. 优化乘除法和模余
   一般整数的位运算最多只要一个周期，而乘法要三个周期，除法十几个，模余需要几十甚至上百个，而通常移位运算只要一个周期。
   某些情况下，可以将除法转化为乘法，或者保存某些除法的中间结果，必要时甚至可以使用某些近似算法。如下面的代码中的除法可转化为乘法：

for(int i = 0; i < numRows; i++){
    for(int j = 0; j < numCols; j++){
        int index = i*numCols + j;
        r[index] = a[index]/b[j];
    }
}

将除法转换成乘法后代码如下所示：

for(int j = 0; j < numCols; j++){
    rb[j] = 1.0f/b[j];
}
for(int i = 0; i < numRows; i++){
    for(int j = 0; j < numCols; j++){
        int index = i*numCols + j;
        r[index] = a[index]*rb[j];
    }
}

为了将多次除法转成一次除法加多次乘法，笔者先使用一个临时数组rb保存中间结果。整数乘以一个整数可以转变成左移操作，如果乘数是常量，编译器会自动执行这种转换。整数除法和模余是非常耗时的，要少使用，如果是除以或模2的幂，则可转变为右移或位与运算。

4. 选择更具体的库函数或算法如2的整数次方可以采用移位运算实现，而且很多语言的数学库内有特殊操作的快速实现。如1加某个极小数的对数有log1p，如求2的n次方可以用函数pow2（n）而不是pow（2，n）。

5. 其他如声明float时加f后缀，使用const、static，少用虚函数等。尽量给编译器更具体更多的信息，以便编译器能够做出更好的优化决定。

标签：int,代码,++,编译器,循环,串行,优化,分支
From： https://www.cnblogs.com/moguw/p/18200785