目录
Part2. Source Code Tuning For CPU
数据驱动优化
7 CPU Front-End Optimizations
7.1 Machine code layout //机器码布局
7.2 Basic Block
7.3 Basic block placement
7.4 Basic block alignment
7.5 Function splitting //函数拆分
7.6 Function grouping //函数分组
7.7 Profile Guided Optimizations //基于性能分析的优化
7.8 Optimizing for ITLB
7.9 Chapter Summary
8 CPU Back-End Optimizations
8.1 Memory Bound //内存受限
8.2 Core Bound //核心受限
8.3 Chapter Summary
9 Optimizing Bad Speculation
9.1 Replace branches with lookup //将分支替换为查找表
9.2 Replace branches with predication
9.3 Chapter Summary
10 Other Tuning Areas
10.1 Compile-Time Computations //编译时计算
10.2 Compiler Intrinsics //编译器内置函数
10.3 Cache Warming //缓存预热
10.4 Detecting Slow FP Arithmetic
10.5 System Tuning
11 Optimizing Multithreaded Applications
11.1 Performance Scaling And Overhead //性能扩展和开销
11.2 Parallel Efficiency Metrics //并行效率指标
11.3 Analysis With Intel VTune Profiler
11.4 Analysis with Linux Perf
11.5 Analysis with Coz
11.6 Analysis with eBPF and GAPP
11.7 Detecting Coherence Issues
11.8 Chapter Summary
Epilog
Appendix A. Reducing Measurement Noise
Appendix B. The LLVM Vectorizer
Part2. Source Code Tuning For CPU
在第二部分中，我们将了解如何使用CPU监测功能（参见第6节）来找到可以针对CPU执行调优的代码部分。对于像大型分布式云服务、科学高性能计算软件、AAA游戏等性能关键应用程序来说，了解底层硬件如何工作非常重要。如果在开发过程中没有关注硬件，那将是一次从一开始就失败的尝试。
在对性能至关重要的工作负载进行处理时，传统的算法和数据结构并不总是表现良好。例如，链表在大多数情况下已经被“扁平”数据结构所取代。传统上，链表的每个新节点都是动态分配的。除了涉及许多昂贵的内存分配操作外，这可能导致列表的所有元素在内存中分散存储。遍历这样的数据结构需要为每个元素进行随机内存访问。尽管算法复杂度仍然是O(N)，但实际上，执行时间比普通数组要差得多。某些数据结构（如二叉树）具有天然的链表表示形式，因此可能会诱使我们以指针追踪的方式实现它们。然而，更高效的“扁平”版本的这些数据结构也存在，比如boost::flat_map、boost::flat_set。
链表优于数组的原因：
链表相对于数组具有一些优点，这些优点使得它在某些情况下比数组更加有效或适用：
1. 动态大小：链表的大小可以动态地增长或缩小，不需要提前分配固定大小的存储空间。这使得链表对于处理需要频繁插入或删除操作的情况更加灵活和高效。
2. 插入和删除操作：在链表中进行插入和删除元素的操作较为高效。相比之下，对于数组而言，在插入或删除元素时通常需要移动其他元素，这可能会导致较高的时间复杂度。
3. 内存管理：链表的节点可以根据需要进行动态分配和释放，因此可以更好地管理内存。相比之下，数组需要一次性分配固定大小的连续内存块。
4. 灵活性：链表可以具有不同的结构，如单向链表、双向链表、循环链表等。这使得链表在某些问题的解决方案中更加灵活和多样化。
尽管链表有以上优点，但也存在一些缺点。链表的缺点包括无法通过索引直接访问元素、占用更多的内存空间（由于存储了指向下一个节点的指针）和遍历时需要更多的时间（需要通过指针逐个访问节点）。因此，在选择数据结构时，需要根据具体情况和需求权衡利弊。
即使您选择的算法在特定问题上表现最好，但对于您特定的情况可能并非最佳选择。例如，二分查找在已排序数组中查找元素是最优的。然而，该算法通常受到分支预测错误的影响，因为每次测试元素值时，有50%的机会为真。这就是为什么在小型（少于20个元素）整数数组中，线性搜索通常更好的原因。
性能工程是一门艺术，就像任何艺术一样，可行的场景是无穷无尽的。本章试图解决与CPU微架构相关的优化问题，而不试图覆盖所有可能的优化机会。然而，我认为至少需要提到一些高级优化方法：
• 如果程序使用解释型语言编写（如Python、JavaScript等），可以将其性能关键部分重写为开销较小的语言。
• 分析程序中使用的算法和数据结构，看看是否可以找到更好的替代方案。
• 调整编译器选项。检查是否至少使用了以下三个编译器标志：-O3（启用与机器无关的优化）、-march（针对特定CPU代数启用优化）、-flto（启用程序间优化）。
• 如果问题可以高度并行化计算，可以使用线程，或者考虑在GPU上运行。
• 使用异步IO来避免在等待IO操作时发生阻塞。
• 利用更多的RAM来减少CPU和IO的使用量（记忆化、查找表、数据缓存、压缩等）。
以上是一些高级的性能优化方法，但请注意，在优化代码性能时并非适用于所有情况。具体的优化策略应该根据实际情况和需求进行权衡和选择。
数据驱动优化
“数据驱动”优化是调优中最重要的技术之一，它基于对程序正在处理的数据进行内省。该方法侧重于数据的布局以及在程序中如何进行转换。一个经典的例子是Structure-Of-Array到Array-Of-Structures (SOA-to-AOS)的转换，如图14所示。
Listing 14 SOA to AOS transformation.
//SOA
struct S {
int a[N];
int b[N];
int c[N];
// many other fields
};
<=>
//AOS
struct S {
int a;
int b;
int c;
// many other fields
};
S s[N];对于哪种布局更好的问题的答案取决于代码如何访问数据。如果程序在数据结构上进行迭代并且仅访问字段b，则SOA更好，因为所有内存访问都是顺序的（空间局部性）。然而，如果程序在数据结构上进行迭代并且对对象的所有字段（即a、b、c）执行过多的操作，则AOS更好，因为结构的所有成员很可能位于同一缓存行中。它还能更好地利用内存带宽，因为需要读取的缓存行数量更少。
这类优化基于对程序所操作的数据、数据的布局以及相应的修改进行了解。
个人经验：事实上，我们可以说，在某种程度上，所有的优化都是数据驱动的。即使在下一节中我们将要介绍的转换也是基于对程序执行的一些反馈信息：函数调用计数、性能分析数据、性能计数器等。
另一个非常重要的数据驱动优化例子是"小尺寸优化"。其思想是预先分配一定量的内存给容器，以避免动态内存分配。这在小型和中型容器中特别有用，当元素的上限可以被很好预测时。这种方法已成功应用于整个LLVM基础设施，并提供了显著的性能优势（例如搜索SmallVector）。相同的概念也在boost::static_vector中实现。
显然，这并不是完整的数据驱动优化列表，但正如之前所述，没有试图列出所有的优化。读者可以在easyperf博客上找到更多的示例。
现代CPU是非常复杂的设备，几乎不可能预测某些代码片段的性能。CPU对指令的执行取决于许多因素，而涉及的部件数量对人类来说太大了，无法完全了解。幸运的是，通过我们在第6节中讨论的所有性能监控功能，我们可以知道从CPU的角度看，你的代码是什么样子。
请注意，你实施的优化可能对每个平台都不一定有益。例如，循环阻塞非常依赖于系统中内存层次结构的特性，尤其是L2和L3缓存的大小。因此，针对具有特定L2和L3缓存大小的CPU进行调优的算法可能对具有较小缓存的CPU效果不好。重要的是要在将应用程序运行的平台上进行测试更改。
接下来的三章以最便于与TMA（参见第6.1节）一起使用的方式组织。这种分类背后的思想是提供一种检查清单，工程师可以使用它来有效地消除TMA揭示的低效率。再次强调，这并不是一个完整的转换列表，因为人们可以提出更多的转换。然而，这是一个试图描述典型转换的尝试。
7 CPU Front-End Optimizations
CPU前端（FE）组件在第3.8.1节中进行了讨论。大多数情况下，CPU FE的低效率可以描述为后端等待执行指令，但FE无法提供指令的情况。结果是，在没有执行任何实际有用工作的情况下浪费了CPU周期。由于现代处理器是4宽度（即，它们每个周期可以提供四个微操作），可能出现未填充所有四个可用槽的情况。这也可能是执行效率低下的来源。实际上，IDQ_UOPS_NOT_DELIVERED性能事件记录了由于前端停顿而未利用的可用槽位数。TMA使用此性能计数器的值来计算其“前端边界”指标。
FE无法向执行单元传递指令的原因有很多。但通常归结为缓存利用和无法从内存中提取指令的问题。只有当TMA指向较高的“前端边界”指标时，才建议开始优化针对CPU FE的代码。
个人经验：大多数实际应用程序将会出现一个非零的“前端边界”指标，这意味着一定比例的运行时间将会在次优的指令获取和解码上浪费。幸运的是，这通常低于10%。如果你看到“前端边界”指标在20%左右，那么一定值得花时间进行优化。
7.1 Machine code layout //机器码布局
当编译器将您的源代码转换为机器代码（二进制编码）时，它会生成一系列的字节序列。例如，对于以下的C代码：
if (a <= b)
c = 1;编译器会产生如下的汇编代码:
; a is in rax
; b is in rdx
; c is in rcx
cmp rax, rdx
jg .label
mov rcx, 1
.label:汇编指令将按顺序进行编码，并在内存中进行布局：
400510 cmp rax, rdx
400512 jg 40051a
400514 mov rcx, 1
40051a ...这就是所谓的机器码布局。请注意，对于同一个程序，可以以许多不同的方式进行代码布局。例如，给定两个函数：foo和bar，我们可以将bar放在二进制文件中先于foo，或者反过来改变它们的顺序。这会影响指令在内存中的偏移位置，进而影响生成的二进制代码的性能。在本章的其余部分，我们将研究一些常见的机器码布局优化技巧。
7.2 Basic Block
基本块（Basic Block）是一系列指令的序列，具有单一入口和单一出口。图40展示了一个简单的基本块示例，其中MOV指令是入口指令，而JA是出口指令。虽然基本块可以有一个或多个前驱和后继，但是在中间的指令不能退出该块。
保证基本块中的每条指令将被执行一次。这是一个非常重要的属性，被许多编译器转换所利用。例如，它极大地减少了控制流图分析和转换的问题，因为对于某些问题类别，我们可以将基本块中的所有指令视为一个实体处理。
7.3 Basic block placement
假设程序中存在一个热路径，该路径在某些错误处理代码（coldFunc）之间：
// hot path
if (cond)
coldFunc();
// hot path again图41展示了该代码片段的两种可能的物理布局。图41a是大多数编译器在没有提供提示的情况下默认生成的布局。图41b所展示的布局可以通过反转条件cond并将热代码作为默认执行路径来实现。在一般情况下，哪种布局更好主要取决于cond是否通常为真。如果cond通常为真，则最好选择默认布局，否则我们将执行两次跳转而不是一次。而且，在一般情况下，我们希望内联受到cond保护的函数。然而，在这个特定的例子中，我们知道coldFunc是一个处理错误的函数，并且可能不经常被执行。通过选择41b的布局，我们保持了代码热点之间的顺序执行，并将已执行的分支转换为未执行的分支。
对于前面在本节中呈现的代码，布局41b表现更好有几个原因。首先，未执行的分支基本上比已执行的分支更便宜。一般情况下，现代英特尔CPU每个周期可以执行两个未执行的分支，但每两个周期才能执行一个已执行的分支。
其次，布局41b更好地利用了指令和uop高速缓存（DSB，请参见第3.8.1节）。由于所有热代码都是连续的，不存在缓存行碎片化问题：L1I缓存中的所有缓存行都被热代码使用。对于uop高速缓存也是如此，因为它也是基于底层代码布局进行缓存的。
最后，对于取指单元来说，已执行的分支也更昂贵。它会获取连续的16字节块，因此每个已执行的跳转意味着跳转后的字节是无用的。这降低了最大有效的取指吞吐量。
为了建议编译器生成改进的机器码布局版本，可以使用__builtin_expect161结构提供提示：
// hot path
if (__builtin_expect(cond, 0)) // NOT likely to be taken
coldFunc();
// hot path again开发人员通常会编写LIKELY辅助宏来使代码更易读，因此经常可以找到类似下面所示的代码。自C++20起，有一个标准的[[likely]]属性，应该优先使用。
#define LIKELY(EXPR) __builtin_expect((bool)(EXPR), true)
#define UNLIKELY(EXPR) __builtin_expect((bool)(EXPR), false)
if (LIKELY(ptr != nullptr))
// do something with ptr优化编译器在遇到LIKELY/UNLIKELY提示时不仅会改进代码布局，还会在其他地方利用这些信息。例如，当将UNLIKELY提示应用于本节中的原始示例时，编译器会阻止对coldFunc的内联，因为现在它知道coldFunc不太可能经常执行，而优化其大小更有益，即只保留对该函数的调用。在switch语句中插入__builtin_expect提示也是可能的，如清单15所示。
Listing 15 Built-in expect hint for switch statement
for (;;) {
switch (__builtin_expect(instruction, ADD)) {
// handle different instructions
}
}使用这个提示，编译器将能够稍微不同地重新排列代码，并优化热门的switch语句以更快地处理ADD指令。有关这种转换的更多详细信息可以在easyperf163博客上找到。
7.4 Basic block alignment
有时性能可能会根据指令在内存中的布局偏移而发生显著变化。考虑一下清单16中呈现的简单函数。
Listing 16 Basic block alignment
void benchmark_func(int* a) {
for (int i = 0; i < 32; ++i)
a[i] += 1;
}一款良好的优化编译器可能会生成适用于Skylake架构的机器码，示例如下：
00000000004046a0 <_Z14benchmark_funcPi>:
4046a0: mov rax,0xffffffffffffff80
4046a7: vpcmpeqd ymm0,ymm0,ymm0
4046ab: nop DWORD PTR [rax+rax*1+0x0]
4046b0: vmovdqu ymm1,YMMWORD PTR [rdi+rax*1+0x80] # loop begins
4046b9: vpsubd ymm1,ymm1,ymm0
4046bd: vmovdqu YMMWORD PTR [rdi+rax*1+0x80],ymm1
4046c6: add rax,0x20
4046ca: jne 4046b0
# loop ends
4046cc: vzeroupper
4046cf: ret代码本身对于Skylake架构来说是相当合理的，但其布局并不完美（参见图42a）。与数据缓存一样，指令缓存行通常是64字节长。在图42中，粗框表示缓存行边界。请注意，循环跨越多个缓存行：它从缓存行0x80 - 0xBF开始，结束于缓存行0xC0 - 0xFF。这类情况通常会导致CPU前端的性能问题，特别是对于像上面例子中的小循环而言。
为了解决这个问题，我们可以使用NOP指令将循环指令向前移动16字节，使整个循环位于一个缓存行中。图42b显示了使用NOP指令执行此操作的效果，其中用蓝色突出显示了NOP指令。需要注意的是，由于基准测试仅运行该热门循环，因此可以确保这两个缓存行都留在L1I缓存中。关于布局42b性能更好的原因并不容易解释，涉及大量的微架构细节，本书将避免详细介绍这些。
尽管CPU架构师努力在设计中隐藏这种瓶颈，但在某些情况下，代码布局（对齐）确实会对性能产生影响。如图42a所示，默认情况下，LLVM编译器会识别循环并将它们对齐到16字节边界。为了达到我们示例中所示的期望代码布局（图42b），可以使用-mllvm -align-all-blocks选项。然而，要小心使用此选项，因为它可能会降低性能。插入将被执行的NOP指令可能会给程序增加开销，特别是如果它们处于关键路径上。NOP指令不需要执行，但仍然需要从内存中获取、解码和退休。后者还会消耗FE数据结构和缓冲区中的空间，类似于所有其他指令。
为了对对齐进行细粒度控制，还可以使用ALIGN汇编指令。为了进行实验，开发人员可以发出汇编清单，然后插入ALIGN指令：
; will place the .loop at the beginning of 256 bytes boundary
ALIGN 256
.loop
dec rdi
jnz rdi7.5 Function splitting //函数拆分
函数拆分的思想是将热点代码与冷却代码分离。这种优化对于具有复杂控制流图（CFG）且在热路径中包含大量冷却代码的相对较大函数非常有益。下面是一个可能会受益于这种转换的代码示例（见清单17）。为了从热路径中删除冷却基本块，我们可以将其剪切并放入自己的新函数中，并创建对它的调用（见清单18）。
Listing 17 Function splitting: baseline version.
void foo(bool cond1, bool cond2) {
// hot path
if (cond1) {
// large amount of cold code (1)
}
// hot path
if (cond2) {
// large amount of cold code (2)
}
}Listing 18 Function splitting: cold code outlined.
void foo(bool cond1, bool cond2) {
// hot path
if (cond1)
cold1();
// hot path
if (cond2)
cold2();
}
void cold1() __attribute__((noinline)) { // cold code (1) }
void cold2() __attribute__((noinline)) { // cold code (2) }
图43对该转换进行了图形化表示。由于我们在热路径中只留下了CALL指令，下一个热指令很可能位于同一缓存行中。这提高了CPU前端数据结构（如I-cache和DSB）的利用率。
这种转换包含另一个重要的思想：禁用冷却函数的内联。即使我们为冷却代码创建一个新函数，编译器仍然可能决定将其内联，从而有效地撤消我们的转换。这就是为什么我们想要使用noinline函数属性来防止内联。另外，我们还可以在cond1和cond2分支上应用UNLIKELY宏（参见7.3节），以向编译器传达不希望内联cold1和cold2函数的意图。
最后，新函数应该在.text段之外创建，例如在.text.cold中。如果函数从未被调用，这可能会改善内存占用，因为它不会在运行时加载到内存中。
7.6 Function grouping //函数分组
根据前面章节中描述的原则，可以将热函数分组在一起，以进一步提高CPU前端缓存的利用率。当热函数被分组在一起时，它们可能共享同一缓存行，从而减少CPU需要获取的缓存行数量。
图44以图形方式表示了对foo、bar和zoo进行分组。默认布局（见图44a）需要读取四个缓存行，而在改进版本中（见图44b），foo、bar和zoo的代码只适用于三个缓存行。此外，当我们从foo调用zoo时，由于我们已经获取了那个缓存行，zoo的开头已经在I-cache中。
类似于之前的优化，函数分组提高了I-cache和DSB-cache的利用率。当存在许多小型热函数时，这种优化效果最佳。
链接器负责将程序中的所有函数按照指定的方式布局到生成的二进制输出中。尽管开发人员可以尝试自行重新排序程序中的函数，但不能保证所期望的物理布局。多年来，人们一直在使用链接器脚本来实现这个目标。如果使用GNU链接器，这仍然是一种可行的方法。
Gold链接器（ld.gold）对于解决这个问题有一个更简单的方法。为了在二进制文件中获得所需的函数顺序，可以首先使用"-ffunction-sections"标志编译代码，这将把每个函数放入单独的节中。然后，应该使用"--section-ordering-file=order.txt"选项提供一个包含按所需最终布局排序的函数名称的文件。LLD链接器也具有相同的功能，它是LLVM编译器基础设施的一部分，并通过"--symbol-ordering-file"选项进行调用。
HFSort169是一种解决将热函数分组在一起问题的有趣方法，它是一种基于分析数据自动生成节顺序文件的工具[Ottoni and Maher, 2017]。使用此工具，Facebook工程师在大型分布式云应用程序（如Facebook、百度和维基百科）中获得了2%的性能改进。目前，HFSort已集成到Facebook的HHVM项目中，不作为独立工具提供。LLD链接器采用HFSort算法的实现170，它根据分析数据对节进行排序。
7.7 Profile Guided Optimizations //基于性能分析的优化
编译程序并生成优化的汇编代码是基于启发式算法的过程。代码转换算法包含许多针对特定情况下最佳性能的边界条件。在编译器做出许多决策时，它会根据一些典型案例来猜测最佳选择。例如，在决定是否将特定函数内联时，编译器可以考虑到该函数将被调用的次数。问题在于编译器事先并不知道这些信息。
这就是为什么性能分析信息非常有用。有了性能分析信息，编译器可以做出更好的优化决策。大多数编译器都有一组基于反馈的转换，可以根据反馈的分析数据调整其算法。这组转换被称为Profile Guided Optimizations（PGO）。有时在文献中还可以找到Feedback Directed Optimizations（FDO）这个术语，实质上它指的是与PGO相同的内容。当可用时，编译器通常会依赖于性能分析数据。否则，它将回退到使用标准算法和启发式规则。
使用Profile Guided Optimizations往往可以使真实工作负载的性能提高多达15%。PGO不仅改善了内联和代码布局，还改善了寄存器分配等方面的优化。
生成性能分析数据可以基于两种不同的方式：代码插装（参见第5.1节）和基于采样的性能分析（参见第5.4节）。这两种方式相对容易使用，并且在第5.8节中讨论了与之相关的优缺点。
在LLVM编译器中，可以通过使用"-fprofile-instr-generate"选项构建程序来利用第一种方法。这将指示编译器对代码进行插装，在运行时收集性能分析信息。然后，LLVM编译器可以使用"-fprofile-instr-use"选项消耗性能分析数据，重新编译程序并输出经过PGO调优的二进制文件。有关在clang中使用PGO的指南在文档中有描述。
GCC编译器使用不同的选项组合"-fprofile-generate"和"-fprofile-use"，如GCC文档所述。
第二种方法是基于采样生成用于编译器的性能分析数据输入，可以借助于AutoFDO工具。该工具将Linux perf生成的采样数据转换为GCC和LLVM等编译器可以理解的格式。请注意，编译器会"盲目"地使用您提供的性能分析数据。编译器假设所有工作负载的行为都相同，因此它只针对单个工作负载对您的应用程序进行优化。使用PGO的用户应该在选择要进行性能分析的工作负载时要小心，因为虽然改善了应用程序的一个用例，但其他用例可能会受到影响。幸运的是，它不一定要完全是单个工作负载，因为可以将来自不同工作负载的性能分析数据合并在一起，代表应用程序的一组用例。
在2018年中期，Facebook开源了其二进制重链接工具BOLT。BOLT适用于已编译的二进制文件。它首先对代码进行反汇编，然后利用性能分析信息进行各种布局变换（包括基本块重新排序、函数拆分和分组），最后生成优化的二进制文件。Google也开发了一个类似的工具，名为Propeller，它与BOLT具有类似的目的，但声称在某些方面具有优势。可以将优化重链接器集成到构建系统中，并从优化的代码布局中获得额外5-10%的性能提升。唯一需要担心的是获取具有代表性和有意义的工作负载以收集性能分析信息。
7.8 Optimizing for ITLB
在优化前端（FE）效率时，虚拟地址到物理地址的转换对于内存地址非常重要。主要是通过TLB（参见第3节）来提供这些转换，它在专用条目中缓存最近使用的内存页转换。当TLB无法满足转换请求时，会进行耗时的内核页表页面访问，以计算每个引用的虚拟地址的正确物理地址。当TMA指向高ITLB开销174时，本节中的建议可能会派上用场。
通过将应用程序的性能关键代码部分映射到大页面，可以减少ITLB压力。这需要重新链接二进制文件，以便将文本段调整到适当的页面边界，为大页面映射做准备（请参阅libhugetlbfs的指南175）。有关大页面的一般讨论，请参见第8.1.3节。
除了使用大页面外，还可以使用标准的技术来优化I-cache性能，从而改善ITLB性能。例如，通过重新排序函数使热函数更加相邻，通过LTO/IPO176减少热区域的大小，使用基于配置文件的优化，以及减少过度的内联。
7.9 Chapter Summary
CPU前端优化的摘要总结如表6所示。
个人经验：我认为代码布局的改进经常被低估，最终被省略和遗忘。我同意你可能会从一些低 hanging 的优化措施开始，比如循环展开和矢量化机会。但是知道你可以通过更好地布局机器代码来获得额外的5-10%的性能提升仍然是有用的。如果你能为你的应用程序找到一组典型的用例，通常使用PGO是最好的选择。
8 CPU Back-End Optimizations
CPU后端（BE）组件在第3.8.2节中进行了讨论。大部分情况下，CPU后端的低效率可以描述为FE已经获取和解码指令，但是BE负载过重，无法处理新指令。从技术上讲，这是一种FE无法传递uops的情况，因为后端缺乏接受新uops所需的资源。其中一个例子是由于数据缓存未命中或除法器负载过重而导致的停顿。
我想强调给读者的建议是，只有当TMA指向较高的“后端限制”指标时，才建议开始优化针对CPU后端的代码。TMA进一步将后端限制指标分为两个主要类别：内存限制和核心限制，我们将在接下来进行讨论。
8.1 Memory Bound //内存受限
当一个应用程序执行大量的内存访问并花费大量时间等待它们完成时，这样的应用程序被称为受内存限制。这意味着要进一步提高其性能，我们可能需要改进内存访问方式、减少此类访问次数或升级内存子系统本身。
内存层次结构性能非常重要的说法得到了图45的支持。该图显示了内存和处理器之间性能差距的增长。垂直轴采用对数刻度，显示了CPU-DRAM性能差距的增长。内存基线是1980年64KB DRAM芯片的内存访问延迟。典型的DRAM性能改进每年为7%，而CPU每年可以享受20-50%的改进。[Hennessy和Patterson，2011]
在TMA中，内存受限（Memory Bound）估计了CPU流水线由于需求加载或存储指令而可能停顿的插槽比例。解决这类性能问题的第一步是找出导致高内存受限指标的内存访问（请参阅第6.1.4节）。一旦确定了具有问题的内存访问，就可以应用多种优化策略。下面我们将讨论几种典型情况。
8.1.1 Cache-Friendly Data Structures
如果变量在缓存中可以在几个时钟周期内获取，但如果不在缓存中，则从RAM内存中获取该变量可能需要超过一百个时钟周期。关于编写有利于缓存的算法和数据结构的重要性有很多信息，因为这是一个高性能应用程序的关键因素之一。缓存友好代码的关键支柱是时间和空间局部性（请参见第3.5节）的原则，其目标是允许有效地从缓存中获取所需的数据。在设计缓存友好代码时，将变量及其在内存中的位置视为缓存行，而不仅仅是个别变量，这将会很有帮助。
8.1.1.1 Access data sequentially.
利用空间局部性最佳的方法是进行连续的内存访问。通过这样做，我们可以允许硬件预取器（请参见第3.5.1.5.1节）识别内存访问模式，并提前获取下一块数据。在清单19中展示了一个实现这种缓存友好访问的C代码示例。该代码之所以“缓存友好”，是因为它按照内存中的排布顺序（行优先遍历）访问矩阵的元素。如果调换数组索引的顺序（例如，matrix[column][row]），将会导致按列优先遍历矩阵，这不利用空间局部性并且降低性能。
Listing 19 Cache-friendly memory accesses.
for (row = 0; row < NUMROWS; row++)
for (column = 0; column < NUMCOLUMNS; column++)
matrix[row][column] = row + column;清单19中呈现的示例是经典的，但通常实际应用程序比这复杂得多。有时候，为了编写缓存友好的代码，你需要更加深入一些。例如，在一个排序的大数组中，标准的二分查找实现并不利用空间局部性，因为它测试位于彼此相距很远且不共享同一缓存行的不同位置的元素。解决这个问题最著名的方法是使用Eytzinger布局[Khuong和Morin，2015]来存储数组的元素。其思想是使用类似广度优先搜索（BFS）的布局，在一个数组中维护一个隐式的二叉搜索树，通常在二叉堆中可见。如果代码在数组中执行大量的二分查找，将其转换为Eytzinger布局可能会有益处。
8.1.1.2 Use appropriate containers.
几乎每种编程语言都有各种准备好的容器可供使用。但了解它们的底层存储和性能影响是很重要的。选择适当的C++容器的一个很好的逐步指南可以在[Fog, 2004，第9.7章 数据结构和容器类]中找到。
此外，在选择数据存储方式时，要考虑代码对数据的处理方式。考虑这样一种情况：在对象大小较大时，需要在数组中存储对象还是存储指向这些对象的指针之间进行选择。存储指针的数组需要更少的内存。这对于修改数组的操作有益，因为指针数组需要传输的内存较少。然而，如果保留对象本身，则通过数组进行线性扫描将更快，因为它更加缓存友好并且不需要间接内存访问。
8.1.1.3 Packing the data. //使数据更紧凑
通过使数据更紧凑，可以提高内存层次结构的利用率。有许多方法可以压缩数据。其中一个经典示例是使用位域（bitfields）。在清单20中展示了一个可能受益于数据压缩的代码示例。如果我们知道a、b和c表示的是占用一定位数进行编码的枚举值，我们可以减小结构体S的存储空间（参见清单21）。
Listing 20 Packing Data: baseline struct.
struct S {
unsigned a;
unsigned b;
unsigned c;
}; // S is sizeof(unsigned int) * 3Listing 21 Packing Data: packed struct.
struct S {
unsigned a:4;
unsigned b:2;
unsigned c:2;
}; // S is only 1 byte这样做大大减少了来回传输的内存量，并节省了缓存空间。但需要牢记的是，这样做会增加访问每个压缩元素的成本。由于b的位与a和c共享同一机器字（machine word），编译器需要执行右移（>>）和按位与（AND）操作来加载它。类似地，存储值时需要执行左移（<<）和按位或（OR）操作。在计算效率低下的内存传输引起延迟的情况下，数据压缩是有益的。
此外，程序员可以通过重新排列结构体或类中的字段来减少内存使用，以避免编译器添加的填充字节（padding）。编译器插入未使用的内存字节（填充）的原因是为了实现对结构体的各个成员进行有效存储和提取。在示例中，如果按照成员大小递减的顺序声明S1的成员，则可以减小其大小。
8.1.1.4 Aligning and padding.
另一种提高内存子系统利用率的技术是对数据进行对齐。可能会出现这样的情况：一个占据16字节的对象跨越了两个缓存行，即它在一个缓存行上开始，在下一个缓存行上结束。获取这样的对象需要读取两个缓存行，如果对象正确对齐，可以避免这种情况。清单23展示了如何使用C++11的alignas关键字来对齐内存对象。
最有效地访问变量的方式是将其存储在可被变量大小整除的内存地址上。例如，double类型占用8字节的存储空间。因此，最好将其存储在可以被8整除的地址上。大小应始终为2的幂次方。大于16字节的对象应存储在可以被16整除的地址上。
Listing 22 Avoid compiler padding.
struct S1 {
bool b;
int i;
short s;
}; // S1 is sizeof(int) * 3
struct S2 {
int i;
short s;
bool b;
}; // S2 is sizeof(int) * 2Listing 23 Aligning data using the “alignas” keyword.
// Make an aligned array
alignas(16) int16_t a[N];
// Objects of struct S are aligned at cache line boundaries
#define CACHELINE_ALIGN alignas(64)
struct CACHELINE_ALIGN S {
//...
};因此，最好将其存储在可以被8整除的地址上。大小应始终为2的幂次方。大于16字节的对象应存储在可以被16整除的地址上。这样做有助于减少内存带宽的利用，并提高性能。
对齐可能会导致未使用字节的空洞，从而降低内存带宽的利用率。在上面的示例中，如果结构体S只有40字节，那么下一个S对象将从下一个缓存行的开头开始，这意味着每个包含S结构体对象的缓存行将有64 - 40 = 24个未使用的字节。
有时需要填充数据结构成员以避免缓存争用（详见[Fog, 2004, 第9.10章 缓存争用]）和伪共享（见第11.7.3节）。例如，在多线程应用程序中，当两个线程A和B访问同一结构体的不同字段时，可能会发生伪共享问题。当成员a和b有可能占用同一缓存行时，缓存一致性问题可能会严重降低程序的速度。为了解决这个问题，可以填充S，使得成员a和b不共享同一缓存行，如清单25所示。
Listing 24 Padding data: baseline version.
struct S {
int a; // written by thread A
int b; // written by thread B
};Listing 25 Padding data: improved version.
#define CACHELINE_ALIGN alignas(64)
struct S {
int a; // written by thread A
CACHELINE_ALIGN int b; // written by thread B
};对于通过malloc进行的动态分配，返回的内存地址保证满足目标平台的最小对齐要求。有些应用程序可能会受益于更严格的对齐要求。例如，使用64字节对齐而不是默认的16字节对齐来动态分配16字节。为了利用这一点，POSIX系统的用户可以使用memalign API。其他用户可以按照这里的描述自行实现。
在对齐考虑中最重要的领域之一是SIMD代码。当依赖编译器自动向量化时，开发人员不需要做任何特殊处理。然而，当您使用编译器矢量内置函数（参见第10.2节）编写代码时，很常见它们要求地址可以被16、32或64整除。编译器内置头文件提供的矢量类型已经进行了注释，以确保适当的对齐。
// ptr will be aligned by alignof(__m512) if using C++17
__m512 * ptr = new __m512[N];8.1.1.5 Dynamic memory allocation.
首先，有许多可以替代malloc的内存分配器，它们更快、更具可伸缩性，并且更好地解决了地址碎片问题。只需使用非标准的内存分配器，就可以获得几个百分点的性能提升。其中一些流行的内存分配库包括jemalloc和tcmalloc。
其次，可以使用自定义分配器来加速分配过程，例如，使用arena分配器。其主要优点之一是开销较低，因为此类分配器不会为每个内存分配执行系统调用。另一个优点是其高度灵活性。开发人员可以基于操作系统提供的内存区域实现自己的分配策略。一个简单的策略是维护两个不同的分配器，每个分配器都有自己的arena（内存区域）：一个用于热数据，一个用于冷数据。将热数据放在一起可以提供共享缓存行的机会，从而改善内存带宽利用率和空间局部性。它还改善了TLB利用率，因为热数据占用的内存页面较少。此外，自定义内存分配器可以使用线程本地存储来实现每个线程的分配，并消除线程之间的任何同步。当应用程序基于线程池并且不会生成大量线程时，这将非常有用。
8.1.1.6 Tune the code for memory hierarchy.
对于某些应用程序，性能取决于特定级别缓存的大小。其中最著名的例子是使用循环分块（tiling）改进矩阵乘法的性能。其思想是将矩阵的工作大小分成较小的片段（块），以便每个块都适应L2缓存。
大多数体系结构都提供类似于CPUID的指令，允许我们查询缓存的大小。另外，可以使用缓存无关算法，其目标是在任何缓存大小下都能够良好地工作。
英特尔的CPU具有数据线性地址硬件（见第6.3.3节），支持如easyperf博客文章所描述的缓存分块技术。
通过合理利用缓存结构和缓存相关的特性，可以显著提高应用程序的性能。
8.1.2 Explicit Memory Prefetching //显示内存预取
在通用工作负载中，常常存在数据访问没有明确模式或是随机的情况，因此硬件无法提前有效预取数据（请参考第3.5.1.5.1节中有关硬件预取器的信息）。这些情况下，缓存未命中无法通过选择更好的数据结构来消除。例如，在第26个代码清单中展示了这种情况的一个例子。假设calcNextIndex返回彼此差异显著的随机值。在这种情况下，后续加载arr[j]会指向内存中的完全新位置，并且很可能导致缓存未命中。当arr数组足够大时，硬件预取器将无法捕捉到模式并未能提前获取所需的数据。在第26个示例中，计算索引j和请求元素arr[j]之间存在一段时间窗口。由于这一点，我们可以使用__builtin_prefetch等显式预取指令，如第27个代码清单所示。
使用显式预取指令可以在计算索引和访问该索引对应元素之间的时间窗口中，提前将需要的数据加载到缓存中，从而减少缓存未命中的次数。这样可以显著改善访存性能，在数据访问无明显模式或随机的情况下尤为有效。
Listing 26 Memory Prefetching: baseline version.
for (int i = 0; i < N; ++i) {
int j = calcNextIndex();
// ...
doSomeExtensiveComputation();
// ...
x = arr[j]; // this load misses in L3 cache a lot
}为了让预取提示生效，请确保提前将其插入到适当的位置，以便在加载的值在其他计算中使用之前，它已经存在于缓存中。同时，也不要插入得太早，因为这样可能会污染缓存，使得一段时间内没有使用的数据占据了缓存空间。为了估计预取窗口，可以使用第6.2.5节中描述的方法。
工程师最常使用显式内存预取的场景是获取下一次循环迭代所需的数据。然而，线性函数预取也可以非常有帮助，例如，当您事先知道数据的地址，但在一定延迟（预取窗口）后请求该数据时。这种情况下，线性函数预取能起到很好的作用。
Listing 27 Memory Prefetching: using built-in prefetch hints.
for (int i = 0; i < N; ++i) {
int j = calcNextIndex();
__builtin_prefetch(a + j, 0, 1); // well before the load
// ...
doSomeExtensiveComputation();
// ...
x = arr[j];
}确实，显式内存预取并不可移植，这意味着在一个平台上可以获得性能提升，并不保证在另一个平台上也能获得类似的加速效果。更糟糕的是，当不正确使用时，它可能会恶化缓存的性能。如果使用错误大小的内存块或者过于频繁地请求预取，可能会迫使其他有用的数据从缓存中被驱逐出去。
虽然软件预取能够让程序员具备控制和灵活性，但要正确使用并不总是容易。考虑一种情况，我们想要将预取指令插入到平均IPC为2的代码片段中，每次DRAM访问需要100个周期。为了达到最佳效果，我们需要在加载之前的200个指令处插入预取指令。但这并不总是可能的，特别是当加载地址就在加载本身之前计算时。指针追踪问题可以是显式预取无法解决的一个很好的例子。
最后，显式预取指令会增加代码大小并增加CPU前端的压力。预取指令就像其他任何指令一样，会消耗CPU资源，当使用不当时，可能会降低程序的性能。
8.1.3 Optimizing For DTLB
正如第3节所描述的，TLB是一个快速但有限的核心缓存，用于内存地址的虚拟地址到物理地址的转换。如果没有TLB，每个应用程序的内存访问都需要耗时的内核页表页行走来计算每个引用的虚拟地址的正确物理地址。
TLB层次结构通常包括L1 ITLB（指令）、L1 DTLB（数据）和L2 STLB（指令和数据的统一缓存）。L1 ITLB的缺失通常只会导致非常小的惩罚，通常可以通过乱序执行来隐藏。STLB的缺失将导致调用页行走器。在运行时，这个惩罚可能是明显的，因为在此过程中，CPU会停顿[Suresh Srinivas, 2019]。假设Linux内核中默认的页面大小为4KB，现代的L1级别的TLB缓存只能保存最近使用的几百个页面表项，覆盖大约1MB的地址空间，而L2 STLB则可以保存多达几千个页面表项。具体的数字可以在https://ark.intel.com上找到特定处理器的信息。
在Linux和Windows系统上，应用程序被加载到内存中的是以4KB页面为单位的，默认情况下大多数系统都是这样的。分配许多小页面是昂贵的。如果一个应用程序活跃地引用了数十GB或数百GB的内存，那么就需要很多4KB大小的页面，每个页面都会争夺有限的TLB条目。使用大的2MB页面，可以用只有十个页面就映射20MB的内存，而使用4KB页面则需要5120个页面。这意味着需要更少的TLB条目，从而减少了TLB缺失的次数。无论是Windows还是Linux，都允许应用程序建立大页内存区域。HugeTLB子系统的支持取决于体系结构，而AMD64和Intel 64体系结构均支持2MB（huge）和1GB（gigantic）页面。
正如我们刚刚学到的那样，减少ITLB缺失的一种方法是使用更大的页面大小。值得庆幸的是，TLB也能够缓存2MB和1GB页面的条目。如果前面提到的应用程序使用了2MB页面而不是默认的4KB页面，它将使TLB的压力减少512倍。同样地，如果它从使用2MB页面更新为使用1GB页面，它将再次将TLB的压力减少512倍。这是一个很大的改进！对于某些应用程序来说，使用较大的页面大小可能有益，因为在缓存中用于存储转换的空间较少，可以为应用程序代码提供更多的可用空间。巨大的页面通常会导致更少的页行走，并且由于表本身更紧凑，所以在发生TLB缺失时，在内核页表中进行页行走的惩罚也会降低。
大页面可以用于代码、数据或两者兼而有之。如果您的工作负载有一个大的堆，那么对数据使用大页面是值得尝试的。像关系型数据库系统（如MySQL、PostgreSQL、Oracle等）和配置有大堆区域的Java应用程序这样的大内存应用程序经常受益于使用大页面。在[Suresh Srinivas, 2019]中，有一个使用巨大页面优化运行时的示例，展示了这个功能如何在三个环境中的三个应用程序中提高性能并减少ITLB缺失（最多50％）。
然而，就像其他许多功能一样，大页面并不适用于每个应用程序。如果一个应用程序只想分配一个字节的数据，那么使用4KB页面而不是巨大页面会更好；这样可以更有效地使用内存。
在Linux操作系统上，有两种在应用程序中使用大页面的方式：显式和透明巨大页面。
8.1.3.1 Explicit Hugepages.
作为系统内存的一部分，巨大页面可以作为巨大页面文件系统（hugetlbfs）提供，应用程序可以使用系统调用（例如mmap）来访问它。可以通过cat /proc/meminfo命令和HugePages_Total条目来检查系统上适当配置的巨大页面。巨大页面可以在启动时或运行时进行预留。在启动时进行预留增加了成功的可能性，因为内存尚未被显著碎片化。有关预留巨大页面的详细说明，请参考Red Hat性能调优指南。
还有一种选项是使用libhugetlbfs库，在大型页面之上动态分配内存，该库覆盖了现有动态链接二进制可执行文件中使用的malloc调用。它不需要修改代码甚至重新链接二进制文件；最终用户只需配置几个环境变量即可。它可以同时使用显式预留的巨大页面和透明页面。有关更多详细信息，请参阅libhugetlbfs的操作文档。
对于从代码中对大页面的访问需要更精细控制的情况（即不影响每个内存分配），开发人员有以下替代方案：
• 使用MAP_HUGETLB标志的mmap（示例代码197）。
• 使用挂载的hugetlbfs文件系统中的文件的mmap（示例代码198）。
• 使用SHM_HUGETLB标志的shmget（示例代码199）。
8.1.3.2 Transparent Hugepages.
Linux还提供透明巨大页面支持（THP），它可以自动管理大页面，并对应用程序透明。在Linux下，您可以启用THP，在需要大块内存时动态切换到巨大页面。THP功能有两种操作模式：系统级和进程级。当启用系统级THP时，内核会尝试在可能分配巨大页面的情况下为任何进程分配巨大页面，因此不需要手动预留巨大页面。如果按进程启用了THP，内核仅将巨大页面分配给通过madvise系统调用归属的各个进程的内存区域。您可以使用以下命令检查系统中是否已启用THP：
$ cat /sys/kernel/mm/transparent_hugepage/enabled
always [madvise] never如果值始终为"always"（系统级）或"madvise"（进程级），则THP对您的应用程序可用。使用"madvise"选项，只有通过madvise系统调用标记为MADV_HUGEPAGE的内存区域内启用了THP。有关每个选项的完整规范，可以在Linux内核文档中找到有关THP的文档。
8.1.3.3 Explicit vs. Transparent Hugepages.
与显式巨大页面（EHP）需要提前在虚拟内存中保留不同，THP并不需要。内核在后台尝试分配一个THP，如果失败，将默认使用标准的4k页面。这一切对用户来说都是透明的。分配过程可能涉及多个内核进程，负责为未来的THP在虚拟内存中腾出空间（可能包括将内存交换到磁盘、碎片化或压缩页面）。透明巨大页面的后台维护会带来非确定性的内核延迟开销，因为它管理着不可避免的碎片化和交换问题。而EHP则不会受到内存碎片化的影响，也无法被交换到磁盘上。
其次，EHP可用于应用程序的所有段，包括文本段（即同时受益于DTLB和ITLB），而THP仅适用于动态分配的内存区域。
THP的一个优点是相比EHP需要较少的操作系统配置工作，这有助于加快实验速度。
8.2 Core Bound //核心受限
第二类CPU后端瓶颈是核心限制（Core Bound）。一般来说，该指标表示CPU乱序执行引擎内的所有停顿，并且这些停顿不是由于内存问题引起的。核心限制指标有两个主要类别：
• 硬件计算资源短缺。这表明某些执行单元过载（执行端口争用）。当工作负载频繁执行大量的重型指令时，就会出现这种情况。例如，除法和平方根运算由Divider单元处理，其延迟时间可能比其他指令要长很多。
• 软件指令之间的依赖关系。这表示程序数据流或指令流中的依赖关系限制了性能。例如，依赖浮点运算的高延迟算术操作会导致指令级并行性（ILP）较低。
在本小节中，我们将介绍最常见的优化技术，如函数内联、矢量化和循环优化。这些优化旨在减少执行的指令总数，在工作负载经历高的Retiring指标时也会有所帮助。但作者认为在这里讨论它们是合适的。
8.2.1 Inlining Functions
函数内联是将对函数F的调用替换为针对该调用实际参数进行特化的F代码。内联是最重要的编译器优化之一，不仅可以消除函数调用的开销，还可以启用其他优化。这是因为当编译器内联一个函数时，编译器分析的范围扩大到了更大的代码块。然而，内联也有一些缺点：可能会增加代码大小和编译时间。
在很多编译器中，函数内联的主要机制依赖于某种成本模型。例如，对于LLVM编译器，它基于计算每个函数调用（调用点）的成本和阈值来进行内联。只有当成本小于阈值时才会进行内联。通常，内联一个函数调用的成本基于该函数中指令的数量和类型。阈值通常是固定的，但在某些情况下可以变化。
在这个普遍成本模型周围存在许多启发式规则。例如：
- 微小的函数（包装器）几乎总是会被内联。
- 仅有一个调用点的函数是内联的首选候选对象。
- 大型函数通常不会被内联，因为它们会使调用者函数的代码膨胀。
此外，也存在一些内联存在问题的情况：
- 递归函数无法内联到其自身。
- 通过指针引用的函数可以在直接调用的位置进行内联，但必须保留在二进制文件中，即不能完全内联和消除。对于具有外部链接的函数也是如此。
如前所述，编译器在判断是否内联一个函数时通常采用成本模型方法，这在实践中通常效果良好。一般来说，依靠编译器来做出所有内联决策并在需要时进行调整是一个不错的策略。成本模型无法考虑到每种可能的情况，这给改进留下了空间。有时编译器需要开发人员提供特殊提示。一种找到程序中潜在内联候选的方法是查看分析数据，特别是函数的前导部分和尾声部分的热度。下面是一个函数剖面的示例，其中前导和尾声部分消耗了函数时间的约50%：
这可能是一个强有力的指标，表明如果我们内联该函数，前导和尾声部分的运行时间可能会被节省下来。需要注意的是，即使前导和尾声部分是热点代码，也不一定意味着内联该函数就会有利可图。内联触发了许多不同的变化，因此很难预测结果。始终通过测量改变后的代码的性能来确认是否需要强制内联。
对于GCC和Clang编译器，可以使用C++11的[[gnu::always_inline]]属性来给内联 foo 函数提供提示，如下所示的代码示例。对于MSVC编译器，可以使用__forceinline关键字。
[[gnu::always_inline]] int foo() {
// foo body
}8.2.2 Loop Optimizations
循环是几乎所有高性能（HPC）程序的核心。由于循环代表着需要执行大量次数的代码片段，因此执行时间的大部分都花费在循环中。对于这样一个关键的代码片段来说，微小的改变可能会对程序的性能产生很大的影响。因此，仔细分析程序中热门循环的性能并了解改进它们的可能选项非常重要。
要有效优化一个循环，关键是了解循环的瓶颈所在。一旦找到了耗时最长的循环，尝试确定其瓶颈。通常情况下，循环的性能受限于以下一个或多个方面：内存延迟、内存带宽或计算机的计算能力。屋顶线性模型（Roofline Performance Model）（第5.5节）是评估不同循环性能与硬件理论极限之间关系的良好起点。自顶向下的微架构分析（Top-Down Microarchitecture Analysis）（第6.1节）也是了解瓶颈信息的另一个良好来源。
通过使用这些工具和方法，可以更好地了解循环的性能问题，并确定如何改进循环以提高程序性能。这包括利用合适的算法、优化数据布局、使用矢量化指令、循环展开、循环分块等技术来减少内存延迟、提高内存带宽和充分利用计算能力。此外，根据具体的硬件架构和应用场景，调整循环的执行策略也非常重要。
在本节中，我们将介绍一些最常见的循环优化方法，以解决前面提到的各种瓶颈类型。首先，我们将讨论低级优化，这些优化只在单个循环内部对代码进行移动。这类优化通常有助于使循环内的计算更加有效。接下来，我们将介绍高级优化，它们对循环进行重构，通常涉及多个循环。第二类优化的目标通常是改善内存访问，消除内存带宽和内存延迟问题。需要注意的是，这里列举的并不是所有已发现的循环变换的完整列表。读者可以参考[Cooper and Torczon，2012]以获取有关每种变换的更详细信息。
编译器可以自动识别执行某种循环变换的机会。然而，有时候需要开发人员的干预才能达到预期的结果。在本节的第二部分，我们将探讨在循环中发现性能改进机会的可能方式。了解对给定循环执行了哪些变换，以及编译器无法做到哪些优化，是成功进行性能调优的关键之一。最后，我们将考虑使用多面体框架优化循环的另一种替代方式。
8.2.2.1 Low-level optimizations.
首先，我们将考虑简单的循环优化，这些优化会转换单个循环内部的代码：循环不变式代码移动（Loop Invariant Code Motion）、循环展开（Loop Unrolling）、循环强度降低（Loop Strength Reduction）和循环不交换（Loop Unswitching）。这些优化通常有助于改善具有高算术密集度的循环的性能（参见第5.5节），即当循环受到CPU计算能力限制时。一般来说，编译器在执行这些转换时表现良好；然而，仍然存在一些情况，编译器可能需要开发人员的支持。我们将在后续章节中讨论这个问题。
Loop Invariant Code Motion (LICM).
在循环中永远不会改变的表达式被称为循环不变式（loop invariants）。由于它们的值在循环迭代过程中保持不变，我们可以将循环不变式表达式移到循环外部。我们可以通过将结果存储在一个临时变量中，并在循环内部使用临时变量来实现这一操作（参见清单28）。
Loop Unrolling.
归纳变量（induction variable）是循环中的一个变量，其值是循环迭代次数的函数。例如，v = f(i)，其中i是迭代次数。在每次迭代中修改归纳变量可能很昂贵。相反，我们可以展开循环，并为每个归纳变量的增量执行多次迭代（参见清单29）。循环展开的主要好处是每次迭代可以执行更多的计算。在每次迭代结束时，需要增加索引值、进行测试，并且如果还有更多迭代需要处理，则跳转回循环的顶部。这个工作可以被看作是循环的“税”，可以减少。通过将清单29中的循环展开2倍，我们将执行的比较和分支指令数量减少了一半。
循环展开是一个众所周知的优化方法，但仍然有很多人对此感到困惑，并尝试手动展开循环。我建议开发人员不应该手动展开任何循环。首先，编译器在进行循环展开时表现非常出色，通常能够实现很优化的展开方式。第二个原因是处理器具有“内置展开器”，这得益于其乱序推测执行引擎（参见第3节）。当处理器等待第一次迭代的加载完成时，它可以推测性地开始执行第二次迭代的加载操作。这可以向前跨越多次迭代，在指令重排序缓冲区（ROB）中有效地展开循环。
所以，由于编译器和处理器都能够自动处理循环展开，开发人员无需手动展开循环。这样做更容易导致代码复杂性增加、易错和可读性下降。如果开发人员尝试手动展开循环，可能会产生不必要的代码冗余和维护成本。相反，应该将精力放在编写清晰、简洁且易于理解的代码上，让编译器和处理器负责优化循环展开以提高性能。
Loop Strength Reduction (LSR).
LSR（循环强度降低）的思想是用廉价的指令替换昂贵的指令。这种转换可以应用于所有使用归纳变量的表达式。强度降低通常应用于数组索引。编译器通过分析变量在循环迭代中的演变方式来执行LSR（见清单30）。
Loop Unswitching.
如果一个循环内部包含一个不变的条件判断语句，我们可以将其移到循环外部。这可以通过复制循环体，并将其放置在条件判断语句的if和else子句中的各个版本中来实现（见清单31）。虽然循环拆分可能会使代码量增加一倍，但现在每个新的循环都可以单独进行优化。
循环拆分是一种优化技术，它的目标是减少循环内部的条件判断次数，以提高执行效率。当循环中的条件在每次迭代中都保持不变时，这种优化可以提供更好的性能。
通过将循环体复制到条件判断语句的if和else子句中，我们可以在每个版本的循环中单独进行优化。这样，编译器可以针对不同的条件进行优化，并生成更有效的代码。
虽然循环拆分会导致代码量增加，但这种优化可以提高程序的执行效率。通过分别对每个拆分后的循环进行优化，可以针对不同的条件进行更精细的控制流优化和计算优化，从而获得更好的性能。
8.2.2.2 High-level optimizations.
还有一类循环变换可以改变循环的结构，通常会影响到多个嵌套循环。我们将介绍循环交换、循环分块（瓦片化）以及循环融合和分布（分裂）。这组变换旨在改进内存访问方式，消除内存带宽和内存延迟的瓶颈。从编译器的角度来看，合法且自动地进行高级循环变换非常困难。往往很难证明所做的任何优化的益处。在这种意义上，开发人员处于更好的位置，因为他们只需关注在特定代码段中变换的合法性，而不必考虑可能发生的每种情况。不幸的是，这也意味着我们经常需要手动进行这样的变换。
循环交换、循环分块和循环融合与分布是用于优化内存访问、消除内存带宽和内存延迟瓶颈的重要循环变换技术。循环交换可以改变循环的执行顺序，以优化数据的局部性，并提高缓存效率。循环分块通过将大循环分割成小的块，可以减少对主存的访问次数，以及提高数据重用和并行性。循环融合和分布可以将多个循环合并或拆分，以减少内存访问次数，并提高数据的局部性。
由于进行高级循环变换是非常困难的，因此开发人员通常需要手动进行这些变换，以在特定代码段中实现性能优化。他们需要评估和验证变换的合法性，并权衡所带来的性能提升是否值得投入。编译器很难在所有情况下自动进行这些变换，因此开发人员的角色仍然非常重要。
Loop Interchange.
循环交换是指交换嵌套循环的循环顺序。内部循环中使用的归纳变量切换到外部循环，反之亦然。清单32展示了一个关于i和j的嵌套循环交换的示例。循环交换的主要目的是对多维数组的元素进行顺序内存访问。通过按照内存中元素布局的顺序进行访问，我们可以提高内存访问的空间局部性，并使我们的代码更加缓存友好（见第8.1.1节）。这种转换有助于消除内存带宽和内存延迟的瓶颈。
Loop Blocking (Tiling).
循环分块（瓦片化）的思想是将多维执行范围分割成较小的块（块或瓦片），以便每个块都适合CPU缓存210。如果算法使用大型多维数组，并对其元素进行跨步访问，那么缓存利用率可能很低。每次这样的访问都可能将未来访问所需的数据推出缓存（缓存驱逐）。通过将算法划分为较小的多维块，我们可以确保在循环中使用的数据保持在缓存中直到被重复使用。
在清单33所示的例子中，算法对数组a的元素进行行主序遍历，同时对数组b进行列主序遍历。循环嵌套可以分割为较小的块，以最大程度地重用数组b的元素。
循环分块是一种广为人知的优化一般矩阵乘法（General Matrix Multiplication，GEMM）算法的方法。它增强了内存访问的缓存重用，并改善算法的内存带宽和内存延迟。
Loop Fusion and Distribution (Fission).
当两个循环迭代相同范围并且彼此不引用对方的数据时，可以将它们合并为一个循环。循环融合是将两个独立的循环合并为一个循环的过程。在第34段代码示例中展示了循环融合的例子。另一种相反的操作称为循环分配（分裂），即将循环拆分成多个独立的循环。
循环融合有助于减少循环开销（参见循环展开讨论），因为两个循环可以使用相同的归纳变量。此外，循环融合可以提高内存访问的时间局部性。在第34段代码示例中，如果结构体的 x 和 y 成员恰好位于同一缓存行上，最好将两个循环融合起来，因为我们可以避免重复加载同一缓存行。这将减少缓存占用，并提高内存带宽利用率。
然而，并非总是循环融合能够提高性能。有时候将一个循环拆分为多个阶段、预先过滤数据、排序和重组数据等操作会更好。通过将大循环分割成多个较小的循环，可以限制每次循环迭代所需的数据量，从而有效地增加内存访问的时间局部性。这对于存在高缓存争用的情况特别有帮助，而这通常发生在大型循环中。循环分配还可以减少寄存器压力，因为在每次循环迭代中执行的操作更少。此外，将大循环拆分为多个较小的循环还有助于CPU前端的性能，因为可以更好地利用指令缓存（参见第7节）。最后，分布式后，编译器可以单独对每个小循环进行进一步优化。
8.2.2.3 Discovering loop optimization opportunities.
正如我们在本节开头讨论的那样，编译器将承担优化循环的繁重工作。您可以依靠它们来对循环代码进行所有明显的改进，比如消除不必要的工作、进行各种peephole优化等。有时候编译器足够聪明，可以默认生成快速版本的循环，而其他情况下我们需要自己进行一些重写来帮助编译器。正如之前所说，从编译器的角度来看，合法且自动地进行循环转换是非常困难的。通常，当编译器无法证明变换的合法性时，它必须保守处理。
考虑列表35中的代码。编译器无法将表达式strlen(a)移出循环体。因此，循环在每次迭代中检查字符串是否到达末尾，这显然是慢速的。编译器不能提升这个调用的原因是，数组a和b的内存区域可能重叠。在这种情况下，将strlen(a)移出循环体是不合法的。如果开发者确信内存区域不会重叠，他们可以在foo函数的两个参数上使用restrict关键字声明，即char* __restrict__ a。
有时候，编译器可以通过编译优化备注（参见第5.7节）告知我们转换失败的情况。然而，在这种情况下，无论是Clang 10.0.1还是GCC 10.2都无法明确告知表达式strlen(a)未被提升出循环。唯一的方法是根据应用程序的配置文件查看生成的汇编代码的热点部分。分析机器代码需要基本的汇编语言阅读能力，但这是一项非常有价值的活动。
首先尝试获取最容易的优化是一个合理的策略。开发者可以使用编译器优化报告或检查循环的机器代码以寻找简单的改进方法。有时候，我们可以通过使用用户指令来调整编译器的转换。例如，当我们发现编译器将我们的循环展开了4倍时，我们可以检查是否使用更高的展开系数会提高性能。大多数编译器都支持#pragma unroll(8)，它会指示编译器使用用户指定的展开系数。还有其他的指令来控制特定的转换，比如循环向量化、循环分布等。有关完整的用户指令列表，请查阅编译器的手册。
接下来，开发者应该确定循环中的瓶颈，并根据硬件的理论最大性能进行评估。可以首先使用Roofline性能模型（第5.5节），它将揭示开发者应该尝试解决的瓶颈。循环的性能受以下因素之一或多个因素的限制：内存延迟、内存带宽或机器的计算能力。一旦确定了循环的瓶颈，开发者可以尝试应用本节前面讨论过的转换技术之一。
个人经验：尽管针对特定的计算问题有众所周知的优化技术，但在很大程度上，循环优化是一种需要经验的“黑魔法”。我建议您依靠编译器，只有在必要时才进行必要的转换。最后，保持代码尽可能简单，如果性能提升微不足道，不要引入过于复杂的改变。
8.2.2.4 Use Loop Optimization Frameworks
在过去的几年中，研究人员们开发了一些技术来确定循环转换的合法性并自动对循环进行转换。其中一个创新是多面体框架（polyhedral framework）。GRAPHITE是最早集成到生产编译器中的多面体工具之一。GRAPHITE基于从GCC的低级中间表示GIMPLE中提取的多面体信息，执行一系列经典的循环优化。GRAPHITE证明了该方法的可行性。
基于LLVM的编译器使用自己的多面体框架：Polly。Polly是一个面向LLVM的高级循环和数据局部性优化器及优化基础设施。它使用基于整数多面体的抽象数学表示来分析和优化程序的内存访问模式。Polly执行经典的循环转换，特别是瓦片化和循环合并，以改善数据局部性。该框架在许多著名基准测试中实现了显著的加速（Grosser等人，2012年）。下面是一个示例，展示了Polly如何将Polybench 2.0基准套件中的GEneral Matrix-Multiply（GEMM）核心的速度提升近30倍：
$ clang -O3 gemm.c -o gemm.clang
$ time ./gemm.clang
real 0m6.574s
$ clang -O3 gemm.c -o gemm.polly -mllvm -polly
$ time ./gemm.polly
real 0m0.227sPolly是一个强大的循环优化框架，然而它仍然无法处理一些常见且重要的情况。在LLVM基础设施的标准优化流程中，Polly并未启用，并且需要用户显式地提供编译器选项来使用它（-mllvm -polly）。当寻找加速循环的方法时，使用多面体框架是一个可行的选择。
8.2.3 Vectorization //向量化
在现代处理器上，使用SIMD指令可以比常规的非矢量化（标量）代码实现显著加速。在进行性能分析时，软件工程师最重要的任务之一是确保热点代码由编译器进行向量化处理。本节旨在引导工程师发现向量化的机会。回顾一下关于现代CPU的SIMD能力的一般信息，读者可以参考第3.7节。
大多数向量化都是自动完成的，无需用户干预（自动向量化）。也就是说，编译器会自动识别源代码中产生SIMD机器代码的机会。依赖自动向量化是一个很好的策略，因为现代编译器可以为各种源代码输入生成快速的向量化代码。正如前面给出的建议一样，作者建议让编译器完成其工作，只有在必要时才进行干预。
在一些罕见的情况下，软件工程师需要根据从编译器或分析数据中获得的反馈来调整自动向量化。在这种情况下，程序员需要告诉编译器某个代码区域是可向量化的，或者向量化是有益的。现代编译器具有扩展功能，允许高级用户直接控制向量化器，并确保代码的某些部分得到高效的向量化处理。后续章节将提供使用编译器提示的几个示例。
需要注意的是，在一些问题中，SIMD具有无可替代的价值，而自动向量化并不起作用，并且在不久的将来也不太可能起作用（可以参考[Muła和Lemire, 2019]中的一个示例）。如果编译器无法生成所需的汇编指令，可以借助编译器内置函数来重写代码片段。在大多数情况下，编译器内置函数提供了与汇编指令的一对一映射（请参见第10.2节）。
个人意见：尽管在某些情况下开发人员需要使用编译器内置函数，但我建议主要依赖编译器的自动向量化，只有在必要时才使用内置函数。使用编译器内置函数的代码类似于内联汇编，很快就会变得难以理解。编译器的自动向量化通常可以通过pragma和其他提示进行调整。
一般来说，编译器会进行三种类型的向量化：内部循环向量化、外部循环向量化和SLP（超级字级并行）向量化。本节主要讨论内部循环向量化，因为这是最常见的情况。关于外部循环和SLP向量化，我们在附录B中提供了一般信息。
8.2.3.1 Compiler Autovectorization.
许多因素可能阻碍自动向量化，其中一些因素与编程语言的语义相关。例如，编译器必须假设无符号循环索引可能会溢出，这可能会阻止某些循环转换。另一个例子是C语言的假设：程序中的指针可以指向重叠的内存区域，这会使程序的分析变得非常困难。另一个主要障碍是处理器本身的设计。在某些情况下，处理器对于某些操作没有高效的向量指令。例如，在大多数处理器上不支持执行受位掩码控制的加载和存储操作。另一个例子是有符号整数到双精度浮点数的向量宽度格式转换，因为结果涉及不同大小的向量寄存器。
尽管存在所有这些挑战，软件开发人员可以解决其中许多问题并启用向量化。在本节的后面部分，我们将提供如何与编译器合作并确保热点代码由编译器进行向量化的指导。
向量化器通常分为三个阶段：合法性检查、盈利性检查和转换本身：
- 合法性检查：在此阶段，编译器检查是否可以将循环（或其他代码区域）转换为使用向量。循环向量化器检查循环的迭代是否连续，即循环按线性方式进行。向量化器还确保循环中的所有内存和算术操作可以扩展为连续操作，循环的控制流在所有通道上都是统一的，并且内存访问模式是统一的。编译器必须检查或确保生成的代码不会触及不应该触及的内存，并且操作的顺序将被保留。编译器需要分析指针的可能范围，如果有一些缺失的信息，它必须假设转换是非法的。合法性阶段收集了一系列必须满足的要求，以使循环向量化合法。
- 盈利性检查：然后，向量化器检查转换是否具有盈利性。它比较不同的向量化因素，并确定哪个向量化因素执行速度最快。向量化器使用成本模型来预测不同操作（例如标量加法或向量加载）的成本。它需要考虑将数据洗牌到寄存器中的附加指令，预测寄存器压力，并估算确保满足允许向量化的前提条件的循环保护的成本。检查盈利性的算法很简单：1）累加代码中所有操作的成本，2）比较每个代码版本的成本，3）将成本除以预期执行计数。例如，如果标量代码花费8个周期，而向量化代码花费12个周期，但一次执行4个循环迭代，则向量化版本的循环可能更快。
- 转换：最后，在向量化器确定转换是合法且具有盈利性之后，它们会转换代码。这个过程还包括插入启用向量化的保护。例如，大多数循环使用未知的迭代计数，因此编译器必须生成循环的标量版本以及向量化的版本，以处理最后几次迭代。编译器还必须检查指针是否重叠等。所有这些转换都使用在合法性检查阶段收集的信息进行。
8.2.3.2 Discovering vectorization opportunities.
Amdahl定律告诉我们，在程序执行过程中，我们应该花时间仅分析那些最常使用的代码部分。因此，性能工程师应该专注于通过分析工具（见5.4节）突出显示的热点代码部分。正如前面提到的，向量化最常用于循环。
发现改进向量化的机会应该从分析程序中的热点循环开始，并检查编译器对它们进行了哪些优化。检查编译器的向量化备注（见5.7节）是了解这一点的最简单方法。现代编译器可以报告一个特定循环是否被向量化，并提供额外的细节，例如向量化因子（VF）。如果编译器无法将一个循环向量化，它也能告诉失败的原因。
使用编译器优化报告的另一种方法是检查汇编输出。最好分析来自性能分析工具的输出，该工具显示给定循环的源代码与生成的汇编指令之间的对应关系。然而，这种方法需要具备读取和理解汇编语言的能力。想要弄清楚编译器生成的指令的语义可能需要一些时间218。但是这种技能是非常有价值的，并且通常可以提供额外的见解。例如，我们可以发现生成的代码存在不够优化的问题，比如缺乏向量化、向量化因子不够优化、执行不必要的计算等。
在尝试加速可向量化代码时，开发人员经常遇到几种常见情况。下面我们介绍四个典型场景，并给出在每种情况下的一般指导。
8.2.3.3 Vectorization is illegal.
在某些情况下，遍历数组元素的代码可能无法进行向量化。向量化备注非常有效地解释了出现问题的原因，以及编译器无法对代码进行向量化的原因。第36条示例展示了一个循环内的依赖关系，阻止了向量化。
Listing 36 Vectorization: read-after-write dependence.
void vectorDependence(int *A, int n) {
for (int i = 1; i < n; i++)
A[i] = A[i-1] * 2;
}虽然由于上述的硬性限制，有些循环无法进行向量化，但在某些约束条件放宽的情况下，其他循环可能是可以进行向量化的。有些情况下，编译器无法对循环进行向量化，是因为它无法证明向量化是合法的。编译器通常非常保守，只有在确保不会破坏代码的情况下才进行转换。通过向编译器提供额外的提示，可以放宽这种软性限制。例如，在转换执行浮点算术运算的代码时，向量化可能会改变程序的行为。浮点加法和乘法是可交换的，也就是说，可以交换左操作数和右操作数而不改变结果：(a + b == b + a)。然而，这些操作不是可结合的，因为舍入发生的时间不同：((a + b) + c) != (a + (b + c))。第37条示例中的代码无法通过编译器自动进行向量化。原因是向量化会将变量sum转换为向量累加器，这会改变操作的顺序，并可能导致不同的舍入决策和不同的结果。
Listing 37 Vectorization: flfloating-point arithmetic.
1 // a.cpp
2 float calcSum(float* a, unsigned N) {
3 float sum = 0.0f;
4 for (unsigned i = 0; i < N; i++) {
5 sum += a[i];
6 }
7 return sum;
8 }然而，如果程序在最终结果上可以容忍一点不准确性（通常是这种情况），我们可以将这个信息传递给编译器以启用向量化。Clang和GCC编译器提供了一个标志 -ffast-math220，允许进行此类转换：
$ clang++ -c a.cpp -O3 -march=core-avx2 -Rpass-analysis=.*
...
a.cpp:5:9: remark: loop not vectorized: cannot prove it is safe to reorder
floating-point operations; allow reordering by specifying '#pragma clang
loop vectorize(enable)' before the loop or by providing the compiler
option '-ffast-math'. [-Rpass-analysis=loop-vectorize]
...
$ clang++ -c a.cpp -O3 -ffast-math -Rpass=.*
...
a.cpp:4:3: remark: vectorized loop (vectorization width: 4, interleaved
count: 2) [-Rpass=loop-vectorize]
...让我们再来看另一个典型情况，当编译器无法证明循环在非重叠内存区域上操作时，它通常选择保守一点。让我们回顾一下第5.7节中提供的第9条示例。当编译器尝试对第38条示例中的代码进行向量化时，通常无法做到这一点，因为数组a、b和c的内存区域可能重叠。
Listing 38 a.c
1 void foo(float* a, float* b, float* c, unsigned N) {
2 for (unsigned i = 1; i < N; i++) {
3 c[i] = b[i];
4 a[i] = c[i-1];
5 }
6 }这是由GCC 10.2提供的优化报告（使用-fopt-info启用）：
$ gcc -O3 -march=core-avx2 -fopt-info
a.cpp:2:26: optimized: loop vectorized using 32 byte vectors
a.cpp:2:26: optimized: loop versioned for vectorization because of possible
aliasingGCC已经识别出数组a、b和c的内存区域可能存在重叠，并创建了同一个循环的多个版本。编译器插入了运行时检查来检测内存区域是否重叠。根据这些检查，它在向量化和标量化版本之间进行调度。在这种情况下，向量化带来了插入潜在昂贵的运行时检查的成本。如果开发人员知道数组a、b和c的内存区域不重叠，可以在循环前面插入#pragma GCC ivdep或使用__restrict__关键字，如第10条示例中所示。这样的编译器提示将消除GCC编译器插入之前提到的运行时检查的需要。
由于编译器的本质是静态工具，它们只根据它们处理的代码进行推理。例如，一些动态工具（如Intel Advisor）可以检测给定循环中是否实际发生了跨迭代依赖或对具有重叠内存区域的数组的访问等问题。但请注意，这类工具只提供建议。轻率地插入编译器提示可能会引起真正的问题。
8.2.3.4 Vectorization is not beneficial.
在某些情况下，编译器可以对循环进行向量化，但认为这样做并不划算。在第39条示例中的代码中，编译器可以对数组A的内存访问进行向量化，但需要将对数组B的访问拆分为多个标量加载。散射/聚集模式相对昂贵，而能够模拟操作成本的编译器通常决定避免向具有这种模式的代码进行向量化。
Listing 39 Vectorization: not benefificial.
1 // a.cpp
2 void stridedLoads(int *A, int *B, int n) {
3 for (int i = 0; i < n; i++)
4 A[i] += B[i * 3];
5 }以下是第39条代码的编译器优化报告：
$ clang -c -O3 -march=core-avx2 a.cpp -Rpass-missed=loop-vectorize
a.cpp:3:3: remark: the cost-model indicates that vectorization is not
beneficial [-Rpass-missed=loop-vectorize]
for (int i = 0; i < n; i++)
^用户可以使用#pragma hint指令来强制Clang编译器对循环进行向量化，如第40条示例所示。然而，请记住，向量化是否具有盈利性在很大程度上取决于运行时数据，例如循环的迭代次数。编译器没有这些信息可用，因此它们通常倾向于保守处理。开发人员可以在寻找性能提升空间时使用这类提示。
Listing 40 Vectorization: not benefificial.
1 // a.cpp
2 void stridedLoads(int *A, int *B, int n) {
3 #pragma clang loop vectorize(enable)
4 for (int i = 0; i < n; i++)
5 A[i] += B[i * 3];
6 }开发人员应该意识到使用向量化代码的隐藏成本。使用AVX和尤其是AVX512向量指令会导致频率大幅降低。代码的向量化部分应该足够热门，以证明使用AVX512是合理的。
8.2.3.5 Loop vectorized but scalar version used. //循环被向量化，但使用了标量版本。
在某些情况下，编译器可以成功地对代码进行向量化，但向量化代码在分析器中不可见。当检查循环的相应汇编代码时，通常很容易找到循环主体的向量化版本，因为它使用了向量寄存器，这在程序的其他部分通常不常见，并且代码被展开并填充了检查和多个版本，以适应不同的边缘情况。
如果生成的代码没有被执行，可能的原因之一是编译器生成的代码假设循环的迭代次数比程序实际使用的要高。例如，在现代CPU上有效地进行向量化，程序员需要使用AVX2进行向量化，并将循环展开4-5次，以便为流水线化的FMA单元生成足够的工作。这意味着每次循环迭代需要处理大约40个元素。许多循环的迭代次数可能低于此值，并且可能回退到使用标量的剩余循环。通过分析器可以轻松发现这些情况，标量的剩余循环会变得明显，而向量化代码则保持不活跃。
解决这个问题的方法是强制向量化器使用较低的向量化因子或展开次数，以减少循环处理的元素数量，并使更多迭代次数较低的循环访问快速向量化的循环主体。开发人员可以通过#pragma hints指令来实现这一点。对于Clang编译器，可以使用#pragma clang loop vectorize_width(N)，如easyperf博客中所示。
8.2.3.6 Loop vectorized in a suboptimal way
当你看到一个循环被向量化并在运行时执行时，通常意味着程序的这部分已经表现良好。然而，也有例外情况。有时候人工专家可以提出比编译器生成的代码更高效的代码。
最优的向量化因子可能不直观，原因有几个。首先，对于人类来说，想象CPU内部的操作是困难的，除了实际尝试多种配置外别无选择。涉及多个向量通道的向量重组操作可能比预期的更加昂贵，这取决于许多因素。其次，在运行时，程序可能以不可预测的方式行为，这取决于端口压力和许多其他因素。建议是尝试强制向量化器选择特定的向量化因子和展开因子，并测量结果。向量化指令可以帮助用户枚举不同的向量化因子，并找出最高性能的一种。
对于每个循环来说，可能的配置相对较少，而在典型输入上运行循环是人类能做到而编译器无法做到的。
最后，有些情况下，标量的未向量化版本的循环性能比向量化版本好。这可能是因为向量操作（如gather/scatter加载、掩码、重组等）很耗费资源，而编译器为了实现向量化必须使用这些操作。性能工程师也可以尝试以不同的方式禁用向量化。对于Clang编译器，可以通过编译选项-fno-vectorize和-fno-slp-vectorize来禁用，或者使用特定于特定循环的提示，例如#pragma clang loop vectorize(enable)。
8.2.3.7 Use languages with explicit vectorization.
向量化也可以通过使用专门用于并行计算的编程语言重写程序的部分来实现。这些语言使用特殊的结构和对程序数据的了解，将代码高效地编译成并行程序。最初，这些语言主要用于将工作转移到特定的处理单元，例如图形处理单元（GPU）、数字信号处理器（DSP）或可编程门阵列（FPGA）。然而，一些编程模型也可以针对CPU进行优化（例如OpenCL和OpenMP）。
其中一种并行语言是Intel® Implicit SPMD Program Compiler（ISPC），我们将在本节中介绍一些。ISPC语言基于C编程语言，并使用LLVM编译器基础架构为许多不同的体系结构生成优化代码。ISPC的关键特性是"接近底层"的编程模型和在SIMD体系结构上的性能可移植性。它要求从传统的编程思维方式转变，但给程序员更多控制CPU资源利用的权力。
ISPC的另一个优点是其互操作性和易用性。ISPC编译器生成的是标准的目标文件，可以与传统的C/C++编译器生成的代码链接。由于使用ISPC编写的函数可以像使用C代码一样调用，因此ISPC代码可以轻松地插入任何本地项目中。
在 ISPC 中，我们可以使用类似于程序清单 37 中展示的简单函数的示例来重写代码。ISPC将程序视为基于目标指令集的并行实例运行。例如，当使用 SSE 和浮点数时，它可以同时计算 4 个操作。每个程序实例将对向量值 i 进行操作，如 (0,1,2,3)，然后是 (4,5,6,7)，以此类推，从而一次有效地计算出 4 个和。正如您所看到的，使用了一些不典型于 C 和 C++ 的关键字：
• export 关键字表示该函数可以从与 C 兼容的语言中调用。
• uniform 关键字表示变量在程序实例之间共享。
• varying 关键字表示每个程序实例都有自己的变量副本。
• foreach 关键字与经典的 for 循环相同，只是它将工作分布在不同的程序实例之间。
Listing 41 ISPC version of summing elements of an array.
export uniform float calcSum(const uniform float array[],
uniform ptrdiff_t count)
{
varying float sum = 0;
foreach (i = 0 ... count)
sum += array[i];
return reduce_add(sum);
}由于函数 calcSum 必须返回一个单一值（一个 uniform 变量），而我们的 sum 变量是 varying 类型的，因此我们需要使用 reduce_add 函数来收集每个程序实例的值。ISPC还会根据需要生成 peeled 循环和余数循环，以考虑那些没有正确对齐或不是向量宽度的倍数的数据。
“贴近底层”的编程模型。传统的 C 和 C++ 语言存在一个问题，即编译器并不总是对代码的关键部分进行向量化优化。通常情况下，程序员会使用编译器内置函数（参见第10.2节），这绕过了编译器的自动向量化，但一般而言比较困难，并且需要在新的指令集出现时进行更新。ISPC通过默认将每个操作都视为SIMD操作来帮助解决这个问题。例如，ISPC 语句 sum += array[i] 在隐式中被视为一个并行进行多次相加的SIMD操作。ISPC不是一个自动向量化的编译器，它不会自动发现向量化的机会。由于 ISPC 语言与 C 和 C++ 非常相似，相比使用内置函数，ISPC 更好地允许您专注于算法而不是低级指令。此外，据报道，在性能方面，ISPC 的性能与手写的内置函数代码相媲美[Pharr 和 Mark 2012]或超越[228]。
性能可移植性。ISPC 可以自动检测 CPU 的特性，以充分利用所有可用的资源。程序员可以编写一次 ISPC 代码，然后编译为许多矢量指令集，如 SSE4、AVX 和 AVX2。ISPC 还可以为不同的架构生成代码，如 x86 CPU、ARM NEON，并且还具有实验性的对 GPU 卸载的支持。
8.3 Chapter Summary
• 大多数实际应用程序经历的性能瓶颈与 CPU 后端相关。这并不奇怪，因为与内存相关的问题以及低效的计算都属于这个类别。
• 内存子系统的性能增长速度不及 CPU 的性能增长速度。然而，在许多应用程序中，内存访问是性能问题的常见来源。加速这类程序需要重新审查它们访问内存的方式。
• 在第8.1节中，我们讨论了一些常见的缓存友好数据结构、内存预取和利用大内存页面来改善 DTLB 性能的技巧。
• 低效的计算也在实际应用程序的性能瓶颈中占据重要部分。现代编译器非常擅长通过执行许多不同的代码转换来消除不必要的计算开销。然而，我们有很大机会比编译器提供的优化效果更好。
• 在第8.2节中，我们展示了如何通过强制进行某些代码优化来搜索程序中的性能潜力。我们讨论了诸如函数内联、循环优化和向量化等常见的转换方法。
9 Optimizing Bad Speculation
现代CPU中的预测功能在第3.3.3节中有描述。当分支预测错误时，会导致显著的速度惩罚。当这种情况经常发生时，CPU需要清除之前提前完成的所有推测工作，并重新开始填充正确路径的指令。通常，由于分支预测错误，现代CPU会经历15-20个时钟周期的惩罚。
如今，处理器在预测分支结果方面非常出色。它们不仅可以遵循静态预测规则，还可以检测动态模式。通常，分支预测器会保存先前分支结果的历史记录，并试图猜测下一个结果。然而，当模式变得难以跟随对CPU分支预测器来说，它可能会影响性能。通过查看TMA Bad Speculation指标，可以了解程序因分支预测错误而受到的影响程度。
个人经验：程序总是会发生一定数量的分支预测错误。普通应用程序的“Bad Speculation”率在5-10%的范围内是正常的。如果这个指标超过了10%，我建议注意一下。
由于分支预测器擅长寻找模式，因此以往优化分支预测的建议已不再适用。过去可以通过在分支指令前添加一个预测提示（0x2E：分支不被采取，0x3E：分支被采取）来提高性能。尽管这种技术可以改善旧平台上的性能，但在新平台上并不会产生收益。
也许，摆脱分支预测错误的唯一直接方法就是摆脱分支本身。在接下来的两节中，我们将了解如何使用查找表和条件执行来替代分支。
9.1 Replace branches with lookup //将分支替换为查找表
使用查找表可以避免分支语句，从而提高性能。在代码示例中，函数mapToBucket将值映射到相应的桶中。对于均匀分布的值v，它们被映射到各个桶的概率是相等的。在基准版本生成的汇编代码中，通常会看到很多分支语句，这可能导致高错误预测率。希望能够通过使用单个数组查找来重写mapToBucket函数，如Listing 43所示。
Listing 43中的mapToBucket函数的汇编代码应该只使用一条分支语句，而不是多条。对于典型的热路径，该函数将执行未使用的分支和一条加载指令。由于我们预计大多数输入值将落入buckets数组覆盖的范围内，用于保护越界访问的分支将被CPU正确预测。此外，buckets数组相对较小，因此我们可以期待它位于CPU缓存中，这将确保对它的快速访问。[Lemire, 2020]
Listing 42 Replacing branches: baseline version.
int mapToBucket(unsigned v) {
if (v >= 0 && v < 10) return 0;
if (v >= 10 && v < 20) return 1;
if (v >= 20 && v < 30) return 2;
if (v >= 30 && v < 40) return 3;
if (v >= 40 && v < 50) return 4;
return -1;
}Listing 43 Replacing branches: lookup version.
int buckets[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
... };
int mapToBucket(unsigned v) {
if (v < (sizeof (buckets) / sizeof (int)))
return buckets[v];
return -1;
}当需要映射一个更大范围的值时，分配一个非常大的数组是不切实际的。在这种情况下，我们可以使用区间映射数据结构来实现这一目标，它可以使用较少的内存但具有对数级的查找复杂度。读者可以在Boost和LLVM中找到现有的区间映射容器的实现。
9.2 Replace branches with predication
有些分支语句可以通过执行分支的两个部分并选择正确的结果来有效地消除（条件执行）。当存在这种情况时，可能会尝试使用转换来消除if条件判断语句，如Listing 44所示。
对于Listing 45中的代码版本，编译器可以消除分支并生成CMOV指令234。CMOVcc指令检查EFLAGS寄存器中一个或多个状态标志（CF、OF、PF、SF和ZF）的状态，并在标志处于指定状态（或条件）时执行移动操作。[Int, 2020, Volume 2]下面是基准版本和改进版本的两个汇编清单：
修改后的汇编代码序列不再包含原始的分支指令。然而，在第二个版本中，x和y都是独立计算的，然后只选择一个值。虽然这种转换消除了分支预测错误的成本，但它可能比原始代码执行更多的工作。性能改进在很大程度上取决于computeX和computeY函数的特性。如果这些函数很小且编译器能够内联它们，那么可能会带来明显的性能优势。如果这些函数很大，那么承受分支预测错误的代价可能比执行两个函数更低廉。
需要注意的是，条件执行并不总是对应用程序的性能有益。条件执行的问题在于它限制了CPU的并行执行能力。对于Listing 44中的代码片段，CPU可以选择if条件的true分支，并继续以a = computeX()的值进行代码的推测执行。例如，如果后续存在使用a索引数组元素的加载操作，这个加载可以在我们得知if分支的真实结果之前就发出。对于Listing 45中的代码，这种推测是不可能的，因为CPU不能在CMOVNE指令完成之前发出使用a的加载指令。
因此，是否使用条件执行（predication）取决于具体情况。在某些情况下，消除分支预测错误的成本可能超过了通过条件执行带来的性能改进。在进行优化时，需要权衡条件执行和并行执行之间的平衡，以获得最佳性能。
二分查找（binary search）是一个很好的例子，可以展示在选择标准版本和无分支版本代码之间进行权衡时所涉及的折衷。下面是两种情况的描述：
1. 对于一个大数组的搜索，该数组不适合存储在CPU缓存中，基于分支的二分查找版本表现更好，因为与内存访问的延迟相比（由于缓存未命中而较高），分支预测错误的代价较低。由于存在分支，CPU能够推测它们的结果，这允许同时从当前迭代和下一迭代加载数组元素。推测还会继续进行，可能会同时存在多个加载操作。
2. 对于适合存储在CPU缓存中的小数组，情况则相反。无分支的二分查找仍然需要将所有的内存访问串行化，正如前面解释的那样。但是，这次加载操作的延迟很小（只有几个周期），因为数组适合CPU缓存。基于分支的二分查找会遭受持续的预测错误，其代价约为20个周期。在这种情况下，预测错误的代价远大于内存访问的代价，因此无法获得推测执行带来的好处。在这种情况下，无分支版本通常会更快。
二分查找是一个很好的例子，可以说明在选择标准版本和无分支版本实现时如何进行推理。现实世界中的场景可能更难分析，因此建议测量数据，判断是否有必要在你的情况下替换分支语句。
9.3 Chapter Summary
• 现代处理器在预测分支结果方面表现非常出色。因此，我建议只有在TMA报告指出存在高不良预测度量时才开始修复分支预测错误的工作。
• 当分支预测器难以跟踪分支结果模式时，应用程序的性能可能会受到影响。在这种情况下，无分支版本的算法可能更好。在本章中，我们展示了如何使用查找表和条件执行来替换分支语句。在某些情况下，还可以使用编译器内置函数来消除分支，就像[Kapoor, 2009]所示。
• 无分支算法并不是普遍适用的。始终进行测量，以确定在你的情况下哪种方式更好。
10 Other Tuning Areas
在本章中，我们将介绍一些与前三章中讨论的类别没有明确关联但仍然非常重要的优化主题。这些主题虽然不属于特定的类别，但在本书中找到它们的位置是非常有意义的。
10.1 Compile-Time Computations //编译时计算
如果程序的一部分执行的计算与输入无关，可以提前进行预计算，而不是在运行时执行。现代优化编译器已经将很多计算移到编译时，特别是像 int x = 2 * 10 这样的简单情况转换为 int x = 20。然而，如果涉及到分支、循环和函数调用等更复杂的计算，在编译时处理可能会有困难。C++语言提供了一些功能，可以确保某些计算在编译时发生。
在C++中，可以使用各种元编程技术将计算转移到编译时。在C++11/14之前，开发人员使用模板来实现这一目标。理论上，可以使用模板元编程来表示任何算法，但这种方法往往语法复杂，编译速度较慢。然而，这是一种成功的方法，它开启了一类新的优化方式。幸运的是，随着每个新的C++标准推出，元编程变得更加简单。C++14标准允许使用constexpr函数，而C++17标准则提供了if constexpr关键字来实现编译时分支。这种新的元编程方式允许在编译时进行许多计算，同时不影响代码的可读性。[Fog, 2004, 第15章 元编程]
以下是通过将计算转移到编译时来优化应用程序的示例46。假设程序涉及对一个数是否为质数的测试。如果我们知道大部分被测试的数字都小于1024，我们可以预先计算结果，并将它们保存在一个constexpr数组primes中。在运行时，大部分isPrime函数的调用只需要从primes数组中加载一次数据，这比在运行时计算要快得多。
10.2 Compiler Intrinsics //编译器内置函数
有些应用程序很少有需要大量调优的热点部分。然而，编译器在这些热点位置生成的代码并不总是符合我们的期望。例如，一个程序在循环中进行一些计算，但编译器以次优的方式进行了向量化。这通常涉及一些棘手或特殊的算法，我们可以想出更好的指令序列来实现。使用C和C++语言的标准结构很难甚至不可能让编译器生成所需的汇编代码。
幸运的是，有办法在不编写低级汇编语言的情况下，强制编译器生成特定的汇编指令。为了实现这一点，可以使用编译器内置函数（compiler intrinsics），它们会被转换成具体的汇编指令。内置函数具有与内联汇编相同的好处，但同时提高了代码的可读性，允许编译器类型检查，帮助指令调度，并有助于减少调试工作。示例中的代码清单47展示了如何使用编译器内置函数（函数bar）重写函数foo中的同样循环的例子。
在代码清单47中，两个函数生成了类似的汇编指令。然而，还有几个注意事项。首先，当依赖自动向量化时，编译器会插入所有必要的运行时检查。例如，它会确保有足够的元素供应给向量执行单元。其次，函数foo将为处理循环剩余部分生成一个回退的标量版本。最后，大多数向量内置函数假设数据是对齐的，因此bar使用了movaps（对齐加载），而foo使用了movups（非对齐加载）。在使用编译器内置函数时，开发人员必须自行处理安全方面的问题。
当使用非可移植的平台特定内置函数编写代码时，开发人员还应为其他架构提供备选方案。可以在该参考文档中找到适用于Intel平台的所有可用内置函数的列表。
10.3 Cache Warming //缓存预热
第7节和第8.1.1节详细介绍了指令缓存和数据缓存，以及它们各自的性能影响，并提供了具体的技术来最大化利益。然而，在某些应用负载中，对延迟最敏感的代码部分往往是最不经常执行的。这导致函数块和相关数据随着时间推移从指令缓存(I-cache)和数据缓存(D-cache)中被淘汰出去。然后，就在我们需要执行那个关键但很少执行的代码片段时，我们遇到了I-cache和D-cache的缺失惩罚，这可能超过我们的目标性能预算。
这样的负载示例可以是一个高频交易应用程序，它持续从股票交易所读取市场数据信号，并在检测到有利的市场信号时向交易所发送买入订单。在上述负载中，涉及读取市场数据的代码路径最常执行，而执行买入订单的代码路径很少执行。如果我们希望我们的买入订单尽快达到交易所，并利用市场数据中检测到的有利信号，则在决定执行关键代码时不希望出现缓存缺失。这就是缓存预热技术的帮助之处。缓存预热包括定期运行延迟敏感的代码，以使其保持在缓存中，同时确保不会完全执行任何不需要的操作。运行延迟敏感的代码还可以“热身”数据缓存，将延迟敏感的数据引入其中。事实上，这种技术经常用于像CppCon 2018 lightning演讲中描述的交易应用程序中。
10.4 Detecting Slow FP Arithmetic
对于使用浮点数值的应用程序，存在一定的概率会出现异常情况，即浮点数变为非规格化数。对非规格化数进行操作可能会变得慢10倍甚至更多。当CPU处理尝试对非规格化浮点数进行算术操作的指令时，需要对这种情况进行特殊处理。由于这是异常情况，CPU会请求微码辅助。微码序列器（MSROM）将向流水线提供大量微操作（参见4.4节），以处理这种情况。
TMA方法将这类瓶颈归类为“Retiring”（退休）类别。这是“高Retiring”并不意味着好事情的情况之一。由于对非规格化数进行的操作通常代表程序的不良行为，可以只收集FP_ASSIST.ANY性能计数器的值。该值应该接近零。Blog easyperf中介绍了一个进行非规格化浮点运算并因此遇到许多FP assist的示例。C++开发人员可以通过使用std::isnormal()函数来防止其应用程序陷入与次正常值的操作。或者，可以更改SIMD浮点运算的模式，在CPU控制寄存器中启用“flush-to-zero”（FTZ）和“denormals-are-zero”（DAZ）标志，以防止SIMD指令生成非规格化数。在代码级别禁用次正常浮点数可以使用专用宏来完成，这可能因编译器而异。
10.5 System Tuning
在调优应用程序以充分利用CPU微架构的各种复杂功能之后，我们最不希望的就是系统固件、操作系统或内核破坏我们的努力。即使是经过高度调优的应用程序，如果遭遇系统管理中断（SMI），即整个操作系统被停止以执行固件代码的BIOS中断，那么它的意义也将变得微乎其微。这种中断可能每次运行10到100毫秒。
可以说，开发人员通常对应用程序执行的环境几乎没有任何控制权。当我们发布产品时，不太可能调整每个客户可能拥有的设置。通常，足够大的组织会有专门的运维团队来处理此类问题。然而，当与这些团队的成员进行沟通时，了解其他可能限制应用程序性能的因素非常重要。
如第2.1节所示，现代系统有许多需要调整的地方，避免受到系统干扰并不容易。一份针对基于x86服务器部署的性能调优手册的示例是Red Hat的指南。在那里，您将找到消除或显著减少来自系统BIOS、Linux内核和设备驱动程序等应用程序干扰源的缓存中断的提示，以及许多其他应用程序干扰源。在将任何应用程序部署到生产环境之前，这些指南应作为所有新服务器构建的基准镜像。
对于调整特定的系统设置，往往并不总是一个简单的“是”或“否”的答案。例如，您的应用程序是否会受益于启用了环境中的Simultaneous Multi-Threading (SMT)功能，事先并不清楚。一般的指导方针是只为展示相对较低IPC的异构工作负载启用SMT。另一方面，如今CPU制造商提供的处理器核心数量如此之高，以至于SMT远不像过去那样必要。然而，这只是一个一般的指导方针，正如本书中所强调的一切，最好根据自己的实际情况进行测量。
大多数开箱即用的平台都配置为在尽可能节省电力的同时实现最佳吞吐量。但是有些行业对实时性要求更高，比其他一切更关心较低的延迟。例如，汽车组装线上运行的机器人就是这样一个行业的例子。这些机器人执行的动作是由外部事件触发的，通常有事先确定的时间预算，因为下一个中断即将到来（通常称为“控制循环”）。满足此类平台的实时目标可能需要牺牲机器的总吞吐量，或者允许它消耗更多能源。在这个领域中，一个流行的技术是禁用处理器的睡眠状态，以保持其随时准备作出反应。另一种有趣的方法被称为Cache Locking，它为特定数据集保留了CPU缓存的部分空间，有助于优化应用程序内的内存延迟。
11 Optimizing Multithreaded Applications
现代CPU每年都在不断增加核心数量。截至2020年，您可以购买一款具有50个以上核心的x86服务器处理器！甚至一个中档台式机通常也会配置8个执行线程。由于每个CPU都拥有如此强大的处理能力，如何有效利用所有的硬件线程成为一个挑战。为了应用程序未来的成功，准备软件以适应日益增长的CPU核心数量非常重要。
多线程应用程序有其特殊性。在处理多个线程时，某些单线程执行的假设将被否定。例如，我们不能再通过查看单个线程来确定热点，因为每个线程可能有自己的热点。在常见的生产者-消费者设计中，生产者线程可能在大部分时间都处于休眠状态。对这样的线程进行分析无法揭示为什么我们的多线程应用程序无法良好扩展的原因。
11.1 Performance Scaling And Overhead //性能扩展和开销
在处理单线程应用程序时，对程序的某一部分进行优化通常会对性能产生积极影响。然而，在多线程应用程序中，情况并非一定如此。有些应用程序中，线程A执行一些非常耗时的操作，而线程B则很早就完成了任务，只是在等待线程A完成。无论我们如何改进线程B，应用程序的延迟都不会减少，因为它将受到运行时间较长的线程A的限制。
这种效果被广泛称为阿姆达尔定律，它规定了并行程序的加速比受到其串行部分的限制。图46展示了理论上加速限制与处理器数量的关系。对于一个75%并行的程序，加速因子趋于4。
Figure 47a展示了Starbench并行基准套件中h264dec基准测试的性能扩展情况。我在拥有4个核心/8个线程的Intel Core i5-8259U上进行了测试。请注意，在使用了4个线程之后，性能的扩展并不明显。很可能，获取一个拥有更多核心的CPU也无法提高性能。
实际上，进一步增加计算节点到系统中可能会导致性能的倒退。这种效应可以通过Neil Gunther提出的通用可伸缩性定律（Universal Scalability Law，USL）来解释，该定律是阿姆达尔定律的一个扩展。USL描述了计算节点（线程）之间的通信作为另一个限制性能的因素。随着系统的扩展，开销开始阻碍性能的提升。超过临界点后，系统的能力开始下降（参见图48）。USL被广泛用于建模系统的容量和可伸缩性。
USL描述的性能下降由几个因素驱动。首先，随着计算节点数量的增加，它们开始竞争资源（争用）。这导致额外的时间用于同步这些访问。另一个问题出现在多个工作线程之间共享的资源上。我们需要在多个工作线程之间保持共享资源的一致状态（一致性）。例如，当多个工作线程频繁更改某个全局可见对象时，这些更改需要广播到使用该对象的所有节点。由于额外的一致性维护需求，通常操作开始花费更多时间完成。在Intel Core i5-8259U上的h264dec基准测试中，通信开销可以在图47b中观察到。请注意，随着我们为该任务分配超过4个线程，基准测试在执行的指令和核心周期方面都遇到了更多的开销。
优化多线程应用程序不仅涉及到本书中描述的所有技术，还需要检测和缓解争用和一致性带来的影响。下面的小节将介绍用于解决这些额外挑战以调优多线程程序的技术。
11.2 Parallel Efficiency Metrics //并行效率指标
在处理多线程应用程序时，工程师应该小心地分析基本指标，如CPU利用率和IPC（参见第4节）。其中一个线程可能显示出高CPU利用率和高IPC，但实际上它可能只是在一个锁上自旋。这就是为什么在评估应用程序的并行效率时，建议使用有效的CPU利用率，它只基于有效时间。
11.2.1 Effective CPU Utilization
表示应用程序有效利用可用的CPU的效率。它显示系统上所有逻辑CPU的平均CPU利用率的百分比。CPU利用率指标仅基于有效时间，不包括并行运行时系统和自旋时间引入的开销255。100%的CPU利用率意味着您的应用程序在运行的整个时间内保持所有逻辑CPU核心繁忙。[Int, 2020]
对于指定的时间间隔T，可以计算出有效CPU利用率的公式如下：
11.2.2 Thread Count
应用程序通常具有可配置的线程数量，这使它们能够在具有不同核心数量的平台上高效运行。显然，如果使用的线程数低于系统可用的线程数，则会浪费其资源。另一方面，运行过多的线程可能会导致CPU时间增加，因为某些线程可能正在等待其他线程完成，或者时间可能浪费在上下文切换上。除了实际的工作线程，多线程应用程序通常还有辅助线程：主线程、输入和输出线程等。如果这些线程占用了大量时间，它们就需要专用的硬件线程。这就是为什么知道总线程数并正确配置工作线程数非常重要。
为了避免线程创建和销毁的开销，工程师通常会分配一个线程池，其中包含多个线程等待任务由监督程序分配并进行并发执行。这对于执行短期任务尤其有益。
11.2.3 Wait Time
等待时间发生在软件线程由于阻塞或导致同步的API而等待时。等待时间是每个线程的时间；因此，总等待时间可以超过应用程序的经过时间。[Int, 2020]
由于同步或抢占，操作系统调度程序可以将线程从执行中切换出来。因此，等待时间可以进一步分为同步等待时间和抢占等待时间。大量的同步等待时间可能意味着应用程序具有高度竞争的同步对象。我们将在以下部分探讨如何找到它们。显著的抢占等待时间可以表示线程过多的问题，可能是由于应用程序线程数量过多或与操作系统线程或系统上的其他应用程序冲突。在这种情况下，开发人员应考虑减少总线程数或增加每个工作线程的任务粒度。
11.2.4 Spin Time
自旋时间是CPU繁忙的等待时间。这通常发生在同步API导致软件线程等待时，CPU需要进行轮询。[Int, 2020]。
实际上，内核同步原语的实现更倾向于在锁定期间进行一段时间的自旋，而不是立即进行线程上下文切换（这是昂贵的）。然而，过多的自旋时间可能反映了无法进行有效工作的机会的丧失。
11.3 Analysis With Intel VTune Profiler
Intel VTune Profiler使用专门针对多线程应用程序的分析类型，称为线程分析。它的摘要窗口（见图49）显示了关于整个应用程序执行的统计信息，识别了我们在第11.2节中描述的所有指标。通过有效CPU利用率直方图，我们可以了解捕获到的应用程序行为的几个有趣事实。首先，平均而言，同一时间只有5个硬件线程（图表上的逻辑核心）被利用。其次，几乎从未同时激活所有8个硬件线程。
11.3.1 Find Expensive Locks
接下来，工作流程建议我们识别最有争议的同步对象。图50显示了这些对象的列表。我们可以看到__pthread_cond_wait明显突出，但由于程序中可能有数十个条件变量，我们需要知道哪个是CPU利用率低下的原因。
为了知道这一点，我们可以简单地点击__pthread_cond_wait，这将让我们进入底部向上视图，如图51所示。我们可以看到导致线程在条件变量上等待的最常见路径（等待时间的47%）：__pthread_cond_wait <- x264_8_frame_cond_wait <- mb_analyse_init。
接下来，我们可以通过在分析中双击相应的行，跳转到x264_8_frame_cond_wait的源代码（参见图52）。然后，我们可以研究锁的原因，以及使该位置的线程通信更高效的可能方法。
11.3.2 Platform View
Intel VTune Profiler的另一个非常有用的功能是平台视图（参见图53），它允许我们观察程序执行的任何时刻每个线程在做什么。这对于理解应用程序的行为并找到潜在的性能空间非常有帮助。例如，我们可以看到在从1秒到3秒的时间间隔内，只有两个线程持续地利用了相应的CPU核心的约100%（TID为7675和7678的线程）。在该时间间隔内，其他线程的CPU利用率是突发性的。
平台视图还具有缩放和过滤功能。这使我们能够了解每个线程在指定的时间范围内执行的操作。要查看此内容，选择时间线上的范围，右键单击并选择“放大”和“通过选择进行过滤”。Intel VTune Profiler将显示在此时间范围内使用的函数或同步对象。
11.4 Analysis with Linux Perf
Linux perf工具可以对应用程序可能创建的所有线程进行性能分析。它具有-s选项，可以记录每个线程的事件计数。使用此选项，在报告的末尾，perf会列出所有线程的线程ID以及每个线程收集的样本数：
要过滤特定软件线程的样本，可以使用--tid选项：
Linux perf还自动提供了我们在11.2节中讨论的一些指标：
11.4.1 Find Expensive Locks
要使用Linux perf找到最具争用的同步对象，需要对调度器上下文切换（sched:sched_switch）进行采样，这是一个内核事件，因此需要root权限：
上面的输出显示了哪些线程最频繁地被切换出执行。请注意，我们还收集调用堆栈（--call-graph dwarf，参见第5.4.3节），因为我们需要它来分析导致昂贵的同步事件的路径：
上面的列表显示了导致等待条件变量（__pthread_cond_wait）和后续的上下文切换最频繁的路径。这个路径是x264_8_macroblock_analyse -> mb_analyse_init -> x264_8_frame_cond_wait。从这个输出中，我们可以得知84%的所有上下文切换是由于在x264_8_frame_cond_wait内的线程等待条件变量引起的。
11.5 Analysis with Coz
在11.1节中，我们定义了识别影响多线程程序整体性能的代码部分的挑战。由于各种原因，优化多线程程序的某个部分并不总是会产生明显的结果。Coz259是一种新型的分析器，它解决了这个问题，并填补了传统软件分析器留下的空白。它使用一种称为“因果分析”的新技术，在应用程序运行时通过虚拟加速代码段来预测某些优化的总体效果。它通过插入减慢所有其他并发运行代码的暂停来实现这些“虚拟加速”。[Curtsinger和Berger，2015]
将Coz分析器应用于Phoronix测试套件中的C-Ray基准的示例显示在第54页上。根据图表，如果我们将c-ray-mt.c中的第540行的性能提高20％，Coz预计C-Ray基准整体应用程序性能会相应增加约17％。一旦我们在该行上达到约45％的改进，按照Coz的估计，对应的应用程序的影响开始趋于平稳。有关此示例的更多详细信息，请参阅easyperf博客上的文章。
11.6 Analysis with eBPF and GAPP
Linux支持各种线程同步原语，包括互斥锁、信号量、条件变量等。内核通过futex系统调用支持这些线程原语。因此，通过在内核中跟踪futex系统调用的执行，并收集涉及的线程的有用元数据，可以更容易地识别争用瓶颈。Linux提供了内核跟踪/分析工具来实现这一点，其中最强大的是Extended Berkeley Packet Filter（eBPF）。
eBPF是基于一个在内核中运行的沙盒化虚拟机，它允许在内核内安全高效地执行用户定义的程序。这些用户定义的程序可以用C语言编写，并通过BCC编译器262编译成BPF字节码，以便加载到内核虚拟机中。这些BPF程序可以在特定的内核事件执行时启动，并通过各种方式将原始或处理后的数据返回给用户空间。
开源社区提供了许多用于通用目的的eBPF程序。其中一个工具是通用自动并行分析器(GAPP)，它帮助跟踪多线程争用问题。GAPP使用eBPF来跟踪多线程应用程序的争用开销，通过对已识别的串行化瓶颈的重要性进行排名，收集被阻塞的线程和导致阻塞的线程的堆栈跟踪信息。GAPP最好的一点是它不需要代码更改、昂贵的插装或重新编译。GAPP分析器的创建者能够确认已知的瓶颈，并且在Parsec 3.0基准套件263和一些大型开源项目上揭示了新的、以前未报告的瓶颈。[Nair和Field，2020]
11.7 Detecting Coherence Issues
11.7.1 Cache Coherency Protocols
多处理器系统采用缓存一致性协议来确保在每个含有独立缓存实体的核心共享使用内存时的数据一致性。如果没有这样的协议，如果CPU A和CPU B都将内存位置L读入其各自的缓存中，并且处理器B随后修改了其缓存中L的值，那么这两个CPU会对相同内存位置L拥有不一致的值。缓存一致性协议确保任何对缓存条目的更新都会被及时地更新到相同位置的任何其他缓存条目中。
最著名的缓存一致性协议之一是MESI（Modified Exclusive Shared Invalid），它用于支持类似于现代CPU中使用的写回缓存。它的首字母缩写表示缓存行可能被标记的四种状态（见图55）：
• Modified - 缓存行仅存在于当前缓存中，并且已被修改，与RAM中的值不同。
• Exclusive - 缓存行仅存在于当前缓存中，并且与RAM中的值相匹配。
• Shared - 缓存行既存在于此处，也存在于其他缓存行中，并且与RAM中的值相匹配。
• Invalid - 缓存行未使用（即不包含任何RAM位置）。
当从内存中获取时，每个缓存行都有一个编码的状态标记。然后，缓存行的状态会从一个状态转换到另一个264。实际上，CPU厂商通常会实现稍微改进的MESI变体。例如，Intel使用MESIF265，它添加了一个Forwarding（F）状态，而AMD使用MOESI266，则添加了Owning（O）状态。但是这些协议仍然保持了基本MESI协议的核心。
正如前面的例子所示，缓存一致性问题可能会导致程序的顺序不一致。通过使用侦听式缓存来监视所有内存事务并相互协作以维护内存一致性，可以减轻这个问题。不幸的是，这种方法会带来一些成本，因为一个处理器对缓存线的修改会使另一个处理器的相应缓存行无效。这会导致内存停顿并浪费系统带宽。与只能限制应用程序性能的串行化和锁定问题不同，一致性问题可能会导致USL在第11.1节中所描述的逆向效果。两种广为人知的一致性问题类型是“真共享”和“假共享”，接下来我们将探讨这两种问题。
11.7.2 True Sharing
真共享是指两个不同的处理器访问同一个变量时发生的情况（见列表48）。
首先，真共享意味着可能难以检测的数据竞争。幸运的是，有一些工具可以帮助识别此类问题。Clang的Thread Sanitizer和helgrind就是其中的一些工具。为了避免列表48中的数据竞争，应将sum变量声明为std::atomic<unsigned int> sum。
使用C++原子操作可以帮助解决真共享时的数据竞争问题。然而，这实际上会对原子变量的访问进行串行化，可能会影响性能。解决真共享问题的另一种方式是使用线程本地存储（TLS）。TLS是在给定的多线程进程中，每个线程都可以分配内存来存储线程特定数据的方法。通过这样做，线程修改它们的本地副本，而不是争用全局可用内存位置。在列表48中，可以通过使用TLS类说明符来修复示例：thread_local unsigned int sum（自C++11起）。主线程然后应该合并所有工作线程的本地副本的结果。
11.7.3 False Sharing
错误共享（False Sharing）是指两个不同的处理器修改不同的变量，这些变量恰好位于同一个缓存行上（见列表49）。图56说明了错误共享问题。对于多线程应用程序来说，错误共享经常是性能问题的来源。因此，现代分析工具内置了检测此类情况的支持。TMA将经历真/假共享的应用程序描述为内存受限。通常，在这种情况下，您会看到争用访问度量指标（Contested Accesses）的高值。
在使用Intel VTune Profiler时，用户需要进行两种类型的分析来查找和消除错误共享问题。首先，运行微架构探索（Microarchitecture Exploration）分析，该分析实施了TMA方法来检测应用程序中是否存在错误共享。正如前面所提到的，争用访问度量指标的高值促使我们深入挖掘并运行Memory Access分析，并启用“分析动态内存对象”选项。该分析有助于找出导致争用问题的数据结构的访问。通常，这种内存访问具有较高的延迟，这将由分析揭示。在Intel开发者社区中有使用Intel VTune Profiler解决错误共享问题的示例。
Linux perf也支持查找错误共享。与Intel VTune Profiler类似，首先运行TMA（参见章节6.1.2）以了解程序是否存在错误共享问题。如果是这种情况，可以使用perf c2c工具来检测具有高缓存一致性成本的内存访问。perf c2c会匹配不同线程的存储和加载地址，看看是否发生了修改缓存行的命中。读者可以在专门的博客文章中找到关于该过程和如何使用工具的详细解释。
可以通过对齐/填充内存对象来消除错误共享。在第11.7.2节的示例中，可以通过确保sumA和sumB不共享同一个缓存行来解决问题（详见第8.1.1.4节）。
从性能的一般角度考虑，最重要的是考虑可能的状态转换的成本。在所有缓存状态中，唯一不涉及昂贵的跨缓存子系统通信和数据传输的是Modified (M)和Exclusive (E)状态。因此，缓存行保持M或E状态的时间越长（即跨缓存的数据共享越少），多线程应用程序所产生的一致性开销就越低。在Nitsan Wakart的博客文章《深入研究缓存一致性》中可以找到一个展示这个属性如何被应用的示例。
11.8 Chapter Summary
• 不充分利用现代多核CPU的应用程序将落后于竞争对手。为了未来应用程序的成功，准备软件以适应日益增长的CPU核心数量非常重要。
• 处理单线程应用程序时，优化程序的一部分通常会对性能产生积极影响。然而，对于多线程应用程序，情况并非总是如此。这种效应被广泛称为阿姆达尔定律，它规定并行程序的加速比受限于其串行部分。
• 线程间通信可能导致速度变慢，这可以通过通用可扩展性定律解释。这给调优多线程程序带来了额外的挑战。优化多线程应用程序的性能还涉及检测和减轻争用和一致性效应。
• Intel VTune Profiler是分析多线程应用程序的“首选”工具。但在过去几年中，还出现了其他具有独特功能的工具，例如Coz和GAPP。
Epilog
//后记
感谢您阅读整本书。我希望您喜欢并且觉得有用。如果这本书能帮助您解决实际问题，我将更加开心。在这种情况下，我会认为这是一次成功，证明我的努力没有白费。在您继续努力之前，让我简要总结一下本书的要点，并给出最后的建议：
• 硬件性能增长的速度不如过去几年快。性能调优比过去40年更为关键。在不久的将来，它将是性能提升的关键驱动因素之一。
• 软件默认情况下并不具备最佳性能。存在某些限制，阻止应用程序充分发挥其性能潜力。硬件和软件组件都有这样的限制。
• “过早优化是万恶之源”。但相反的情况也经常发生。推迟性能工程可能为时已晚，并且可能会造成与过早优化同样的问题。设计未来产品时不要忽视性能方面的考虑。
• 现代系统的性能是不确定的，取决于许多因素。有意义的性能分析应考虑噪声，并使用统计方法分析性能测量数据。
• 理解CPU微架构可以帮助您理解进行的实验结果。然而，在对代码进行具体更改时不要过于依赖这种知识。您的心理模型永远无法像CPU内部的实际设计一样准确。几乎不可能预测特定代码片段的性能。始终进行测量！
• 性能优化很困难，因为没有预先确定的步骤或算法可供遵循。工程师需要从不同角度解决问题。了解可用的性能分析方法和工具（包括硬件和软件）。如果您的平台支持，我强烈建议采用Roofline模型和TMA方法。它将帮助您正确引导工作方向。此外，了解何时可以利用其他硬件性能监控功能，例如LBR、PEBS和PT。
• 理解应用程序性能的限制因素以及修复的可能方式。第2部分介绍了针对每种类型的CPU性能瓶颈的一些基本优化方法：前端瓶颈、后端瓶颈、退出和错误推测。当您的应用程序属于上述四种类别之一时，请参阅第7-10章了解可用的选项。
• 如果修改的效益微乎其微，应保持代码的简洁和清晰。
• 有时，改进一个系统上的性能可能会减慢另一个系统上的执行速度。确保在您关心的所有平台上测试您的更改。
这些要点提供了对开发人员在改善应用程序性能方面的宝贵指导。
希望这本书能帮助您更好地理解您的应用程序性能和CPU性能的一般情况。当然，它并没有涵盖您在进行性能优化工作时可能遇到的所有可能场景。我的目标是给您一个起点，并向您展示在现代CPU上处理性能分析和调优的潜在选择和策略。
如果您喜欢阅读这本书，请务必将其传给您的朋友和同事。我会感激您在社交媒体平台上推广这本书的帮助。
我很愿意听取您对这本书的反馈意见，您可以通过我的电子邮件dendibakh@gmail.com与我联系。请让我知道您的想法、意见和对这本书的建议。我将在我的博客easyperf.net上发布有关这本书的所有更新和未来信息。
祝您进行性能调优时顺利愉快！
Appendix A. Reducing Measurement Noise
以下是可能导致性能测量中增加不确定性的一些特征示例。请参阅第2.1节中的完整讨论。
Dynamic Frequency Scaling
动态频率调整（Dynamic Frequency Scaling，DFS）是一种通过在运行要求高的任务时自动提高CPU工作频率来增加系统性能的技术。举个DFS实施的例子，Intel CPU具有Turbo Boost功能，而AMD CPU则采用Turbo Core功能。
以下是在Intel® Core™ i5-8259U上运行单线程工作负载时，Turbo Boost可能产生的影响示例：
当启用Turbo Boost时，平均频率要高得多。
DFS可以在BIOS中永久禁用。在Linux系统上以编程方式禁用DFS功能，您需要root访问权限。下面是实现此目的的方法：
Simultaneous Multithreading //同时多线程?
现代CPU核心通常采用同时多线程（Simultaneous Multithreading，SMT）的方式制造。这意味着在一个物理核心中，可以同时执行两个线程。通常，架构状态会被复制，但执行资源（ALU、缓存等）不会被复制。这意味着如果我们在同一个核心上以“同时”的方式运行两个独立的进程（在不同的线程中），它们可以相互竞争资源，例如缓存空间。
SMT可以在BIOS中永久禁用。在Linux系统上以编程方式禁用SMT，您需要root访问权限。下面是如何关闭每个核心的兄弟线程的方法：
echo 0 > /sys/devices/system/cpu/cpuX/onlineCPU线程的兄弟对可以在以下文件中找到：
/sys/devices/system/cpu/cpuN/topology/thread_siblings_list例如，在具有4个核心和8个线程的Intel® Core™ i5-8259U上：
Scaling Governor //频率调整策略
Linux内核能够控制CPU频率以实现不同的目的。其中之一是为了节省功耗，在这种情况下，Linux内核中的频率调整策略（Scaling Governor）可以决定降低CPU运行频率。为了进行性能测量，建议将频率调整策略设置为performance，以避免出现非标频率。以下是如何为所有核心设置频率调整策略的方法：
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > $i
doneCPU Affinity
处理器亲和力（Processor affinity）使得进程可以绑定到特定的CPU核心。在Linux中，可以使用taskset工具来实现这一点。这是如何使用taskset工具的方法：
请注意，cpu迁移的次数降至0，即该进程永远不会离开core0。另外，您还可以使用cset工具，为您要进行基准测试的程序保留特定的CPU。如果使用Linux perf工具，请至少保留两个核心，这样perf会在一个核心上运行，而您的程序会在另一个核心上运行。下面的命令将所有线程移出N1和N2（-k选项表示连内核线程也一同移出）：
$ cset shield -c N1,N2 -k on下面的命令将在隔离的CPU上运行在 -- 后的命令：
$ cset shield --exec -- perf stat -r 10 <cmd>Process Priority
在Linux中，可以使用nice工具来提高进程优先级。通过增加优先级，进程将获得更多的CPU时间，并且Linux调度器将更倾向于优先处理该进程，而不是普通优先级的进程。niceness的取值范围为-20（最高优先级）到19（最低优先级），默认值为0。
请注意，在前面的示例中，基准测试的进程被操作系统中断了100多次。如果我们通过以sudo nice -n -N方式运行基准测试来提高进程优先级，效果如下：
$ perf stat -r 10 -- sudo nice -n -5 taskset -c 1 a.exe
0 context-switches
0 cpu-migrations请注意，上下文切换的次数变为0，因此该进程获得了连续的计算时间，没有被中断。
Filesystem Cache
通常，一部分主内存被用于缓存文件系统的内容，包括各种数据。这样可以减少应用程序需要直接访问磁盘的次数。
下面是一个示例，展示了文件系统缓存如何影响简单的git status命令的运行时间：
# clean fs cache
$ echo 3 | sudo tee /proc/sys/vm/drop_caches && sync && time -p git status
real 2,57
# warmed fs cache
$ time -p git status
real 0,40可以通过运行以下两个命令来清空当前的文件系统缓存：
$ echo 3 | sudo tee /proc/sys/vm/drop_caches
$ sync或者，你可以进行一次干燥运行，只是为了预热文件系统缓存，并将其排除在测量范围之外。这个干燥的迭代可以与基准测试输出的验证结合起来。
Appendix B. The LLVM Vectorizer
该段描述了截至2020年的Clang编译器中LLVM循环向量化器的状态。内层循环向量化是将内部循环中的代码转换为在多个循环迭代中使用向量的代码的过程。SIMD向量中的每个通道在连续的循环迭代上执行独立的算术操作。通常情况下，循环并不处于干净的状态，向量化器需要猜测和假设缺失的信息，并在运行时检查细节。如果这些假设被证明是错误的，向量化器将退回到执行标量循环。下面的示例突出显示了LLVM向量化器支持的一些代码模式。
Loops with unknown trip count
LLVM循环向量化器支持具有未知迭代次数的循环。在下面的循环中，迭代的起始点和结束点未知，而向量化器有一种机制可以对不从零开始的循环进行向量化。在这个示例中，n可能不是向量宽度的整数倍，因此向量化器需要将最后几次迭代作为标量代码执行。保留循环的标量副本会增加代码大小。
void bar(float A, float B, float K, int start, int end) {
for (int i = start; i < end; ++i)
A[i] *= B[i] + K;
}Runtime Checks of Pointers
在下面的示例中，如果指针A和B指向连续的地址，则对代码进行向量化是不允许的，因为一些A的元素会在从数组B读取之前被写入。
一些程序员使用restrict关键字来通知编译器指针是不相交的，但在我们的例子中，LLVM循环向量化器无法知道指针A和B是唯一的。循环向量化器通过在运行时插入代码来处理此循环，检查数组A和B是否指向不相交的内存位置。如果数组A和B重叠，则执行标量版本的循环。
void bar(float A, float B, float K, int n) {
for (int i = 0; i < n; ++i)
A[i] *= B[i] + K;
}Reductions
在这个例子中，sum变量被循环的连续迭代使用。通常情况下，这会阻止向量化，但是向量化器可以检测到sum是一个约简变量。sum变量会变成一个整数向量，在循环结束时，将数组的元素相加以得到正确的结果。LLVM向量化器支持多种不同的约简运算，例如加法、乘法、异或、与和或运算。这些约简操作使得向量化可以更高效地处理这类循环，提高程序的性能。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
sum += A[i] + 5;
return sum;
}当使用 `-ffast-math` 参数时，LLVM向量化器支持浮点数约简操作。
Inductions //归纳变量
在这个例子中，循环的归纳变量 i 的值被保存到一个数组中。LLVM循环向量化器知道如何对归纳变量进行向量化处理。当循环向量化时，向量化器会自动处理归纳变量的更新和传播，以提高代码的运行效率。这样可以将归纳变量的操作扩展为向量操作，从而充分利用SIMD指令并加速循环的执行。
void bar(float A, float B, float K, int n) {
for (int i = 0; i < n; ++i)
A[i] = i;
}If Conversion
LLVM循环向量化器能够“展开”代码中的IF语句，并生成一条指令流。向量化器支持内层循环中的任何控制流程。内层循环可以包含复杂的IF嵌套、ELSE以及GOTO语句。向量化器能够处理这些控制流程，使得循环的操作可以以向量化的方式执行，从而提高代码的效率和性能。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
if (A[i] > B[i])
sum += A[i] + 5;
return sum;
}Pointer Induction Variables
这个例子使用了标准C++库中的std::accumulate函数。这个循环使用了C++迭代器，它们是指针，而不是整数索引。LLVM循环向量化器可以检测到指针归纳变量，并对该循环进行向量化处理。这个功能非常重要，因为许多C++程序使用迭代器来遍历容器或集合。通过支持指针归纳变量的向量化，向量化器可以更高效地处理这类循环，提高程序的性能和效率。
int baz(int *A, int n) {
return std::accumulate(A, A + n, 0);
}Reverse Iterators
LLVM循环向量化器可以对逆向计数的循环进行向量化处理。
int foo(int *A, int *B, int n) {
for (int i = n; i > 0; --i)
A[i] +=1;
}Scatter / Gather
LLVM循环向量化器可以对代码进行向量化处理，使其成为一系列散布/收集内存的标量指令序列。
int foo(int * A, int * B, int n) {
for (intptr_t i = 0; i < n; ++i)
A[i] += B[i * 4];
}在许多情况下，成本模型会判断这种转换不具备盈利性。
Vectorization of Mixed Types
LLVM循环向量化器可以对包含混合类型的程序进行向量化处理。向量化器的成本模型可以估计类型转换的成本，并决定是否进行向量化处理是有利可图的。这意味着即使循环中存在不同类型的变量，向量化器也可以根据类型转换的代价来判断是否对其进行向量化处理。通过在向量化时考虑类型转换的成本，向量化器可以更加精确地评估优化的收益，以提高代码的性能和效率。
int foo(int *A, char *B, int n, int k) {
for (int i = 0; i < n; ++i)
A[i] += 4 * B[i];
}Vectorization of function calls
LLVM循环向量化器可以对内部数学函数进行向量化处理。请参考下表列出的这些函数：
- fabs: 绝对值（浮点数）
- sqrt: 平方根
- cbrt: 立方根
- sin: 正弦
- cos: 余弦
- exp: 指数函数
- log: 自然对数函数
- log10: 以10为底的对数函数
- pow: 幂函数
- ceil: 向上取整
- floor: 向下取整
- round: 四舍五入
- trunc: 截断小数部分
LLVM循环向量化器可以检测到这些内部数学函数，并将其转化为相应的向量指令，以在向量级别上执行计算，提高代码的执行效率和性能。
Partial unrolling during vectorization
现代处理器具有多个执行单元，只有包含高度并行性的程序才能充分利用机器的全部宽度。LLVM循环向量化器通过对循环进行部分展开来增加指令级并行性（ILP）。
在下面的示例中，整个数组被累加到变量sum中。这种做法是低效的，因为处理器只能使用一个执行端口。通过展开代码，循环向量化器可以同时使用两个或更多的执行端口，从而提高程序的并行性。
int foo(int *A, int *B, int n) {
unsigned sum = 0;
for (int i = 0; i < n; ++i)
sum += A[i];
return sum;
}LLVM循环向量化器使用成本模型来决定何时对循环进行展开是划算的。
展开循环的决策取决于寄存器压力和生成的代码大小。
SLP vectorization
SLP（超级字级并行性）向量化器尝试将多个标量操作组合成向量操作。它从底向上地处理代码，跨越基本块，寻找可组合的标量操作。SLP向量化的目标是将类似的独立指令组合成向量指令。使用这种技术可以对内存访问、算术操作和比较操作进行向量化。例如，下面的函数对其输入（a1、b1）和（a2、b2）执行非常相似的操作。基本块向量化器可以将以下函数组合为向量操作。
void foo(int a1, int a2, int b1, int b2, int *A) {
A[0] = a1*(a1 + b1);
A[1] = a2*(a2 + b2);
A[2] = a1*(a1 + b1);
A[3] = a2*(a2 + b2);
}Outer loop vectorization. //外部循环向量化
外部循环向量化是发生在数据并行应用程序中最外层循环的一种向量化形式。例如，OpenCL和CUDA依赖于外部循环向量化，因为它们指定了在循环的外部维度上的迭代之间是相互独立的。换句话说，这种向量化技术可以同时处理多个迭代，利用数据并行性来提高程序的执行效率。通过将外部循环中的迭代打包成向量操作，可以在单个指令中处理多个数据元素，从而充分利用SIMD（单指令多数据）指令集并行性，提高程序的并行性和性能。
