编译器优化的局限性 Link to 编译器优化的局限性

• 受到代码限制,不能改变程序的行为
• 可能会被代码风格混淆,比如数据的变化范围比数据类型的范围小
• 分析只建立在过程内,不对整个程序分析
• 分析基于静态信息而非动态输入
• 当编译器无法决定是否优化时,就选择不优化

举例阐述: Link to 举例阐述:

1. 过程调用

1
2
3
4
5
6

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

每次判断都要执行一次 strlen(s) 很显然能优化为

1
2
3
4
5
6
7

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

但是编译器却不能做出这样的优化,原因正是在于:

• 下方代码对字符串进行修改,可能导致字符串长度发生变化
• 分析建立在过程内部, strlen(s)函数对于编译器是未知的,即使它是库函数,仍有可能由程序员覆盖定义.

2. 内存混淆

1
2
3
4
5
6
7
8
9

/* sum rows is of n*n matrix a and store in vector b */
void sum_rows(double *a,double *b, long n){
	long i, j;
	for(i=0;i<n;i++){
		b[i]=0;
		for(j=0;j<n;j++)
			b[i] += a[i*n+j];	
	}
}

实际上的汇编代码会将b数组不断从内存中取出,运算,再保存回去.读取内存十分耗费时间.完全可以取出后完成所有运算再放回,但编译器不会自动做这样的优化,因为可能存在两个数组引用同一块内存(别名引用)的情况,这样b数组运算后保存到内存就可能影响a数组的数据,编译器不能保证这种情况不会发生. 解决办法是手动创建一个临时变量来保存运算的结果.

常用的优化 Link to 常用的优化

1. 代码移动 循环不变式外提:对产生相同结果的代码提到循环外. 例如

1
2
3
4

for(i=0;i<n;i++){
	for(j=0;j<n;j++)
		a[n*i+j] = b[j];
}

=>

1
2
3
4
5

for(i=0;i<n;i++){
	int ni = n*i;
	for(j=0;j<n;j++)
		a[ni+j] = b[j];
}

当gcc使用O1以及更高的优化级别时会实施. 2. 减少计算量 通过移位和加法来实现一个操作数为常数的乘除法. 例如 x*16 => x<<4

1
2
3
4
5

for(i = 0;i<n;i++){
	int ni = n*i;
	for(j = 0;j<n;j++)
		a[ni+j] = b[j];
}

=>

1
2
3
4
5
6

int ni = 0;
for(i=0;i<n;i++){
	for(j=0;j<n;j++)
		a[ni+j] = b[j];
	ni += n;
}

3. 复用表达式 如果含有相同的(子)表达式,在gcc -O1以上会有优化

超标量指令处理器(Superscalar Processor) Link to 超标量指令处理器(Superscalar Processor)

定义:在一个时钟周期能执行多条指令的处理器. 现代CPU设计: 程序是一个顺序执行的指令序列,但CPU读取尽可能多的指令序列,发现有的指令之间不是相互依赖的,可以进行指令级并行计算. 将程序进行拆分重组,使这些基本单元尽可能保持繁忙.

流水线功能单元(Pipeline Functional Units) Link to 流水线功能单元(Pipeline Functional Units)

假设一个乘法运算需要3个时钟周期,对于

1
2
3
4
5
6

long mult_eg(long a, long b, long c){
	long p1 = a*b;
	long p2 = a*c;
	long p3 = p1*p2;
	return p3;
}

利用并行可以在7个时钟周期内完成:(注意这是单核实现,不用多核)

所以,有些指令比较慢,但通过流水线技术可以缩短时间.除法没有流水线.

循环展开 Link to 循环展开

假如要计算一个数组的乘积 (2*1)循环展开:

1
2
3
4

/* Combine 2 elements at a time */ 
for (i = 0; i < limit; i+=2) { 
x = x OP (d[i] OP d[i+1]); 
}

可以充分利用流水线 能够有效降低运算的延迟(latency)

还有一种(2*2)循环展开:

1
2
3
4
5

/* Combine 2 elements at a time */ 
for (i = 0; i < limit; i+=2) { 
	x0 = x0 OP d[i]; 
	x1 = x1 OP d[i+1]; 
}

所以,可以展开成K组,根据测试结果选择最好性能.取决于数据的类型和加法器/乘法器的数量.不明觉厉啊. 在讲浮点代码时提到的%ymm寄存器,从硬件层面展现了流水线的实施原理: SIMD 操作

• 单精度:
• 双精度: 跟向量运算一样,所以这方面的优化叫做向量化编程.

分支预测 Link to 分支预测

由于CPU的乱序执行, CPU指令单元必须走在执行单元之前,但遇上分支,预测哪一个分支会被执行,然后CPU提前执行对应分支的代码. 如果结果证明预测正确,就继续(乱序执行);如果预测错误,只能舍弃并倒回去.

获得高性能 Link to 获得高性能

• 好的编译器优化
• 注意避免隐秘的算法低效
• 编写对编译器友好的代码:注意避免重复的过程调用和内存引用
• 关注最深层循环
• 利用指令级并行
• 避免难以预测的分支
• 充分利用缓存(局部性)