前言

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

我們在優(yōu)化數(shù)據(jù)面的歷程中，基于 LLVM 編譯工具鏈，圍繞 C++ Devirtualization 以及編譯優(yōu)化進行了較多探索，落地了 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）為了提供較好的抽象與可擴展性，較多使用了 C++ 的 virtual 函數(shù)，雖然這能為編寫程序帶來極大的便捷性，但是編譯后生成的機器指令中會包含大量 indirect call，每個 indirect call 都不可避免地需要進行一次動態(tài)跳轉(zhuǎn)，過多的 indirect call 會帶來如下問題：

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

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

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

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

Speculative Devirtualization 原理介紹

下面以一個例子解釋 Speculative Devirtualization 的原理，假設(shè)我們編寫了一個 Foo 的接口以及一個 FooImpl 的具體實現(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ù)的機器指令偽代碼大致如下：

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

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

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

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

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

PGO 優(yōu)化實踐

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

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

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

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

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

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

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

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

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

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

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

在編譯時，由于編譯器并不能假設(shè) a 為 true 或者 false 的概率，通常按照同樣的 block 順序輸出機器指令，偽匯編代碼如下。其中，先對參數(shù) a 進行 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 的實際執(zhí)行中，由于指令順序執(zhí)行以及 pipeline 預(yù)執(zhí)行等機制，因此，會優(yōu)先執(zhí)行當(dāng)前指令緊接著的下一條指令。上面的指令對 a_staff 是有利的，如果 a 為 true，那么整個流水線便一氣呵成，沒有跳轉(zhuǎn)的開銷；相反的，指令對 b_staff 不利，如果 a 為 false，那么 pipeline 中先前預(yù)執(zhí)行的 a_staff 計算則會被作廢，轉(zhuǎn)而需要從 .else 處的重新加載指令，并重新執(zhí)行 b_staff，這些消耗會顯著降低指令的執(zhí)行性能。

從上面的分析可以得出，如果恰好在實際運行中，a 為 true 的概率比較大，那么該代碼片段會比較高效，反之則低效。借助對程序運行期的 profile 數(shù)據(jù)進行采集，則可以得到上面的分支判斷中，實際走 if 分支和走 else 分支的次數(shù)。借助該統(tǒng)計數(shù)據(jù)，在 PGO 編譯中，若走 else 分支的概率較大，編譯器便可以對輸出的機器指令進行調(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 運行期的 profile 數(shù)據(jù)，首先需要進行正常的最優(yōu)編譯并生成二進制。為了避免二進制中同名 static 函數(shù)符號的歧義，以及區(qū)分同一行 C++ 代碼中多個函數(shù)的調(diào)用，提高 PGO 的優(yōu)化效果，我們需要新增
-funique-internal-linkage-names 和
-fdebug-info-for-profiling 這兩個 clang 編譯參數(shù)，此外，還需要增加 -Wl,--no-rosegment 鏈接參數(shù)，否則 linux-perf 收集到的 perf 數(shù)據(jù)無法通過 AutoFDO 轉(zhuǎn)換工具轉(zhuǎn)換成 LLVM 所需的格式。

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

perf record -p <pid> -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 <binary> --out=llvm.prof

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

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

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

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

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

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

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

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

WPD 的嘗試

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