跳转至

Chapter 5 优化程序性能

1）引入：编写高效程序的要求

  • 必须选择一组合适的算法与数据结构
  • 编写出编译器能够有效优化以转换成高效可执行代码的源代码
  • 将一个任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行的计算（利用并行性每个并行的线程都以最高性能执行）
  • 研究程序的汇编代码是理解编译器以及产生的代码会如何运行的最有效手段之一

2）优化编译器的能力与局限性

1. 常见的编译器优化控制：

-Og: 让gcc做一组基本的优化 -O1 / -O2 / -O3: 让gcc做更大量的优化，进一步提高程序的性能

2. 制约优化的安全性因素：

思考为什么上述的gcc优化不能无限“进步”？ 因为有（1）内存别名使用 & （2）函数调用副作用 等产生意想不到的后果 因此：编译器必须很小心地对程序只进行安全的优化！

[1] 内存别名使用：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void f1(long *xp,long *yp)
{
    *xp += *yp;
    *xp += *yp;
}

void f2(long *xp,long *yp)
{
    *xp += 2*(*yp);
}
1. 乍一看这两个函数实现的功能完全一样，它们都是将存储在由指针yp指向的位置处的值加到指针xp指向的位置处的值 2. 再一看：f2的效率高于f1 （f2只有三次内存引用：读*xp，读*yp，写*xp）（f1需要六次内存引用：2x读*xp，2x读*yp，2x写*xp） 3. 这时会不由自主的想到：是不是f2可以作为f1代码的优化版本？ 4. 事实上并不是！仔细思考：

当xp==yp时：此时f1进行的运算会将xp的原值增加4倍；f2的运算会将xp的原值增加3倍！ 此时就产生了分歧！！！ 编译器不知道f1会如何调用，因此它必须假设参数xp和yp可能会相等！ 因此它不能产生f2风格的代码作为f1的优化版本

  • def(内存别名使用，memory aliasing)：两个指针可能指向同一个内存位置的情况
  • 在只执行安全的优化中，编译器必须考虑到“内存别名使用”的特殊情况，这在某种程度上也就限制了可能的优化策略
[2] 函数调用副作用：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
long f();

long f1()
{
    return f() + f() + f() + f();
}

long f2()
{
    return 4 * f();
}
1. 乍一看这两个函数实现的功能完全一样，都是将f()调用得到的返回值x4 2. 再一看：f2的效率高于f1（f2只调用一次f；f1调用了四次f） 3. 这时会不由自主的想到：是不是f2可以作为f1代码的优化版本？ 4. 事实上并不是！仔细思考： 考虑这样的函数f：
C++
1
2
3
4
5
long counter = 0;
long f()
{
    return counter++;
}

此时： 对f1的调用：返回0+1+2+3 = 6 对f2的调用：返回4x0 = 0 产生分歧！ 绝大多数编译器不会主动去判断一个函数是否有副作用 因此它不能产生f2风格的代码作为f1的优化版本

  • 如果这个函数没有副作用，它就可能被优化成f2中的模样；反之，编译器会假设最bad的情况，并保持所有函数调用不变！这在某种程度上也就限制了可能的优化策略！
  • 可以使用内联函数(inlining)进行优化

3）表示程序性能

度量标准：每元素的周期数（Cycles Per Element, CPE）

4）消除循环带来的低效率

一种常见的优化方案叫做“代码移动”(code motion)
  1. def(代码移动)：识别程序中会执行多次(eg：for循环)，但是计算结果始终不变的计算操作，因而可以将该计算移动到代码前面不会被多次求值的部分
  2. 例子：
    C++
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    源代码：
string str;
cin >> str;
for(int i=0;i<strelen(str);i++)
{
    ......
}

这样的代码并不好，因为每一次的循环都会单独计算一遍strlen(str)
实际上此处的strlen(str)是定值
因此不妨将strlen(str)提前计算，然后带入，减少不必要的计算量

