WARNING

这是《深入理解计算机系统》(CS)的笔记，彼时还未上CO,OS等计算机系统基础课，存在理解不到位与错误之处.

使程序运行得更快，需要：

• 合适的算法与数据结构
• 机器代码级别的优化，使之更适合硬件。优化编译器有很多局限，需要程序员帮助。
• 增加程序并行性，并发编程。还有一些利用硬件特点的并发，如循环展开等技术，后续详述。
  开始之前：本文中对于程序性能的描述：CPE，每个元素要花多少时间周期。

一、对于所有程序的通用初级优化#

1）减少过程（如函数等）调用。尤其在循环的条件中，尽量避免用函数，尽可能用“内联”的形式。比如

char S[BUFSIZE];  
...  
for(int i=0;i<strlen(S);i++){  
	do something...  
};  

显然是低效的，因为每次都要调用strlen()。
优化编译器无法自动地将其修改成不反复调用的情况，因为编译器很难判断过程中S的长度是否是动态变化的。很多类似的优化，需要程序员帮助编译器完成。

2）减少内存访问
尤其是对指针操作，这会导致指针指向的值无法存在寄存器中。常用的方法是，用局部变量存储需要不断迭代的值。

/* 将数组A中的值累乘，存入*dest指向的空间 */  
void fun1(data_t A[],long size,data_t *dest)  
{  
	*dest=A[0];  
	for(long i=1;i<size;i++){  
		*dest*=A[i];  
	}  
}  
  
void fun2(data_t A[],long size,data_t *dest)  
{  
	data_t acc=A[0];  
	for(long i=1;i<size;i++){  
		acc*=A[i];  
	}  
	*dest=acc;  
}  

fun2优于fun1，因为acc可以存在寄存器中，避免过多的内存引用。高级别优化编译器能直接完成类似效果的优化，但注意fun1 和fun2的结果并不总是一样的，当*dest指向的空间时数组A中的某个元素时，有区别。
使用本地局部变量快于直接使用形参（指针形参），但受寄存器数量制约，局部变量多了会存在内存中。

二、从硬件角度看程序性能优化#

1、现代处理器#

（《深入理解计算机系统》P358）
乱序处理。对指令的执行顺序可能相当程度不同于原始顺序，多条指令并行执行（这个对于提升程序性能很重要，处理器的计算能力常常不能被完全发挥出来）。
指令控制单元与执行单元。不详述。执行单元中，所有指令经过的过程进一步细分为了 条件分支、运算、加载、存储 等单元，每个单元都流水线化，可以并行执行。而各个模块中都有不同子单元。制约程序性能的有三组：首先是最直接的运算单元，然后是包含预测行为的分支，最后是加载与存储的组合。将依次从三个单元进行程序优化。

2、运算单元#

参考机中（Intel Core i7 Haswell）主要运算单元的信息，其它机器应该差不多。其中，延迟是指执行一次相应运算的时钟周期，发射是相邻的同种运算所间隔的时间，发射为1说明完全流水线化，而除法的延迟等于发射，说明完全不流水线化。容量是具有这种运算单元硬件的个数。

对于程序，由它们可以得出运算的两个界限：延迟界限、吞吐量界限，它们都是最开始说的CPE。延迟界限是单次执行某种运算所需的时间界，而吞吐量界限是达到最大吞吐量（比如塞满流水线）时能达到的时间界，是终极界限。

后续利用硬件特性提升性能，主要是利用有的运算有多个单元，实现并行计算，剪断关键路径，或者利用流水线特性，尽可能斩断前后相关避免转发或者等待，塞满流水线，逼近吞吐量界限。

本文不涉及硬件是如何乱序执行、识别并实现这些并行的，只讨论提高性能的结论。

2.1、循环展开#

循环展开有两种：循环一轮进行多次迭代，或者 扩展多个累计变量。
作为例子，原始数组元素累乘函数如下：

/* 这已经是经过“一”初步优化后的结果 */  
void func0(double a[],double *dest,long length)  
{  
	double acc=a[0];  
	for(long i=1;i<length;i++){  
		acc*=a[0];  
	}  
	*dest=acc;  
}  

循环一轮进行多次迭代（如下），减小循环轮次。当运算本身不是限制速度的因素时，这样做往往能取得优化效果。这种情况一般多出现在整数加法。

/* 简单的循环展开 k*1 */  
void func1(double a[],double *dest,long length)  
{  
	double acc=a[0];  
	long edge=length-1,i;  
	for(i=1;i<edge;i+=2){  
		acc=acc*a[i]*a[i+1];  
	}  
	for(;i<length;i++){  
		acc*=a[i];  
	}  
	*dest=acc;  
}  

