Question

0x07-C语言效率(上)

大概所有学习C语言的初学者，都被前辈说过，C语言是世界上接近最速的编程语言，当然这并不是吹牛，也并不是贬低其他语言，诚然非C语言能写出高速度的代码，但是C语言更容易写出高速的程序(高速不代表高效)，然而再好的工具，在外行人手中也只能是黯淡没落。

对于现代编译器，现代CPU而言，我们要尽量迎合CPU的设计(比如架构和处理指令的方式等)，虽然编译器是为程序员服务，并且在尽它最大的能力来优化程序员写出的代码，但是毕竟它还没有脱离电子的范畴，如果我们的代码不能让编译器理解，编译器无法帮我们优化代码，那么我们就无法写出一个高速的程序。

对于此，我们可以暂且忽略CPU的设计，因为我们在层面上只能考虑如何迎合编译器的优化规则，而CPU则是语言以及编译器的事情了。

提高程序的速度，就C语言而言可以有这几种方法:

• 首先还是要设计合理的大纲，正所谓一个程序最大的性能提升就是它第一次运行的时候
• 要避免连续的函数调用。
• 消除不必要的存储器使用(并非推荐使用register)
• 使用循环展开技巧，一般编译器的优化选项能自动帮你修改代码成循环展开
• 对于一个操作的核心耗时部分，通过重新组合技术来提高速度
• 多采用几种风格的写法，而不是直观的认为，因为计算机的想法和你是不一样的

• 注：随着编译器的版本更新，即使不开启优化选项，自带的编译器优化依旧能够为我们编写的代码提供一部分优化，这便是不使用老版本编译器的原因，虽然作为一个程序员不应该太依赖于编译器，但是我认为，时代在进步，信息量正在无限的膨胀，但是人类的大脑以及精力在一个大时代内是有限的，换句话说对于普通人而言我们的记忆是有限的，我们不应该把精力放在前人已经做完的事情上，而是要站在巨人的肩膀上向更远处眺望，如此我们应该充分利用工具来帮助我们实现一些既有的功能，而程序员应该更 专注于发现新的思路，以及想法，在图灵测试尚未有人打破之前，程序员依赖编译器并不是一件错误的事情。

  对于当下的编译器，以GCC(GCC不仅仅是一个编译器，但这里将它当成编译器的代名词)为例，-O2是一个为大众所接受的优化等级，对于其他编译器，一般程序员可以选择使用由Google和Apple联合开发的编译器clang也是一个很好的选择， 在-O2的优化等级下，GCC一般情况下能够自动执行循环展开优化，

开始

1. .

    /*struct.h*/   
    #include <stdio.h>
    typedef struct me{
            int        value;
            struct me* next;
    }data_t;
   
    typedef struct{
            int index;
            data_t* storage;
    }block;    
   

   为了测试方便我们首先定义了两个结构体，分别是:

   block代表一个块，每个块都有一个序号(int)，一个数据域data_t
data_t代表一个数据域，原型是一个链表，每个data_t对象中包含一个数据和一个指针。

    /*main.c*/
    #include "struct.h"
    #define ARR_SIZE 10
    static inline int get_len(const data_t* data)
    {
        int len = 0;
   
        if(!data)
            fprintf(stderr,"The data in %p is NULL\n",data);
        else
            while(!data->next)
            {
                ++len;
                data = data->next;
            }
        return len;
    }
   
    static inline void mix_cal(const block* process, int result[])
    {
        for(int i = 0;i < get_len(process->storage);++i)
        {
            *result += (process->storage)[i];
        }
    }
   

   此时我们得到了两个测试函数，get_len和mix_cal分别用来得到data_t长度，以及计算数据域的总和。

    /*main.c*/    
    int main(void)
    {
        block* block_in_all[ARR_SIZE]  = { NULL };
        int    result_in_all[ARR_SIZE] = { 0 };
        /*
         * 假设生成了许多的`block`类型对象
         * 将许多的`block`放置在一个数组中，每个元素类型为`block*`
         * 每个block对象中都包含非空的data_t类型的数据域
         */
        for(int i = 0;i < ARR_SIZE;++i)
        {
            mix_cal(block_in_all[i], result_in_all+i);
        }
        for(int i = 0;i < ARR_SIZE;++i)
        {
            printf("The %dth block have the total %d data\n",
                        block_in_all[i]->index, result_in_all[i]);
        }
   
        return 0;
    }
   

   耐心读完上述的代码，它是用来求和的，求一个域中的所有元素的和。仔细分析一下，很容易就能看见一些缺点，最大的莫过于在mix_cal函数中对于get_len函数的调用，在此处看来十分明显，但是我们在编写程序的时候是否能够注意到这个问题呢？
   对于一些不必要的函数调用我们要做的便是将他们提取出来，使用临时变量是一个很好的办法，因为在编译器的帮助下临时变量在允许的情况下能够充分的利用CPU的寄存器。之所以是允许的情况下，是因为寄存器的数量并不多，而编译器在寄存器的使用上需要考虑许多的复杂因素，故并不是每次使用临时变量都能加入寄存器。但这并不妨碍我们提升程序的性能。

   在此处，我们应该将for循环中的判断语句里的get_len函数提取出来，在外部使用一个临时变量接收结果，而不是在循环中一直调用该函数。

    int len = get_len(process->storage);
   

