参考文章：
计算机系统课程 笔记总结 CSAPP第五章 优化程序性能（5.1-5.14）_頔潇的博客-CSDN博客
CSAPP 第五章: 优化程序性能 - 码农教程 (manongjc.com)
介绍、
首先，在开始着手优化程序性能之前，需要考虑现有程序的算法和数据结构，先优化算法和数据结构。这种优化获得的提升是数量级的提升，比如从 O(n^2) 复杂度到 O(n) 复杂度，这种理论上复杂度的优化，在数据量上去之后，效果明显。
接下来就是要相信编译器是很聪明的，它帮助你做很多性能优化，gcc 开启 -O 选项进行优化。但是呢，我们需要认识到编译器的界限在哪里，编译器不会帮你做哪些优化。对于编译器，它要考虑的是如何保证优化后程序的行为一致。因为一些问题的存在，编译器无法确定是否可以优化。最典型的问题是 memory aliasing，出现的场景是两个指针指向同一块内存地址。函数可能有 side effect，所以函数调用不会被轻易的优化，除非是 inline。知道了编译器能与不能，就可以写出编译器比较好优化的代码了。
最后是基于对现有处理器结构的理解，对内存层级的理解进行优化。现代处理器中处理指令和执行指令一般是分开的，处理指令的地方我们称之为 ICU(Instruction control unit)，执行指令的地方我们称之为 EU(Execution unit)。ICU 负责取指令，将指令解码成更小的可执行单元。EU 负责接收这些更小的可执行单元，这些分解的操作可以并行执行，因此可以利用这一点对程序进行优化。这章提到了三个优化的技巧：Loop Unrolling, Multiple Accumulators, Reassociation Transformation。此外，现代处理器还提供了 SIMD(Single Instruction Multiple Data)，单条指令，多个数据，使用这些指令可以获取更好的并行度，从而进一步提高程序性能。
这一章很重要的一个知识点是数据流图的分析，借助数据流图的分析，我们找到并定位程序的性能瓶颈。在分析数据流图的时候，需要意识到处理器的流水线特性。一个指令可以分解为多个小操作，这些小操作可以流水并行。因此在使用数据流图分析的时候，要考虑这一点。
优化技巧、
（1）Eliminating Loop Inefficiencies，减少循环时低效调用和过程调用，比如 for 循环当中检查边界，如果每次都调用一个方法获取长度，这将大大增加时间消耗，更坏的情况是导致了算法复杂度的改变。
例如下面的代码，将一个字符串全部转换为小写：
void lower(char*const p)
{
for (size_t i = 0; i < strlen(p); ++i)
{
if (p[i] >= 'A' && p[i] <= 'Z')
{
p[i] -= ('A' - 'a');
}
}
}
size_t strlen(const char* p)
{
size_t length = 0;
while(*p != '\0')
{
++length;++p;
}
return length;
}
'a'-'A' 这是用来大小写字母转换的，在ASCII码里面26个小写字母依次排列，他们的值依次差1.大写字母也是一样的。但是大小写字母数值不是连在一起的，小写的都比大写的大。如果要将一个小写字母转换成大写的，那么要么用那个小写字母减去之间的固定差值就能得到对应的大写字母，你写的这个'a'-'A'就是用来计算这个固定差值的。用这个差值就能实现大小写的转换，可以对照着ASCII码表看一下就明白了。
这个代码看起来没有任何的问题，实际上也没有任何的问题，但是却存在性能不好的情况。如果输入的字符串是一个50万长度的字符串，那么这个函数的性能将会很低很低。原因是在循环中不断调用了 strlen() 这个函数，调用的次数是字符串长度的次数，将近50万次非常大，这个函数是求字符串大小的函数，每次调用都会从字符串的头部遍历这个字符串直到第一个为 '\0' 的字符，这个操作是一个线性操作，执行过程中字符串长度不断减少，但是执行的速度却不是很快，基本上是一个二次的操作，因此这个性能将会很低。
我们可以做一些改动，使其性能提升。如下所示，经过测验在字符串几十万甚至上百万时，性能非常高。
void lower(char*const p)
{
size_t n = strlen(p); //引入一个局部变量来表示字符串长度这个不变的数
for (size_t i = 0; i < n; ++i)
{
if (p[i] >= 'A' && p[i] <= 'Z')
{
p[i] -= ('A' - 'a');
}
}
}（2）Eliminating Unneeded Memory References，减少不必要的内存引用。使用一个寄存器变量做临时读写，将最后的结果写入到内存中。如果每次都写入内存，那么会很低效。
数值需要从内存中读出，再写入，浪费内存引用时间。我们注意到这种操作涉及到了CPU从数据总线中向内存中取值，通常速度远远慢于CPU本身的计算操作，也慢于CPU取出内部寄存器值的操作，很多时候，一个程序的计算瓶颈就在这些去内存的操作中，因此要尽量避免不必要的内存引用。以下举个代码例子进行进一步说明。
void foo(double* p, size_t len, double* addr)
{
for (size_t i = 0; i < len; ++i)
{
*addr += p[i];
}
}void foo(double* p, size_t len, double* addr)
{
double tmp = 0;
for (size_t i = 0; i < len; ++i)
{
tmp += p[i];
}
*addr = tmp;
}第一种方式是每一个循环中都进行更新，显然其需要更多但是却没必要的内存引用，第二种通过一个临时变量的形式，避免了多次频繁无用地访问内存。观察其两者的汇编，就会发现和我们之前分析的是一致的。因此我们要养成引入局部变量的习惯。
(3）Loop Unrolling，循环展开。for 循环每次步进 2 或者更多，提供指令级别并行。
循环展开技术是一种提升程序执行速度的非常有效的优化方法，它可以由程序员手工编写，也可由编译器自动优化。循环展开的本质是，利用CPU指令级并行，来降低循环的开销，当然，同时也有利于指令流水线的高效调度。例如下面的例子：
void f(void)
{
int x[100];
size_t i;
for (i = 0; i < 100; i++) {
x[i] = 10；
}
}循环展开的写法如下：
void f(void)
{
int x[100];
size_t i;
for (i = 0; i < 100; i+=2) {
x[i+0] = 10；
x[i+1] = 10；
}
}注意，这里递增步长 i += 2，就是说，循环次数从原来的100次，减少为循环 100/2 = 50次了。注意这里步进的是偶数，因此对于偶数次循环不会发生缓冲区溢出或者数组越界，但是对于奇数次循环则会出现问题。
其实在我们开启了编译器优化的时候，编译器会自动对我们的循环代码进行循环展开，让我们可以在保持了代码可读性的同时，又能享受到循环展开对我们程序性能的提高。
循环展开的优点：
第一，减少了分支预测失败的可能性。
第二，增加了循环体内语句并发执行的可能性，当然，这需要循环体内各语句不存在数据相关性。
循环展开的缺点：
第一，造成代码膨胀，导致ELF文件（或Windows PE文件）尺寸增大。
第二，代码可读性显著降低，前一个人写的循环展开代码，很可能被不熟悉的后续维护人员改回去。
（4）Multiple Accumulators，使用多个累积变量。从数据流图的角度去分析，使用多个累积变量可以获得更好的指令并行。
（5）Reassociation Transformation。算术运算的时候，可以先计算某些部分来获得更好的指令并行。
（6）SIMD，从指令级别的角度看，使用单条指令多条数据去加速并行。
（7）Register Spilling。如果使用了太多累积变量，超过了寄存器的数量，那么会开始使用放在内存中的栈变量，这样将会导致访存，使性能下降。
（8）现代处理器采用了乱序执行的策略，对于分支执行，它会选择一个分支直接执行，如果分支预测错误了，那么将会清理环境，重新取指令，重新执行。为了减少这种分支预测错误带来的代价，可以使用 Conditional Moves 类别的指令来减少分支预测错误的代价。
（9）Do Not Be Overly Concerned about Predictable Branches。不用过多担心分支预测。因为很多情况下，分支预测的结果往往是正确的，只有最后一个元素预测错误，比如判断 index 是否已经在数组的边界等操作。不过对于一些比较随机的判断，分支预测的性能却不会很好，所以这些随机的分支判断可以使用 Conditional Moves 进行优化。
Comments NOTHING