前言

字節(jié)跳動(dòng)在內(nèi)部大規(guī)模落地了 Service Mesh，提供 RPC、HTTP 等多種流量代理能力，以及豐富的服務(wù)治理功能。Service Mesh 架構(gòu)包含數(shù)據(jù)面和控制面，其中，字節(jié)跳動(dòng) Service Mesh 數(shù)據(jù)面基于開(kāi)源的 Envoy 項(xiàng)目進(jìn)行二次開(kāi)發(fā)及改造，并針對(duì)主要的流量代理及服務(wù)治理功能進(jìn)行了重寫(xiě)，項(xiàng)目采用 C++ 語(yǔ)言編寫(xiě)。

我們?cè)趦?yōu)化數(shù)據(jù)面的歷程中，基于 LLVM 編譯工具鏈，圍繞 C++ Devirtualization 以及編譯優(yōu)化進(jìn)行了較多探索，落地了 LTO (Link Time Optimization)、PGO (Profile Guided Optimization) 、C++ Devirtualization 等編譯優(yōu)化技術(shù)，獲得了 25% 的可觀性能收益。本文將分享我們?cè)谧止?jié)跳動(dòng) Service Mesh 數(shù)據(jù)面的編譯優(yōu)化方向相關(guān)工作。

背景

字節(jié)跳動(dòng) Service Mesh 數(shù)據(jù)面以及依賴(lài)的 Envoy(下稱(chēng) mesh proxy)為了提供較好的抽象與可擴(kuò)展性，較多使用了 C++ 的 virtual 函數(shù)，雖然這能為編寫(xiě)程序帶來(lái)極大的便捷性，但是編譯后生成的機(jī)器指令中會(huì)包含大量 indirect call，每個(gè) indirect call 都不可避免地需要進(jìn)行一次動(dòng)態(tài)跳轉(zhuǎn)，過(guò)多的 indirect call 會(huì)帶來(lái)如下問(wèn)題：

• 間接指令跳轉(zhuǎn)開(kāi)銷(xiāo)：由于運(yùn)行期的實(shí)際函數(shù)(或接口)代碼地址是動(dòng)態(tài)賦值的，機(jī)器指令無(wú)法做更多優(yōu)化，只能直接執(zhí)行 call 指令，這對(duì)于 cache 局部性、指令預(yù)執(zhí)行以及分支預(yù)測(cè)都十分不友好。
• 無(wú)法內(nèi)聯(lián)優(yōu)化：由于 virtual 函數(shù)的實(shí)現(xiàn)本身是多態(tài)的，編譯中無(wú)法得出實(shí)際運(yùn)行期會(huì)執(zhí)行的實(shí)現(xiàn)，因此也無(wú)法進(jìn)行內(nèi)聯(lián)優(yōu)化。同時(shí)在很多場(chǎng)景下，調(diào)用一個(gè)函數(shù)只是為了得到部分返回值或副作用，但函數(shù)實(shí)現(xiàn)通常還執(zhí)行了某些額外計(jì)算，這些計(jì)算本可以通過(guò)內(nèi)聯(lián)優(yōu)化消除，由于無(wú)法內(nèi)聯(lián)，indirect call 會(huì)執(zhí)行更多無(wú)效的計(jì)算。
• 阻礙進(jìn)一步的編譯優(yōu)化：indirect call 相當(dāng)于是指令中的一個(gè)屏障，由于其本身是一個(gè)運(yùn)行期才能確定的調(diào)用，它在編譯期會(huì)使各種控制流判斷以及代碼展開(kāi)失效，從而限制進(jìn)一步編譯及鏈接的優(yōu)化空間。

雖然 virtual 函數(shù)會(huì)較大損失性能，但它又是必需的：第一，很多模塊本身就需要?jiǎng)討B(tài)的子類(lèi)實(shí)現(xiàn);第二，將功能模塊聲明為 virtual 接口對(duì)于測(cè)試編寫(xiě)更友好，便于提供 mock 實(shí)現(xiàn);第三，C++ 對(duì)于 virtual 函數(shù)及接口的支持較為成熟，代碼結(jié)構(gòu)簡(jiǎn)單清晰，即便對(duì)于靜態(tài)多態(tài)的接口，如果不使用 virtual 函數(shù)而是換做 template 模式來(lái)支持(例如 CRTP)，代碼結(jié)構(gòu)也會(huì)異常復(fù)雜，且上手成本較高，較難維護(hù)。

