標籤：

如果沒有PGO，JIT 編譯相比AOT 編譯有哪些優勢？

01-05

據說JIT 編譯可以拿到比AOT編譯更多的運行時信息。但是如果一個純JIT（第一次執行時編譯，無profiling feedback）的話具體可以拿到哪些AOT拿不到的信息呢？

我知道有一點：JIT 可以拿到運行環境的硬體信息，從而做指令集的定向優化，而不是AOT中兼容最低配置。

除此之外還有嗎？

首先，討論這個問題一定要確定我們討論的主題是「JIT可以比AOT在哪些方面做得更好」，而不要陷入「JIT編譯出來的代碼的整體效果怎樣就比AOT編譯要更好」的大坑。前者只是一些局部點的討論，而後者則要牽扯更多方面。

後者的話，AOT編譯最大的優勢就是有機會不計成本（資源開銷）地做代碼分析和優化，使得它可以承受更重量級的優化而得到更好的代碼。而JIT就算是有adaptive dynamic compilation / tiered compilation來分擔初始開銷，畢竟是在應用運行的同時來編譯，做什麼分析/優化都要考慮時間和空間開銷，所以跟傳統AOT的強項沒辦法硬碰硬。

=======================================

JIT+PGO的情況

那麼回到正題，JIT能做些什麼有趣的事情。

題主一上來先把JIT最擅長的方面給禁了——不讓JIT搭配PGO做優化。現實中JIT編譯最大的優勢就是可以通過FDO（feedback-directed optimization）或者叫PGO（profile-guided optimization）來做優化，這樣可以以少量的初始運行時開銷，換取一些本來要通過重量級靜態分析才可以得到、或者靜態分析根本無法得到的一些運行時信息，然後基於它來做優化就可以事半功倍。

先放個傳送門來講解一些相關名詞的關係：JIT編譯，動態編譯與自適應動態編譯 - 編程語言與高級語言虛擬機雜談（仮） - 知乎專欄

JIT會做的典型的FDO / PGO可以有這麼一些點：

  1. type-feedback optimization：主要針對多態的面向對象程序來做優化。根據profile收集到的receiver type信息來把原本多態的虛方法調用點（virtual method call site）或屬性訪問點（property access site）根據類型來去虛化（devirtualize）。

  2. single-value profiling：這個相對少見一些。它的思路是有些參數、函數返回值可能在一次運行中只會遇到一個具體值。如果是這樣的話可以把那個具體值給記錄下來，然後在JIT編譯時把它當作常量來做優化，於是常見的常量相關優化（常量摺疊、條件常量傳播等）就可以針對一個靜態意義上本來不是常量的值來做了。
  3. branch-profile-based code scheduling：主要目的是把「熱」的（頻繁執行的）代碼路徑集中放在一起，而把「冷」的（不頻繁執行的）代碼路徑放到別的地方。AOT編譯的話常常會利用一些靜態的啟發條件來猜測哪些路徑比較熱，或者讓用戶指定哪些路徑比較熱（例如 likely() / unlikely() 宏），而JIT搭配PGO的話可以有比較準確的路徑熱度信息，對應可以做的優化也就更吻合實際執行情況，於是效果會更好。
  4. profile-guided inlining heuristics：根據profile信息得知函數調用點的熱度，從而影響內聯決策——對某個調用點，到底值不值得把目標函數內聯進來。
  5. implicit exception：隱式異常，例如Java / C#的空指針異常檢查，又例如Java / C#的除以零檢查。這些異常如果在某塊代碼里從來沒有發生過，就可以用更快的方式來實現，而不必生成顯式檢查代碼。但如果在某塊代碼經常發生這種異常，則顯式檢查會更快。更多討論請跳傳送門：如何評價《王垠：C 編譯器優化過程中的 Bug》？

上面的(1)和(2)在JIT+PGO的場景中，生成的代碼常常會帶有條件判斷（guard）來檢查運行時實際遇到的值是否還跟profile得到的信息一致，只有在一致的時侯才執行優化的代碼，否則執行後備（fallback）的不優化代碼。

當然這樣的優化還是結合一些靜態分析效果更佳。

例如說，對下面的Java偽代碼，假設有介面IFoo和一個實現了該介面的類Foo。

void func(IFoo obj) {
obj.bar(); // call site 1
obj.bar(); // call site 2
}

