CPU性能分析与优化（一）

近50年来，处理器的发展趋势如下，单核性能趋，频率，功耗趋于平稳，核数，晶体管数量在增加。

即使堆核数，没有合适的软件优化工作，性能也不会提升很多。Leiserson 2020年的论文指出，短期内大多数应用程序的大部分性能提升来自软件栈。下图中是作者的实验结果，在不改变硬件的情况下，对矩阵乘法提速62806倍

影响性能的因素有3：

1. cpu，但是cpu只能默认执行给定的输入，没法挑选合适的算法，如果算法复杂度过高，性能也会很差。
2. compiler，compiler有可能生成次优代码，比如面对inline，loop unrolling等函数，编译器依赖于复杂的cost model核启发式方法，但是只能解决通用的情况。此外还需要考虑安全性，编译器开发人员的保守设计。
3. 算法复杂度，算法复杂度需要数据输入的情况，并且和硬件的分支预测和缓存也要挂钩。

作者的个人经验：90%的性能改进都可以在源代码层面完成，而无需深入编译器内部。

当前的处理器核数较多，单核性能趋于稳定，多核多线程之间的高效通信也是一个问题。

此外，AI和专用加速器也会提升性能。

有句古话：过早的优化是万恶之源 ，但是工业界得出的经验是相反的，因为屎山写成，比过早优化危害更大。

什么是性能分析？

大部分性能优化都依赖于直觉，并不能对程序性能产生实际影响。举例，缺乏经验的程序猿会使用++i代替i++，但是编译器会自动识别不使用i的情况并优化，所以该操作是多此一举。

还有很多优化技巧是过去有效，但是现在的编译器已经默认具备了。比如基于xor的swap，但是std::swap也能够产生同样快的代码。偶然的改动不会提高应用程序的性能，不应该凭直觉来修改代码。

本书介绍的perf-ninja性能分析方法都有一个共同点，基于程序执行的信息，分析和解释这些数据，再修改源代码。共有两个工作：

1. 找到性能瓶颈
2. 修复关键代码

书中提供了配套的练习 perf-ninja

Performance Analysis on a Modern CPU

Measuring performance

性能的快慢不是是和否的问题，性能问题比大多数功能问题更难以追踪和复现（硬件也是）。在解压缩文件时，可能会得到相同的解压结果，但是CPU的性能曲线可能无法重现。

下面将一个概念：测量偏差，即更改源代码中看似无关的部分，可能会对程序性能产生重大影响。这种问题比较棘手，因此本书只讨论比较高层次的方向。

首先讲硬件环境产生的测量偏差，比如DFS(dynamic frequency scaling)，允许cpu短期内提高频率，使得性能提升，但是CPU无法长时间超频，一段时间后会回落至基准值。下面是针对DFS的实验，第一次超频，第二次不超频，运行相同的benchmark，结果是第一次运行比第二次快一秒，因为频率高了。

软件的测量偏差可以以文件系统缓存为例，对一个执行大量文件操作的应用程序运行benchmark，第一次运行，缓存没有预热，性能较低，第二次运行缓存预热完毕，明显快于第一次。

硬件和软件环境会产生偏差，UNIX环境大小，链接顺序也会影响且不可预测，影响内存布局也会影响性能。甚至允许linux top也会影响测量结果。想要获得一致的测量结果，就需要在相同的运行条件下运行benchmark，但是想获得完全相同的环境并且消除偏差几乎不可能。只能通过控制大部分输入，环境配置等来变得接近相同。可以使用temci工具来配置相机你的环境，减少差异。

注意事项是，不建议消除系统的非确定性行为，重心应该放在优化的目标系统配置。非确定性行为不一定是有害的，可能产生不一致的结果，但是目的是提高系统的整体性能。禁用非确定性行为，可以减少噪声，但是可能延长运行时间。

此外，如果在公有云上面运行，可能会被其他客户的工作负载所影响。这导致很多云供应商和超级计算机直接在生产系统上监控性能。但是没有其他参与者，可能会无法正确反映真实世界的场景，导致在实验环境中运行良好，但是在生产环境中失败。解决方案是，设计能够代表真实世界应用场景的benchmark。

大型服务提供商通过实施遥测系统监控用户设备的性能。Netflix运行在全球数千台设备上，运行工程师分析这些设备上收集到的数据，从而确定优化的重点。但是测量开销比较大，监控服务会影响运行服务的性能，只能使用轻量级监控，总开销只能接受1%。解决测量开销，可以增加采样间隔，使用统计方法。