2. .

   依旧是上方的代码，我们来讲述一下，循环展开。

   对于mix_cal函数，我们或者说编译器可以如何提升它的速度呢？我们说过一点的小改变都可能对一个程序的最终代码产生极大的影响，对此最常用的便是尝试，前人之路早已铺好，不需要重复造轮子了。

   循环展开:

    int reality = len - 1, i;
    for(i = 0;i < reality;i+=2)
    {
        *result = *result + (process->storage)[i] 
                          + (process->storage)[i+1];
    }
    for(;i < len;++i)
    {
        *result +=  (process->storage)[i];
    }
   

   这就是循环展开中的2次循环展开，同样还有n次循环展开。

   同样，在刚才提到过寄存器的使用以及减少不必要的开销，在此程序中对于(process->storage)[i]这样的存储器位置解引用太过浪费，我们总是将其优化成本低临时变量的使用

    data* local_data = process->storage;
   

   这将为程序带来十分可观的节约，虽然这些工作在编译器的优化中都能包括，但是一旦我们的代码难以被编译器所理解(虽然编译器的升级最大的目的就是提升优化效果)，那么我们很可能得到一个性能不够可观的程序。所以当我们并不是特别紧凑的时候，可以将这些工作当成我们的本分来做，而不是交给编译器来做。

   以及对于外部存储位置 result 我们在此处也是存在着浪费，同样我们应该使用一个临时变量来存储总和，而不是每次得到结果便对它进行解引用操作。

    int local_result = 0;
    /*...*/
    local_result = local_result + local_data[i] + local_data[i+1];
    /*...*/
    *result = local_result;
   

   在上方我们可以看见循环展开被称作2次循环展开，那么自然可以推断有n次循环展开，自然是有的，对于一个n次循环展开的式子我们有一个简便的上界确定公式即:

    reality = len - n + 1;
   

   至于展开几次最好，依然是视环境而定。 故最终的版本应该为：

    static inline void mix_cal(const block* process, int result[])
    {
        int local_result = 0;
        int len = get_len(process->storage);
        int reality = len - 1, i;
        data* local_data = process->storage;
   
        for(i = 0;i < reality;i+=2)
            local_result += local_data[i] + local_data[i+1];
        for(;i < len;++i)
            local_result += local_data[i];
   
        *result = local_result;
    }
   

   解释：循环展开将元素相加分为两个部分，第一部分每次加两个元素，由于如此做会剩余元素没有加，故在第二部分将剩下的元素都加起来。

3. . 还有一种叫做重新组合的技巧，即为让一个表达式中的运算数自由组合，组合出最快速的一种，但是这种方法未曾试验过。故不提及。

