浅谈C语言编程中程序的一些基本的编写优化技巧
|
大概所有学习C语言的初学者，都被前辈说过，C语言是世界上接近最速的编程语言，当然这并不是吹牛，也并不是贬低其他语言，诚然非C语言能写出高速度的代码，但是C语言更容易写出高速的程序(高速不代表高效)，然而再好的工具，在外行人手中也只能是黯淡没落。 对于现代编译器，现代CPU而言，我们要尽量迎合CPU的设计(比如架构和处理指令的方式等)，虽然编译器是为程序员服务，并且在尽它最大的能力来优化程序员写出的代码，但是毕竟它还没有脱离电子的范畴，如果我们的代码不能让编译器理解，编译器无法帮我们优化代码，那么我们就无法写出一个高速的程序。 对于此，我们可以暂且忽略CPU的设计，因为我们在层面上只能考虑如何迎合编译器的优化规则，而CPU则是语言以及编译器的事情了。 提高程序的速度，就C语言而言可以有这几种方法: 首先还是要设计合理的大纲，正所谓一个程序最大的性能提升就是它第一次运行的时候
注：随着编译器的版本更新，即使不开启优化选项，自带的编译器优化依旧能够为我们编写的代码提供一部分优化，这便是不使用老版本编译器的原因，虽然作为一个程序员不应该太依赖于编译器，但是我认为，时代在进步，信息量正在无限的膨胀，但是人类的大脑以及精力在一个大时代内是有限的，换句话说对于普通人而言我们的记忆是有限的，我们不应该把精力放在前人已经做完的事情上，而是要站在巨人的肩膀上向更远处眺望，如此我们应该充分利用工具来帮助我们实现一些既有的功能，而程序员应该更 专注于发现新的思路，以及想法，在图灵测试尚未有人打破之前，程序员依赖编译器并不是一件错误的事情。 对于当下的编译器，以GCC(GCC不仅仅是一个编译器，但这里将它当成编译器的代名词)为例，-O2是一个为大众所接受的优化等级，对于其他编译器，一般程序员可以选择使用由Google和Apple联合开发的编译器clang也是一个很好的选择， 在-O2的优化等级下，GCC一般情况下能够自动执行循环展开优化， 开始.
/*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
/*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 NULLn",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 datan",block_in_all[i]->index,result_in_all[i]);
}
return 0;
}
耐心读完上述的代码，它是用来求和的，求一个域中的所有元素的和。仔细分析一下，很容易就能看见一些缺点，最大的莫过于在mix_cal函数中对于get_len函数的调用，在此处看来十分明显，但是我们在编写程序的时候是否能够注意到这个问题呢？ 在此处，我们应该将for循环中的判断语句里的get_len函数提取出来，在外部使用一个临时变量接收结果，而不是在循环中一直调用该函数。 int len = get_len(process->storage); . 依旧是上方的代码，我们来讲述一下，循环展开。 对于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;
}
解释：循环展开将元素相加分为两个部分，第一部分每次加两个元素，由于如此做会剩余元素没有加，故在第二部分将剩下的元素都加起来。 . 还有一种叫做重新组合的技巧，即为让一个表达式中的运算数自由组合，组合出最快速的一种，但是这种方法未曾试验过。故不提及。 . 对于条件分支预测错误造成的时间损耗，称之为惩罚，最通俗的说法，就是当你编写的代码中含有条件分支的时候，处理器会选择去预判某一个分支是此次正确的支路，这样可以避免修改任何实际的寄存器和存储器，一直到确定了实际结果，要是不对，那就惨了，这段时间做的事情都白费了。但是也不必过分的关心这种条件分支的预测，这也是我放在最后说的意义所在。 这里有两种较为客观的方法，一种被称为命令式，一种被称为功能式 命令式：
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;
}
两个形式的好处前者对于可预测数据来说，是一个很好的模型，后者则是中庸之道，什么是可预测不可预测，比如一个数是负数还是正数这就是不可预测的，用前面那个代码会有很大的惩罚。 . 多路并行的技巧也是一个很重要的思路，可能在很多人眼中看来，两条语句依次写出和合并的效果一定是一样。但是多路并行有一个缺点就是对寄存器的数量有所要求，当寄存器不够时(称为溢出)，性能不升反降。同样是对于循环展开，此次使用四次循环展开加二路并行：
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语言工程这个意思，大部分人是这么测试的: 首先在一个文件夹里创建两个文件 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;
}
然后编译运行，发现可以通过啊！！标准怎么说在其他文件中不可见？而把static.h去掉#include之后发现报错test undefined，瞬间初学者就凌乱了。 好吧，实际上是前辈们以及教材的错，因为从始至终，所有外界现象都告诉我们C程序是独立的一个一个文件组成的，但是并没有告诉我们要先将他们弄成一个工程！此处如果是使用Visual Studio学习C语言的可能会对工程这个概念理解的稍微好一些，虽然不推荐使用 VS 学习C语言。 你想要实现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关键字一起使用，为的就是让函数更加快。但是有利有弊，可以自己权衡一下。 注：存储器山就是对于不同步长不同大小文件的读取速率的三维坐标图，形似一座山，z轴为速率，x轴为步长，y轴为文件大小（字节），某些主流的测评软件便是这个原理(将存储器山的图像进行一下简单的变换，就能得到哪些软件呈现的效果图像)。 上文提到过，任何一点小改动，都有可能让程序的性能发生很大的变动，这是为什么？ 当时我们并未深究，由于我们惯性的认为计算机的运作方式和人类的运作方式一致，也在过往的经验中认为计算机一定是在任何方面超越人类的存在，但是实际上，计算机除了在重复计算方面比人类的速度要快速以外，其他方面远远落后于人类的大脑，即便是我们最稀疏平常的视觉识别(看东西识别物体)，在计算机看来都是一门极其高深的领域，所以我们现在的时代的计算机还处于起步状态，在这种时代里，程序员的作用是无可替代的，同样程序员的一举一动关乎计算机的命运。 可能在很多的方面，都已经接触了一台计算机的主要组成构造，和程序员最息息相关的便是CPU，主存以及硬盘了，可能到现在为止很多程序员仍然认为编程序和这些存储器有什么关系？然而一个程序员，特别是编写C语言程序的程序员，最大的影响因素便来自于此，在计算机的存储器结构中，分为四种层次: 但是有没有想过，为什么计算机存储器系统要分成这四层结构呢？我们知道，上述四种存储器的读写速度依次降低，我们为什么不选择一种速度中庸的，价格也中庸的材料，制造所有层次的存储器呢？ 有人给出的解释是，一个编写良好的程序总是倾向于访问层次更高的存储器，而对于现在的技术，价格高昂而无法大量制造的高速存储器来说，我们可以选择按层次分配构造，让我们以最低的成本的存储器达到使用最高的速度存储器的效果。 前方提到了局部性，局部性体现在了，当步长越大，空间局部性越低，大多数情况下会造成性能降低，比如最常见的多维数组循环(我鲜少使用多维数组的原因之一便在于此)，前面说过多维数组实际上只是数个一维数组的包装而已，C语言中并没有真正的多维数组，而是将其解读成内存中的一维的连续内存，但是当我们遍历它的时候，C语言为了不让我们被底层实现所困扰，所以生成了多维数组遍历的假象： 让我们重温一遍"多维数组"：
#include <stdio.h>
int main(void)
{
int dim_1_arr[4] = {1,2,3,4};
int dim_2_arr[2][2] = { {1,2},{3,4} };
int result_1 = 0;
int result_2 = 0;
for(int i = 0;i < 4;++i)
result_1 += dim_1_arr[i];
return 0;
}
此例中，对一维数组进行步长为 1 遍历求和，假设内存中数组的起始位置是 0
0 => 4 => 8 => 12
for(int j = 0;j < 3;++j){
for(int i = 0;i < 3;++i){
result_2 += dim_2_arr[i][j];
}
}
此例中，我们的步长是多少呢？我们来看一下 0 => 8 => 4 => 12 可以很清晰的看出两段不同代码之间的跳跃，为什么？观察到多维数组的遍历中我们和平时的做法有些不同，是先对i进行遍历，再对j进行遍历，这就导致了程序必须在内存块中无规律的跳动，这里的无规律是计算机认为的无规律，虽然在我们看来的确是有迹可寻，优秀的编译器能够对它进行优化处理。就事论事，即这段程序的空间局部性比较差，对于一个在内存中大幅度跳跃，无规律跳跃的程序都将影响程序的性能。这个判定对于一个连续的内存块来说是很重要的，比如C语言中的结构体。 实际上C语言也是能够面向对象的，但是十分复杂，就像拿着棒子织衣服一样。而C语言的机构体能够让我们在一定程度上初步理解对象这个概念，因为它是一个完整的个体，虽然对外界毫不设防。 对于结构体：
#define VECTOR 4
typedef struct{
double salary;
int index[4];
}test_data;
int main(void)
{
int result_1 = 0;
int result_2 = 0;
test_data dim_1_arr[VECTOR];
/* ...填充数据 */
for(int i = 0;i < VECTOR;++i)
{
for(int j = 0;j < 4;++j)
result_1 += dim_1_arr[i].index[j];
}/* for loop 1 */
for(int j = 0;j < 4;++j)
{
for(int i = 0;i < VECTOR;++i)
result_2 += dim_1_arr[i].index[j];
}/* for loop 2 */
return 0;
}
还是和上方一样，假设 dim_1_arr 起始位置为 0 for loop 1： 8 => 12 => 16 => 20 ==> 32 => 36 => 40 => 44 ==> ... for loop 2： 8 => 32 => 56 => 80 ==> 12 => 36 => 60 => 84 ==> ... 从上方不完整的比较来看，loop 1 相对于 loop 2 来说有更好的空间局部性，很明显在 loop 2 中，CPU读取是在无规律的内存位置跳跃，而 loop 1 则是以单调递增的趋势向前(这里的向前指的是直观上的向前)读取内存。 在此处回顾一下C语言的结构体性质与知识： 内存对齐便是对于一个结构体而言，其所占内存大小总是最大成员的整数倍，其中最大成员指的是最基本成员，即：
typedef struct{
test_data test_1;
int test_2;
}test_data_2;
/*...*/
printf("The size of test_data_2 = %dn",sizeof(test_data_2));
/*...*/
` 输出： The size of test_data_2 = 32 `
typedef struct{
int index[4];
int store_1;
int store_2;
}test_data_3;
typedef struct{
test_data_3 test_3;
int test_4;
}test_data_4;
/*...*/
printf("The size of test_data_4 = %dn",sizeof(test_data_4));
/*...*/
` 输出： The size of test_data_2 = 28` 仔细对比`test_data_3`与`test_data`的差异，可以发现不同处，在前者的内部包含了一个`double`类型的成员，在我的机器上它的长度为 `8` ，后者的内部包含了两个`int`类型的成员，每个长度为 `4`，但是他们的长度在直观上是一样的！但是真正在使用的时候我们才能察觉到其中的差异，这就是我所说的**最基本成员**的意义所在。虽然我们在使用结构体的时候，能够将其当作一个整体，但是实际上他们与内建(build-in)的类型还是有一些差异的。 之所以没有详细的介绍时间局部性是因为，对于时间局部性而言，其最大的影响因素便是操作区域的大小，比如我们操作的数组或者文件的大小，越小时间局部性越好，试想一下对于一个小的文件和大的文件，我们更容易操作到同一块地方多次的，必定是小的文件。而操作文件的大小有时候并不能很好得成为我们的操作因素，故只能多关注空间局部性。 在前方提到了，一般情况下，局部性好的程序能够让程序比局部性差的程序更有效率，而对于局部变量而言，一个好的编译器总是尽可能的将之优化，使其能充分使用CPU寄存器,那么寄存器的下方,也就是速度最接近寄存器的,便是所谓的高速缓存器了，对于高速缓存器而言，其最大的功效便是缓冲，缓冲有两层意思： 缓存数据，使下一次需要的数据尽可能的“靠近”CPU，此处的靠近并不是物理意义上的距离靠近。 总的来说，对于高速缓存器来说，一般分为三层，第一层比较特殊由独立的两个部分组成，第二层第三层则是各自独立一体并未区分功能(既存数据又存指令)，而第一层和第二层则是每个核单独享有不同的缓存器，第三层则是各个核共享一个层，所以我们经常看见在个人计算机上，L3的大小经常是以MB为单位的，而第一层则多以KB甚至是Byte为单位。 高速缓存器的各个层依然遵守逐步降速的规律，即读取周期 L1 < L2 < L3，而影响较大的便是上文提到的的命中率，我们知道越上层的高速缓存器总是将下层的存储器映射在自己的存储器中，而按照逻辑推断，上层的实际空间比下层的要小，因为上层的空间更加宝贵速度更快，这就导致我们无法将下层的空间一一对应的映射到上层里，那么我们就想到一个办法，并不是将下层存储器的内容完全映射到上层，而是上层有选择性的将下层的部分内容抽取到上层，这便是不命中之后的操作。 对于CPU从存储器中读取数据这个操作，如果我们使用了高速缓存以及内存这两个概念，那么就会有一个延伸概念，命中。而对于这个概念只有两种情况，命中或者不命中。而对于一个初始化的高速缓存器，它一定是空的，也许在物理意义上它并不是空，但是实际上在程序看来它的确是空的，为了区分这个，高速缓存器专门使用了一个位(bit)来表示此组是否有效(即是否为空)，既然它是空的那么，我们第一次无论如何都无法命中数据，这时候该层的高速缓存器就会向下一层，在该层中寻找所要的数据，每次要向下一层申请寻找的行为一般称为惩罚，而当我们从存储器中将所需的数据加载到高速缓存器中的时候，我们便开始了运算，而一切关于高速缓存器效率的改进都集中在命中率的提升。 假设有一个数组需要操作，由于数组是一个连续的内存空间，对其进行步长为1的操作拥有很好的空间局部性，那么可以当成一个很好的例子，在高速缓存器看来读取一个有n(n>N)个元素的数组vector并不是一次性读完，而是分次读取，如果读取了k次那么至少有k次不命中，这是不可避免的，而对于读取的数据也不一定是我们需要的，用书上的例子来说： 很好理解，因为缓存器空，所以第一次操作必然不命中，所以我们需要向下级存储器读取我们需要的数据，那么第二访问高速缓存的时候，可以命中`vector[0]`，依次命中后续两个，直到需要`vector[4]`，出现了不命中，那么我们就需要重复上一步，再次读取三个数据，依次类推直到结束。`vector:|[0]|[1]|[2]|[3]|[4]|[5]|[6]|[7]|[]|[]|[]|` 现在我们能够从一定层面上解释为什么局部性好的程序比局部性差的程序要有更好的效率了，原因就在对于高速缓存器的利用，**首先反复利用本地临时变量能够充分的调用高速缓存器的功能做到读写的最优化，其次步长为越小也越能尽最大的能力发挥高速缓存器读取的数据**，在这点上再回过头思考多维数组的遍历并进行操作，如果没有考虑空间局部性(即先操作大块，再操作小块)，那么在高速缓存器中，它的不命中率令人发指，这也是操作不当效率低的原因。 步长 | 1 | 2 | 3 | 4 | 5 | 以上所说的每次读取下一级别存储器数据的时候，都是按照内存对齐，来读取的，如果你的内存数据，例如读取结构体时，没有放在内存对齐的位置(此处所说的内存对齐位置是以每次该级别存储器读取的大小为对齐倍数，而不是结构体在内存中存储时的内存对齐位置)，那么会将该位置的前后补齐倍数的起始位置来读取
也就意味着，并不是每次缓存读取都是如此的完美，恰好都从内存中数据的首部开始读取，而是整片根据内存倍数进行读取。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |