写程序最主要的目标是使它在任何情况下都能正确工作，但在很多情况下，让程序运行的快也是一个重要的因素。编写高效程序要做到一下几点：
- 必须选择一组适当的数据结合和算法；
- 编写出编译器能有效优化的源代码；
- 编写适合不同处理器架构和性能的代码。
当然，有人可能会说，优化代码可以依靠编译工具（如GCC）的优化选项，为什么还需要我们自己亲自干呢？有这种疑问的请继续阅读，没有疑问的可以跳过第0节。
0. 为什么不能完全依靠编译器的自动优化？
介绍一下常用GCC编译器的优化选项：
- 基本优化命令行选项：-Og 一般用于小型程序的优化，用于学习理解
- 一般优化命令行选项：-O1 一般用于小型软件项目的优化
- 标准优化命令行选项：-O2 一般用于大中型软件项目的优化，较多使用
- 高级优化命令行选项：-O3 一般用于超大型软件项目的优化，较少使用
编译器必须很小心的对程序只使用安全的优化，即对于程序可能遇到的所有情况，在优化前后必须得到相同的结果。为了解释一种程序转换是否安全，我们先看一个例子:
void twiddle_1(long *xp, long *yp)
{
*xp += *yp;
*xp += *yp;
}
void twiddle_2(long *xp, long *yp)
{
*xp += 2 * (*yp);
}
咋一看，这两个程序似乎表达同一个意思，而且第2个会更高效一点。因为第一个程序总共要进行6次内存引用，而第二个只需要3次内存引用。
先介绍一个术语——内存别名使用：两个指针指向同一个内存位置的情况。
由于在优化之前，编译器会考虑所有可能的情况，其中一种情况就是“内存别名使用”。此时，第一个函数会执行以下的计算：
*xp += *xp; /*double value at xp*/
*xp += *xp; /*double value at xp*/
结果是xp的值增加4倍。另一方面，第二个函数twiddle_2会执行以下的计算：
*xp += 2 *（*xp）; /*triple value at xp*/
结果是xp的值增加3倍。但编译器并不知道你会如何使用第一个函数twiddle_1，保险起见它不能将函数1优化成函数2的样子。所以我们不能完全依靠编译器的自动优化工具来对自己的代码进行优化，而是要结合代码实际使用情况，有针对性的结合几种优化原则，来帮助编译器对代码进行无差错优化。
1. 减少函数调用次数
循环语句中的代码往往要执行多次，它的高效与否往往决定了整个程序的性能瓶颈。所以在循环语句中，我们要尽可能的降低其运行消耗（时间消耗内存消耗）。先看一段代码：
void lower_1(char *s)
{
int i;
for(i=0; i<strlen(s); i++)
if(s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
void lower_2(char *s)
{
int i;
int len = strlen(s);
for(i=0; i<len; i++)
if(s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
第一个函数中，每次循环都要调用函数strlen一次，而函数调用所花费的性能代价是很大的。第二个函数在循环展开之前就把字符串的长度存在了一个标量中，以后循环中就使用该标量值来代替调用函数strlen，而从寄存器中读取一个值相比于调用一个函数来获得值无论在时间上还是存储开销上都大大降低。实验可知，当字符串长度为100万字符时，函数lower_1需要花费1000秒的时间，而函数lower_2仅需要2毫秒，性能提升近50万倍！
2. 减少内存引用次数
加载或读取内存地址是非常耗时耗力的，虽然现在绝大多数处理器都使用了缓冲技术来减少程序运行中的内存引用的时间开销，但相比于直接读取寄存器它的速度还是相当相当慢的。看下面一个例子：
void func1(int *a[], int length, int *dest)
{
int i;
int len = length;
for(i=0; i < len; i++){
*dest += a[i];
}
}
void func2(int *a[], int length, int *dest)
{
int i;
int len = length;
int val=0;
for(i=0; i < len; i++){
val += a[i];
}
*dest = val;
}
第一个函数中，每次循环都要对内存地址dest进行一次读写；而第二个函数巧妙的设定了一个局部变量用于循环内的计算，当循环结束在将结果放到指定的内存地址dest处。
3. 循环展开
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。
- 它减少了操作的数量，例如循环索引语句和条件分支语句的计算次数；
- 它提供了一些方法进一步改进代码，减少关键路径上的操作次数。
3.1 减少循环次数
下面一段程序将上节中的函数func2中的for语句进行了“2x1”循环展开：
void func3(int *a[], int length, int *dest)
{
int i;
int len = length;
int limit = length-1;
int val=0;
for(i=0; i < limit; i+=2){
val = val + a[i] + a[i+1];
}
for( ; i < len; i++){
val = val + a[i];
}
*dest = val;
}
当然，我们也可以进行“kx1”循环展开，
void func3(int *a[], int length, int *dest)
{
int i;
int len = length;
int limit = length -（k -1);
int val=0;
for(i=0; i < limit; i+=2){
val = val + a[i] + ... +a[i+k-1];
}
for( ; i < len; i++){
val = val + a[i];
}
*dest = val;
}
3.2 提高并行性
随着集成度的提高，现代处理器一般都具有多核结构，或者支持超标量技术(SIMD)，这就给我们程序员编码提供了另一种选择，利用编写并行性较高的程序 来达到提高运行速度的目的。
对于一个可结合和可交换的合并运算来说（整数加或乘），我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。
我们将func3函数重新编写成“2x2”循环展开形式：
void func4(int *a[], int length, int *dest)
{
int i;
int len = length;
int limit = length-1;
int val_1=0;
int val_2=0;
for(i=0; i < limit; i+=2){
val_1 += a[i];
val_2 += a[i+1];
}
for( ; i < len; i++){
val_1 += a[i];
}
*dest = val_1 + val_2;
}
相应的“kxk”模式，相比大家应该知道怎么变了吧？此处k的最大取值取决于你程序运行所在处理器中寄存器的个数和流水线级数。一般情况下k取10以内问题都不大。
3.3 重新结合变换
这是一种利用改变结合变换达到提高并行性目的的方法。
废话不多说，看码：
void func3(int *a[], int length, int *dest)
{
int i;
int len = length;
int limit = length-1;
int val=0;
for(i=0; i < limit; i+=2){
val = val + a[i] + a[i+1];
}
for( ; i < len; i++){
val = val + a[i];
}
*dest = val;
}
void func5(int *a[], int length, int *dest)
{
int i;
int len = length;
int limit = length-1;
int val=0;
for(i=0; i < limit; i+=2){
val = val + (a[i] + a[i+1]); /*此处添加了一对圆括号*/
}
for( ; i < len; i++){
val = val + a[i];
}
*dest = val;
}
正如以上代码所示，func5仅比func3在循环语句中添加了一对括号，从而改变了该语句执行时的顺序，产生了我们称为“2x1a”的循环展开形式。
对于刚接触C的来说，这两个函数看上去本质是一样的，但是当我们运用性能分析工具gprof来比较这两个函数的时候，会得到令人吃惊的结果：2x1a的性能几乎等同于2x2的性能。
考虑v = v * x * y * z;如何添加括号，以达到最优性能呢？
答案：v = v * ((x * y) * z)或v = v * (x * (y * z))
4. 用条件送传指令代码代替分支语句
总所周知，现代处理器普遍具有分支预测功能，它为我们程序的快速运行提供了不小的功劳。例如在预测循环测试条件时，我们处理器总是判定条件成立（当然，程序运行的绝大部分时间也确实如此），只有在最后一次时，我们才会预测错误。而这时付出的代价和前面所带来的收益可以忽略不记。
因为绝大部分循环条件测试的结果都是显而易见的，我们可以忽略分支预测错误的惩罚。但在一些场合（比较大小），他的测试结果是随机的，此时我们就不得不考虑分支预测错误时所带来的惩罚了。为此有没有一种方法来避免使用条件分支呢？答案看码！
/*给定两个数组，比较每个相对应的位置的值，
将小的放在a数组中，大的放在b数组中。*/
void minmax_1(int a[], int b[], int len)
{
int i;
for(i=0; i<len; i++){
if(a[i] > b[i]){
int t = a[i];
a[i] = b[i];
b[i] = t;
}
}
void minmax_2(int a[], int b[], int len)
{
int i;
for(i=0; i<len; i++){
int min = a[i] < b[i] ? a[i] : b[i];
int max = a[i] < b[i] ? b[i] : a[i];
a[i] = min;
b[i] = max;
}
}
}
5.总结
上述总总描述了许多优化程序性能的基本策略：
1. 高层设计
为遇到的问题选择适当的算法和数据结构。
2.基本编码原则
- 消除连续的函数调用，有可能时将计算或访存移到循环外。
- 消除不必要的内存引用，引入临时变量来保存中间结果，在最后的值计算出来时，才存放到数组或全局变量中。
3.底层优化
- 展开循环，降低开销，并且使得进一步的优化成为可能。
- 通过多个累计变量和重新结合等技术，找到提高指令级并行。
- 用条件传送指令代替条件语句，使得减少分支预测错误的惩罚。
网友评论