考慮到 virtual 函數(shù)本身的優(yōu)勢(shì)，以及對(duì)代碼結(jié)構(gòu)的改造成本，我們決定在代碼層繼續(xù)保持 virtual 函數(shù)的結(jié)構(gòu)，轉(zhuǎn)而從編譯優(yōu)化的角度對(duì)其性能開(kāi)銷(xiāo)進(jìn)行優(yōu)化。

調(diào)研

針對(duì) virtual 函數(shù)的優(yōu)化(即 devirtualization，或 Indirect Call Promotion)大致可分為三類(lèi)：Link Time Optimization (LTO)、 Whole Program Devirtualization (WPD) 以及 Speculative Devirtualization，它們大致的原理如下：

• Link Time Optimization (LTO)：鏈接時(shí)優(yōu)化，在編譯階段生成中間編譯對(duì)象代替?zhèn)鹘y(tǒng)的二進(jìn)制對(duì)象，并保留了元信息，接著在最終的鏈接階段以全局的視角鏈接所有中間編譯對(duì)象，執(zhí)行跨模塊的優(yōu)化手段，并生成二進(jìn)制代碼。LTO 分為 full LTO 和 thin LTO，full LTO 主要串行執(zhí)行，鏈接非常耗時(shí)，thin LTO 以少量的優(yōu)化損失作為代價(jià)換取并發(fā)的執(zhí)行模型，極大加快鏈接速度。由于 LTO 在鏈接階段具有全局的視角，因此可以進(jìn)行跨模塊的類(lèi)型推導(dǎo)，進(jìn)行一定的 devirtualization 優(yōu)化。
• Whole Program Devirtualization (WPD)：通過(guò)分析程序中類(lèi)的繼承結(jié)構(gòu)，得到某個(gè) virtual 函數(shù)的所有子類(lèi)實(shí)現(xiàn)，并依據(jù)這個(gè)結(jié)果進(jìn)行 devirtualization。這個(gè)優(yōu)化需要結(jié)合 LTO 才能夠?qū)嵤?，且?jīng)過(guò)實(shí)踐，該優(yōu)化效果并不理想(后文闡述)。
• Speculative Devirtualization：該優(yōu)化針對(duì)某個(gè) virtual callsite，“投機(jī)”地假設(shè)其運(yùn)行期的實(shí)現(xiàn)是某個(gè)或某幾個(gè)特定的子類(lèi)，如果命中了，則可以直接顯式地調(diào)用對(duì)應(yīng)的實(shí)現(xiàn)邏輯，否則，再走常規(guī)的 indirect call 邏輯。這個(gè)優(yōu)化結(jié)合 PGO 才有較好效果。

本文主要關(guān)注 Speculative Devirtualization 以及 PGO 優(yōu)化技術(shù)的原理及實(shí)踐，對(duì) LTO 以及 WPD 的原理不作過(guò)多展開(kāi)。

Speculative Devirtualization 原理介紹

下面以一個(gè)例子解釋 Speculative Devirtualization 的原理，假設(shè)我們編寫(xiě)了一個(gè) Foo 的接口以及一個(gè) FooImpl 的具體實(shí)現(xiàn)，如下所示：

struct Foo {
    virtual ~Foo() = default;
    virtual void do_something() = 0;
};

struct FooImpl : public Foo {
    void do_something() override { ... }
};

接著，在其他模塊使用了 Foo 接口，如下：

void bar(Foo &foo) {
    foo.do_something();
}

經(jīng)過(guò)編譯后，bar 函數(shù)的機(jī)器指令偽代碼大致如下：

addr = vtable.do_something.addr@foo
call *addr