4. . 对于条件分支预测错误造成的时间损耗，称之为惩罚，最通俗的说法，就是当你编写的代码中含有条件分支的时候，处理器会选择去预判某一个分支是此次正确的支路，这样可以避免修改任何实际的寄存器和存储器，一直到确定了实际结果，要是不对，那就惨了，这段时间做的事情都白费了。但是也不必过分的关心这种条件分支的预测，这也是我放在最后说的意义所在。

   这里有两种较为客观的方法，一种被称为命令式，一种被称为功能式

   命令式：

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

   功能式：

    int min, max;
    for(int i = 0;i < n;++i)
    {    
        min = a[i] < b[i] ? a[i] : b[i];
        max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
   

   很清晰的一个例子，明显看出来，前者对于不同情况所作的程序步数明显不同，而后者无论什么情况都是相同的程序步。

   两个形式的好处前者对于可预测数据来说，是一个很好的模型，后者则是中庸之道，什么是可预测不可预测，比如一个数是负数还是正数这就是不可预测的，用前面那个代码会有很大的惩罚。

5. . 多路并行的技巧也是一个很重要的思路，可能在很多人眼中看来，两条语句依次写出和合并的效果一定是一样。但是多路并行有一个缺点就是对寄存器的数量有所要求，当寄存器不够时(称为溢出)，性能不升反降。同样是对于循环展开，此次使用四次循环展开加二路并行：

    for(i = 0;i < reality;i+=4){
        local_result_1 += local_data[i] + local_data[i+1];
        local_result_2 += local_data[i+2] + local_data[i+3];
    }//也可以分成四路并行，每一路存一个。这种做法充分利用了CPU流水线的性能
    for(;i < len;++i)
        local_result_1 += local_data[i];
   
    *result = local_result_1 + local_result_2;
   

结束

Tips:

上文中写到的函数大都带有static inline关键字，这是何意？首先我们要确定一件事情，对于非工程的单文件而言，static函数并没有什么意义(意义指的是对于可见性而言，并非说它一无是处)，许多人对于static函数感到茫然的原因在于:我明明将一个函数声明定义成static类型了，但是我还是可以在别的文件中访问到啊！

其实这是因为你根本就没有理解C语言工程这个意思，大部分人是这么测试的:

1. 首先在一个文件夹里创建两个文件 test_static.c和static.h:

    /*static.h*/
    #ifndef STATIC_H
    #define STATIC_H
    static void test(void);
   
    static void test(void);
    {
        printf("Hello World!\n");
    }
    #endif
   

   ...

    /*test_static.c*/
    #include <stdio.h>
    #include "static.h"
   
    void test(void);
    int main(void)
    {
        test();         //编译通过，可以运行。
        return 0;
    }
   

2. 然后编译运行，发现可以通过啊！！标准怎么说在其他文件中不可见？而把static.h去掉#include之后发现报错test undefined，瞬间初学者就凌乱了。

3. 好吧，实际上是前辈们以及教材的错，因为从始至终，所有外界现象都告诉我们C程序是独立的一个一个文件组成的，但是并没有告诉我们要先将他们弄成一个工程！此处如果是使用Visual Studio学习C语言的可能会对工程这个概念理解的稍微好一些，虽然不推荐使用 VS 学习C语言。

4. 你想要实现static函数仅在本文件可见的效果，请你先补习一下工程这个概念，对于任何可见或者不可见的概念而言都是建立在一个工程内而言，而不是像上方的代码，使用#include来表示，你都#include了，那还有什么可见不可见的当然都可见了。所以一个static函数可见于不可见是基于一个个工程里的所有C语言源文件而言的。所以你将常看见前辈们这么回答你的提问:

    /*static.h*/
    #ifndef STATIC_H
    #define STATIC_H
    static void test(void);
   
    static void test(void);
    {
        printf("Hello World!\n");
    }
    #endif
   

   ...

    /*test_static.c*/
    #include <stdio.h>
   
    void test(void);
    int main(void)
    {
        test();         //报错，因为test是static函数。
        return 0;
    }
   

   发现了吗？在上方代码中，少了一行#include "static.h"但是这个代码依旧可行，因为这两个文件是建立在同一个工程里的，而不是在一个文件夹中随意新建两个源文件这么简单，你可以使用各个IDE的工程功能来进行测试。

回到正题，在这里稍微提一下static对函数的某些作用，它可以让函数放在一个静态的空间中，而不是栈里，这是的它的调用更加快速，经常与inline关键字一起使用，为的就是让函数更加快。但是有利有弊，可以自己权衡一下。

参考:深入理解计算机系统--Randal E.Bryant / David O'Hallaro