前言

字節跳動在內部大規模落地了 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 的具體實現，如下所示：

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();
}

經過編譯后，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)
    // do a_staff...
else
    // do b_staff...
return

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

test a, a
je   .else  ; jump if a is false
.if:
; do a staff...
ret
.else:
; do b staff...
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 更有利。

test a, a
jne  .if  ; jump if a is true
.else:
; do b staff...
ret
.if:
; do a staff...
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 數據采集。

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

完成 perf 數據采集后，使用 AutoFDO 工具（
https://github.com/google/autofdo）將 perf 數據轉換成 LLVM profile 格式。

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

帶 PGO 的優化編譯

得到 profile 數據后，即可進行最后一步帶 PGO 優化的重編譯步驟，需要注意的是，該次編譯的源碼必須和之前 profile 采集用的源碼完全一致，否則會干擾優化效果。為了開啟 PGO 優化，只需要再添加 -fprofile-sample-use=llvm.prof clang 編譯參數，使用該 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 函數生效，因此在現階段還無法帶來顯著的性能收益。