另一个比较有效的方法是Automated Detection of Performance Regressions , 主要受众是软件供应商，供应商的目标是尽可能高的提高软件迭代频率，但是性能bug出现的频率也会增加。软件的性能回归是指从一个版本发展到下一个版本所带来的bug，需要性能测试来衡量哪些提交会改变软件性能。

软件开发过程中，想要完全避免性能退步不现实，只能通过测试和诊断工具降低bug渗入生产代码的可能性。一种方式是，让人每天查看图表并比较结果，但是人的注意力是优先的，且该工作相当耗时，不能长期维持。下图中，性能曲线有很多细小的波动，性能曲线并不明显，很容易出错。

另一个方式是设置阈值，但是性能测试存在波动性，如何选择阈值本身也比较麻烦。阈值过低，可能会被噪声干扰，阈值过高难以发现问题。

第三种方式是使用统计分析方法。主要用算术平均值，以及观察运行时间直方图，但是非正态分布的情况可能产生误导性的结果。根据这些问题，又衍生出另外的算法，如Kolmogorov-Smirnov，implemented change point analysis等。

另一个方法是autoperf，使用硬件性能计数器PMC诊断性能退步。首先，它根据从原始程序中收集到的 PMC 配置文件数据，学习修改后函数的性能分布。然后，它根据从修改后的程序中收集到的 PMC 配置文件数据，将性能偏差检测为异常。AutoPerf 表明，这种设计可以有效诊断一些最复杂的软件性能缺陷，如隐藏在并行程序中的缺陷。

但是，无论采用哪个算法，典型的CI系统都应该自动执行以下操作：

1. 设置测试的系统
2. 运行benchmark
3. 报告结果
4. 确定性能是否发生变化
5. 对性能的意外变化发出警告
6. 可视化结果

CI系统应该支持自动和手动的benchmark测试，产生可复现的结果。CI的及时性比较重要，因为慢了就会有更多的代码合并，并且快一点，程序猿还能记得出错的代码。CI系统不仅考虑性能回归，还需要对意外引入的性能变化发出警告。假设某个无害的提交使得性能提高10%，且通过当前所有的CI功能测试，但是这可能是CI系统本身有bug，该情况经常发生。作者建议建立自动化的性能统计跟踪系统，并且尝试使用不同的算法，降低风险。

下面讲Manual Performance Testing

主要为本地的性能性能评估提供建议，因为CI系统存在一些不可控性（硬件故障，测试系统问题，需要增加额外指标），本地的性能评估仍然有必要。

如何确定性能真的提升了？建议不要只运行一次性能测量，而是多次运行，也不应该依赖单一的指标如min mean median等。

下图是两个版本的程序所收集的性能测量值分布图,显示了特定版本程序获得特定计时的概率。A有32%概率在102秒内完成，B大部分情况下比A慢，但是即使所有情况下B的测量结果都比A慢，概率也不可能是100%，因为总能为B找到额外的比A快的样本。

分布图的优势是可以发现benchmark不需要的行为，如果分布是双峰状，则benchmark可能经历了两种不同类型的行为。双峰分布可能是代码同时具有快速和慢速路径，如访问缓存和竞争锁/非竞争锁，需要隔离不同的模式分别进行测试。

数据科学家通常绘制分布图展示测量结果，而非计算加速比。常用的分布图是箱型图，这样可以在同一张图上对多个分布图进行比较。通常观察性能测量分布很难估算速度的提升，且不适用于自动化的CI系统。通常我们希望得到一个标量值，该值代表程序两个版本性能分布之间的加速比，例如 "A 版本比 B 版本快 X%"。

使用假设检验方法确定两个分布之间的统计关系，如果数据集之间的关系会根据临界概率拒绝零假设，则具有统计意义。

wiki补充：零假设的内容一般是希望能证明为错误的假设，与零假设相对的是备择假设，即希望通过证伪零假设而证明正确的另一种假说。如果一个统计检验的结果拒绝（reject）零假设（结论不支持零假设），而实际上真实的情况属于零假设，那么称这个检验犯了第一类错误。反之，如果检验结果支持零假设，而实际上真实的情况属于备择假设，那么称这个检验犯了第二类错误。通常的做法是，在保持第一类错误出现的机会在某个特定水平上的时候（即显著性差异值或α值），尽量减少第二类错误出现的概率。