上述偽代碼將傳入?yún)?shù) foo 的 do_something 函數(shù)的實(shí)際地址進(jìn)行加載，接著對(duì)該地址執(zhí)行一個(gè) call 指令，即動(dòng)態(tài)多態(tài)分發(fā)的基本原理。

對(duì)于上述例子，在 Speculative Devirtualization 優(yōu)化中，編譯器假設(shè)在實(shí)際運(yùn)行中，foo 大概率是 FooImpl 的對(duì)象，因而生成的指令中，先判斷該假設(shè)是否成立，如果成立，則直接調(diào)用 FooImpl::do_something()，否則，再走常規(guī)的 indirect call，偽代碼如下：

addr = vtable.do_something.addr@foo
if (addr == FooImpl::do_something)
    FooImpl::do_something()
else
    call *addr

可以看到，上面的偽代碼中，獲取實(shí)際的函數(shù)地址后，并沒(méi)有直接執(zhí)行一個(gè) indirect call，而是先判斷它是不是 FooImpl，如果命中，則可以直接調(diào)用 FooImpl::do_something()。這個(gè)例子只有一個(gè)子類(lèi)實(shí)現(xiàn)，如果有多個(gè)，也是類(lèi)似會(huì)有 if 判斷，等所有 if 判斷都失敗后，最后 fallback 到 indirect call。

初步看來(lái)，這個(gè)做法反而增加了指令量，有悖于優(yōu)化的直覺(jué)。然而，假設(shè)大部分調(diào)用中， foo 參數(shù)的類(lèi)型都是 FooImpl 的話(huà)，實(shí)際上只是增加一個(gè)地址的比較指令。并且，由于 CPU 指令的順序執(zhí)行特征，這里不會(huì)有分支跳轉(zhuǎn)的開(kāi)銷(xiāo)(盡管有個(gè) if)。進(jìn)一步地，直接調(diào)用 FooImpl::do_something() 與 else 分支中的 call *addr 在高級(jí)語(yǔ)言中看起來(lái)似乎并沒(méi)有區(qū)別，然而在編譯器的視角中是完全不一樣的。這是因?yàn)镕ooImpl::do_something()是明確的靜態(tài)函數(shù)，可以直接應(yīng)用內(nèi)聯(lián)優(yōu)化，不僅能夠省去函數(shù)跳轉(zhuǎn)的開(kāi)銷(xiāo)，還可以消除函數(shù)實(shí)現(xiàn)中不必要的計(jì)算?？紤]一個(gè)極端場(chǎng)景，假設(shè)FooImpl::do_something()的實(shí)現(xiàn)是個(gè)空函數(shù)，經(jīng)過(guò)內(nèi)聯(lián)后，整個(gè)過(guò)程由最開(kāi)始的一個(gè) indirect call，優(yōu)化成了只需比較一次函數(shù)地址即可結(jié)束的過(guò)程，這帶來(lái)的性能差異是巨大的。

當(dāng)然，正如這個(gè)優(yōu)化給人的直覺(jué)一樣。如果上面 foo 的類(lèi)型不是 FooImpl，那么這就是個(gè)負(fù)優(yōu)化，也正因如此，這個(gè)優(yōu)化在默認(rèn)情況下基本不會(huì)生效，而是要在 PGO 優(yōu)化中才會(huì)被觸發(fā)。由于在 PGO 優(yōu)化中，編譯器具備程序在運(yùn)行期的 profile 信息，其中就包括 indirect call 調(diào)用各個(gè)實(shí)現(xiàn)函數(shù)的概率分布，因此編譯器可以根據(jù)這個(gè)信息，針對(duì)高概率的函數(shù)實(shí)現(xiàn)開(kāi)啟該優(yōu)化。

PGO 優(yōu)化實(shí)踐

PGO(Profile Guided Optimization)，也稱(chēng) FDO(Feedback Directed Optimization)，是指利用程序運(yùn)行過(guò)程中采集到的 profile 數(shù)據(jù)，來(lái)重新編譯程序以達(dá)到優(yōu)化效果的 post-link 優(yōu)化技術(shù)。其原理認(rèn)為，對(duì)于特征相似的 input，程序運(yùn)行的特征也相似，因此，我們可以把運(yùn)行期的 profile 特征數(shù)據(jù)先采集一遍，再用來(lái)指導(dǎo)編譯過(guò)程進(jìn)行優(yōu)化。