累积变量扩展，利用有两个浮点数乘法器的特点，用两个实际上没有相互关系的迭代，并行计算，从而实现同时执行两个乘法，突破浮点乘法的延迟界限。

/* 累积变量扩展 k*k */  
void func2(double a[],double *dest,long length)  
{  
	double acc0=a[0],acc1=a[1];  
	long i,edge=length-1;  
	for(i=2;i<edge;i+=2){  
		acc0*=a[i];    //偶项  
		acc1*=a[i+1];   //奇项  
	}  
	for(;i<length;i++){  
		acc0*=a[i];  
	}  
	*dest = acc0 * acc1;  
}  

上面这个累积变量扩展程序中，主循环中的两个乘法并行进行，最后得到1.5的 CPE。

2.2、运算重新结合（运算树最矮化）#

通过调整运算的顺序提高并行度。
具体而言，对于语句

acc = acc * a[i] * a[i+1];  

来说，两个乘法都在一次循环的关键路径中。必须更新了acc才能进入下一次循环，而且要有了acc * a[i]的结果才能接着* a[i+1]，一个循环中必须顺序执行两个乘法，关键路径中有两个乘法，而一个循环中处理两个元素，CPE预测为3，没有优化。
但如果：

acc = acc * (a[i] * a[i+1]);  

a[]中元素和循环无关，机器可以不断地取出a中元素计算计算，不必等待acc更新。所以当其中一个乘法器在计算acc*=(...)的时候，另一个乘法器已经在计算后面几轮所用的a[i]*a[i+1]了。这样整体来看，单次循环中的关键路径只有一个乘法，而一次迭代两项，得1.5的CPE。

此外，除了利用多个并行的运算器，在完全流水线化的运算中，也可以通过重新结合运算顺序，尽可能斩断前后循环轮次中的变量数值联系，尽可能避免需要bubble或stall的冒险，充分利用流水线，毕竟吞吐量界限。

2.3、向量指令#

AVX硬件的向量指令可以同时对多个数据进行同种计算，大大提高并行度。GCC支持对C的支持向量拓展，不细说。

3、分支预测#

降低分支预测错误的可能性，使用更容易被编译器翻译成条件传送的代码。当然，必须明确不应该过于关注分支预测错误，它一般只是小问题。

3.1、利于条件传送#

问号表达式、功能性代码比命令式代码容易翻译成条件传送，比如：

/* 归并排序中的Merge部分，命令式 */  
void merge(long src1[],long src2[],long dst[],long l1,long l2)  
{  
	long i1,i2,id;  
	for(i1=i2=id=0;i1<l1&&i2<l2;){  
		if(src1[i1]<src2[i2])  
			dst[id++]=src1[i1++];  
		else  
			dst[id++]=src2[i2++];  
	}  
	while(i1<l1){  
		dst[id++]=src1[i1++];  
	}  
	while(i2<l2){  
		dst[id++]=src2[i2++];  
	}  
}  
/* 使用功能性代码替换第一个循环中的内容 */  
......  
long v1=src1[i1],v2=src2[i2],take=(src1[i1]<src2[i2]);  
dst[id++]=take ? v1 : v2;  
i1+=take;  
i2+=(1-take);  

后者更容易被翻译成条件传送。

4、存储系统#

加载、存储可能造成冒险。当存储后接着加载时，加载可能要用前序存储要更新但还未更新完的地址。
存储单元维护一个存储临时寄存器，存放正在（至少将要）执行的存储操作，包括地址和数据。进行读取时，对这个文件进行扫描，如果有地址一样的，就用这个新值。但好像不能直接传送，而是要等这条存储指令执行完毕。
编程中，也应避免加载、存储的“首尾相连“。
存储中有很多微妙的细节。

三、代码剖析#

Unix自带代码剖析工具GPROF。Intel VTUNE，Linux VALGRIND等。
编译时候使用 -pg 避免使用内联替换优化程序，方便追踪函数调用。

gcc -Og -pg prog.c -o prog  
./prog **argv...  

运行较慢，会额外生成一个gmon.out文件。使用GPROF:

gprog prog  

生成测试结果。
注意：1）采用定时中断轮询法确定调用函数时间，是估计值。2）不要执行内联替换。3）不会对库函数计时，通过包装函数可以解决。

利用代码剖析工具可以关注目前主要的性能瓶颈，集中发力。