内存优化最后一弹——优化函数运行

2021-12-05 13:16:01

快起来，这真的是最后一篇啦！

计算非零位的个数 / counting the number of bits set

例1：测试单个的最低位，计数，然后移位。

//example1
int countbit1(uint n)
{
    int bits = 0;
    while (n != 0) {
        if(n & 1) bits++;
            n >>= 1;
    }
      return bits;
}

例2：先除4，然后计算被4处的每个部分。循环拆解经常会给程序优化带来新的机会。

//example - 2
int countbit2(uint n)
{
    int bits = 0;
    while (n != 0) {
        if (n & 1) bits++;
        if (n & 2) bits++;
        if (n & 4) bits++;
        if (n & 8) bits++;
            n >>= 4;
    }
    return bits;
}

尽早地退出循环 / Early loop breaking

通常没有必要遍历整个循环。举例来说，在数组中搜索一个特定的值，我们可以在找到我们需要值之后立刻退出循环。下面的例子在10000个数字中搜索-99。

found = FALSE; 
for(i=0;i<10000;i++) 
{ 
    if(list[i] == -99) { 
         found = TRUE; 
    } 
} 
if(found) printf("Yes, there is a -99. Hooray!\n");

这样做是可行的，但是不管这个被搜索到的项目出现在什么位置，都会搜索整个数组。跟好的方法是，再找到我们需要的数字以后，立刻退出循环。

found = FALSE; 
for(i = 0; i < 10000; i++) 
{ 
    if( list[i] == -99 ) { 
        found = TRUE; 
        break; 
    } 
} 
if( found ) printf("Yes, there is a -99. Hooray!\n");

如果数字出现在位置23上，循环就会终止，忽略剩下的9977个。

函数设计 / Function Design

保持函数短小精悍，是对的。这可以使编译器能够跟高效地进行其他的优化，比如寄存器分配。

调用函数的开销 / Function call overhead

对处理器而言，调用函数的开销是很小的，通常，在被调用函数所进行的工作中，所占的比例也很小。能够使用寄存器传递的函数参数个数是有限制的。这些参数可以是整型兼容的（char,short,int以及float都占用一个字），或者是4个字以内的结构体（包括2个字的double和long long）。

假如参数的限制是4，那么第5个及后面的字都会被保存到堆栈中。这会增加在调用函数是存储这些参数的，以及在被调用函数中恢复这些参数的代价。

int f1(int a, int b, int c, int d) { 
    return a + b + c + d;
}
int g1(void) {
    return f1(1, 2, 3, 4);
}
int f2(int a, int b, int c, int d, int e, int f) {
    return a + b + c + d + e + f;
}
ing g2(void) {
    return f2(1, 2, 3, 4, 5, 6);
}

g2函数中，第5、6个参数被保存在堆栈中，在f2中被恢复，每个参数带来2次内存访问。

最小化参数传递的开销 / Minimizing parameter passing overhead

为了将传递参数给函数的代价降至最低，我们可以：尽可能确保函数的形参不多于四个，甚至更少，这样就不会使用堆栈来传递参数。

如果一个函数形参多于四个，那就确保在这个函数能够做大量的工作，这样就可以抵消由传递堆栈参数所付出的代价。

用指向结构体的指针作形参，而不是结构体本身。把相关的参数放到一个结构里里面，然后把它的指针传给函数，可以减少参数的个数，增加程序的可读性。将long类型的参数的个数降到最小，因为它使用两个参数的空间。对于double也同样适用。

避免出现参数的一部分使用寄存器传输，另一部分使用堆栈传输的情况。这种情况下参数将被全部压到堆栈里。避免出现函数的参数个数不定的情况。这种情况下，所有参数都使用堆栈。

叶子函数 / Leaf functions

如果一个函数不再调用其他函数，这样的函数被称为叶子函数。在许多应用程序中，大约一半的函数调用是对叶子函数的调用。叶子函数在所有平台上都可以得到非常高效的编译，因为他们不需要进行参数的保存和恢复。在入口压栈和在出口退栈的代价，跟一个足够复杂的需要4个或者5个参数的叶子函数所完成的工作相比，是非常小的。

