引言

随着eBPF在关键路径上的应用越来越多，编译器生成的eBPF代码性能变得愈发重要。虽然clang通常能生成高效程序，但有时会产生冗余代码、异常指令序列选择、不必要的窄操作数宽度等问题，导致手动优化的程序可以显著更快。

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

K2架构概述

K2使用MCMC（马尔可夫链蒙特卡洛）与Metropolis-Hastings接受准则驱动搜索。MCMC内部循环必须从当前状态生成新候选，并为其分配成本。然后使用当前状态和候选状态的成本来偏置选择，随机决定下一个当前状态。

算法上，几乎所有繁重工作都在步骤2中进行。为了计算候选成本，K2使用自定义用户空间eBPF解释器在一组输入上解释它。对于这些输入，如果候选产生与原始程序相同的输出，K2然后将候选转换为符号表示，并使用Z3定理证明器执行等价检查。

设置基准测试

K2可以在GitHub上找到，作者还上传了一个会议工件，包含用于生成论文结果的测试和基准。我们将使用它作为基准测试的基础，因为输入eBPF程序多样化，如果我们找到使K2在这些输入目标上运行更快的优化，那么它们应该能够泛化。

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

开始使用Prodfiler很简单。按照文档创建新项目并在几次点击中部署Prodfiler。一旦启动运行，我们就可以通过运行上述基准测试来收集基线数据。

第一幕：内存分配器优化

查看Prodfiler的Top N Functions视图，我们发现内存管理函数占据了前20个函数中的5个位置。实际上，如果我们对它们的CPU使用率求和，会发现应用程序整整10%的CPU时间花在内存管理上！

我们选择用mimalloc替换系统分配器。mimalloc是系统分配器的即插即用替代品。使用它就像将其安装位置添加到LD_PRELOAD并运行应用程序一样简单。

通过这一更改，我们发现内存管理已降至约5%，而不是之前的10%。在基准测试中，我们看到平均加速比为1.08倍，最小为1.05倍，最大为1.12倍。

第二幕：std::vector性能问题

在Top N Functions中，前两个项目单独占用了15%的CPU预算，并且与访问std::vector容器相关。这是一个相当极端的CPU预算比例，分配给任何一个内置数据结构。

通过分析调用图，我们发现两个函数（prog_state::init_safety_chk和inout_t::operator=）负责几乎所有对此函数的调用。这些相同的两个函数也负责所有对std::vector::operator[]的调用。

问题在于std::vector的特殊实现阻止了编译器自动向量化复制循环。我们决定用std::vector<char8_t>替换std::vector，这解决了别名问题，并允许编译器生成直线SIMD代码。

通过用vector<char8_t>替换vector并使编译器能够自动向量化相关循环，我们相对于mimalloc版本实现了1.31倍的平均加速，最大为1.57倍，最小为1.12倍。相对于默认版本，我们现在实现了1.43倍的平均加速，最大为1.75倍，最小为1.22倍。

第三幕：Z3优化

查看Top N Functions，我们发现Z3_solver_check()函数及其子函数负责K2完成的约46%的工作！我们决定通过修改Z3的编译方式来进行优化。

gcc和clang都支持配置文件引导优化（PGO）和链接时优化（LTO）。对Z3应用PGO和LTO为我们之前的版本带来了平均1.1倍的性能改进，最大为1.17倍，最小为1倍。

作为最后努力，我们还对K2本身进行了PGO（但没有进行LTO），这带来了另外1.03倍的平均性能增益，最大为1.09倍，最小为1倍。

结论

在替换mimalloc、用std::vector<char8_t>替换std::vector并应用PGO/LTO之后，我们实现了1.62倍的平均性能改进，最大为1.91倍，最小为1.42倍。在实践中，这意味着如果我们最初每秒探索10,000个状态，在相同的时间预算内，我们现在平均探索约16,000个，在最佳情况下我们探索几乎两倍的数量！

Prodfiler可以作为迭代过程的一部分使用，以显著提高应用程序性能。我将Prodfiler视为一个"Huh?“生成器，因为它的各种视图往往在我的大脑中引发"Huh - that’s weird"的想法，这是弄清楚为什么某些意外组件被分配尽可能多CPU的第一步。