PGO 優(yōu)化依賴(lài)程序運(yùn)行期所采集的 profile 數(shù)據(jù)，profile 數(shù)據(jù)的采集有兩種方式，一是編譯期插樁(例如 clang 的 -fprofile-instr-generate 編譯參數(shù));二是運(yùn)行期使用 linux-perf 工具采集，并將 perf 的數(shù)據(jù)轉(zhuǎn)換成 LLVM 可識(shí)別的 profile 格式。對(duì)于第二種方式，AutoFDO 是更通用的叫法。AutoFDO 的整體流程如下圖所示：

我們的實(shí)踐采用的是第二種方式：運(yùn)行期采集 perf 。這是因?yàn)?，如果采用插樁的方式，就只能采集特?benchmark 的 profile，而不能采集線(xiàn)上真實(shí)流量的 profile，畢竟不可能在線(xiàn)上環(huán)境運(yùn)行一個(gè)插樁的版本。PGO 的成功實(shí)踐極大地促進(jìn)了 devirtualization 的效果，同時(shí)，由于本身也帶來(lái)了其他的優(yōu)化機(jī)制，獲得了 15% 的性能收益，下面介紹我們?cè)?PGO 優(yōu)化上的重點(diǎn)工作。

基于 Profile 數(shù)據(jù)的 PGO 優(yōu)化基本原理介紹

程序運(yùn)行期采集到的 profile 數(shù)據(jù)中，記錄了該程序的熱點(diǎn)函數(shù)及指令，這里不做過(guò)多展開(kāi)，以?xún)蓚€(gè)簡(jiǎn)單例子說(shuō)明它是如何指導(dǎo)編譯器做 PGO 優(yōu)化的。

virtual 函數(shù) PGO 優(yōu)化示例

第一個(gè)例子接著上文中的 Foo 接口。假設(shè)程序中除了有 FooImpl 子類(lèi)外，還存在 BarImpl 以及其他子類(lèi)，在 Speculative Devirtualization 優(yōu)化前，程序是直接獲取到實(shí)際函數(shù)地址后執(zhí)行 call 指令，而 profile 數(shù)據(jù)則會(huì)記錄在所有采集到的這個(gè)調(diào)用樣本中，實(shí)際調(diào)用了 FooImpl、BarImpl 以及其他子類(lèi)實(shí)現(xiàn)的次數(shù)。例如，該調(diào)用點(diǎn)一共被采樣 10000 次，其中有 9000 次都是調(diào)用 FooImpl 實(shí)現(xiàn)，那么編譯器認(rèn)為這里大概率都是調(diào)用 FooImpl，就可以針對(duì) FooImpl 開(kāi)啟 Speculative Devirtualization，從而優(yōu)化 90% 的 case?？梢钥闯?，這個(gè)優(yōu)化對(duì)于只有單個(gè)實(shí)現(xiàn)的 virtual 函數(shù)是極佳的，它在保留了未來(lái)的 virtual 函數(shù)可擴(kuò)展性的基礎(chǔ)上，將其性能優(yōu)化到與普通直接函數(shù)調(diào)用無(wú)異。

分支判斷 PGO 優(yōu)化示例

第二個(gè)例子是一個(gè)針對(duì)分支判斷的優(yōu)化示例。假設(shè)有如下代碼片段，該代碼片段判斷參數(shù) a 是否為 true，若是，則執(zhí)行 a_staff 的邏輯;否則，執(zhí)行 b_staff 邏輯。

if (a)
    // do a_staff...
else
    // do b_staff...
return

在編譯時(shí)，由于編譯器并不能假設(shè) a 為 true 或者 false 的概率，通常按照同樣的 block 順序輸出機(jī)器指令，偽匯編代碼如下。其中，先對(duì)參數(shù) a 進(jìn)行 bool 判斷，若為 true ，則緊接著執(zhí)行 a_staff 的邏輯，再 return;否則，便跳轉(zhuǎn)到 .else 處，再執(zhí)行 b_staff 的邏輯。