如果只應用上述(1)的type-feedback optimization，我們可能會發現profile記錄下來兩個bar()的調用點的receiver type都是Foo，於是一個很傻的JIT可能會生成這樣的代碼：

void func(IFoo obj) {
// call site 1
if (obj.klass == Foo) { // guard
Foo.bar(obj); // devirtualized
} else {
obj.bar(); // virtual call as fallback
}

// call site 2
if (obj.klass == Foo) { // guard
Foo.bar(obj); // devirtualized
} else {
obj.bar(); // virtual call as fallback
}
}

這樣的JIT雖然應用了profile信息來做優化，但是沒有對代碼做足夠靜態分析和優化，沒有發現其實兩個調用點都是一樣的引用，類型肯定相同。

而一個沒那麼傻的JIT編譯器可能會生成這樣的代碼，把guard產生的類型信息傳播出去：

void func(IFoo obj) {
if (obj.klass == Foo) { // guard
Foo.bar(obj); // devirtualized call site 1
Foo.bar(obj); // devirtualized call site 2
} else {
obj.bar(); // virtual call as fallback
obj.bar(); // virtual call as fallback
}
}

這是假設沒有足夠靜態信息來判斷obj運行時的實際類型的情況。

那麼稍微改變一下例子，變成這樣：

void func() {
IFoo obj = new Foo();
obj.bar();
obj.bar();
}

此時只使用type-feedback optimization的比較傻的JIT編譯器還是會生成跟前面類似的代碼：

void func() {
IFoo obj = new Foo();

// call site 1
if (obj.klass == Foo) { // guard
Foo.bar(obj); // devirtualized
} else {
obj.bar(); // virtual call as fallback
}

// call site 2
if (obj.klass == Foo) { // guard
Foo.bar(obj); // devirtualized
} else {
obj.bar(); // virtual call as fallback
}
}

而一個做了類型信息傳播的JIT編譯器則會發現new Foo()是一個可以確定準確類型的表達式，把這個信息傳播出去就可以確定後面兩個bar()的調用點都肯定會調用Foo.bar()。於是它可以忽略收集到的profile信息，優先藉助靜態分析/優化的結果而生成這樣的代碼：

void func(IFoo obj) {
Foo obj = new Foo();
Foo.bar(obj); // devirtualized call site 1
Foo.bar(obj); // devirtualized call site 2
}

一個做了足夠優化的AOT編譯器會對這個例子生成跟後者一模一樣的代碼，而不需要藉助profile信息。

舉這兩組例子只是想提醒一下讀這篇回答的同學們，不是所有「JIT」的優化程度都一樣，不要對JIT的行為「想當然」。Profile信息對程序優化的影響會收到輸入程序的實際情況的影響，也會受到搭配的編譯器自身所做的優化的影響。

很多現實中的JIT都是在優化開銷和目標性能之間的權衡，設計出發點的差異會導致實現的巨大不同。

=======================================

JIT不搭配PGO的情況

前戲結束，終於來到正餐。

其實JIT編譯（或者寬泛而言，「動態生成代碼」（dynamic code generation））最大的優勢就是利用運行時信息。運行時信息有很多種，並不是所有都算「profile」；而對運行時信息的使用也非常多樣化。同學們一定要有open mind來發揮自己的想像力 &>_&<

然而同時值得注意的是，有不少JIT編譯器之所以很難被改造為AOT編譯器使用，很大一部分原因就來自於它們在設計之初就只考慮被用作JIT編譯器，無條件內嵌或者說依賴了很多運行時的值，如果要改造為AOT編譯器使用則需要把這些根深蒂固的依賴都挖掉，工作量常常會大得讓人放棄orz

