优化程序性能

第一，我们必须选择一组适当的算法和数据结构。
第二，我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。

为什么我们需要优化程序，现代编译器不是具有很强的优化能力吗？

ans:因为编译器只进行安全的优化，消除可能出现的异常的运行时行为。意味着我们需要写出适合编译器优化的代码，优化程序性能。

内存别名使用

两个指针可能指向同一个内存位置的情况称为内存别名使用 (memory aliasing)


void twiddlel(long *Xp, long *yp) 
{ 
*XP += *yp; 
*XP += *yp; 
} 
void twiddle2(long *XP, long *yp) 
{ 
*XP += 2* *yp; 
}

乍一看两个函数好像没有区别，但是当*XP与*YP指向同一内存时。twiddle1变为原来的四倍，twiddle2变为原来的三倍。改变了程序的行为。

如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，这就限制了可能的优化策略。

函数调用

long f(); 
long func1  { 
return f() + f() + f() + f() ; 
} 
long func2 () { 
return 4*f () ; 
}

以 funcl 作为源代码时，会很想产生 func2 风格的代码。

long counter= O;
long f() { 
return counter++; 
}

这个函数有个副作用它修改了全局程序状态的一部分。改变调用它的次数会改变程序的行为。特别地，假设开始时全局变最 counter 都设置为 o, funcl 的调用会返回0+1+2+3=6, 而对 func2 的调用会返回 4•0=0。

大多数编译器不会试图判断一个函数是否没有副作用，如果没有，就可能被优化成像func2 中的样子。相反，编译器会假设最糟的情况，并保持所有的函数调用不变。

内联函数替换优化函数调用

对func1进行内联优化

I* Result of inlining fin func1 *I 
long func1in0 { 
long t = counter++; 
t += counter++; 
t += counter++; 
t += counter++; 
return t; 
 
}

这样的转换既减少了函数调用的开销，也允许对展开的代码做进一步优化。

当优化等级-o1 者更高的等级时,GCC会尝试内联替换
在某些情况下，最好能阻止编译执行内联替换
如果一个函数调用已经用内联替换优化过了，那么任何对这个调用进行追踪或设置断点的尝试都会失败
用内联替换消除的函数调用是无法被正确剖析的。

表示程序性能

引入度量标准每元素的周期数 (Cycles Per Element, CPE), 作为一种表示程序性能并指导我们改进代码的方法。

/* Compute prefix sum of vector a */
void psum1(float a[], float p[], long n)
{
    long i; 
    p[0] = a[0]; 
    for (i=1; i<n; i++)
        p[i] = p[i-1] + a[i];
}
void psum2(float a[], float p[], long n)
{
    long i; 
    p[0] = a[0]; 
    for (i = 1; i < n-1; i+=2) {
        float mid_val = p[i-1] + a[i]; 
        p[i]= mid_val; 
        p[i+1] =mid_val + a[i+1];
    }
    /* For even n, finish remaining element */
    if (i<n)
        p[i] = p[i-1] + a[i];
}

函数psum2使用了2*1循环展开。相较于psum1循环次数为n次，循环次数降为n/2次。psum1进行三次访存，psum2进行五次访存。不难得出psum2运行速度将快于psum1。

