优化程序性能 | 《深入理解计算机系统》第五章笔记

前言

作为一个程序员，其编写的程序需要正确且高效。一个高效的程序具备以下两点：

1. 对于需要解决的问题，程序选择了正确的算法与数据结构；
2. 源代码可以被编译器有效优化为高效的可执行代码。

因此，需要学习如何对程序的性能进行优化。其本质是兼顾高级语言的可读性，同时考虑编译器的优化方式，在编译器的优化范围内，尽可能的提高程序的高效性。

编译器能力的局限

现代的编译器，虽然能够对源代码进行一定的优化，但是其仍然可能出现错误。所以一般来说，编译器仍然会以程序的安全性（优化后的可执行代码要与原始代码能够产生相同的结果）为主，然后才考虑程序的高效性。

void twiddle1(long *xp, long *yp) {
	*xp += *yp;
	*xp += *yp;
}

void twiddle2(long *xp, long * yp) {
	*xp += 2 * *yp;
}

以上面两个函数为例，在一般情况下，调用两个函数后的结果是一致的，但是twiddle2在性能上略有优势。不过编译器在遇到twiddle1时，并不会直接优化得到twiddle2这个函数，因为当指向的地址是一致的，那么两个函数最终得到的结果并不相同。编译器在编译的时候无法预知xp,yp指向的具体地址，不能盲目的进行程序的优化，否则会得到不一样的运行结果。
编译器也不会判断函数调用的时候会不会产生副作用（见书P344，比如函数内尝试修改全局函数），所以一般情况下，它会假设最糟糕的情况，并保持所有的函数调用不变。

优化程序性能的具体方法

程序性能的评价指标

每元素的周期数（Cycles Per Element, CPE).简单说就是处理一个元素（比如一行代码）经历的CPU时钟的周期数，该指标越小，程序的性能越优。
CPE一定是一个整数，但是在实验中是经过拟合得到的结果，所以不可避免的会产生小数

消除循环的低效率

void for01(vector<int>>& nums) {
	for(int i = 0; i < nums.size(); i++) {
		...
	}
} 

void for02(vector<int>>& nums) {
	int n = nums.size();
	for(int i = 0; i < n; i++) {
		...
	}
}

由于每次循环迭代时都会对测试条件求值，如果采用for01的方式，则每次都要对向量的长度进行计算。而向量的长度是不变的，所以可以优化为for02的代码，这样就只用计算一次向量的长度。

这样的代码优化的方法被称为代码移动（code motion）。对于循环中将要执行多次但是计算结果不会改变的计算，可以将计算移动到循环前面，则不会多次求重复值。

上述优化操作可以避免渐进低效率的发生，比如一下两个函数。lower1的时间复杂度本质是$O(n^2)$,lower2的时间复杂度是$O(n)$.如果字符串长度较短，则难以察觉二者的性能差异。

void lower1(char* s) {
	long i;
	for(i = 0; i < strlen(s); i++)
		if(s[i] >= 'A' && s[i] <= 'Z')
			s[i] -= ('A' - 'a')
}

void lower2(char *s) {
	long i;
	long len = strlen(s);
	for(i = 0; i < len; i++)
		if(s[i] >= 'A' && s[i] <= 'Z')
			s[i] -= ('A' - 'a')
}

减少过程调用

该优化方法指直接访问底层数据结构，比如

1. 直接通过数组int*存储数据，而不是vector<int>。
2. 使用容器，如vector时，在已知数据量的时候，提前申请足够的内存空间，避免反复扩容。

消除不必要的内存引用

尽量避免反复从内存读取数值，可以引入在循环外声明的临时变量，来消除不必要的内存读写。
sum1相比sum2,每次循环会多一次从内存的读，多一次向内存的写。（获得res处的数据，更新res的值）。sum2使用临时变量，规避了上述问题，因为tmp一直存储于寄存器中，并不需要向内存进行读写操作。

void sum1(int* v, int length, int* res) {
	for(int i = 0; i < length; i++) {
		*res = *res + v[i];
	}
}

void sum2(int* v, int length, int* res) {
	int tmp = 0;
	for(int i = 0; i < length; i++) {
		tmp = tmp + v[i];
	}
	*res = tmp;
}