使用 Prodfiler 优化 eBPF 优化器（重发版）

如何在不修改任何代码的情况下将应用程序性能提升近 2 倍？请继续阅读！

这是我在 2021 年 10 月 4 日首次发表在 prodfiler.com 上的博客重发版。Prodfiler 已被 Elastic 收购，现称为 Elastic Universal Profiler。

本文将详细介绍如何使用 Prodfiler 发掘 K2（论文、视频）中的优化空间。K2 是一个 eBPF 优化编译器，完全受 CPU 限制，采用依赖高速创建和检查候选方案的引导搜索技术。通过 Prodfiler，我们可以轻松发现 K2 中消耗最多 CPU 周期的组件，从而进行相应优化。最终结果是获得速度提升 1.4-1.9 倍的 K2 版本，这意味着在相同资源下可以探索更大的搜索空间。

优化改进概述

发现的改进主要来自三个方面：

1. 用性能更好的 mimalloc 替换系统分配器

2. 辅助编译器自动向量化热点循环

3. 对 K2 及其重要依赖 Z3 应用 PGO 和 LTO

引言

随着 eBPF 的更多用例被发现（许多处于关键路径上），编译器生成的 eBPF 代码性能变得越来越重要。虽然 clang 通常能生成高效程序，但有时会产生存在冗余、异常指令序列选择、不必要的窄操作数宽度等问题的代码，导致手动优化程序可以显著更快。手动优化 eBPF 指令具有挑战性、耗时且容易出错，因此与更传统目标平台的编译一样，存在对在编译阶段投入时间以换取运行时性能的工具的需求。

今年 8 月，罗格斯大学的研究人员发布了 K2，这是一个用于 eBPF 代码的优化编译器。K2 以现有 eBPF 程序为输入，搜索语义等同于原始程序但更快更小的程序。在他们的论文中，他们证明相对于最佳 clang 编译程序，他们的方法可以将程序大小减少 6-26%，将这些程序的平均数据包处理延迟降低 1-55%，并将吞吐量提高高达 5%。

K2 架构简要概述

K2 的核心是 MCMC 与 Metropolis-Hastings 接受标准[1]。对于我们的目的，只需将 MCMC 视为一种搜索技术，在其内部循环中必须从当前状态生成新候选并为其分配成本。然后使用当前状态和候选状态的成本随机决定下一个当前状态。给定固定的时间预算（并假设合理的候选生成和成本函数），结果的质量与在该时间段内可以探索的状态数量直接相关。因此，基于 MCMC 的应用程序是 Prodfiler 等工具的主要目标，因为我们能够挤出的任何性能增益都可能使应用程序使用相同资源找到更高质量的结果。

设置基准测试

K2 可以在GitHub上找到，作者还上传了包含用于生成论文结果的测试和基准测试的会议工件。我克隆了这个存储库这里以添加一些辅助脚本。主要的 K2 存储库关于如何实际安装和运行的信息有点少，但幸运的是有一个安装脚本这里，可以按需遵循。如何运行 K2 优化 eBPF 程序的示例可以在这个脚本中找到。该脚本将在 11 个不同的 eBPF 程序上调用 K2，以尝试找到更高效的实现。我们将以其作为基准测试的基础，因为输入 eBPF 程序多样化，并且我们可以相对确定，如果我们找到使 K2 在这些输入目标上运行更快的优化，那么它们应该具有通用性。

使用 Prodfiler 进行基准测试和优化

开始使用 Prodfiler 很简单。按照这里的文档创建新项目并在几次点击中部署 Prodfiler。一旦启动并运行，我们就可以通过运行上述基准测试来收集基线数据。我创建的用于执行此操作的脚本可以在这里找到。默认情况下，它运行每个基准测试 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>，一个 notoriously weird 容器。在内存使用受关注的情况下，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<bool>谋杀性能

随着最简单的获胜方式解决，我们现在可能必须做一些实际工作。幸运的是，我们有一个清晰的起点。回到 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 all 对这个函数的调用。这两个相同的函数也负责所有对std::vector<bool>::operator[]的调用，这是 Top N Functions 列表中的第二个函数。有了这个，我们可以跳入代码，试图弄清楚为什么这么多时间花费在操作这些向量上，以及我们可以做些什么。

init_safety_chk函数如下（来源）：

所以我们有一系列 bools 在每次候选的安全检查上被复制。表示寄存器是否可读和内存是否可读的两个容器具有固定大小，分别为 11 和 512。查看inout_t::operator=的代码，我们看到类似的模式。inout_t::operator=中的复制将比init_safety_chk中的复制具有更大的影响，因为这个赋值运算符在候选的错误成本计算中被调用，次数与可用于解释该候选的具体输入次数相同。

鉴于这些向量具有固定大小，并且原则上至少应包含很少的数据，人们可能想知道为什么我们要在复制它们上花费如此多的 CPU，即使复制确实每个候选发生多次。在具有 SIMD 指令的 CPU 上，复制这些数据量不应该每次都是无循环的指令块吗？好吧，让我们看看编译器如何处理该代码。注意：本文中的反汇编屏幕截图不是来自 Prodfiler，而是来自 Binary Ninja。

上述代码是为复制stack_readable向量的内容而生成的。如我们所见，我们肯定没有直接的 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.22x-1.75x 的速度提升，给定相同的 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 使用异常作为机制从调用栈深处通信非致命错误到更高层函数。我们可以重写这个以使用返回值或输出参数来指示相同的信息并节省这种开销，但这再次可能是相当多的工作而收益不多。我从这些数据中的最终观察是，Top 10 函数中有 4 个在 Z3 中，这是我们将深入研究的那个，因为它暗示任何对 Z3 的优化都可能产生显著影响。