我们也可以重写pnum1减小内存访问次数来提高程序性能。

 void psumla(float a[], float p[J, long n) 
{
   long i; 
 float last_val, val; 
 last_val = p[O] = a[O]; 
 for (i = 1; i < n; i ++) { 
 val = last_val + a [i] ; 
 p[i] = val; 
 last_val = val; 
 } 
}

程序示例

combine1

通过使用编译时常数 IDENT OP 的不同定义，这段代码可以编译成对数据执行不同的运算。

I* Implementation vith maximum use of data abstraction *I 
void combine1(vec_ptr v, data_t *dest) 
{ 
long i; 
*dest = !DENT; 
for (i = O; i < vec_length(v); i++) { 
data_t val; 
get_vec_element(v, i, &val); 
*dest = *dest OP val; 
} }

消除循环的低效率

combine2

1 /* Move call to vec_length out of loop*/
2 void combine2(vec_ptr v, data_t *dest) 
3 { 
4 long i; 
5 long length= vec_length(v); 
6 
7 *dest = IDENT; 
8 for (i = O; i < length; i++) { 
9 data_t val; 
10 get_vec_element(v, i, &val); 
11 *dest =*dest OP val; 
12 } 
13 }

这个优化是一类常见的优化的一个例子，称为代码移动 (code motion) 。这类优化包括识别要执行多次（例如在循环里）但是计算结果不会改变的计算因而可以将计算移动到代码前面不会被多次求值的部分。在本例中，我们将对 vec_length 的调用从循环内部移动到循环的前面。

大小写转换

1 I* Convert string to lowercase: slow *I 
2 void loweri(char *S) 
3 { 
4 long i; 
5 
6 for (i = O; i < strlen(s); i++) 
7 if (s [i] >='A'&& s [i] <='Z') 
8 s [i] -= ('A'-'a') ; 
9 } 
10 
11 I* Convert string to lowercase: faster *I 
12 void lower2(char *s) 
13 { 
14 long i; 
15 long len = strlen(s); 
16 
17 for (i = O; i < len; i++) 
18 if (s[i] >='A'&& s[i] <='Z') 
19 s [i) -= ('A'-'a') ; 
20 } 
21 
22 I* Sample implementation of library function strlen *I 
23 I* Compute length of string *I 
24 size_t strlen(const char *s) 
25 { 
26 long length = 0; 
27 while (*s !='\0') { 
28 s++; 
29 length++; 
30 } 
31 return length; 
32 }

对于一个长度为 n的字符串， strlen 所用的时间与 n平方成正比。因为对 lowerl 次迭代的每一次都会调用 strlen, 所以 lowerl 的整体运行时间是字符串长度的二次项，正比于 $n^2$ 。

lower2显然是线性的。

一个有经验的程序员工作的一部分就是避免引入这样的渐近低效率。

减少过程调用

combine3

data_t *get_vec_start(vec_ptr v) 
{ 
return v->data; 
} 

I* Direct access to vector data *I 
void combine3(vec_ptr v, data_t *dest) 
{ 
long i; 
long length= vec_length(v); 
data_t *data= get_vec_start(v); 
*dest = !DENT; 
for (i = O; i < length; i++) { 
*dest = *dest OP data[i]; 
} 
}

消除不必要的内存调用

assembly of combine3:

通过引入中间变量，我们可以消除不必要的内存调用。我们得到combine4。

combine4


/• Accumulate result in local variable•/ 
void combine4(vec_ptr v, data_t•dest) 
{ 
long i; 
long length= vec_length(v); 
data_t•data= get_vec_start(v); 
data_t acc = !DENT; 
for (i = O; i < length; i++) { 
ace= ace OP data[i); 
} 
*dest = ace; }

assembly of combine4:

编译器未进行优化的原因

combine3 将它的结果累积在目标位中，在本例中，目标位置就是量的最后一个元素。因此，这个值首先被设置为 1’，然后设为 2•1 =2, 然后设为3 •2=6 。最后一次迭代中，这个值会乘它自己，得到最后结果 36 。对于 combine4情况来说直到最后向都保持不变，结束最后一个元素会被设置为计算出来的值1 • 2 • 3 • 5 = 30。程序的行为被改变，因此编译器只能保守的优化代码。

理解现代处理器

概念

指令集并行：同时对多条指令进行求值
延迟界限 (latency bound)：当一系列操作必须按照严格顺序执行时，就会遇到延迟界限 (latencybound), 因为在下一条指令开始之前，这条指令必须结束。
吞吐量界限 (throughput bound) ：刻画了处理器功能单元的原始计算能力。这个界限是程序性能的终极限制。

整体操作

我们假想的处理器设计是不太严格地基千近期的 Intel 处理器的结构。

超标量 (superscalar) , 意思是它可以在每个时钟周期执行多个操作，

乱序的 (out of order) , 意思就是指令执行的顺序不定要与它们在机器级程序中的顺序一致。

整个设计有两个主要部分：

指令控制单元 (Instruction Control Unit, ICU) ：负责从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作

执行单元 (Execution Unit, EU)：后者执行这些操作。

ICU 从指令高速缓存 (instruction cache) 中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近访问的指令。通常， ICU 会在当前正在执行的指令很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到 EU 。
分支预测 (branch prediction)，处理器会猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行 (speculative execution)的技术，处理器会开始取出位千它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。标记为取指控制的块包括分支预测，以完成确定取哪些指令的任务。

ICU 中，退役单元 (retirement unit)记录正在进行的处理，并确保它遵守机器级程序的顺序语义。
寄存器重命名 (register renaming)：控制操作数在执行单元间传送的最常见的机制称为寄存器重命名 (register renaming) 。当一条更新寄存器的指令译码时，产生标记 t, 得到一个指向该操作结果的唯一的标识符。条目 (r, t) 被加入到一张表中，该表维护着每个程序寄存器与会更新该寄存器的操作的标之间的关联。当随后以寄存器作为操作数的指令译码时，发送到执行单元的操作会包作为操作数源的值。当某个执行单元完成第一个操作时，生成一个结果 (v, t)’ 指明标记为的操作产生值。所有等待作为源的操作都能使用作为源值，这就是一种形式的数据转发。通过这种机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件再读出来，使得第二个操作能够在第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目当一条被译码的指令需要寄存器 r, 而又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。有了寄存器重命名，即使只有在处理器确定了分支结果之后才能更新寄存器，也可以预测着执行操作的整个序列。

功能单元的性能

一个是延迟 (latency), 它表示完成运算所需要的总时间；
另一个是发射时间 (issue time), 它表示两个连续的同类型的运算之间需要的最小时钟周期数；
还有一个是容量 (capacity), 它表示能够执行该运算的功能单元的数量。

流水线化的功能单元实现为一系列的阶段(stage) , 每个阶段完成一部分的运算。发射时间为1的功能单元被称为完全流水线化的 (fully pipelined) : 每个时钟周期可以开始一个新的运算。
除法器（用于整数和浮点除法，还用来计算浮点平方根）不是完全流水线化的—— 它的发射时间等于它的延迟。这就意味着在开始条新运算之前，除法器必须完成整个除法。我们还看到，对千除法的延迟和发射时间是以范围的形式给出的，因为某些被除数和除数的组合比其他的组合需要更多的步骤。除法的长延迟和长发射时间使之成为了一个相对开销很大的运算。
最大吞吐量：表达发射时间的一种更常见的方法是指明这个功能单元的最大吞吐量，定义为发射时间的倒数。一个完全流水线化的功能单元有最大的吞吐量，每个时钟周期一个运算，而发射时间较大的功能单元的最大吞吐量比较小。具有多个功能单元可以进一步提高吞吐量。对一个容量为 C, 发射时间为 I的操作来说，处理器可能获得的吞吐量为每时钟周期 C/I个操作。比如，我们的参考机可以每个时钟周期执行两个浮点乘法运算我们将看到如何利用这种能力来提高程序的性能。

延迟界限给出了任何必须按照严格顺序完成合并运算的函数所需要的最小 CPE 值。
根据功能单元产生结果的最大速率，吞吐量界限给出了 CPE 的最小界限。

处理器操作的抽象模型

只读：这些寄存器只用作源值，可以作为数据，也可以用来计算内存地址，但是在循环中它们是不会被修改的。循环 combine4 的只读寄存器是 rax
只写：这些寄存器作为数据传送操作的目的。在本循环中没有这样的寄存器。
局部：这些寄存器在循环内部被修改和使用，迭代与迭代之间不相关。在这个循环中，条件码寄存器就是例子： crnp 操作会修改它们，然后 jne 操作会使用它们，不过这种相关是在单次迭代之内的。
循环：对于循环来说，这些寄存器既作为源值，又作为目的，一次迭代中产生的值会在另一次迭代中用到。可以看到， %rdx %xmm0 combine4 的循环寄存器，对应千程序

循环寄存器之间的操作链决定了限制性能的数据相关

关键路径 (critical path), 这是执行一组机器指令所需时钟周期数的一个下界。

循环展开

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

把这个思想归纳为对一个循环按任意因子k进行展开，由此产生 k*l 循环展开。

循环展开能够从两个方面改进程序的性能。

首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。
第二，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。

combine5

1 I* 2 x 1 loop unrolling *I 
2 void combine5(vec_ptr v, data_t *dest) 
3 { 
4 long i; 
5 long length= vec_length(v); 
6 long limit = length-1 ; 
7 data_t *data = get_vec_start(v); 
8 data_ t ace = !DENT; 
9 
10 I* Combine 2 elements at a time *I 
11 for (i = O; i < limit; i+=2) { 
12 ace = (ace OP data [i]) OP data [i +1] ; 
13 } 
14 
15 I* Finish any remaining elements *I 
16 for (; i < length; i++) { 
1 7 ace = ace OP data [i] ; 
18 } 
19 *dest = ace; 
20 }

我们看到对于整数加法， CPE 有所改进，得到的延迟界限为 1. 00 会有这样的结果。是得益于减少循环开销操作相对于计算向和所需要的加法数，降低开销操作的数。此时，整数加法的一个周期的延迟成为了限制性能的因素。

但是对于

用优化等级3或更高等级调用 GCC, 它就会执行循环展开。

多个累计变量

combine6


/• 2 x 2 loop unrolling•/ 
void combine6(vec_ptr v, data_t•dest) 
{ 
long i; 
long length= vec_length(v); 
long limit = length-1; 
data_t•data= get_vec_start(v); 
data_ t accO = !DENT; 
data_t acc1 = !DENT; 
I* Combine 2 elements at a time *I 
for (i = O; i < limit; i+=2) { 
accO = accO OP data[i]; 
acc1 = acc1 OP data[i+1]; 
} 
I* Finish any remaining elements *I 
for (; i < length; i++) { 
accO = accO OP data[i]; 
} 
*dest = accO OP accl; }

可以看到我们成功突破了延迟界限，处理器不再需要延迟一个加法或乘法操作以待前一个操作完成。

重新结合变换


I* 2 x 1a loop unrolling *I 
2 void combine7(vec_ptr v, data_t *dest) 
3 { 
4 long i; 
5 long length= vec_length(v); 
6 long limit= length-1; 
7 data_t *data = get_vec_start(v); 
8 data_t ace = !DENT; 
9 
10 I* Combine 2 elements at a time *I 
11 for (i = O; i < limit; i+=2) { 
12 ace = ace OP (data [i] OP data [i +1]) ; 
13 } 
14 
15 I* Finish any remaining elements *I 
16 for (; i < length; i++) { 
1 7 ace = ace OP data [i] ; 
18 } 
19 *dest = ace· 
20 }

总的来说，重新结合变换能够减少计算中关键路径上操作的数量，通过更好地利用功能单元的流水线能得到更好的性能。大多数编译器不会尝试对浮点运算做重新结合，因为这些运算不保证是结合的。

AVX 向量寄存器数据既可以是整数也可以是浮点数。 AVX 指令可以对这些寄存器执行向量操作，比如并行执行多组数值的加法或乘法。

一些限制因素

寄存器溢出

如果我们的并行度超过了可用的寄存器数量，那么编译器会诉诸溢出 (spilling), 将某些临时值存放到内存中，通常是在运行时堆栈上分配空间。

一旦编译器必须要诉诸寄存器溢出，那么维护多个累积变量的优势就很可能消失。

分支预测和预测错误处罚

不要过分关心预测的分支
书写适合用条件传送实现的代码

功能式风格

练习题5.9

理解内存性能

加载的性能

一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。

存储的性能

对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会他哪指令。另一方面，对于内存
作，只有到计算出加储的地址被计算出来以，处理器才能确定哪些指令会影响他的哪些。

应用：性能提高技术

1) 高级设计。为遇到的问题选择适当的算法和数据结构。要特别警觉，避免使用那些会渐进地产生糟糕性能的算法或编码技术。
2) 基本编码原则。避免限制优化的因素，这样编译器就能产生高效的代码。
• 消除连续的函数调用。在可能时，将计算移到循环外。考虑有选择地妥协程序的模块性以获得更大的效率
• 消除不必要的内存引用。引入临时变量来保存中间结果只有在最后的值计算出来时，才将结果存放到数组或全局变量中
3) 低级优化。结构化代码以利用硬件功能。
• 展开循环，降低开销，并且使得进一步的优化成为可能。通过使用例如多个累积变址和重新结合等技术，找到方法提高指令级并行。
• 用功能性的风格重写条件操作，使得编译采用条件数据传送。

确认和消除性能瓶颈

小结

这个编译器明明很强却过分谨慎。了解到编译器是如何优化程序的，我们也就要写出编译器能识别并优化程序的代码。