讓我先放個簡單列表，回頭有空再補充更多內容或者展開其中一些來講解。

  1. 可以把許多運行時才確定的地址 / 指針值當作常量。

  2. 可以針對程序一次啟動所配置的參數而生成最合適的代碼，減少運行時條件判斷。
  3. 可以針對當前運行的機器的實際狀況生成最合適的機器碼。比針對通用情況編譯的AOT編譯結果更優，而比包含運行時檢查機器功能（例如用cpuid檢測某些指令是否可用）的AOT編譯結果減少運行時檢查開銷。
  4. 針對動態鏈接的場景，可以跨越動態鏈接的模塊邊界做優化（例如跨越模塊邊界將函數調用內聯）。
  5. 可以選擇性編譯頻繁執行的代碼，減少編譯後的代碼的內存開銷，特別在諸如資源極其受限的嵌入式場景有特殊用法。
  6. 有些功能可能靜態編譯的計算量太大，而放在運行時根據具體值來JIT編譯則可以只對特定情況計算，很好地達到性能與開銷的平衡。
  7. 常常會允許做code patching，針對代碼實際運行遇到的值做特化，並且在實際的值發生變化時跟隨做調整。
  8. 有可能運行動態對代碼做instrumentation，並且根據收益和開銷來動態調整instrumentation的詳細程度。在收集到足夠信息後可以動態撤銷instrumentation代碼來恢復到原有性能。
  9. 最後但其實可能是最重要的，是JIT編譯常常可以做「激進的預測性優化」（aggressive speculative optimization），在預測錯誤時可以靈活地fallback到安全的不那麼優化的代碼上。
    1. 例如說一個方法可以只編譯「執行過的部分」或者「預測可能會執行的部分」。如果實際執行到之前沒編譯的路徑上，那就當場再編譯就是了。
    2. 例如說在支持動態載入代碼的場景中，靜態編譯只能以open-world assumption來做保守優化，而JIT編譯可以做closed-world assumption做激進的優化，並且當動態載入了新代碼使之前的預測不再準確時，拋棄之前編譯的代碼而重新編譯。

---------------------------------------------

對上面的(1)，舉幾個例子。

例如說微軟的CLR的JIT編譯器，目前是對一個方法只能正常JIT編譯一次的，所以用不上「PGO」。但它可以利用許多運行時的值，例如說這樣：

void Bar() {
}

void Foo() {
Bar();
}

void Goo() {
Bar();
}

void Main() {
Foo();
Goo();
}

假如程序從Main()方法開始執行，全部沒有被NGen，那麼走的就是正常的「第一次被調用時才JIT編譯」的路徑。於是，假如沒有發生內聯，JIT編譯的順序是調用樹的深度優先遍歷：

Main() -&> Foo() -&> Bar() -&> Goo()

在編譯Main()時，它要調用的Foo()與Goo()尚未被編譯，其編譯後方法入口地址尚未知，所以Main()里對它們的調用就會生成對它們的prestub的調用代碼，用於觸發JIT編譯並把調用點patch到對編譯好的方法入口地址的直接調用。放個傳送門：什麼是樁代碼（Stub）？ - RednaxelaFX 的回答 - 知乎。編譯Foo()的時候也是類似，Bar()尚未被編譯所以只能先生成對prestub的調用，等prestub被調用的時候觸發JIT編譯並把調用點patch為直接調用。

而JIT編譯Goo()時，它要調用的Bar()方法已經被JIT編譯好了，其方法入口地址是已知的，所以可以生成直接調用其方法入口地址的代碼。

無論Main()、Foo()、Goo()、Bar()分別在哪個「模塊」（.NET Assembly意義上）中，它們在運行時都是被混在一起的，跨模塊調用不會有額外開銷，不會因為Foo()與Bar()不在一個模塊而導致該調用要經過諸如GOT結構來做間接調用。

然後，例如說在HotSpot JVM中，「常量對象」（例如Java對象的Klass、例如說String常量等）的引用值可以被直接嵌入到生成的代碼中。這些地址也是只有運行時才能確定的。

再例如，如果有一個帶JIT帶GC的運行時環境，GC使用連續的虛擬地址空間並且分兩代，那麼要檢查一個引用指向的對象是在young generation還是在old generation，只要看該引用值是否小於兩代之間的分界地址即可。這個地址顯然也是一個運行時值，用JIT的話就可以很輕鬆地把地址內嵌到生成的代碼中，而AOT編譯的話常常需要為此生成一個內存讀操作。

---------------------------------------------

對上面的(2)，舉點例子。

例如說，HotSpot JVM的解釋器其實是「JIT」出來的——是在VM啟動的過程中動態生成出來的。根據某次啟動所配置的參數，例如說是否要在解釋器中做profiling，它可以選擇性生成代碼，完全不生成該次運行所不需要的代碼，從而讓解釋器代碼在內存中的布局更加緊湊，提高代碼局部性。

---------------------------------------------

對上面的(3)…就不舉例子了。這個可能是被討論得最多的場景，似乎大家都知道這是什麼意思。

---------------------------------------------