Prodfiler 提供了两种方法来深入了解这些函数的使用方式。第一种是我们之前看到的调用图，第二种是火焰图，我们现在将使用它。火焰图在人们想要洞察最昂贵的调用栈时非常有用，以比调用图更信息密集和易于导航的方式（但代价是不表示与每个函数相关的 CPU 使用率总和，而是表示每个调用栈的数据）。

火焰图证实了我们的假设，即 Z3 是一个值得优化的目标。我们可以在图中看到Z3_solver_check()函数及其子函数负责 K2 完成的整整约 46%的工作！我们可以通过两种方式攻击这个：

1. K2 可能调用 Z3 比需要的多。如果您从前面回忆，Z3 仅在 K2 未能通过在一组输入上解释该程序来区分候选程序与原始程序时调用。通过生成更多样化的输入集，我们可能能够区分候选与原始程序而不经常去 Z3。

2. 我们可以尝试使 Z3 本身表现更好。

给定足够的时间，我们很可能会同时做（1）和（2），甚至可能从（1）开始。然而，到这个阶段，我开始享受尝试通过尽可能最少侵入的更改来改进 K2 性能的挑战，因此决定单独进行（2）。现在，改进 Z3，世界上最强大和流行的定理证明器之一，如果我们实际上想通过算法或实现更改来这样做，实际上会比选项（1）多很多工作。不过，我们还有另一个选项可用：修改 Z3 的编译方式。

gcc 和 clang 都支持 Profile Guided Optimization (PGO) 和 Link Time Optimization (LTO) [4]。PGO 和 LTO 是互补的，使用两者通常可以获得 5-20%范围的性能改进，高个位数改进是合理的期望。由于各种原因，很少开源软件分发编译时带有 PGO/LTO，甚至没有启用它们的构建目标（尽管这正在改变）。幸运的是，通常自己动手很简单[5]。

PGO 是一个三步编译过程，其中首先构建应用程序的仪器化[6]版本，然后在该应用程序上运行一系列输入以收集数据，最后使用该数据重新编译应用程序的优化版本。对于第一阶段，我随机选择了三个基准测试（socket-0、xdp_kern_xdp1 和 xdp_cpumap_enqueue）并各运行三次。这三个基准测试包含在下面的图中，但值得记住的是，存在过度拟合[7]其特性的可能性，这可能意味着人们希望折扣这些结果并专注于其他结果。在下面各种最小/最大/平均值计算中，我已排除了它们。

对 Z3 应用 PGO 和 LTO 使我们比先前版本平均获得 1.1 倍性能改进，最大 1.17 倍，最小 1 倍（与之前性能相同）。总体而言，这使我们比原始版本平均改进 1.54 倍，最小 1.37 倍，最大 1.79 倍！

作为最终努力，我决定还 PGO（但不 LTO[8]）K2 本身以给出最终结果：

PGO'ing K2 本身平均又带来 1.03 倍性能增益，最大 1.09 倍，最小 1 倍。这些是适度的改进，但值得记住的是，平均 44%的 K2 执行时间实际上花费在 Z3 内部，因此 PGO'ing 其余代码只能做这么多。

所以，最终，在换入 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 的第一步。有时该路径的终点只是解决我对目标软件的误解，但通常是发现一些被忽视的特性以未预期的方式消耗 CPU。这是 Prodfiler 的真正价值 – 它允许以零摩擦收集精确数据，从单个应用程序到整个集群，并将该数据可视化，以便工程师可以轻松扫描它以寻找“Huh？”时刻。所以，总之，无论是 Prodfiler 还是其他，我推荐您找到一个“Huh？”-生成器。结合一些持久性，在现代软件堆栈中可以找到巨大的性能改进。狩猎愉快！

脚注

[1] 这提供了对 MCMC/MH 的良好介绍，STOKE 论文值得一读，以获取程序优化中随机搜索的另一个示例。[2] 除非您换入的“其他东西”是自定义分配器，专门为应用程序的内存分配模式设计。这当然在某些场景中是合理的方法，但可能过度杀伤，除非您真的耗尽了所有其他替代方案。[3] 在将inout_t和prog_state类中的vector<bool>替换为vector<char8_t>并重新运行基准测试后，我看到map_t::clear现在是第二昂贵的函数，占用 3-4%的 CPU 预算。在调查后，我发现了另一个vector<bool>实例导致编译器产生逐字节循环来清零向量。我也用vector<char8_t>替换了它，允许编译器使用memset而不是循环。显示的结果也包括此更改的效果。[4] 对 PGO 和 LTO 的有用高级概述可以在这里找到。参见 gcc 和 clang 的文档以获取更多信息。[5] 在未来的博客文章中，我将专门介绍 Z3 的 PGO/LTO，但 gcc 关于标志-fprofile-generate、-fprofile-use和-flto的文档是一个好的起点。这个 StackOverflow 帖子也有一些关于 PGO 的高级信息。[6] 还有另一种 PGO 方法使用采样分析器而不是仪器。Google AutoFDO 论文是信息的一个好起点。[7] 我不确定这种过度拟合的可能性实际上有多显著。K2 随机生成给定起始状态的候选，因此即使从相同状态开始，探索的搜索空间也可能不相同，因此 Z3 的使用也不会相同。[8] LTO'ing K2 导致操作我们引入的vector<char8_t>类型的函数在各种位置内联，并且出于某种原因，一旦发生这种情况，gcc 将不再展开和向量化那些循环。我将在未来的文章中深入探讨这一点。更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）公众号二维码

办公AI智能小助手