字節(jié)跳動 Service Mesh 數(shù)據(jù)面編譯優(yōu)化實(shí)踐

作者：字節(jié)跳動技術(shù)團(tuán)隊(duì) 2022-04-07 16:35:59

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

前言

字節(jié)跳動在內(nèi)部大規(guī)模落地了 Service Mesh，提供 RPC、HTTP 等多種流量代理能力，以及豐富的服務(wù)治理功能。Service Mesh 架構(gòu)包含數(shù)據(jù)面和控制面，其中，字節(jié)跳動 Service Mesh 數(shù)據(jù)面基于開源的 Envoy 項(xiàng)目進(jìn)行二次開發(fā)及改造，并針對主要的流量代理及服務(wù)治理功能進(jìn)行了重寫，項(xiàng)目采用 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% 的可觀性能收益。本文將分享我們在字節(jié)跳動 Service Mesh 數(shù)據(jù)面的編譯優(yōu)化方向相關(guān)工作。

背景

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

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

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

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

調(diào)研

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

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

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

Speculative Devirtualization 原理介紹

下面以一個(gè)例子解釋 Speculative Devirtualization 的原理，假設(shè)我們編寫了一個(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)過編譯后，bar 函數(shù)的機(jī)器指令偽代碼大致如下：

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

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

對于上述例子，在 Speculative Devirtualization 優(yōu)化中，編譯器假設(shè)在實(shí)際運(yùn)行中，foo 大概率是 FooImpl 的對象，因而生成的指令中，先判斷該假設(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ù)地址后，并沒有直接執(zhí)行一個(gè) indirect call，而是先判斷它是不是 FooImpl，如果命中，則可以直接調(diào)用 FooImpl::do_something()。這個(gè)例子只有一個(gè)子類實(shí)現(xiàn)，如果有多個(gè)，也是類似會有 if 判斷，等所有 if 判斷都失敗后，最后 fallback 到 indirect call。

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

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

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

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

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

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

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

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

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

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

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

第二個(gè)例子是一個(gè)針對分支判斷的優(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ī)器指令，偽匯編代碼如下。其中，先對參數(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ī)制，因此，會優(yōu)先執(zhí)行當(dāng)前指令緊接著的下一條指令。上面的指令對 a_staff 是有利的，如果 a 為 true，那么整個(gè)流水線便一氣呵成，沒有跳轉(zhuǎn)的開銷;相反的，指令對 b_staff 不利，如果 a 為 false，那么 pipeline 中先前預(yù)執(zhí)行的 a_staff 計(jì)算則會被作廢，轉(zhuǎn)而需要從 .else 處的重新加載指令，并重新執(zhí)行 b_staff，這些消耗會顯著降低指令的執(zhí)行性能。

從上面的分析可以得出，如果恰好在實(shí)際運(yùn)行中，a 為 true 的概率比較大，那么該代碼片段會比較高效，反之則低效。借助對程序運(yùn)行期的 profile 數(shù)據(jù)進(jìn)行采集，則可以得到上面的分支判斷中，實(shí)際走 if 分支和走 else 分支的次數(shù)。借助該統(tǒng)計(jì)數(shù)據(jù)，在 PGO 編譯中，若走 else 分支的概率較大，編譯器便可以對輸出的機(jī)器指令進(jìn)行調(diào)整，類似如下的偽匯編指令，從而對 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ù)符號的歧義，以及區(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ù)無法通過 AutoFDO 轉(zhuǎn)換工具轉(zhuǎn)換成 LLVM 所需的格式。

完成編譯后，選擇合適的 benchmark 或者真實(shí)流量運(yùn)行程序，并采用 linux-perf 工具采集 perf 數(shù)據(jù)。經(jīng)過實(shí)踐驗(yàn)證，使用 linux-perf 采集時(shí)，啟用 LBR(Last Branch Record)功能可以獲得更佳的優(yōu)化效果。我們采用如下命令對 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 采集用的源碼完全一致，否則會干擾優(yōu)化效果。為了開啟 PGO 優(yōu)化，只需要再添加 -fprofile-sample-use=llvm.prof clang 編譯參數(shù)，使用該 llvm.prof 文件中的 profile 數(shù)據(jù)進(jìn)行 PGO 編譯優(yōu)化。

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

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

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

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

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

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

WPD 的嘗試

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