如果可能的话，我们就要尽量安排经常被调用的函数成为叶子函数。函数被调用的次数可以通过模型工具（profiling facility）来确定。这里有几种方法可以确保函数被编译成叶子函数：

不调用其他函数：包括那些被转换成调用C语言库函数的运算，比如除法、浮点运算。

使用关键字__inline修饰小的函数。

内联函数 / Inline functions

对于所有调试选项，内嵌函数是被禁止的。使用inline关键字修饰函数后，跟普通的函数调用不同，代码中对该函数的调用将会被函数体本身代替。这会使代码更快，另一方面它会影响代码的长度，尤其是内嵌函数比较大而且经常被调用的情况下。

__inline int square(int x) {
    return x * x;
}
#include <MATH.H>
double length(int x, int y){
    return sqrt(square(x) + square(y));
}

使用内嵌函数有几个优点：

没有调用函数的开销。

因为函数被直接代替，没有任何额外的开销，比如存储和恢复寄存器。

更低的参数赋值开销。

参数传递的开销通常会更低，因为它不需要复制变量。如果其中一些参数是常量，编译器还可以作进一步的优化。

内嵌函数的缺点是如果函数在许多地方被调用，将会增加代码的长度。长度差别的大小非常依赖于内嵌函数的大小和调用的次数。

仅将少数关键函数设置成内嵌函数是明智的。如果设置得当，内嵌函数可以减少代码的长度，一次函数调用需要一定数量的指令，但是，使用优化过的内嵌函数可以编译成更少的指令。

使用查找表 / Using Lookup Tables

有些函数可以近似成查找表，这样可以显著的提高效率。查找表的精度一般比计算公式的精度低，不过在大多数程序中，这种精度就足够了。

许多信号处理软件（比如MODEM调制软件）会大量的使用sin和cos函数，这些函数会带来大量的数学运算。对于实时系统来说，精度不是很重要，sin/cos查找表显得更加实用。使用查找表的时候，尽量将相近的运算合并成一个查找表，这样要比使用多个查找表要更快和使用更少的空间。

浮点运算 / Floating-Point Arithmetic

尽管浮点运算对于任何处理器来讲都是很费时间的，有的时候，我们还是不得不用到浮点运算，比方说实现信号处理。尽管如此，编写浮点运算代码的时候，我们要牢记：

浮点除法是慢的

除法要比加法或者乘法慢两倍，我们可以把被一个常数除的运算写成被这个数的倒数乘（比如，x=x/3.0写成x=x*(1.0/3.0)）。倒数的计算在编译阶段就被完成。

使用float代替double

Float型变量消耗更少的内存和寄存器，而且因为它的低精度所以具有更高的效率。在精度足够的情况下，就要使用float。

不要使用先验函数/transcendental functions

先验函数（比如sin，cos，log）是通过使用一系列的乘法和加法实现的，所以这些运算会比普通的乘法慢10倍以上。

简化浮点表达式

编译器在整型跟浮点型混合的运算中不会进行太多的优化。比如3 * (x / 3) 不会被优化成x，因为浮点运算通常会导致精度的降低，甚至表达式的顺序都是重要的： (a + b) + c 不等于 a + (b + c)。因此，进行手动的优化是有好处的。

不过，在特定的场合下，浮点运算的效率达不到指定的水平，这种情况下，最好的办法可能是放弃浮点运算，转而使用定点运算。当变量的变化范围足够的小，定点运算要比浮点运算精度更高、速度更快。

其他的技巧 / Misc tips

一般情况下，可以用存储空间换取时间。你可以缓存那些经常用到的数据，而不是每次都重新计算、或者重新装载。比如sin/cos表，或者伪随机数的表（如果你不是真的需要随机数，你可以在开始的时候计算1000个，在随后的代码中重复利用就是了）尽量少的使用全局变量。

将一个文件内部的变量声明成静态的，除非它有必要成为全局的。

不要使用递归。递归可以使代码非常整齐和美观，但会产生大量的函数调用和开销。

访问单维数组要比多维数组快使用#defined宏代替经常用到的小函数。

不要用递归，不要用递归，不要用递归！重要的话说三遍，小伙伴们，还请持续关注更新，更多干货和资料请直接联系我，也可以加群710520381，邀请码：柳猫，欢迎大家共同讨论

码农公寓