前言
字节跳动在内部大规模落地了 Service Mesh，供给 RPC、HTTP 等多种流量署理能力，以及丰厚的服务管理功用。Service Mesh 架构包括数据面和操控面，其间，字节跳动 Service Mesh 数据面依据开源的 Envoy 项目进行二次开发及改造，并针对首要的流量署理及服务管理功用进行了重写，项目选用 C++ 言语编写。
咱们在优化数据面的历程中，依据 LLVM 编译东西链，环绕 C++ Devirtualization 以及编译优化进行了较多探究，落地了 LTO (Link Time Optimization)、PGO (Profile Guided Optimization) 、C++ Devirtualization 等编译优化技能，获得了 25% 的可观功用收益。本文将共享咱们在字节跳动 Service Mesh 数据面的编译优化方向相关工作。
背景
字节跳动 Service Mesh 数据面以及依靠的 Envoy（下称 mesh proxy）为了供给较好的笼统与可扩展性，较多运用了 C++ 的 virtual 函数，虽然这能为编写程序带来极大的便捷性，但是编译后生成的机器指令中会包括大量 indirect call，每个 indirect call 都不可防止地需求进行一次动态跳转，过多的 indirect call 会带来如下问题：
- 直接指令跳转开支：因为运转期的实践函数（或接口）代码地址是动态赋值的，机器指令无法做更多优化，只能直接履行 call 指令，这关于 cache 局部性、指令预履行以及分支预测都十分不友好。
- 无法内联优化：因为 virtual 函数的完成自身是多态的，编译中无法得出实践运转期会履行的完成，因而也无法进行内联优化。一起在许多场景下，调用一个函数仅仅为了得到部分返回值或副作用，但函数完成通常还履行了某些额外核算，这些核算本可以经过内联优化消除，因为无法内联，indirect call 会履行更多无效的核算。
- 阻碍进一步的编译优化：indirect call 相当所以指令中的一个屏障，因为其自身是一个运转期才干确定的调用，它在编译期会使各种操控流判别以及代码打开失效，然后约束进一步编译及链接的优化空间。
虽然 virtual 函数会较大丢失功用，但它又是必需的：榜首，许多模块自身就需求动态的子类完成；第二，将功用模块声明为 virtual 接口关于测验编写更友好，便于供给 mock 完成；第三，C++ 关于 virtual 函数及接口的支撑较为老练，代码结构简单明晰，即使关于静态多态的接口，假如不运用 virtual 函数而是换做 template 模式来支撑（例如 CRTP），代码结构也会异常杂乱，且上手本钱较高，较难维护。
考虑到 virtual 函数自身的优势，以及对代码结构的改造本钱，咱们决定在代码层持续保持 virtual 函数的结构，转而从编译优化的角度对其功用开支进行优化。
调研
针对 virtual 函数的优化（即 devirtualization，或 Indirect Call Promotion）大致可分为三类：Link Time Optimization (LTO)、 Whole Program Devirtualization (WPD) 以及 Speculative Devirtualization，它们大致的原理如下：
- Link Time Optimization （LTO） ：链接时优化，在编译阶段生成中心编译方针替代传统的二进制方针，并保留了元信息，接着在终究的链接阶段以大局的视角链接所有中心编译方针，履行跨模块的优化手法，并生成二进制代码。LTO 分为 full LTO 和 thin LTO，full LTO 首要串行履行，链接非常耗时，thin LTO 以少量的优化丢失作为代价交换并发的履行模型，极大加快链接速度。因为 LTO 在链接阶段具有大局的视角，因而可以进行跨模块的类型推导，进行一定的 devirtualization 优化。
- Whole Program Devirtualization （WPD） ：经过分析程序中类的继承结构，得到某个 virtual 函数的所有子类完成，并依据这个成果进行 devirtualization。这个优化需求结合 LTO 才干够实施，且经过实践，该优化作用并不理想（后文阐述）。
- Speculative Devirtualization：该优化针对某个 virtual callsite，“投机”地假定其运转期的完成是某个或某几个特定的子类，假如命中了，则可以直接显式地调用对应的完成逻辑，不然，再走惯例的 indirect call 逻辑。这个优化结合 PGO 才有较好作用。
本文首要重视 Speculative Devirtualization 以及 PGO 优化技能的原理及实践，对 LTO 以及 WPD 的原理不作过多打开。
Speculative Devirtualization 原理介绍
下面以一个比如解释 Speculative Devirtualization 的原理，假定咱们编写了一个 Foo 的接口以及一个 FooImpl 的详细完成，如下所示：
structFoo{
virtual~Foo()=default;
virtualvoiddo_something()=0;
};
structFooImpl:publicFoo{
voiddo_something()override{...}
};
接着，在其他模块运用了 Foo 接口，如下：
voidbar(Foo&foo){
foo.do_something();
}
经过编译后，bar 函数的机器指令伪代码大致如下：
addr=vtable.do_something.addr@foo
call*addr
上述伪代码将传入参数 foo 的 do_something 函数的实践地址进行加载，接着对该地址履行一个 call 指令，即动态多态分发的根本原理。
关于上述比如，在 Speculative Devirtualization 优化中，编译器假定在实践运转中，foo 大概率是 FooImpl 的方针，因而生成的指令中，先判别该假定是否建立，假如建立，则直接调用FooImpl::do_something()，不然，再走惯例的 indirect call，伪代码如下：
addr=vtable.do_something.addr@foo
if(addr==FooImpl::do_something)
FooImpl::do_something()
else
call*addr
可以看到，上面的伪代码中，获取实践的函数地址后，并没有直接履行一个 indirect call，而是先判别它是不是 FooImpl，假如命中，则可以直接调用FooImpl::do_something()。这个比如只要一个子类完成，假如有多个，也是相似会有 if 判别，等所有 if 判别都失败后，最终 fallback 到 indirect call。
开端看来，这个做法反而添加了指令量，有悖于优化的直觉。但是，假定大部分调用中， foo 参数的类型都是 FooImpl 的话，实践上仅仅添加一个地址的比较指令。并且，因为 CPU 指令的次序履行特征，这里不会有分支跳转的开支（尽管有个 if）。进一步地，直接调用FooImpl::do_something()与 else 分支中的call *addr在高级言语中看起来好像并没有差异，但是在编译器的视角中是彻底不相同的。这是因为FooImpl::do_something()是明确的静态函数，可以直接使用内联优化，不只可以省去函数跳转的开支，还可以消除函数完成中不必要的核算。考虑一个极端场景，假定FooImpl::do_something()的完成是个空函数，经过内联后，整个进程由最开端的一个 indirect call，优化成了只需比较一次函数地址即可结束的进程，这带来的功用差异是巨大的。
当然，正如这个优化给人的直觉相同。假如上面 foo 的类型不是 FooImpl，那么这便是个负优化，也正因如此，这个优化在默认情况下根本不会收效，而是要在 PGO 优化中才会被触发。因为在 PGO 优化中，编译器具备程序在运转期的 profile 信息，其间就包括 indirect call 调用各个完成函数的概率分布，因而编译器可以依据这个信息，针对高概率的函数完成敞开该优化。
PGO 优化实践
PGO（Profile Guided Optimization），也称 FDO（Feedback Directed Optimization），是指运用程序运转进程中收集到的 profile 数据，来从头编译程序以到达优化作用的 post-link 优化技能。其原理以为，关于特征相似的 input，程序运转的特征也相似，因而，咱们可以把运转期的 profile 特征数据先收集一遍，再用来指导编译进程进行优化。
PGO 优化依靠程序运转期所收集的 profile 数据，profile 数据的收集有两种方式，一是编译期插桩（例如 clang 的-fprofile-instr-generate编译参数）；二是运转期运用 linux-perf 东西收集，并将 perf 的数据转换成 LLVM 可辨认的 profile 格局。关于第二种方式，AutoFDO 是更通用的叫法。AutoFDO 的全体流程如下图所示：
咱们的实践选用的是第二种方式：运转期收集 perf 。这是因为，假如选用插桩的方式，就只能收集特定 benchmark 的 profile，而不能收集线上实在流量的 profile，毕竟不可能在线上环境运转一个插桩的版别。PGO 的成功实践极大地促进了 devirtualization 的作用，一起，因为自身也带来了其他的优化机制，获得了 15% 的功用收益，下面介绍咱们在 PGO 优化上的重点工作。
依据 Profile 数据的 PGO 优化根本原理介绍
程序运转期收集到的 profile 数据中，记录了该程序的热点函数及指令，这里不做过多打开，以两个简单比如阐明它是如何指导编译器做 PGO 优化的。
virtual 函数 PGO 优化示例
榜首个比如接着上文中的 Foo 接口。假定程序中除了有 FooImpl 子类外，还存在 BarImpl 以及其他子类，在 Speculative Devirtualization 优化前，程序是直接获取到实践函数地址后履行 call 指令，而 profile 数据则会记录在所有收集到的这个调用样本中，实践调用了 FooImpl、BarImpl 以及其他子类完成的次数。例如，该调用点总共被采样 10000 次，其间有 9000 次都是调用 FooImpl 完成，那么编译器以为这里大概率都是调用 FooImpl，就可以针对 FooImpl 敞开 Speculative Devirtualization，然后优化 90% 的 case。可以看出，这个优化关于只要单个完成的 virtual 函数是极佳的，它在保留了未来的 virtual 函数可扩展性的基础上，将其功用优化到与普通直接函数调用无异。
分支判别 PGO 优化示例
第二个比如是一个针对分支判别的优化示例。假定有如下代码片段，该代码片段判别参数a是否为true，若是，则履行a_staff的逻辑；不然，履行b_staff逻辑。
if(a)
//doa_staff...
else
//dob_staff...
return
在编译时，因为编译器并不能假定 a 为 true 或许 false 的概率，通常依照相同的 block 次序输出机器指令，伪汇编代码如下。其间，先对参数a进行bool判别，若为true，则紧接着履行a_staff的逻辑，再 return；不然，便跳转到 .else 处，再履行b_staff的逻辑。
testa,a
je.else;jumpifaisfalse
.if:
;doastaff...
ret
.else:
;dobstaff...
ret
在 CPU 的实践履行中，因为指令次序履行以及 pipeline 预履行等机制，因而，会优先履行当时指令紧接着的下一条指令。上面的指令对a_staff是有利的，假如a为true，那么整个流水线便一气呵成，没有跳转的开支；相反的，指令对b_staff不利，假如a为false，那么 pipeline 中先前预履行的a_staff核算则会被报废，转而需求从.else处的从头加载指令，并从头履行b_staff，这些消耗会明显下降指令的履行功用。
从上面的分析可以得出，假如恰好在实践运转中，a为true的概率比较大，那么该代码片段会比较高效，反之则低效。凭借对程序运转期的 profile 数据进行收集，则可以得到上面的分支判别中，实践走if分支和走else分支的次数。凭借该统计数据，在 PGO 编译中，若走else分支的概率较大，编译器便可以对输出的机器指令进行调整，相似如下的伪汇编指令，然后对b_staff更有利。
testa,a
jne.if;jumpifaistrue
.else:
;dobstaff...
ret
.if:
;doastaff...
ret
Profile 数据的收集及转换
为了收集 mesh proxy 运转期的 profile 数据，首先需求进行正常的最优编译并生成二进制。为了防止二进制中同名 static 函数符号的歧义，以及区别同一行 C++ 代码中多个函数的调用，提高 PGO 的优化作用，咱们需求新增-funique-internal-linkage-names和-fdebug-info-for-profiling这两个 clang 编译参数，此外，还需求添加-Wl,--no-rosegment链接参数，不然 linux-perf 收集到的 perf 数据无法经过 AutoFDO 转换东西转换成 LLVM 所需的格局。
完成编译后，选择适宜的 benchmark 或许实在流量运转程序，并选用 linux-perf 东西收集 perf 数据。经过实践验证，运用 linux-perf 收集时，启用 LBR（Last Branch Record）功用可以获得更佳的优化作用。咱们选用如下指令对 mesh proxy 进程进行 perf 数据收集。
perfrecord-p<pid>-ecycles:up-jany,u-a--sleep60
完成 perf 数据收集后，运用 AutoFDO 东西（github.com/google/auto… 将 perf 数据转换成 LLVM profile 格局。
create_llvm_prof--profileperf.data--binary<binary>--out=llvm.prof
带 PGO 的优化编译
得到 profile 数据后，即可进行最终一步带 PGO 优化的重编译过程，需求注意的是，该次编译的源码有必要和之前 profile 收集用的源码彻底一致，不然会干扰优化作用。为了敞开 PGO 优化，只需求再添加-fprofile-sample-use=llvm.profclang 编译参数，运用该 llvm.prof 文件中的 profile 数据进行 PGO 编译优化。
经过 PGO 编译优化后，mesh proxy 二进制全体的 indirect call 数量下降了 80%，根本完成了 C++ Devirtualization 的方针。此外，PGO 会依据 profile 中的热点函数及指令进行更进一步的内联，对热点指令及内存进行重排，并进一步增强惯例的优化手法，这些都能给功用带来明显的收益。
其他编译优化工作
全静态链接及 LTO 实践
在字节 mesh proxy 到达一定的线上规模后，咱们遇到了动态链接上的一些问题，包括运转机器的 glibc 版别可能较低，以及动态链接的函数调用自身有剩余开支。
考虑到 mesh proxy 自身其实是作为一个独立的 sidecar 运转，并不需求作为一个程序库供其他程序运用，因而，咱们提出将 binary 进行全静态链接的想法。这样做的优点有：一是可以防止 glibc 版别问题，二是消除动态链接函数跳转开支，三是全静态链接下可以进一步使用更多编译优化。
支撑全静态链接后，因为 binary 没有任何外部库依靠，咱们又添加了进一步的编译优化，包括将 thread local storage 的模型改为local-exec，以及 ThinLTO（Link Time Optimization）优化。其间，ThinLTO 带来了将近 8% 的功用提升。
WPD 的测验
为了到达 devirtualization 的作用，咱们也测验了 Whole Program Devirtualization，但实践作用并不理想，只要较少一部分的 indirect call 被优化。经过对 LLVM 相应模块完成的研究，咱们了解到现在的 WPD 优化只对仅有单个完成的 virtual 函数收效，因而在现阶段还无法带来明显的功用收益。
BOLT post-link 优化
在 LTO、PGO 编译优化的基础上，咱们还更进一步探究了 BOLT 这类 post-link 优化技能，并得到了约 8% 的功用收益。考虑到安稳因素，该优化仍在探究与测验中，暂未上线。
后记
希望以上的共享可以对社区有所协助，咱们也在规划将上述编译优化方法回馈到 Envoy 开源社区版别，共同参加 Service Mesh 领域的建设。
参考资料
- people.cs.pitt.edu/~zhangyt/re…
- research.google/pubs/pub452…
- clang.llvm.org/docs/UsersM…
- github.com/llvm/llvm-p…
- llvm.org/devmtg/2015…
- quuxplusone.github.io/blog/2021/0…