test a, a
je   .else  ; jump if a is false
.if:
; do a staff...
ret
.else:
; do b staff...
ret

在 CPU 的實(shí)際執(zhí)行中，由于指令順序執(zhí)行以及 pipeline 預(yù)執(zhí)行等機(jī)制，因此，會(huì)優(yōu)先執(zhí)行當(dāng)前指令緊接著的下一條指令。上面的指令對(duì) a_staff 是有利的，如果 a 為 true，那么整個(gè)流水線(xiàn)便一氣呵成，沒(méi)有跳轉(zhuǎn)的開(kāi)銷(xiāo);相反的，指令對(duì) b_staff 不利，如果 a 為 false，那么 pipeline 中先前預(yù)執(zhí)行的 a_staff 計(jì)算則會(huì)被作廢，轉(zhuǎn)而需要從 .else 處的重新加載指令，并重新執(zhí)行 b_staff，這些消耗會(huì)顯著降低指令的執(zhí)行性能。

從上面的分析可以得出，如果恰好在實(shí)際運(yùn)行中，a 為 true 的概率比較大，那么該代碼片段會(huì)比較高效，反之則低效。借助對(duì)程序運(yùn)行期的 profile 數(shù)據(jù)進(jìn)行采集，則可以得到上面的分支判斷中，實(shí)際走 if 分支和走 else 分支的次數(shù)。借助該統(tǒng)計(jì)數(shù)據(jù)，在 PGO 編譯中，若走 else 分支的概率較大，編譯器便可以對(duì)輸出的機(jī)器指令進(jìn)行調(diào)整，類(lèi)似如下的偽匯編指令，從而對(duì) b_staff 更有利。

test a, a
jne  .if  ; jump if a is true
.else:
; do b staff...
ret
.if:
; do a staff...
ret

Profile 數(shù)據(jù)的采集及轉(zhuǎn)換

為了采集 mesh proxy 運(yùn)行期的 profile 數(shù)據(jù)，首先需要進(jìn)行正常的最優(yōu)編譯并生成二進(jìn)制。為了避免二進(jìn)制中同名 static 函數(shù)符號(hào)的歧義，以及區(qū)分同一行 C++ 代碼中多個(gè)函數(shù)的調(diào)用，提高 PGO 的優(yōu)化效果，我們需要新增 -funique-internal-linkage-names 和 -fdebug-info-for-profiling 這兩個(gè) clang 編譯參數(shù)，此外，還需要增加 -Wl,--no-rosegment 鏈接參數(shù)，否則 linux-perf 收集到的 perf 數(shù)據(jù)無(wú)法通過(guò) AutoFDO 轉(zhuǎn)換工具轉(zhuǎn)換成 LLVM 所需的格式。

完成編譯后，選擇合適的 benchmark 或者真實(shí)流量運(yùn)行程序，并采用 linux-perf 工具采集 perf 數(shù)據(jù)。經(jīng)過(guò)實(shí)踐驗(yàn)證，使用 linux-perf 采集時(shí)，啟用 LBR(Last Branch Record)功能可以獲得更佳的優(yōu)化效果。我們采用如下命令對(duì) mesh proxy 進(jìn)程進(jìn)行 perf 數(shù)據(jù)采集。

perf record -p -e cycles:up -j any,u -a -- sleep 60

