改掉不良习惯，优化程序性能

假期之前给自己下了很大的决心，要看一本1000页以上的技术类书籍，最终在图书馆选择了英文原版的《Computer Systems: A Programmer’s Perspective》，它的中文译名是《深入理解计算机系统》。假期结束后，虽说仅看完了一半，但阅读的几章内容已使我有了不小的提升；书中关于优化程序性能及存储器结构的两章尤为精彩，以下就相关内容谈谈我的理解。

以前曾经固执地以为，应用程序的性能很大程度上取决于内存大小、CPU处理能力等计算机的外在配置；不过读了书中的5、6两章之后，我的看法有了转变，原来应用程序的实现方式也会左右程序性能。我们在写代码的时候经常在不经意间犯一些会降低程序性能的毛病，看似是小问题，实际上这些不良习惯在日后都会留下隐患，对以后的开发造成坏的影响，因此及时改掉很有必要，以下为结合书中内容总结的几点，希望对看到此文的读者有所帮助。

 

第一，在循环结构内部减少使用函数调用。这一条是书中明确提出的，其实很值得我们思考，例如下面的代码片段：

int diff(char a, char b)
{
    if (a != b) return 1;
    else return 0;
}

int diffstr(char *str1, char* str2)
{
    int i = 0, count = 0;

    for (i = 0; i < strlen(str1); i++)
    {
        count += diff(str1[i], str2[i]);
    }

    return count;
}

很明显，代码的意图是要统计两个字符串对应位置字符不同的个数。相信很多人都以这种方式写过代码，乍一看好像也没什么。不过，如果两个字符串足够长的话，代码的低效就会暴露出来，这是因为for循环里面对函数diff的反复调用。我们都知道，函数调用涉及对参数及返回值地址的栈操作，这些本不必要的额外操作对应用程序的性能会造成很大影响，因此调用diff那一句不如直接写成count += (str1[i] != str2[i]);这样一目了然，而且省掉了函数调用的额外开销，经济实惠。很多人认为多用函数调用似乎很有范儿，写的程序更加“专业”，其实大错特错！高级语言中的函数本就是为了某一复杂功能的封装，现在一条语句就能搞定还要进行封装其实就显得多余了，而且反而带来了负担；尤其是在循环结构中如果要用到对同一函数的调用，我们应该注意能否进行像上面的优化。

事实上代码中还有一处函数调用有待优化，不过比较隐蔽，不像函数体中的调用那么明显。没错，那就是strlen函数。该函数在每次判断循环结束条件的时候要调用一次，这显然也是一种浪费，因为在整个过程中str1的长度根本不变！于是我们其实可以在之前就用局部变量把这个长度保存下来，以后每次比较的时候就用i和这个局部变量作比较，达到同样的目的，但省去了又一个函数调用。于是，经过优化的代码如下所示：

int diffstr1(char *str1, char* str2)
{
    int i = 0, count = 0, len = strlen(str1);

    for (i = 0; i < len; i++)
    {
        count += (str1[i] != str2[i]);
    }

    return count;
}

上面经过优化的代码将字符串长度预先保存在局部变量里是常用的技巧，省掉了(len-1)次对strlen函数的调用，提升了程序性能，值得我们借鉴。

 

下面说说第二条，让你的应用程序更多地使用寄存器，而不是内存。也许读者会有疑问，我们控制得了调不调用函数，难道生成的可执行程序使用寄存器还是内存我们也能控制吗？答案是：很大程度上可以。请看下面的程序：

int diffsquare(int a, int b)
{
    int x[2];

    x[0] = a + b;
    x[1] = a - b;

    return x[0] * x[1];
}

其实就是一个平方差函数，不过代码的实现方式很新奇。请注意，新奇不一定就是创新，也可能是标新立异，很遗憾这份代码就属于后者。代码的一大问题是：局部变量不多，但却是用数组实现的！我们知道，应用程序中函数的局部变量如果很少的话，一般都会将其存储在访问及读写都很快的寄存器中；不过如果是局部数组的话，在运行时是存储在内存中的，而内存的读写通常要比寄存器慢2~3个数量级。尽管有cache（缓存）这回事，但对内存的操作依然要比寄存器慢很多。所以，对这份代码的优化主要就是要消除内存引用：

int diffsquare1(int a, int b)
{
    int x, y;

    x = a + b;
    y = a - b;

    return x * y;
}

尽管改动不大，但编译出来的汇编语言代码却有着天壤之别，内存引用改为寄存器存取，速度和效率都有了提升。

 

最后要说的是，多维数组的不同层次的循环顺序有讲究。例如下面：

int i, j, a[100][100], sum = 0;

for (j = 0; j < 100; j++)
{
    for (i = 0; i < 100; i++)
    {
        sum += a[i][j];
    }
}

二维数组的第二维循环变量作为外层，这是比较少见的，而这一点是有原因的。之所以上面的程序实现方式不为大众所接受，是因为它的效率低下，而根本原因是代码具有较差的空间局部性。这一点要用缓存技术来解释，计算机结构设计师最初设计缓存的目的就是在内存与寄存器之间架起若干座桥梁，提升数据存取速度，而提升的方式主要是局部性。具体点说，就是缓存会把最近使用的数据及它周边的数据存储起来以便以后使用，这是因为缓存不管怎么说也要比内存的读写要快，而且最近使用的数据被再次使用的几率往往较大，另外它周边的数据被使用的几率也较其他数据要大。因此如果应用程序如果能够利用这一点，多去使用最近使用过的数据（体现为时间局部性）以及最近使用过的数据附近的数据（体现为空间局部性），那么性能会有较大提升。可以看出，上面给出的二维数组求和代码段的空间局部性就不好，这时因为它对数组a的访问次序为a[0][0]、a[1][0]、a[2][0]…，这样的顺寻导致相邻数据在内存中的间隔为100*4=400个字节，显然太远了。而如果代码改成通常的方式：

int i, j, a[100][100], sum = 0;

for (i = 0; i < 100; i++)
{
    for (j = 0; j < 100; j++)
    {
        sum += a[i][j];
    }
}

可以看出这一回对数组a的访问次序为a[0][0]、a[0][1]、a[0][2]…，都是按顺序在内存中存储的，这样空间局部性达到最佳，程序的性能自然很好。

 

上面3个例子列举了我们在编程的时候可能存在的不良习惯，尽管细微，但影响绝对不小，单单第一条中对strlen函数调用的优化在书中给出的例子就可使程序性能提升50%左右，可见这些“小毛病”会造成多么严重的“大后果”。书中给出了更为详细的优化程序性能的方法，有兴趣者可自行阅读，体会对程序一步步改进带来的快感。