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

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

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

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

优化改进概述

发现的改进来自以下三个方面：

1. 用性能更好的替代方案（即mimalloc）替换系统分配器
2. 辅助编译器自动向量化一系列热点循环
3. 对K2自身及其最重要依赖Z3应用PGO和LTO

引言

随着eBPF的更多用例被发现（其中许多处于关键路径上），编译器生成的eBPF代码性能变得越来越重要。虽然clang通常能生成高效程序，但有时会产生存在冗余、异常指令序列选择、不必要的窄操作数宽度和其他怪癖的代码，这意味着手动优化程序可以显著更快。手动优化eBPF指令具有挑战性、耗时且容易出错，因此，与更传统目标平台的编译一样，存在一种市场，即花费时间在编译上以在运行时获得性能。

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

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

K2架构简要概述

为了了解我们将要优化的内容，让我们快速浏览一下K2的组件。上图来自K2论文，如果您想了解更多细节，该论文非常易读且高度推荐。

如上所述，作为MCMC驱动，K2的核心是：

1. 从当前状态生成新候选
2. 为该候选分配成本
3. 根据候选成本和当前状态成本，有条件地将当前状态设置为新候选状态

在算法上，几乎所有的繁重工作都在步骤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，一个 notorious 奇怪的容器。std::vector在内存使用是关注点的情况下可能是正确的选择，但如果主要关注CPU使用，那么有更好的选择。好的，这是一个好的开始，但让我们暂时搁置它，继续向下看列表，看看是否有更简单的收益可以找到。

第二个突出的项目是在位置5和6我们可以看到malloc和free函数。实际上，在将上述列表扩展到前20个函数时，我发现malloc相关函数占据了前20个位置中的5个。如果我们求和它们的CPU使用率，我们了解到应用程序的CPU时间的整整10%花费在内存管理上！花费如此多时间在内存管理上的应用程序几乎总是可以通过两种方式加速。一种方法是分析应用程序的内存使用，并尝试调整它以简单地对内存管理函数进行更少的调用。第二种方法是用其他东西替换系统分配器。后一种方法通常工作少得多[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 占CPU预算的15%，并且与访问std::vector容器相关，如前所述。这是分配给任何内置数据结构的相当极端的CPU预算比例，我在这种情况下的期望是有收益可以获得。首先，我们需要弄清楚std::vector被用来表示什么，以及它如何被使用。为了回答这个问题，Prodfiler为每个函数提供了一个调用图，可以通过在Top N Functions视图中点击函数名（或在Flamegraph视图中ctrl-clicking函数）访问。std::vector::operator=的调用图如下所示：

我们可以看到两个函数（prog_state::init_safety_chk和inout_t::operator=）负责 practically 所有对此函数的调用。这两个相同的函数也负责所有对std::vector::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类型替换为uint8_t。然而，在这样做并重新运行基准测试后，性能改进微不足道，并且不像如果上述逐字节复制被直接SIMD替换所期望的那样。回到反汇编，我们发现复制循环变成了以下内容：

出于某种原因，编译器决定产生逐字节复制循环，其中在每次迭代中从内存加载源和目标指针。我在Twitter上询问了这个问题，Travis Downs回应并指出问题是