對上面的(4)，前面舉的CLR的例子已經涉及一點。但比起能生成「直接調用」，更有趣的是JIT編譯通常可以無視模塊邊界而實現跨越模塊的函數調用內聯。

還是用CLR那個例子的話，假如那是一個用C++實現的程序，而Main()、Foo()、Goo()、Bar()四個函數各自在自己的exe或dll里，那它們之間的調用就通常無法被內聯。

而對CLR而言，如果這是一個C#實現的程序，那這幾個方法從什麼模塊而來根本沒關係，照樣都可以內聯。

---------------------------------------------

對上面的(5)，可以舉的有趣例子實在太多，而且應用場景可以相當不同。

以C++模版與C#的泛型實例化為例，一個AOT編譯的C++程序，靜態編譯時編譯器看到了某個模版類/函數的哪些實例化，就必須把該實例化版本的代碼和元數據都生成出來，而假如實際運行只用到了其中的很少數，那就很浪費。

而C#程序在CLR上運行的話，一個泛型類型只有運行時實際用到的實例化版本才會生成對應的代碼和元數據，其中代碼部分還有機會共享，內存開銷就小很多。

而且更有趣的是這樣還可以允許運行時動態創建（反射創建）新的實例化版本。C++的模版在AOT編譯的模型下就做不到這點。

再舉一個例子，看看低端的Java ME的場景。

這種場景的設備可能只有很少內存和持久存儲（RAM和ROM都少），用起來得非常節省。Java位元組碼其實可以看作程序的「壓縮形式」，如果編譯到機器碼的話，所佔空間有可能要膨脹3倍到10倍。如果一個Java應用的所有代碼都被AOT編譯到機器碼，它可能就根本沒辦法裝到設備（ROM）上了。

所以這種場景下Java程序適合以位元組碼的形式持久存儲於ROM上，只佔用很少ROM空間，然後像Monty VM（也叫CLDC HotSpot Implementation）的JVM實現 ，會配置一個非常小的JIT code cache，其中只保留最近執行最頻繁的JIT編譯的代碼，其它代碼都解釋執行——假如觸發了新的JIT編譯而code cache已用滿，則拋棄掉最冷的代碼來讓出空間給新代碼用。這樣就在內存佔有與性能之間達成了一個動態平衡。

「只編譯頻繁執行的路徑」的思路下還有trace-based compilation。這裡就先不展開說了。

---------------------------------------------

針對上面的(6)，簡單舉倆例子。

第一個例子是Sun Labs以前研發過的Fortress語言，它的編譯器實現就混合使用了靜態編譯與動態代碼生成技術——雖說動態生成的是Java位元組碼。這也算是一種形式的JIT。

參考Christine Flood大媽在JVM Language Summit 2011上做的一個Fortress演講提到的一點：

  • Interface Injection
    • Because recursive types could potentially require an infinite
      number of methods the entire type hierarchy can"t be generated at
      compile time, and some classes must be generated on demand at
      run time. Interface injection would save us a whole lot of
      complicated dispatch code.

Fortress語言的recursive type設計使得有些類型根本無法在靜態編譯時完全生成出來（不然編譯器自己就停不了機了orz），所以有些類型就乾脆等到運行時再根據實際使用狀態動態生成出來。

第二個例子是微軟CLR的GC大佬之Patrick Dussud在一個訪談中提到過，他剛工作的時候參與過一個項目，是一個APL語言的實現的runtime優化，其中就涉及JIT編譯技術。

例如說APL的? (Iota) 函數可以生成從1到n的整數數列，而如果對它的結果 + 1的話，就相當於對這個數列的所有元素加1。當時一般的APL runtime實現會在執行iota時一開始就一口氣生成出整個從1到n的數組放在內存里，然後執行加1就真的每個元素都加1。而Patrick參與的項目則嘗試把這些操作「符號化」（symbolic representation + lazy computation），在不需要使用實際值的時候只把操作記錄下來，等到真的要用其中的一些值時才materialize。這個過程中，如果materialize時發現計算是很簡單的就解釋執行之，如果發現計算是複雜計算則動態生成特化的計算代碼（JIT編譯）然後再執行之。

傳送門：Patrick Dussud: Managing Garbage Collection | Behind The Code | Channel 9（從10:00開始的一小段）

---------------------------------------------

針對上面的(7)，code patching，舉點小例子。

