使用Prodfiler优化eBPF优化器（重发版）– Sean Heelan的博客
如何在不修改任何代码的情况下将应用程序性能提升近2倍？请继续阅读！
这是我在2021年10月4日最初发表在prodfiler.com上博客的重发版本。Prodfiler已被Elastic收购，现为Elastic Universal Profiler。
在本文中，我将逐步介绍如何使用Prodfiler发掘K2（论文，视频）中的优化空间，K2是一个用于eBPF的优化编译器。K2完全受CPU限制，并采用了一种引导搜索技术，该技术依赖于高速创建和检查候选解决方案的能力。通过Prodfiler，我们可以轻松发现K2中哪些组件消耗最多的CPU周期，从而相应地进行优化。最终结果是一个速度提升1.4倍至1.9倍的K2版本，这意味着在相同资源下可以探索更大的搜索空间。
预告一下我们将要实现的改进：
- 用性能更好的替代方案（即mimalloc）替换系统分配器
- 辅助编译器自动向量化一系列热点循环
- 对K2本身及其最重要的依赖项Z3应用PGO和LTO
引言
随着eBPF的更多用例被发现，其中许多处于关键路径上，编译器生成的eBPF代码性能变得越来越重要。虽然clang通常能很好地生成高效程序，但有时它生成的代码存在冗余、指令序列选择异常、操作数宽度不必要地窄以及其他怪癖，这意味着手动优化的程序可以显著更快。手动优化eBPF指令具有挑战性、耗时且容易出错，因此，与更传统目标平台的编译一样，市场需要那些在编译阶段花费时间以在运行时获得性能的工具。
今年8月，罗格斯大学的研究人员发布了K2，一个用于eBPF代码的优化编译器。K2以现有的eBPF程序作为输入，并搜索语义上等同于原始程序但更快更小的程序。在他们的论文中，他们证明相对于最佳clang编译的程序，他们的方法可以将程序大小减少6-26%，将这些程序的平均数据包处理延迟降低1-55%，并将吞吐量提高高达5%。
为了驱动其搜索，K2使用带有Metropolis-Hastings接受标准[1]的MCMC。关于MCMC/MH的一个很好的介绍可以在这里找到，但就我们的目的而言，只需将MCMC视为一种搜索技术，在其内部循环中，必须从当前状态生成一个新候选并为它分配一个成本。然后使用当前状态和候选状态的成本来偏置选择，随机决定下一个当前状态。给定固定的时间预算（并假设合理的候选生成和成本函数），结果的质量与在该时间段内可以探索的状态数量直接相关。因此，基于MCMC的应用程序是像Prodfiler这样的工具的主要目标，因为任何我们可以挤出的性能提升都可能使应用程序在相同资源下找到更高质量的结果。
K2架构简要概述
为了了解我们将要优化的内容，让我们快速浏览一下K2的组件。上图来自K2论文，该论文非常易读，如果您想了解更多细节，强烈推荐。
如上所述，作为MCMC驱动的，K2的核心是：
- 从当前状态生成一个新候选
- 为该候选分配一个成本
- 根据候选成本和当前状态的成本，有条件地将当前状态设置为新候选状态
在算法上，几乎所有的繁重工作都在步骤2中进行。为了计算候选的成本，K2使用一组输入在自定义用户空间eBPF解释器上解释它。对于这些输入，如果候选产生与原始程序相同的输出，K2然后将候选转换为符号表示，并使用Z3定理证明器执行等价检查。因此，MCMC搜索的内部循环在计算上相当密集，每个候选需要大量工作来评估。
设置
设置基准测试
K2本身可以在GitHub上找到，方便的是，作者还上传了一个会议工件，包含用于生成论文结果的测试和基准测试。我已将此存储库克隆在这里，以便为本文添加一些辅助脚本。主要的K2存储库关于如何实际安装和运行的信息有点少，但幸运的是，这里有一个安装脚本，可以根据需要遵循。如何运行K2来优化eBPF程序的示例可以在这个脚本中找到。该脚本将在11个不同的eBPF程序上调用K2，以尝试找到更高效的实现。我们将以此作为基准测试的基础，因为输入的eBPF程序多样化，并且我们可以相对确定，如果我们找到使K2在这些输入目标上运行更快的优化，那么它们应该可以推广。
关于设置基准测试的最后一点是，我已将K2克隆在这里，以提供一个默认的Makefile，该文件将构建一个合理的二进制文件，供我们比较改进。K2附带的标准Makefile似乎有一个错误，并且在编译组成程序的大多数文件时没有指定优化级别，因此默认情况下您得不到优化，性能相当差。我的Makefile指定了-O3 -march=native作为默认值。
使用Prodfiler进行基准测试和优化
开始使用Prodfiler很简单。按照这里的文档创建一个新项目，并通过几次点击部署Prodfiler。一旦它启动并运行，我们就可以通过运行上述基准测试来收集我们的基线数据。我创建的用于执行此操作的脚本可以在这里找到。默认情况下，它运行每个11个基准测试15次。我们将使用它来收集我们的结果并确保我们的优化推广，但还有一个“快速”模式，运行3个基准测试各3次，这对于快速检查假设很有用。
第一幕 – MCMC中的M和C代表MalloCMalloC
打开Prodfiler的Top N Functions视图给我们以下内容（提示：独占CPU意味着函数本身的CPU使用率，不包括它调用的函数的CPU使用率。包含CPU意味着函数本身及其调用的函数的CPU使用率）。
Top N Functions视图是我通常的起点，以了解应用程序在哪里花费时间。相当经常，Top 10 Functions中的一个或多个条目会让我想“嗯，这很奇怪”，并提供潜在性能胜利的线索。这个视图特别擅长浮现那些每次执行都很便宜，但被调用如此频繁以至于意外主导执行时间的函数。
在K2的Top 10 Functions中，有两个特别突出。第一个是大量时间花费在从STL容器分配和检索项目上。根据函数名称和相关的源文件，我们可以推断该容器是std::vector<bool>，一个 notorious 奇怪的容器。在内存使用是关注点的情况下，std::vector<bool>可能是正确的选择，但如果主要关注CPU使用，那么有更好的选择。好的，这是一个好的开始，但让我们暂时搁置它，继续查看列表，看看是否有更简单的收益可以找到。
第二个突出的项目是在位置5和6我们可以看到malloc和free函数。事实上，在将上述列表扩展到前20个函数时，我发现malloc相关函数占据了前20个位置中的5个。如果我们求和它们的CPU使用率，我们了解到应用程序整整10%的CPU时间花费在内存管理上！花费如此多时间在内存管理上的应用程序几乎总是可以通过两种方式加速。一种方法是分析应用程序的内存使用，并尝试调整它以简单地减少对内存管理函数的调用。第二种方法是用其他东西替换系统分配器。后一种方法通常工作量少得多[2]，也是我们将在这里采用的方法。如今有许多分配器选择，其中jemalloc和tcmalloc特别知名。一个较新的进入者是mimalloc。在基准测试中，mimalloc与其他可用选项相比表现良好，是我们本文的选择。
mimalloc是系统分配器的即插即用替代品。使用它就像将其安装位置添加到LD_PRELOAD并运行您的应用程序一样简单。
通过这个更改，我们可以看到free函数完全退出了Top 10 Functions，如果我们求和mimalloc中所有函数的使用率，我们发现内存管理已降至约5%，而不是之前的10%。太棒了！这是5%的CPU预算，现在希望分配给更有用的事情。
那么，我们从这个变化中得到什么样的性能提升呢？下图显示了mimalloc运行时与默认运行时的对比。X轴显示mimalloc运行的速度提升作为默认运行的因子。注意：Y轴从0.8开始截断，以便更容易看到变化的大小。
在基准测试中，我们看到平均速度提升1.08倍，最小1.05倍，最大1.12倍。对于一个零努力的变化来说不错，但让我们看看还能找到什么！
第二幕 – std::vector谋杀性能
随着最简单的胜利完成，我们现在可能必须做一些实际工作。幸运的是，我们有一个清晰的起点。回到Top N Functions，我们可以看到前两个项目 alone 占用了15%的CPU预算，并且与访问std::vector<bool>容器有关，如前所述。这是分配给任何内置数据结构的相当极端的CPU预算比例，在这种场景下，我的期望是有收益可以获得。首先，我们需要弄清楚std::vector<bool>被用来表示什么，以及它是如何被使用的。为了回答这个问题，Prodfiler为每个函数提供了一个调用图，可以通过在Top N Functions视图中点击函数名（或在Flamegraph视图中ctrl-clicking一个函数）来访问。std::vector<bool>::operator=的调用图如下所示：
我们可以看到两个函数（prog_state::init_safety_chk和inout_t::operator=）负责 practically 所有对此函数的调用。这两个相同的函数也负责所有对std::vector<bool>::operator[]的调用，这是Top N Functions列表中的第二个函数。有了这个，我们可以跳入代码，试图弄清楚为什么这么多时间花费在操作这些向量上，以及我们能做些什么。
init_safety_chk函数如下（源）：
所以我们有一系列布尔值在每次候选的安全检查中被复制。代表寄存器是否可读和内存是否可读的两个容器是固定大小的，分别为11和512。查看inout_t::operator=的代码，我们看到类似的模式。inout_t::operator=中的复制将比init_safety_chk中的复制有更大的影响，因为这个赋值运算符在计算候选的错误成本时被调用，次数与可用于解释该候选的具体输入数量相同。
鉴于这些向量是固定大小的，并且至少在原则上应该包含很少的数据，人们可能想知道为什么我们在复制它们上花费如此多的CPU，即使复制确实每个候选发生多次。在具有SIMD指令的CPU上，复制这些数据量不应该每次都是无循环的指令块吗？好吧，让我们看看编译器如何处理那段代码。注意：本文中的反汇编截图不是来自Prodfiler，而是来自Binary Ninja。
生成上述代码来复制stack_readable向量的内容。如我们所见，我们 certainly 没有直接的SIMD指令序列，而是一个循环，中间有一个分支，将迭代STACK_SIZE次。如果我们查看stl_bitvector.h中operator=的实现，这个原因变得明显：
好的，所以很明显编译器在这里无法帮助我们并自动向量化。那么我们的选择是什么？嗯，K2没有非常高的内存占用，并且使用std::vector<bool>而不是，例如，将相同信息表示为字节向量所节省的内存在大方案中并不显著。我的第一个想法是简单地将bool类型替换为uint8_t。然而，在这样做并重新运行基准测试后，性能改进微不足道，一点也不像如果上述逐字节复制被直接SIMD替换所期望的那样。回到反汇编，我们发现复制循环变成了以下内容：
出于某种原因，编译器决定生成一个逐字节复制循环，其中每次迭代都从内存加载源和目标指针。我在Twitter上询问了这个问题，Travis Downs回应并指出问题是C++中uint8_t类型可以别名所有其他类型！因此编译器不能保证对向量的每次写入不修改源和目标指针，因此必须在每次循环迭代时从内存重新加载它们。Travis有一篇优秀的博客文章进一步扩展了这一点在这里。
Travis有许多建议来解决这个问题，我决定采用的方法是使用C++20的char8_t类型而不是uint8_t。这个类型没有别名问题，并给我们想要的直接SIMD代码：
如您在左侧所见，还有代码生成来执行逐字节复制，但这在实践中永远不会达到，因为它只在源和目标向量重叠时进入。那么，这如何帮助我们的性能呢？
结果相当好！通过用vector<char8_t>替换vector<bool>并启用编译器自动向量化相关循环，我们比mimalloc版本平均速度提升1.31倍，最大1.57倍，最小1.12倍。相对于默认版本，我们现在平均速度提升1.43倍，最大1.75倍，最小1.22倍。查看Top N Functions视图，我们还可以看到operator=和operator[]现在分别占总数的0.82%和0.62%，从12.3%和3.93%下降[3]。
这在实践中意味着，随着1.22倍至1.75倍的速度提升，给定相同的CPU预算，K2可以执行显著更大的搜索。具体来说，在改进最显著的基准测试（xdp_map_access）中，默认情况下K2每秒可以探索约4600个候选，但通过我们的改进，这跃升至约8000个候选每秒！
第三幕 – Z3
平均1.43倍的速度提升不错，但在结束之前，让我们最后看一下分析数据，看看是否还有其他突出的东西。
瞥一眼Top N Functions告诉我们，内存管理函数仍然显著，malloc和free（位置1和10）约占7.5%的CPU。我们可以采取几个方向，包括审查K2的内存分配模式以查看它们是否在某些方面次优，或者可能对mimalloc应用PGO/LTO以希望使其更快。前一个选项可能有点工作，后一个选项我觉得不太可能给出超过几个百分点的改进。位置7的函数也很有趣，因为从调用图中我们可以看到read_encoded_value_with_base被用作C++异常处理的一部分。查看代码显示K2使用异常作为机制，从调用栈深处通信非致命错误到更高层函数。我们可以重写这个以使用返回值或输出参数来指示相同的信息并节省这种开销，但这 again 可能是相当多的工作，收益不大。我从这些数据中的最终观察是，Top 10函数中有4个在Z3中，正是这个我们将深入挖掘，因为它暗示任何对Z3的优化都可能产生显著影响。
Prodfiler提供了两种方式来挖掘这些函数的使用方式。第一种是我们之前看到的调用图，第二种是火焰图，我们现在将使用它。当一个人想要洞察最昂贵的调用栈时，火焰图非常有用，以比调用图更信息密集和易于导航的方式（以不表示每个函数关联的CPU使用率总和为代价，而是表示每个调用栈的数据）。
火焰图证实了我们的假设，即Z3是一个值得优化的目标。我们可以在图中看到，Z3_solver_check()函数及其子函数负责K2完成的整整约46%的工作！我们可以通过两种方式攻击这个问题：
- K2可能比需要更频繁地调用Z3。如果您 recall 从 earlier，Z3仅在K2未能通过在一组输入上解释该程序来区分候选程序与原始程序时被调用。通过生成更多样化的输入集，我们可能能够更少地转到Z3来区分候选与原始。
- 我们可以尝试使Z3本身表现更好。
如果有足够的时间，我们很可能会同时做(1)和(2)，甚至可能从(1)开始。然而，到这个时候，我开始享受尝试通过尽可能少的侵入性更改来改进K2性能的挑战，因此决定单独进行(2)。现在，改进Z3，世界上最强大和流行的定理证明器之一，如果我们实际上想通过算法或实现更改来这样做，实际上会比选项(1)多很多工作。不过，我们还有另一个选择：修改Z3的编译方式。
gcc和clang都支持配置文件引导优化（PGO）和链接时优化（LTO）[4]。PGO和LTO是互补的，使用两者通常可以获得5-20%的性能改进，高个位数改进是合理的期望。由于各种原因，很少有开源软件分发时编译了PGO/LTO，甚至没有启用它们的构建目标（尽管这正在改变）。幸运的是，通常自己动手很简单[5]。
PGO是一个三步编译过程，其中首先构建应用程序的插装[6]版本，然后在系列输入上运行该应用程序以收集数据，最后使用该数据重新编译应用程序的优化版本。对于第一阶段，我随机选择了三个基准测试（socket-0、xdp_kern_xdp1和xdp_cpumap_enqueue）并各运行三次。这三个基准测试包含在下面的图表中，但值得记住的是，存在过拟合[7]其特性的可能性，这可能意味着人们会想要 discount 这些结果并专注于其他。
对Z3应用PGO和LTO使我们比之前的版本平均获得了1.1倍的性能改进，最大1.17倍，最小1倍（与之前性能相同）。总体而言，这使我们比原始版本平均改进1.54倍，最小1.37倍，最大1.79倍！
作为最后的努力，我决定还对K2本身进行PGO（但不进行LTO[8]）以给出最终结果：
对K2本身进行PGO平均带来了另外1.03倍的性能增益，最大1.09倍，最小1倍。这些是 modest 改进，但值得记住的是，平均44%的K2执行时间实际上花费在Z3内部，因此对代码其余部分进行PGO只能做这么多。
所以，最终，在换入mimalloc、用std::vector<char8_t>替换std::vector<bool>并应用PGO/LTO之后，我们平均性能改进1.62倍，最大1.91倍，最小1.42倍。在实践中，这意味着如果我们 originally 每秒探索10,000个状态，平均我们现在在相同时间预算下探索约16,000个，在最佳情况下我们探索几乎两倍！
结论
在本文中，我们逐步介绍了如何将Prodfiler用作迭代过程的一部分以显著提高应用程序性能。本文中的顺序是我实际使用Prodfiler的方式 – (1) 设置基准测试（理想情况下是真实工作负载；Prodfiler的开销足够低，这是可行的），(2) 运行它们，(3) 然后迭代地处理顶级函数、火焰图和调用图，寻找对应用程序本身、环境、第三方依赖或配置的更改，这些更改可以提高性能。
我将Prodfiler视为一个“Huh？”生成器，因为它的各种视图往往在我的大脑中诱发“Huh – that’s weird”的想法，这是沿着路径弄清楚为什么某些意外组件被分配尽可能多CPU的第一步。有时该路径的终点只是解决我对目标软件的误解，但 often 它是发现一些被忽视的特性，以