完成 perf 數(shù)據(jù)采集后，使用 AutoFDO 工具(https://github.com/google/autofdo)將 perf 數(shù)據(jù)轉(zhuǎn)換成 LLVM profile 格式。

create_llvm_prof --profile perf.data --binary --out=llvm.prof

帶 PGO 的優(yōu)化編譯

得到 profile 數(shù)據(jù)后，即可進(jìn)行最后一步帶 PGO 優(yōu)化的重編譯步驟，需要注意的是，該次編譯的源碼必須和之前 profile 采集用的源碼完全一致，否則會(huì)干擾優(yōu)化效果。為了開(kāi)啟 PGO 優(yōu)化，只需要再添加 -fprofile-sample-use=llvm.prof clang 編譯參數(shù)，使用該 llvm.prof 文件中的 profile 數(shù)據(jù)進(jìn)行 PGO 編譯優(yōu)化。

經(jīng)過(guò) PGO 編譯優(yōu)化后，mesh proxy 二進(jìn)制整體的 indirect call 數(shù)量降低了 80%，基本完成了 C++ Devirtualization 的目標(biāo)。此外，PGO 會(huì)根據(jù) profile 中的熱點(diǎn)函數(shù)及指令進(jìn)行更進(jìn)一步的內(nèi)聯(lián)，對(duì)熱點(diǎn)指令及內(nèi)存進(jìn)行重排，并進(jìn)一步增強(qiáng)常規(guī)的優(yōu)化手段，這些都能給性能帶來(lái)顯著的收益。

其他編譯優(yōu)化工作

全靜態(tài)鏈接及 LTO 實(shí)踐

在字節(jié) mesh proxy 達(dá)到一定的線(xiàn)上規(guī)模后，我們遇到了動(dòng)態(tài)鏈接上的一些問(wèn)題，包括運(yùn)行機(jī)器的 glibc 版本可能較低，以及動(dòng)態(tài)鏈接的函數(shù)調(diào)用本身有多余開(kāi)銷(xiāo)。

考慮到 mesh proxy 本身其實(shí)是作為一個(gè)獨(dú)立的 sidecar 運(yùn)行，并不需要作為一個(gè)程序庫(kù)供其他程序使用，因此，我們提出將 binary 進(jìn)行全靜態(tài)鏈接的想法。這樣做的好處有：一是可以避免 glibc 版本問(wèn)題，二是消除動(dòng)態(tài)鏈接函數(shù)跳轉(zhuǎn)開(kāi)銷(xiāo)，三是全靜態(tài)鏈接下可以進(jìn)一步應(yīng)用更多編譯優(yōu)化。

支持全靜態(tài)鏈接后，由于 binary 沒(méi)有任何外部庫(kù)依賴(lài)，我們又增加了進(jìn)一步的編譯優(yōu)化，包括將 thread local storage 的模型改為 local-exec，以及 ThinLTO(Link Time Optimization)優(yōu)化。其中，ThinLTO 帶來(lái)了將近 8% 的性能提升。

WPD 的嘗試

為了達(dá)到 devirtualization 的效果，我們也嘗試了 Whole Program Devirtualization，但實(shí)際效果并不理想，只有較少一部分的 indirect call 被優(yōu)化。通過(guò)對(duì) LLVM 相應(yīng)模塊實(shí)現(xiàn)的研究，我們了解到目前的 WPD 優(yōu)化只對(duì)僅有單個(gè)實(shí)現(xiàn)的 virtual 函數(shù)生效，因此在現(xiàn)階段還無(wú)法帶來(lái)顯著的性能收益。

BOLT post-link 優(yōu)化

在 LTO、PGO 編譯優(yōu)化的基礎(chǔ)上，我們還更進(jìn)一步探索了 BOLT 這類(lèi) post-link 優(yōu)化技術(shù)，并得到了約 8% 的性能收益?？紤]到穩(wěn)定因素，該優(yōu)化仍在探索與測(cè)試中，暫未上線(xiàn)。

后記

希望以上的分享能夠?qū)ι鐓^(qū)有所幫助，我們也在規(guī)劃將上述編譯優(yōu)化方法回饋到 Envoy 開(kāi)源社區(qū)版本，共同參與 Service Mesh 領(lǐng)域的建設(shè)。

參考資料

• https://people.cs.pitt.edu/~zhangyt/research/pgco.pdf
• ??https://research.google/pubs/pub45290/??
• ??https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization??
• ??https://github.com/llvm/llvm-project/tree/main/bolt??
• ??https://llvm.org/devmtg/2015-10/slides/Baev-IndirectCallPromotion.pdf??
• ??https://quuxplusone.github.io/blog/2021/02/15/devirtualization/??