修改后：
string str;
cin >> str;
int hbx = strelen(str);
for(int i=0;i<hbx;i++)
{
    ......
}
  3. 这里很好地说明了一个常见的问题：一个看上去无足轻重的代码片段有隐藏的渐近低效率(asymptotic inefficiency)

5）减少过程调用

没啥特别的...

6）减少不必要的内存引用

没啥特别的...

7）理解现代处理器

  • 当一系列操作必须严格按照顺序执行时：就会遇到延迟界限(latency bound)，因为在下一条指令开始之前，这条指令必须结束
  • 当代码中的数据相关限制了处理器利用指令级并行的能力时，延迟界限能够限制程序性能
  • 吞吐量界限(throughput bound)刻画了处理器功能单元的原始计算能力，这个界限是程序性能的终极限制

（1）整体操作：

这里我们主要考虑的是乱序处理器，它需要更大更复杂的硬件，但是能够达到更好的指令集合并行度

![[Pasted image 20231118143035.png]] 1. 整个设计主体分为两个部分： [1] 指令集控制单元(ICU)： 负责从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作 [2] 执行单元(EU)： 负责执行这些操作

  1. ICU从指令高速缓存(instruction cache)中读取指令： [1] 指令高速缓存是一个特殊的高速存储器，包含最近访问的指令 [2] 通常情况下：ICU会在当前正在执行的指令很早之前就取指，这样它才有足够的时间对指令译码，并将操作发到EU [3] 一个常见的问题是：当程序遇见分支时，可能有两个选择：(1)选择分支，“控制”被传送到分支目标 ；(2)不选择分支，“控制”直接下移到下一条指令 [4] 现在处理器采用的是==“分支预测(branch prediction)”技术，处理器会猜测是否选择分支，同时还猜测分支的目标地址；使用“投机执行(speculative execution)”==的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对照指令译码。如果事后确定分支预测错误，会将状态重新设置回分支点的原状态，并开始取出和执行另一个方向上的指令 [5] 取指控制的block包括分支预测，以完成确定取哪些指令的任务

  2. 指令译码逻辑接收实际的程序指令，并将它们转换成一组基本操作，每个这样的操作都完成某个简单的计算任务

  3. EU接收来自取指单元的操作： [1] 通常，每个时间周期内会接受多个操作，这些操作会被派送到一组功能单元中 [2] 功能单元：专门用来处理不同类型的操作

  4. 读写内存是使用加载和存储单元来实现的： [1] 加载单元：处理==从内存读数据到处理器==的操作，它有一个加法器可以进行地址计算 [2] 存储单元：处理==从处理器写数据到内存==的操作，它也有一个加法器可以进行地址计算 [3] 加载和存储单元通过“数据高速缓存(data cache)”来访问内存 [4] 数据高速缓存：是一个高速存储器，存放着最近访问的数据值

  5. 回忆一下2.中的“投机执行”技术： [1] 使用“投机执行”技术对操作求值，直至处理器能确定“确实应该实际执行这些指令”之前，最终==结果都不会存放在程序寄存器or数据内存==中 [2] 之前提到的“分支控制被送到EU”，并不是确定分支该向哪里去，而是确定分支预测是否正确！ [3] 如果预测false：EU会丢弃分支点之后计算出来的结果(即我们预测的，且被证实错误的结果)，并且发信号给分支单元，说：“预测是错误的！”，并指出正确的分支目的地；此时：分支单元开始在新的位置取指 [4] 如果预测true：结果将会存放在程序寄存器or数据内存中