假设检验方法对于确定加速或减速是否是随机的很有用。样本较小时，平均值和几何平均值可能受到异常的影响。除非方差很小，否则不能只考虑平均值。如果方差和平均值处于同一个数量级，那么平均值就没有代表性。

下图中只看平均值，A更快，但是查看方差，发现并不是如此。

计算精确加速比的重要因素是收集丰富的样本，即大量运行benchmark。例如，一些 SPEC CPU 2017 基准在现代机器上运行时间超过10分钟。这意味着仅制作三个样本就需要 1 个小时：每个版本的程序需要 30 分钟。试想一下，套件中不仅有一个基准，还有数百个基准。即使将工作分配到多台机器上，要收集统计上足够的数据也会变得非常昂贵。

如何确定需要多少个样本才能达到统计学上的充分分布？这取决于对比的准确性，样本之间的方差越小，所需的样本数量就越少。标准偏差是衡量分布中测量结果一致性的指标。我们可以根据标准偏差动态限制基准迭代次数，从而实施自适应策略，即收集样本直到标准偏差在一定范围内为止。这种方法要求测量次数大于 1。否则，算法会在第一次采样后停止，因为单次运行基准的标准差等于零。一旦标准偏差低于阈值，就可以停止收集测量值。

异常值的存在，对于某些benchmark可能是最重要的指标，不一定需要丢弃。

总结一下上面的：要根据不同的情况选择不同的统计算法，不能仅仅依赖于单一统计指标。

下面讲Software and Hardware Timers

通常使用两个定时器来计算benchmark的运行时间。

一个是System-wide high-resolution timer，这是系统定时器，时间单调上升。linux系统中，通过clock_gettime系统调用来访问，分辨率是ns，该时间在所有的cpu之间保持一致，且与cpu的频率没有关系。但是clock_gettime系统调用获取时间戳需要很长时间，因此不适合短时间运行的时间。c++中使用std::chrono访问该定时器。

另一个是Time Stamp Counter，这是硬件定时器，以硬件寄存器的形式存在，速率恒定，不考虑频率的变化，但是每个CPU都要自己的TSC，适用于测量持续时间从ns到分钟的短事件，可以使用__rdtsc获取TSC。

代码如下

#include <cstdint>
#include <chrono> // returns elapsed time in nanoseconds

uint64_t timeWithChrono()
{
    using namespace std::chrono;
    auto start = steady_clock::now(); // run something
    auto end = steady_clock::now();
    uint64_t delta = duration_cast<nanoseconds>(end - start).count();
    return delta;
}

#include <x86intrin.h>
#include <cstdint> // returns the number of elapsed reference clocks
uint64_t timeWithTSC()
{
    uint64_t start = __rdtsc(); // run something
    return __rdtsc() - start;
}

#include <stdio.h>


int main() {
    uint64_t delta = timeWithChrono();
    printf("Time with chrono: %lu ns\n", delta);

    delta = timeWithTSC();
    printf("Time with TSC: %lu reference clocks\n", delta);
    return 0;
}

运行结果为

Time with chrono: 70 ns Time with TSC: 34 reference clocks

总结：测量的时间段较短，TSC更精确，chrono的延迟更高，适用于长时间运行的情况。rdtsc需要20多个cpu cycle，chrono因为系统调用的开销，延迟是10倍左右。

下面讲Microbenchmarks

定义是为快速测试某种假设而编写的独立小程序，几乎所有的现代语言都有benchmark库，比如googlebenchmark

在编写microbenchmark时，确保microbenchmark在运行时实际执行了要测试的场景很重要，因为编译器可以消除部分代码，导致得出错误的结论。

举例，现代编译器可能会删除整个循环

// foo DOES NOT benchmark 
string creation void foo() { 
for (int i = 0; i < 1000; i++) 
    std::string s("hi");
}

使用DoNotOptimize(s)避免被优化

string creation void foo() { 
for (int i = 0; i < 1000; i++) 
    std::string s("hi");
    DoNotOptimize(s);
}

‘microbenchmark通常用于比较关键功能的不同实现的性能。好的benchmark能够反映实际条件下的性能。还需要考虑同时的其他进程，当其他进程对于DRAM和cache要求不高时，benchmark运行时可能会占据更多的资源，如果其他的进程需要消耗大量的DRAM和cache空间，那么结果会不一致。