例如說，CLRv2對介面方法做所謂「virtual stub dispatch」（VSD），其實是一個monomorphic inline cache call。它會在第一次執行的時候記錄下當時傳入的receiver type，將自身特化成類似這樣的形式：

if (obj.MethodTable == expected_MT_of_Foo) {
call Foo.bar(); // direct call, fastest
} else {
failure_counter++;
if (failure_counter &< 1000) { lookup_target_and_call(); // reflective lookup, slowest } else { patch_self_to_generic(); // patch to generic version, mediocre } }

於是後續調用如果還是對同一receiver type的參數做，就可以走快速路徑做直接調用，而如果遇到了其它receiver type則記錄下失敗次數，當失敗次數超過閾值時把自己patch成泛化的慢速形式。

這種場景雖然有feedback，但是並不需要完善的profile機制，而JIT編譯器自身也不使用profile信息來生成特化代碼，而是讓runtime的別的一些機制，例如stub管理之類來管理跟隨feedback而調整代碼，所以不算PGO編譯。

再舉一個例子。HotSpot VM的Client Compiler（C1）允許對若干類型的場景生成佔位代碼，等到運行時有足夠信息的時候再填進去。

例如說，遇到對尚未載入的類的欄位訪問，因為還不知道欄位所在的偏移量應該是多少，所以還無法生成最終的完整代碼。此時C1可以生成一些nop以及一個runtime call來佔位，等到第一次執行到那個地方的時候就調用進那個runtime call。進到runtime，此時這裡涉及的類肯定以及載入好了，於是查詢好相關的偏移量信息之後，就把原本佔位用的指令patch成實際的欄位訪問代碼。

這裡還有個有趣的細節：如果調用進runtime，發現這個欄位是個常規欄位，就按照上面的流程工作即可。而如果發現這個欄位是個volatile欄位，那就意味著當前方法的C1編譯版代碼在編譯的時候可能沒有考慮足夠重排序相關限制，所以必須要拋棄掉這個版本的編譯代碼，然後重新讓C1再編譯一次。

---------------------------------------------

針對上面的(8)，可以參考CLR的ReJIT功能。

先放倆傳送門：

  • CLR 4.5: David Broman - Inside Re-JIT | Going Deep | Channel 9

  • ReJIT: A How-To Guide

---------------------------------------------

針對上面的(9)，這就好玩了。非常非常好玩。

現代高性能JVM的JIT編譯器非常依賴於這方面的優化。所謂assumption-based speculative optimization就是這種。

先放個傳送門佔位：HotSpot VM有沒有對invokeinterface指令的方法表搜索進行優化？

回頭再展開舉例。

補充一下 @vczh 的回答

AOT面臨的一個無法避免的問題就是判斷哪些代碼會被用到

一個例子是泛型的虛函數，如果發現了對該虛函數的調用，那麼其所有override都是可能用到的，因此需要AOT編譯。

如：C#中最典型的ToString()即為object級別的虛方法，而在framework內有著幾乎一定會調用到的「拿到object-調用ToString」操作，於是乎所有類型的ToString方法都必須被AOT——儘管不少類型你根本不會對其執行ToString。

第二個例子是反射

.Net Native在編譯的時候，需要你給一個配置文件，分別對每個類型（或者每組類型）配置你需要什麼級別的反射調用——僅名稱，構造器，序列化，方法調用：為沒用到的反射操作生成支持也是一件有額外開銷的事情。

（當然，強行做所有代碼路徑的全掃描也能判別，不過這個開銷已經巨大到無法接受了）

AOT支持C#的模板虛函數需要比JIT預先生成大量的可能到時候根本不會運行到的代碼。

也不一定需要真的獲取更多信息才能做優化。比如動態語言，JIT可以做一些假設、然後做specialisation，生成簡潔高效的代碼。運行時假設不成立再fallback回去，執行slow path。另外JIT還可以做code patching，又允許了一些其他優化。

推薦閱讀：

※如何從粗通一門編程語言到精通一門？
※哪一種計算機語言最適合入門？是C語言嗎？可是我覺得指針難死了！？
※各位覺得主流編程語言中哪個編程語言最容易學習？
※有什麼好的 Haskell 中文書籍？
※關於C語言中漢字排序的問題？

TAG:編程語言 | Java虛擬機JVM | 即時編譯JIT | 編譯原理 | 編譯器 |