[evaluation] 这种“预测行为”具有不确定性，一旦发生“预测错误”会导致极大的性能开销。在可以取出新指令/译码 和 发送到执行单元之前，要花费一点时间！

  1. 不同的功能单元被设计来执行不同的操作： 功能单元的这种组合具有同时执行多个同类型操作的潜力

  2. 在ICU中：退役单元(retirement unit) 记录正在进行的处理，并确保它遵循机器级程序的顺序语义 [1]图中有一个寄存器文件在退役单元中，因为退役单元控制着这些寄存器的更新 [2]指令译码时：关于指令的信息被放置在一个先进先出的队列中，除非发生下列2种情况之一，否则不会退出队伍：

  3. 一条指令的==操作完成==，且所有引起这条指令的分支点也都被确认为==“预测正确”==，那么这条==指令就可以retire(退役)==了！所有对程序寄存器的更新也就可以被实际执行了！

  4. 如果某个引起这条指令的分支点显示==“预测错误”，这条==指令就会被flushed(清空)，丢弃之前所有计算出来的结果 [3]这样达到的目的是：预测错误也不会改变程序状态

  5. 正如上面所说：任何对程序寄存器的更新都只会在指令退役后才会发生，只有在处理器确信导致这条指令的所有指令都预测正确了，才会这么做

  6. 控制操作数在执行单元间传送的最常见机制是“寄存器重命名(register renaming)”： [1]具体过程省略 [2]通过这种机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件再读出来，这样可以使第二个操作在第一个操作完成后尽快开始

（2）功能单元的性能：

每个运算都是由下面三个参数进行衡量的： 1）延迟(latency)：完成运算所需要的总时间 2）发射时间(issue time)：两个连续的同类型运算之间需要的最小时钟周期数 3）容量(capacity)：能够执行该计算的功能单位的数量

其余略

8）循环展开：

没啥特别的...

9）提高并行性：

  1. 设置多个累积变量（每一部分相对量减少）
  2. 重新结合变换（括号位置随便换）
  3. 使用向量指令

10）review：

上述三级标题中：5/6/8/9是程序🦍日常生活中可以手动调节的优化方法
但是即使我们这样，依然存在很多值得性能优化的点：这些就是物理层面的限制因素了！

11）一些限制因素

（1）寄存器溢出

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

（2）分支预测&预测错误处罚

  • 正如上面对现代处理器的具体介绍：当分支预测逻辑不能正确预测一个分支是否要跳转时，条件分支可能会招致很大的“预测错误处罚”！
  • 在一个使用“投机执行”的处理器中，处理器会开始执行预测的分支目标处的指令，它会避免修改任何实际的存储器or内存位置，直到确定了实际的结果
  • 如果预测true：结果将会存放在程序寄存器or数据内存中
  • 如果预测false：EU会丢弃分支点之后计算出来的结果(即我们预测的，且被证实错误的结果)，并且发信号给分支单元，说：“预测是错误的！”，并指出正确的分支目的地。这样做就会引起“预测错误处罚”，因为在产生有用的结果之前，必须重新填充命令流水线

gcc目前有一种不错的“命令风格”的处理方法： 翻译成条件传送的基本思想是计算出一个条件表达式or语句两个方向上的值，然后用条件传送选择期望的值

有两个中肯的建议： - 不要过分关心可预测的分支 - 书写适合使用条件传送实现的代码

12）理解内存性能

这一小节补充交代的是：现代处理器EU部分中“功能单元”的加载与存储单元 所有的现代处理器都包含一个或多个“高速缓存(cache)存储器”，以对这样少量的存储器进行快速的访问

  • 加载：从内存读到寄存器
  • 存储：从寄存器写到内存
（1）加载单元的性能：
  • 既依赖于流水线的能力，也依赖于加载单元的延迟
  • "CPE" 通常指的是 "Clocks Per Instruction"，即每条指令的时钟周期数
  • 对于任何数据类型的组合与合并操作，CPE从没有低于0.50
  • 一个制约CPE的因素是，对于每个要计算的元素，所有的示例都需要从内存中读一个值
  • 对于每个被计算的元素必须加载k个值的应用而言：我们不可能获得低于k/2的CPE
（2）存储单元的性能：

内存操作的实现有很多细微之处： - 对于寄存器操作：在指令被译码成操作的时候，处理器就可以确定哪些指令会影响其他哪些指令 - 对于内存操作：只有到加载和存储的地址被计算出来之后，处理器才能确定哪些指令会影响其他的