从 JIT 编译看 Runtime 的过去与未来
作者簡介
常開顏
中國科學(xué)院計算技術(shù)研究所直博生，研究方向為硬件編程語言、編譯技術(shù)。
如果讀者想了解更多有關(guān)?Runtime?相關(guān)的技術(shù)內(nèi)容，歡迎加入編程語言社區(qū) SIG-Runtime。
加入方式：文末有小助手微信，添加并備注加入 SIG-Runtime。
# 編譯器是什么 #
編程語言處理器可以分為三類，它們之間的關(guān)系用一句著名的話說就是：編譯器是特化的解釋器（a compiler is a specialized interpreter）[1]。
-
編譯器 Compiler?能夠給定一種語言的程序，輸出另一種語言里的等價程序（編譯過程會生成新的程序）
-
解釋器 Interpreter?能夠給定一個程序和程序的輸入，計算程序的結(jié)果（解釋過程不生成新的程序）
-
特化器 Specializer?能夠給定一個程序一些提前知道的輸入，創(chuàng)建一個僅需要剩下輸入的等價（但更高效）的程序
注：：即計算機(jī)實(shí)際執(zhí)行的語言
作為一篇科普性質(zhì)的綜述類文章，本文不打算挖掘深度，而是注重廣度，聚焦于提供一個 Runtime 的領(lǐng)域藍(lán)圖。就像 J.R.R.Tolkien 所說："你必須有一張地圖，不管多么粗糙。否則你會四處游蕩。(You must have a map, no matter how rough. Otherwise you wander all over the place.)"
# Runtime 是什么 #
Runtime?包括了?動態(tài)程序的相關(guān)理論?和?程序運(yùn)行時的支持系統(tǒng)：
-
動態(tài)程序的相關(guān)理論?指程序動態(tài)特性相關(guān)的編程語言理論，比如動態(tài)程序驗證，運(yùn)行時并發(fā)程序的動態(tài)驗證等；
-
運(yùn)行時支持系統(tǒng) runtime system?指保障程序在運(yùn)行時正確執(zhí)行的支持系統(tǒng)，比如垃圾回收系統(tǒng)、即時編譯系統(tǒng)、處理器系統(tǒng)等。
由于編程語言的運(yùn)行不僅需要軟件系統(tǒng)的支撐，也需要硬件系統(tǒng)的支撐，因此 Runtime 涉及了軟件和硬件層次的許多交叉方面。此外，Runtime 不僅與通用編程語言有關(guān)，也與領(lǐng)域特定語言有關(guān)。在近來興起的深度學(xué)習(xí)編譯器中，許多框架都用到了即時編譯系統(tǒng)，比如 PyTorch。在云計算興起的時代，在可編程網(wǎng)絡(luò)領(lǐng)域也廣泛用到了編程語言作為接口對設(shè)備進(jìn)行配置，比如阿里云太玄 OS 的跨平臺編程語言和編譯器 Lyra?[2]。
考慮到 Runtime 是一個涉及編程語言理論、體系結(jié)構(gòu)、程序分析等的綜合領(lǐng)域，本文按照應(yīng)用領(lǐng)域把相關(guān)的研究大致分為以下六個領(lǐng)域（如下圖所示），下面對每一個領(lǐng)域做說明。
Runtime 應(yīng)用領(lǐng)域概覽
編譯器運(yùn)行時
編譯器運(yùn)行時屬于傳統(tǒng)的程序運(yùn)行時支持系統(tǒng)，包括了通用語言虛擬機(jī)及其 JIT 編譯，比如：JVM、V8 等。
在傳統(tǒng)的編譯器運(yùn)行時中，一個很大的部分是?垃圾回收技術(shù)（Garbage Collection），由此衍生出了?三色標(biāo)記法、標(biāo)記清掃法、引用計數(shù)法?等不同的垃圾回收方法。
其他和編程語言特性相關(guān)的特性還包括了反射、虛函數(shù)等。
涉及到的其他程序運(yùn)行時的行為還有?并發(fā)?和?事務(wù)。
同時編譯器運(yùn)行時也涵蓋了領(lǐng)域特定語言（Domain Specific Language）及其 JIT 編譯。領(lǐng)域特定語言是專用于某一個領(lǐng)域的編程語言，分為嵌入式領(lǐng)域特定語言和外部領(lǐng)域特定語言，嵌入式領(lǐng)域特定語言包括 Halide、TVM、Tensorflow、JAX 等，外部領(lǐng)域特定語言包括：云原生編程語言 Ballerina，硬件描述語言 Verilog、VHDL。
動態(tài)程序驗證
動態(tài)程序驗證與靜態(tài)驗證基于不同的系統(tǒng)。靜態(tài)程序的驗證一般是從作用域、類型等抽象特性上驗證程序的語義是否符合規(guī)范，而動態(tài)驗證則更為靈活。
從理論上講，可以歸結(jié)為?動態(tài)語義的驗證，比如采用?霍爾邏輯（Hoare Logic）?驗證數(shù)據(jù)結(jié)構(gòu)的正確性，驗證循環(huán)的正確性；還可以使用?混合符號執(zhí)行（Concolic Testing）?來測試程序，縮減符號執(zhí)行造成的搜索空間爆炸的問題，比如使用混合符號執(zhí)行 fuzzing。
從實(shí)踐上講，在 JVM 中，類的加載階段需要進(jìn)行驗證，比如采用變量類型執(zhí)行的方式，把變量的類型壓入虛擬機(jī)棧，在類型執(zhí)行時判斷棧頂類型是否匹配。
動態(tài)程序分析
動態(tài)程序分析是對程序的動態(tài)行為進(jìn)行分析，從而定位程序故障、進(jìn)行調(diào)試或是進(jìn)行更為激進(jìn)的優(yōu)化。在調(diào)試模式中，LLVM 采用?程序插樁?的方法，在局部變量的前后插樁方便調(diào)試時查看它們的值。LLVM 也采用了其他方法來加快程序的運(yùn)行速度，比如收集性能制導(dǎo)優(yōu)化的 profile，在每個分支指令后標(biāo)注類似?!prof !0?的標(biāo)識插入分支相對可能執(zhí)行次數(shù)的元信息來輔助提高程序執(zhí)行速度。還可以在程序運(yùn)行時分析存儲的讀寫序列發(fā)現(xiàn)訪存沖突問題。
動態(tài)程序合成
動態(tài)程序的合成可以分為兩類，一種是?交互式程序合成，比如微軟在 Excel 中的自動填充技術(shù)，可以根據(jù)已經(jīng)存在的單元格數(shù)據(jù)提取相關(guān)信息，與用戶輸入的數(shù)據(jù)進(jìn)行對比，填充空白的單元格。第二種是收集運(yùn)行時信息的?程序合成?技術(shù)，比如 TVM 的自動調(diào)度方案，采用運(yùn)行時的性能模型合成高效率的代碼調(diào)度?[3]。
體系結(jié)構(gòu)優(yōu)化
編程語言與體系結(jié)構(gòu)的交互伴隨運(yùn)行過程始終，在動態(tài)編譯、并行編程和存儲系統(tǒng)方面都有體現(xiàn)。動態(tài)二進(jìn)制指令翻譯是一種與此相關(guān)的研究，把一種形式的二進(jìn)制指令翻譯為另一種形式的二進(jìn)制指令，比如使用動態(tài)二進(jìn)制翻譯的 CPU 模擬器 Qemu。還有用于并行編程的推測調(diào)度和多線程技術(shù)，比如軟件流水技術(shù)、超標(biāo)量技術(shù)。近來興起的?非易失性存儲器（Non-Volatile Memory）?成為數(shù)據(jù)存儲領(lǐng)域新的研究載體，有研究在 Java 語言中加入與 NVM 相關(guān)的關(guān)鍵字，從編程語言的設(shè)計上方便操作新型存儲器。
集成電路設(shè)計
硬件是編程語言運(yùn)行時的核心部分，向上提供指令集作為接口。領(lǐng)域特定語言（DSL）需要領(lǐng)域特定硬件（DSA）來作為實(shí)際載體加速。DSL 加速軟件開發(fā)，DSA 加速領(lǐng)域特定語言的運(yùn)行速度是深度學(xué)習(xí)出現(xiàn)以來的新的趨勢。電子設(shè)計自動化工具作為硬件設(shè)計的重要組成部分一直是重要的組成部分。無論是傳統(tǒng)上的集成電路設(shè)計用的 Verilog、VHDL，還是后來為了方便編程演變出的 HLS 和 Pynq?[4]，都是為了加速芯片設(shè)計而產(chǎn)生的。但是近來興起的 Circt 和 XLS 沿襲了 LLVM 的思路，采用了復(fù)雜系統(tǒng)模塊化的思路，希望能夠?qū)鹘y(tǒng)集成電路設(shè)計工具解耦。
# Runtime 的過去?#
筆者在 Charles N. Fischer 所著的?Crafting a Compiler?[5]?中了解到 Runtime 的發(fā)展歷史。
編程語言設(shè)計的演變導(dǎo)致越來越復(fù)雜的運(yùn)行時存儲組織方法的產(chǎn)生。舉例來說，數(shù)組可以被分配一個單一的固定大小的內(nèi)存塊，而現(xiàn)在有一些新的編程語言，允許數(shù)組的大小在程序執(zhí)行時指定，甚至能夠根據(jù)程序的需要動態(tài)擴(kuò)展。
最初，所有的數(shù)據(jù)都是全局的，其生命周期跨越了整個程序。相應(yīng)地，所有的存儲分配也是靜態(tài)的。在翻譯過程中，一個數(shù)據(jù)對象或指令序列在程序的整個執(zhí)行過程中被簡單地放在一個固定的內(nèi)存地址上。
在 1960 年代，Lisp 和 Algol 60 語言引入了局部變量，這些局部變量（local variables）僅僅能夠在子程序（subprogram）的執(zhí)行的時候被訪問。這種特性導(dǎo)致了?棧式分配（stack allocation）?的產(chǎn)生。當(dāng)過程或者方法被調(diào)用時，新的?棧幀（frame）?被壓入運(yùn)行時棧。棧幀由為所有特定過程中的局部變量分配的空間組成。隨著過程的返回，它的棧幀被彈出，同時被局部變量占據(jù)的空間被取回。因此，僅僅是正在執(zhí)行的過程被分配了空間，而不活躍的過程不需要數(shù)據(jù)空間。這使得相比早期使用靜態(tài)分配翻譯的空間效率更高。而且，遞歸的過程會由于同一個過程不相關(guān)嵌套的活動而請求多個棧幀。
Lisp 和隨后的像 C、C++、C# 和 Java 一類的語言，使得動態(tài)分配數(shù)據(jù)能夠在運(yùn)行期間的任何時候被創(chuàng)建或者釋放。動態(tài)的數(shù)據(jù)請求堆分配（heap allocation），這使得內(nèi)存塊在程序執(zhí)行的任何時間以任何順序被分配和釋放。使用動態(tài)分配，數(shù)據(jù)對象的數(shù)目和大小不需要提前固定。每個程序的執(zhí)行能夠定制它所需要的存儲分配。
所有的存儲分配技術(shù)利用數(shù)據(jù)區(qū)域（data area）這個符號。一個數(shù)據(jù)區(qū)域是一塊被編譯器知道的存儲，這個區(qū)域具有統(tǒng)一的存儲分配的必要條件。也就是說，所有在這個數(shù)據(jù)區(qū)域上的對象共享相同的數(shù)據(jù)分配策略。一個程序的全局變量能夠組成一個數(shù)據(jù)區(qū)域。當(dāng)程序開始運(yùn)行時，所有變量的空間被分配，并且變量仍然再分配直到執(zhí)行結(jié)束。
這里給一個關(guān)于內(nèi)存布局的問題，C++ 語言里給定一個?char *?的變量指針，如何判斷這個變量是?new?動態(tài)分配的還是在棧中呢？如下面的代碼所示，我們只需要根據(jù)棧是在程序虛擬空間的頂端自頂向下生長，而堆是在棧的下方自底向下生長這一規(guī)律就可以判斷。ch?變量是局部變量，分配在棧中，故其地址一定大于堆中的變量地址。
C 語言運(yùn)行時空間分配
bool if_malloc(char *p) {char ch{};char *ch_p{&ch};if (ch_p> p) {return true;}else {return false;} }C 語言沒有垃圾回收等運(yùn)行時機(jī)制，而 C++ 語言有虛方法調(diào)用的運(yùn)行時機(jī)制，比如下面的例子中，如果傳給?fun()?的參數(shù)是?Rectangle?的指針，那么最終調(diào)用的是?Rectangle?類中的?print()?方法，而不是?Shape?類中的方法。?
class Shape { public:virtual void print() {...} }class Rectangle:public Shape { public:virtual void print() override{...} }void fun(Shape* rec) {rec->print(); }再以 Python 為例舉一個和垃圾回收有關(guān)的例子。Python 采用了?引用計數(shù)?作為主要的垃圾回收算法，同時結(jié)合了?分代收集（Generational Collection）算法。這是因為引用計數(shù)在循環(huán)引用的情況下，無法分辨出是否應(yīng)該銷毀對象，從而導(dǎo)致內(nèi)存泄漏。這時就需要顯式地調(diào)用 GC 模塊，如下所示。
import gcclass Base():def __init__(self):passc = Base() d = Base()# 出現(xiàn)循環(huán)引用 c.p = d d.p = c# 顯式執(zhí)行回收 gc.collect()# 談?wù)?JIT 編譯 #
John Aycock 發(fā)表過一篇?A Brief History of Just-In-Time?[6]?的文章，對 JIT 的歷史做了比較詳盡的講解，本文對此文進(jìn)行了解讀。
編譯器的設(shè)計涉及到很多領(lǐng)域，比如正則表達(dá)式、有限自動機(jī)等。傳統(tǒng)上，翻譯一個程序大體上可以分成兩種方法：編譯?和?解釋。編譯執(zhí)行指的是把一個程序翻譯成匯編語言，最終翻譯為更適合執(zhí)行的機(jī)器代碼。解釋執(zhí)行消除了中間的步驟，可以立即執(zhí)行。對比來講，編譯執(zhí)行的效率更高，而解釋執(zhí)行的靈活度更高。
那么?JIT 編譯?指的是什么呢？JIT 編譯（即 Just-In-Time Compile）是指程序開始執(zhí)行后的動態(tài)編譯，用以同時獲得靜態(tài)編譯執(zhí)行和動態(tài)解釋執(zhí)行的收益。
我們從幾個方面比較 JIT、編譯執(zhí)行和解釋執(zhí)行。
執(zhí)行時間上?對于直接被編譯為目標(biāo)機(jī)器可執(zhí)行的指令流而言，編譯的程序運(yùn)行更快。靜態(tài)編譯的最大優(yōu)勢就是能夠耗費(fèi)任意時間來做程序分析與優(yōu)化。而 JIT 系統(tǒng)不能引起程序執(zhí)行的暫停，因此對于 JIT 來說，編譯時間也成為了約束 JIT 最主要的因素。
程序體積上?當(dāng)語言的表示離機(jī)器代碼越高時，就意味著能夠攜帶更多的語義信息解釋執(zhí)行平均來說更小。這也是為什么解釋執(zhí)行的程序平均來說更小。
可移植性上?解釋執(zhí)行的程序還有更便攜的特性。對于像高層次的源碼或者虛擬機(jī)器碼這種機(jī)器獨(dú)立的表示而言，只有解釋器需要提供在不同機(jī)器上的實(shí)現(xiàn)，而被解釋的程序不用考慮這些。
信息獲取上?解釋器能夠訪問輸入?yún)?shù)，控制流和目標(biāo)機(jī)器特性這一類運(yùn)行時的信息。每次運(yùn)行時程序的信息都會發(fā)生變化；這些信息只有在運(yùn)行時才能夠訪問。此外，解釋器也可以收集一些在靜態(tài)分析時不好判定的程序的類型信息。
如果一個程序的表示能夠被 JIT 系統(tǒng)以包括編譯為機(jī)器碼或者解釋的任何方式執(zhí)行，就可以說這個程序是可執(zhí)行的。需要注意的是，JIT 系統(tǒng)不僅包括了翻譯的功能，也包括了加載的功能，這一點(diǎn)和傳統(tǒng)的編譯器有很大不同。JIT 編譯器運(yùn)行的時刻也很重要，當(dāng)基于熱點(diǎn)計數(shù)探測時，如果設(shè)定在方法的開始點(diǎn)進(jìn)入 JIT 后的代碼，則在方法出現(xiàn)某段時間特別長的循環(huán)時，JIT 編譯器始終無法執(zhí)行，就會是一個問題。
JIT 編譯是一種提高解釋程序性能的方法，也被稱為動態(tài)編譯。相比靜態(tài)編譯，動態(tài)編譯有很多優(yōu)勢?[7]。當(dāng)運(yùn)行 Java 或者 C# 應(yīng)用程序時，運(yùn)行時環(huán)境在程序運(yùn)行時能夠生成利于編譯器優(yōu)化性能的配置文件，即 PGO（Profile Guided Optimization）。這就可以產(chǎn)生更多的優(yōu)化代碼。關(guān)于 JIT 編譯的一些缺點(diǎn)包括啟動時的延遲和運(yùn)行時的編譯開銷。因此很多編譯器僅僅編譯那些頻繁使用的代碼。
#?JIT 編譯的歷史
我們討論的內(nèi)容不包括?自修改代碼（self-modifying code）（即程序在運(yùn)行期間（Runtime）會修改自身指令的代碼），因為基本上沒有編譯或者解釋的優(yōu)化會把這個考慮進(jìn)去。也就是說被編譯的程序自己并不知道編譯后自己的樣子。
可能進(jìn)行 JIT 編譯的點(diǎn)?[8]
## LISP
最早的 JIT 實(shí)現(xiàn)可以追溯到 John McCarthy 于 1960 年編寫的 LISP。他在 《符號表達(dá)式的遞歸函數(shù)及其機(jī)器計算》?[9]?一書中提出了?把函數(shù)編譯為機(jī)器語言?的方法，從而無需將編譯器的工作輸出到打孔卡上。另外一個關(guān)于 JIT 早期的工作可以追溯到 1966 年，密西根大學(xué)為 IBM 7090 設(shè)計的?執(zhí)行系統(tǒng)（Executive System）明確指出?匯編器（assembler）[10]?和?加載器（loader）[11]?能夠在程序執(zhí)行時被用來翻譯和加載。Thompson 在 1968 年發(fā)表在 ACM 通訊的論文?[12]?開創(chuàng)了正則表達(dá)式，可以在 QED 文本編輯器中搜索子字符串。為了加速算法，Thompson 將正則表達(dá)式編譯到 IBM 7094 機(jī)器碼。
The time-space tradeoff.
在運(yùn)行時間和空間的權(quán)衡總是 JIT 要考慮的最主要因素，如上圖所示。此外，一項 1971 年基于經(jīng)驗的研究數(shù)據(jù)表明，大多數(shù)程序會花費(fèi)大量的時間執(zhí)行很少的一段代碼。基于這兩種情況，出現(xiàn)了兩種解決方法：混合代碼（Mixed Code）?和?拋棄型編譯（Throw-Away Compiling）。
## APL: Drag-along and Beating
APL?[13]（全稱是 A Programming Language 或 Array Processing Langauge），是由 Kenneth E. Iverson 在 1962 年設(shè)計的一門面向數(shù)組計算的編程語言。Kenneth 后來因?qū)?shù)學(xué)表達(dá)式和編程語言理論的貢獻(xiàn)而獲得了 1979 年的圖靈獎。
由于 APL 語言的動態(tài)特性，大多數(shù) APL 的實(shí)現(xiàn)都是解釋性的。Abrams 在 1970 年提出?[14]?了?拖動（Drag-along）?和?跳動（Beating）?兩種 APL 實(shí)現(xiàn)的優(yōu)化策略，這兩個策略都提高了數(shù)組作為操作數(shù)的速度，其中?拖動?是從時間上優(yōu)化，跳動?是從空間上優(yōu)化。
拖動 Drag-along
拖動 Drag-along?的策略是，通過收集上下文的信息，寄希望于未來會有一個更為高效的求值方法，因此?盡可能地推遲表達(dá)式求值（expression evaluation）。這種方法又被稱為?惰性求值（lazy evaluation）。
為了更直觀地表示惰性求值，下面給出一段偽代碼。直觀來講，我們只有到?print()?語句執(zhí)行時才能夠看到程序的狀況。如果是解釋執(zhí)行就需要?c?d?e?三個臨時存儲才能夠計算。懶惰求值是指并不立即計算?c?d?e，而是直到?print()?執(zhí)行時才開始進(jìn)行上面的計算，這樣做的好處就是既優(yōu)化了信息又不影響用戶的觀察。當(dāng)執(zhí)行到?print(e)?時，惰性求值編譯器會發(fā)現(xiàn)?e=a+b+a+b+a=3*a+2*b=3*a+(b<<1)，這就極大地削弱了運(yùn)算的強(qiáng)度和訪存的數(shù)量。
let c = a + b let d = c + a + b let e = d + a print(e)跳動 Beating
跳動 Beating?通過代碼變換降低表達(dá)式求值時涉及到的數(shù)據(jù)操縱（data manipulation）的次數(shù)。具體來講，即通過將標(biāo)準(zhǔn)形式的代碼變換應(yīng)用于數(shù)組的存儲訪問函數(shù)上，將原本直接訪問的變量替換為那些可以在無需操作數(shù)組值的情況下求值的表達(dá)式。
這么說有點(diǎn)抽象，接下來我用更詳細(xì)地例子解釋 beating。假設(shè)，在 C 語言里訪問數(shù)組都是用?A[i]?這種方式，并且我們已經(jīng)知道了數(shù)組的數(shù)據(jù)布局。但如果想要從二維數(shù)組?A?得到它的轉(zhuǎn)置數(shù)組?B，就需要做一次拷貝。Beating 的思想是，不直接使用存儲（storage）來描述，而是增加一個中間層?數(shù)據(jù)描述子（data-descriptor），用來表示數(shù)據(jù)訪問的順序和范圍等。在加入數(shù)據(jù)描述子后，對數(shù)組的轉(zhuǎn)置等操作就不需要數(shù)據(jù)移動（Data movement）了。如果需要新的變換，只需要在數(shù)據(jù)描述子上變換，而不需要在存儲上變換，從而新的描述子和原來的描述子共享原始的數(shù)據(jù) owner。
為了更清楚地說明中間層數(shù)據(jù)描述子，給出下面針對整數(shù)數(shù)組描述子的偽代碼描述。假設(shè)我們需要反轉(zhuǎn)線性表，我們無需逐個讀取線性表中的數(shù)據(jù)，這會耗費(fèi) O(N) 的時間復(fù)雜度，而只需要在數(shù)據(jù)描述子上重新賦值?begin?和?end，這樣時間復(fù)雜度僅需 O(1)。
/* 轉(zhuǎn)置數(shù)據(jù)描述 */ struct reverse_manipulator {int* data_array;int length;iterator begin; // 初始化為 data_array + length - 1iterator end; // 初始化為 data_array }/* 正向數(shù)據(jù)描述 */ struct data_manipulator {int* data_array;int length;iterator begin; // 初始化為 data_arrayiterator end; // 初始化為 data_array + length - 1 }APL 實(shí)現(xiàn)
Abrams 設(shè)計的 APL Machine 由兩個共享相同內(nèi)存和寄存器的獨(dú)立 JIT 編譯器組成。D-machine 應(yīng)用跳動和拖動來推遲程序的求值，然后由 E-machine 進(jìn)行求值。主要的機(jī)器寄存器是棧區(qū)（stacks），程序會被組織為邏輯段。Abrams 的工作使得為高級語言提供硬件支持變得流行。對 APL 語言有興趣的可以訪問 TryAPL：https://tryapl.org/
由于 Abrams 設(shè)計的?APL Machine?動態(tài)性很強(qiáng)，其類型和數(shù)據(jù)對象的屬性直到運(yùn)行時才能得知，因此這兩種方法與 JIT 編譯相關(guān)。懶惰求值技術(shù)在一些編譯器里得到了應(yīng)用，比如清華的即時編譯深度學(xué)習(xí)框架 Jittor、函數(shù)式語言 Haskell 等。然而跳動（beating）技術(shù)現(xiàn)在還沒有得到大規(guī)模的應(yīng)用，當(dāng)前業(yè)界與這種思想比較相似的就是為了降低顯存而設(shè)計的?重計算方法。
后來，Ronald L. Johnston 基于 Abrams 的 Drag-along 和 Beating 為 APL 實(shí)現(xiàn)了一個動態(tài)增量編譯器 APL\3000?[15]，是 JIT 編譯的一個早期例子。APL 實(shí)現(xiàn)的設(shè)計思想對今天的編譯器設(shè)計，尤其是數(shù)據(jù)密集型的編譯器設(shè)計仍然有很大的啟發(fā)性意義。
## Mixed Code, Throw-Away Code, and BASIC
混合代碼 Mixed Code?即把程序?qū)崿F(xiàn)為?本地代碼（Native code）和?解釋代碼（Interpreted code）的混合形式。這種方法在 1973 年被 Dakin 和 Poole?[16]?以及 Dawson?[17]?分別提出。程序中被頻繁執(zhí)行的代碼會被實(shí)現(xiàn)為本地代碼，而不頻繁執(zhí)行的部分會被解釋執(zhí)行，以此希望在產(chǎn)生很少內(nèi)存占用的同時對速度幾乎不產(chǎn)生影響。這種實(shí)現(xiàn)方式考慮的都是細(xì)粒度的混合（舉個反例，程序是解釋執(zhí)行，而使用的庫是本地代碼，這種就不算 Mixed Code）。
為了更直觀地表示混合代碼執(zhí)行，下面寫一段偽代碼。
if (current_method.can_jit == true) {native_code = load_native_code(current_method);native_code(param); } else {virtual_pc = current_method.getEntry();run(virtual_pc); }偽代碼的第一段?if?語句表明如果虛擬機(jī)判斷這個方法可以 JIT 執(zhí)行，它會動態(tài)加載已經(jīng)編譯好的代碼，然后執(zhí)行這一段本地代碼。否則就進(jìn)行解釋執(zhí)行，獲得要執(zhí)行方法的首指令位置，然后解釋執(zhí)行。
混合代碼方法自 Pittman 1987 年提出了?自定義解釋器（Customizing the interpreter）?[18]?后迎來了重要轉(zhuǎn)折。與原本在程序中混合本地代碼不同的是，自定義解釋器將本地代碼表示為一種特殊的虛擬機(jī)器指令，然后程序整體被編譯成這種虛擬機(jī)器指令。
混合代碼的基本思想（即在不同類型的可執(zhí)行代碼間切換）仍然在后來的 JIT 系統(tǒng)中被廣泛使用。但在當(dāng)時的年代，同時將編譯器和解釋器保留在內(nèi)存中成本太高。除此之外，即使假設(shè)大多數(shù)代碼會在解釋器和編譯器之間共享，仍然會需要維護(hù)兩部分行為上等價但完全不相關(guān)的代碼（即解釋器與編譯器的代碼生成器）。
一部分人認(rèn)為?部分求值（Partial Evaluation）?或?程序特化（Program Specialization）?從某種程度上講是似是而非的，因為一個編譯器可以被看作是一個特殊的解釋器?[19]。然而部分求值技術(shù)現(xiàn)在沒有廣泛傳播。部分求值 / 程序特化?[20]，即在編譯時預(yù)先對一部分代碼進(jìn)行計算，在運(yùn)行時對代碼做特化（specialize），從而生成運(yùn)行速度比原始程序更快的新程序。
下面以一段偽代碼為例解釋（運(yùn)行時）程序特化。原始代碼在運(yùn)行時會發(fā)現(xiàn)?d?是不變量，因此會被特化為下面的代碼。鑒于在運(yùn)行時我們可以獲得更多的信息，因此可以對程序進(jìn)行更多的優(yōu)化。運(yùn)行時的特化與模板中編譯時特化在形式上相似，針對的階段不同。
/* 原始的函數(shù) */ void func(int a, int b, int c, int d) {... } /* 運(yùn)行時，如果發(fā)現(xiàn)不變量，經(jīng)過特化的函數(shù) */ void func(int a, int b, int c, 5) {... }因此，拋棄型編譯?[21]?作為一個純粹的空間優(yōu)化技術(shù)被提出。與靜態(tài)編譯不同，拋棄型編譯只在有需要的時候?qū)Σ糠殖绦騽討B(tài)編譯。當(dāng)內(nèi)存耗盡時，一些或者所有已被編譯好的代碼可能被扔掉，如果有必要，這些代碼將在之后重新生成。
下面使用偽代碼解釋拋棄型編譯的異步過程。當(dāng)方法被調(diào)用時，檢查是否已經(jīng) JIT 編譯好了，如果沒有編譯好，就先進(jìn)行 JIT 編譯，然后執(zhí)行本地代碼。如果內(nèi)存用盡，就先刪除本地代碼。
method.on_call((param)=>{if(method.has_jit == false) {method.native_code = jit_compile(method);}method.native_code(param); })method.on_memory_runout(()=>{method.native_code.delete();method.has_jit = false; }))BASIC 語言可以說是拋棄型編譯的試驗場。Brown?[21]?將拋棄型編譯看作是解決時間和空間權(quán)衡的好方法。Hammond?[22]?更為堅定，他認(rèn)為除非內(nèi)存緊張，使用拋棄型編譯會更有收益。
## HotSpot and FORTRAN
有關(guān)程序在運(yùn)行時自動優(yōu)化?熱點(diǎn)（hot spots）?的動態(tài)編譯最早是由 Gilbert Joseph Hansen 于 1974 年提出?[23]，他解決了三個重要的問題：
哪些代碼應(yīng)該被優(yōu)化？
Hansen 選擇了一個簡單并且低開銷的模型，為每個（通用意義上的）代碼塊維護(hù)一個執(zhí)行頻率計數(shù)器（frequency-of-execution counter）。
這些代碼在什么時候優(yōu)化？
Hansen 設(shè)定了一個執(zhí)行次數(shù)的閾值。當(dāng)計數(shù)器達(dá)到閾值后，就會把關(guān)聯(lián)的代碼塊作為下一層優(yōu)化的候選隊列中。Supervisor 代碼會在兩個代碼塊間被調(diào)用，評估計數(shù)器是否達(dá)到閾值，如果達(dá)到了就做優(yōu)化，然后將控制權(quán)轉(zhuǎn)移到下一個代碼塊中。
代碼應(yīng)該被怎樣優(yōu)化？
Hansen 采用了分次優(yōu)化的方法，即將一系列機(jī)器相關(guān)和機(jī)器無關(guān)的優(yōu)化分到不同的集合中，比如，一個代碼塊可能會先進(jìn)行常量折疊（constant folding）的優(yōu)化，在第二次優(yōu)化時執(zhí)行公共子表達(dá)式消除（common subexpression elimination）優(yōu)化，第三次優(yōu)化再執(zhí)行代碼移動（code motion）優(yōu)化。
Apply in Fortran
Hansen 將這種編譯優(yōu)化方式應(yīng)用在 Fortran 的編譯器中，優(yōu)化器會對執(zhí)行頻次不同的程序進(jìn)行迭代式的優(yōu)化，若一段代碼執(zhí)行的足夠頻繁，最終會被編譯為機(jī)器碼。Hansen 的研究結(jié)果表明，針對 “hot spots” 做解釋和迭代優(yōu)化，其執(zhí)行成本往往遠(yuǎn)低于傳統(tǒng)的編譯器優(yōu)化（即對整個程序做優(yōu)化）。這種優(yōu)化方式較好地限制 JIT 系統(tǒng)在任何給定優(yōu)化點(diǎn)的時間開銷，同時允許我們在 JIT 編譯器中做增量優(yōu)化。
## Smalltalk
Smalltalk 是一種動態(tài)類型、反射式、面向?qū)ο缶幊陶Z言?[24]。當(dāng)新的方法被動態(tài)地添加到一個類時，Smalltalk 源代碼會被編譯為虛擬機(jī)代碼?[25]。Smalltalk 的動態(tài)更新和反射功能在四十年前都已遠(yuǎn)遠(yuǎn)領(lǐng)先與如今的許多主流語言。然而，Smalltalk 語言的運(yùn)行十分慢，而且運(yùn)行開銷極大，這是影響 Smalltalk 發(fā)展的主要原因之一。
為了提高 Smalltalk 的運(yùn)行性能，Deutsch 和 Schiffman 從軟件層面做出了關(guān)鍵的優(yōu)化。他們發(fā)現(xiàn)，只要表示之間的轉(zhuǎn)換對于用戶是自動的且透明的，那么就可以為信息選擇最有效的表示。這個思想放到現(xiàn)代編譯器中，可以引申為 IR 的轉(zhuǎn)換在不影響用戶行為的情況下可以選擇更高效的實(shí)現(xiàn)。
他們的系統(tǒng)使用了?虛擬機(jī)代碼到本地代碼的 JIT 編譯，并將該優(yōu)化技術(shù)比作?宏擴(kuò)展（macro-expansion）。有特色的地方在于，當(dāng)開始執(zhí)行時，程序會被 lazily compile 為本地代碼，并由系統(tǒng)緩存起來以供之后使用。該編譯系統(tǒng)與操作系統(tǒng)中的內(nèi)存管理相關(guān)聯(lián)，編譯出的本地代碼永遠(yuǎn)不會被操作系統(tǒng)的頁面兌換機(jī)制換到外存中（paged out），只會被丟棄然后在必要時重新生成。
## Self
Self 是一種基于原型的面向?qū)ο蟮某绦蛟O(shè)計語言?[26][27]，在一段時間內(nèi) Self 是 Smalltalk 最快的實(shí)現(xiàn)，并且僅比 C 慢兩倍，完全面向?qū)ο蟆?/p>
與本文中提到的許多其他語言相比，Self 更像是一種研究工具。Self 在很多方面受到 Smalltalk 的影響，兩者都是純粹的面向?qū)ο蟮恼Z言。不同的是，Self 摒棄了類而采用了對象的概念，并試圖以其他方式統(tǒng)一一些概念，比如每一個動作都是動態(tài)的和可改變的，即使是基本的操作（如局部變量訪問）也需要調(diào)用一個方法。
Self 語言的復(fù)雜設(shè)計，激發(fā)了大家對 JIT 編譯和優(yōu)化的開創(chuàng)和改進(jìn)。Self 的大部分開發(fā)工作是在 Sun Microsystem 上進(jìn)行的，因此后來很多技術(shù)被直接用在了 Java 的 HotSpot VM 上。在設(shè)計 JIT 的過程中，有研究者發(fā)現(xiàn)觸發(fā)機(jī)制比選擇機(jī)制重要得多。這也和不同的編碼風(fēng)格有關(guān)，比如面向?qū)ο缶幊田L(fēng)格傾向于短的方法。
在 Self 編程語言中，可以在方法正在執(zhí)行的時候修改，這個修改依賴于修改方法的運(yùn)行堆棧。Self 編譯器的 JIT 優(yōu)化還引入了?類型反饋（type feedback）?[28][29]，即程序執(zhí)行時的類型信息由運(yùn)行時系統(tǒng)收集，當(dāng)下一次運(yùn)行時可以根據(jù)這個類型信息進(jìn)行更為激進(jìn)的優(yōu)化。下面分別是已知類型信息和未知類型信息時解釋器的動作，已知類型信息時判斷的條件更少，運(yùn)行得更快。
def func(A, B):return A + Bfunc(0, 1) # 未知類型信息的目標(biāo)偽代碼 if A.typeid == int:if B.typeid == int:return A.getintdata() + B.getintdata() # 已知類型信息的目標(biāo)偽代碼 return A + BSelf 后來被 Sun 拋棄了，但對 Java 語言的研究仍在繼續(xù)。
## Slim Binaries and Oberon
在上個世紀(jì)，將軟件部署到不同的機(jī)器上是個大問題，因為不同的機(jī)器具有不同的體系結(jié)構(gòu)。Franz 使用?瘦二進(jìn)制文件（slim binaries）?[30][31]?來解決這個問題。
瘦二進(jìn)制文件?包含一個高級的、獨(dú)立于機(jī)器表示的程序模塊。當(dāng)模塊被加載時，會迅速生成會根據(jù)運(yùn)行時的環(huán)境動態(tài)調(diào)整的可執(zhí)行的代碼。至于為什么叫 “瘦”，可以考慮一個高層次的 IR 通常會比低層次的 IR 在單位空間上蘊(yùn)含的信息更多，因此占用空間更小。
Franz 認(rèn)為，就目標(biāo)代碼的性能而言，一次生成整個模塊的代碼通常會優(yōu)于 Smalltalk 和 Self 用的一次生成整個方法代碼的策略。因此對于瘦二進(jìn)制文件方法而言，快速的代碼生成很關(guān)鍵。如果之后需要，生成的代碼可以被記錄下來而不是重新生成。
Franz 為 Oberon（一種通用編程語言，由 Niklaus Emil Wirth 在 1987 年推出）[32]?實(shí)現(xiàn)了一個動態(tài)代碼生成系統(tǒng) Juice（https://github.com/berkus/Juice）。Juice 系統(tǒng)實(shí)現(xiàn)了瘦二進(jìn)制文件，允許動態(tài)模塊（Module）的加載。加載和產(chǎn)生瘦二進(jìn)制的代碼要比加載傳統(tǒng)二進(jìn)制文件慢一些。從瘦二進(jìn)制文件發(fā)明開始，Kistler 開始研究如何連續(xù)地進(jìn)行運(yùn)行時優(yōu)化，也就是不斷地優(yōu)化正在執(zhí)行中程序的某一部分。
## Templates, ML, and C
這一部分介紹模板的相關(guān)內(nèi)容，ML（Meta Language）語言相對較早，如今大家也不是很熟悉，但是 C 系的語言大家都很熟悉。ML 和 C 都采用了分階段編譯的方法。單個程序的編譯分為兩個階段：靜態(tài)編譯階段和動態(tài)編譯階段。在運(yùn)行時之前，靜態(tài)編譯器編譯 “模板（templates）”，這些模板的本質(zhì)是運(yùn)行時由動態(tài)編譯器拼接在一起的構(gòu)建塊（building blocks），里面會有一些值在運(yùn)行時填充。模板在執(zhí)行之前需要運(yùn)行時翻譯，也就是特化，動態(tài)編譯器在連接模板之后會做運(yùn)行時優(yōu)化。需要注意的是，這里的模板不是現(xiàn)在 C++ 里的模板。這一個部分現(xiàn)在用的少，只看上面的概念也有點(diǎn)難懂，所以下面舉個例子，源自文獻(xiàn)?[33], 這個例子里?x?是靜態(tài)的，而?y?是動態(tài)的，是只有運(yùn)行時才知道的。
// 源程序 int f(int x,int y) {int l;l = 2 * x;if(l==2)l=l+y;elsel=y*x;return l; }上面是 C 語言的源程序，因為提取模板的方法有很多，下面選擇一種方案提取模板。
/*--t1-begin---*/ int f_t(int y) {int l; /*--t1-end-----*/ /*--t2-begin-----*/l=[h1]+y; /*--t2-end-----*/ /*--t3-begin-----*/l=y*[h2]; /*--t3-end-----*/ /*--t4-begin-----*/return l; } /*--t4-end-----*/上面的代碼總共被劃分成了 4 個模板。因為參數(shù)?x?是原始過程聲明為靜態(tài)的，所以他們可以確定，但是我們不知道程序的調(diào)用者現(xiàn)在給它什么值。因此它作為運(yùn)行時特化器的一個參數(shù)出現(xiàn)，運(yùn)行時的值被轉(zhuǎn)換成了洞，使用?[h1]?和?[h2]?來表示。
下面是動態(tài)編譯器如何特化函數(shù)?f?的過程，此時模板使用運(yùn)行時的值實(shí)例化。
void rt_spec_f(int x) {int l;dump_template(t1);l=2*x;if(l==2) {dump_template(t2);instantiate_hole(t2,l);}else {dump_template(t3);instantiate_hole(t3,x);}dump_template(t4); }局部變量?l?既在靜態(tài)運(yùn)算中，也在動態(tài)運(yùn)算中。運(yùn)行時特化器的第一個運(yùn)算是 dump 模板?t1。原始過程的第一個指令能夠被執(zhí)行是因為它是純靜態(tài)的。然后條件語句被執(zhí)行。條件測試結(jié)果決定 dump 模板?t2?還是 dump 模板?t3。dump 后的模板使用運(yùn)行時的值實(shí)例化。最后模板?t4?被實(shí)例化。
## Erlang
Erlang 是一種通用的并發(fā)的、函數(shù)式、分布式的編程語言，用于設(shè)計大型軟實(shí)時（soft real-time）系統(tǒng)。Erlang 官方實(shí)現(xiàn)的虛擬機(jī) BEAM，可以解釋執(zhí)行；還有編譯為二進(jìn)制的高性能編譯器 HiPE（High Performance Erlang，由 Uppsala University 開發(fā)?[34]）；也支持腳本的方式來執(zhí)行。
Erlang 的 HiPE 實(shí)現(xiàn)旨在解決性能問題。通常情況下，HiPE 編譯器會比 BEAM 編譯器生成更快的代碼。作為一個沒有設(shè)計歷史包袱的系統(tǒng)，HiPE 的突出之處在于用戶必須顯式調(diào)用 JIT 編譯器，這樣做可以在混合代碼執(zhí)行上提供的性能與代碼空間權(quán)衡之上提供給用戶更好的控制度。HiPE 在本地代碼和解釋代碼之間來回執(zhí)行 “模式切換” 時非常小心，在明顯的調(diào)用和返回位置、以及拋出異常時可能需要模式切換。它們的調(diào)用使用調(diào)用者的模式。
## Specialization and O’Caml
O'Caml 是另外一種函數(shù)式編程語言，可以看做是 ML 的一種方言?[35]。O'Caml 的解釋器一直致力于?運(yùn)行時特化（run-time specilization）的工作。
Piumarta 和 Riccardi 把解釋器的指令特化為正在運(yùn)行的程序?[36]。他們首先把解釋的字節(jié)碼動態(tài)翻譯到直接線程代碼，然后把指令塊動態(tài)組合成為新的 “宏操作碼”，修改代碼以使用新指令。這減少了指令分派的開銷，并為宏操作碼中的優(yōu)化提供了機(jī)會。如果指令是分開的，那么這種優(yōu)化是不可能的。他們的技術(shù)沒有考慮動態(tài)執(zhí)行路徑，但是指出了它最適合分派時間是影響性能相對較大因素的低級指令集。
## Prolog
Prolog?[37]?是一個面向邏輯、動態(tài)編譯的編程語言。Prolog 基于謂詞邏輯，具有很強(qiáng)的聲明性特征。最初被運(yùn)用于自然語言等研究領(lǐng)域，現(xiàn)在被廣泛應(yīng)用在人工智能的研究中，比如建造專家系統(tǒng)、自然語言理解等。
為了讓 Prolog 程序的解釋執(zhí)行更加高效，Prolog 代碼會被編譯為 WAM（Warren Abstract Machine，沃倫抽象機(jī)）指令。SICStus 作為 Prolog 編譯器的最大供應(yīng)商，提供了一系列基于 WAM 的 Prolog 實(shí)現(xiàn)。Haygood 與 SICStus 團(tuán)隊一起，開發(fā)了一種新的 Prolog 實(shí)現(xiàn)，能夠被調(diào)用并且動態(tài)加載輸出?[38]，既具備一定的可移植性，又一定程度上提高了性能。（SICStus Prolog 官網(wǎng)：https://sicstus.sics.se，更多介紹可以閱讀：SICStus Prolog -- the first 25 years.[39]）
## Java and JIT
Java 是一門通用的面向?qū)ο蟮木幊陶Z言，于 1995 年由 Sun 正式發(fā)布后，伴隨著互聯(lián)網(wǎng)的迅猛發(fā)展而發(fā)展，逐漸成為重要的網(wǎng)絡(luò)編程語言。
不同于當(dāng)時的其他編譯型語言或解釋型語言，Java 先將源碼靜態(tài)編譯為虛擬機(jī)字節(jié)碼指令，然后再依賴不同平臺的 Java 虛擬機(jī)（JVM）來解釋執(zhí)行字節(jié)碼，從而具備跨平臺的特性。早期的 JVM 只是解釋器，解釋字節(jié)碼很慢，這一定程度上影響了 Java 的運(yùn)行效率。因此，提高 Java 的運(yùn)行效率又重新激發(fā)了研究者們對 JIT 的興趣。而加快 Java 程序運(yùn)行速度的核心方法就是對 Java 字節(jié)碼的?Just in Time Compile（即 JIT 編譯）。
Cramer 等 Sun 研發(fā)人員觀察到?[40]，JIT 編譯帶來的速度提升是有上限的，在他們運(yùn)行的一個配置文件中，適當(dāng)?shù)慕忉寖H占執(zhí)行時間的 68%。他們主張直接使用 JVM 字節(jié)碼（堆棧機(jī)指令集，stack-based）作為 JIT 編譯和優(yōu)化的中間表示。但是只有從字節(jié)碼到本地代碼的翻譯是不夠的，還需要代碼優(yōu)化，而傳統(tǒng)的優(yōu)化技術(shù)是昂貴的。因此，大家尋找對優(yōu)化算法的改進(jìn)，盡可能在算法的執(zhí)行速度和編譯速度之間取得平衡。
Burke 等人提出了只編譯的策略?[41]，沒有任何解釋器。他們的系統(tǒng)也是用 Java 實(shí)現(xiàn)的，對 JIT 的改進(jìn)直接使他們的系統(tǒng)受益。
Agesen?[42]?將 JVM 字節(jié)碼翻譯成 Self 代碼，以利用 Self 編譯器的優(yōu)化。
Azevedo 等人?[43]?嘗試用注釋將代碼優(yōu)化的工作轉(zhuǎn)移到運(yùn)行時間之前，高效的 JIT 優(yōu)化所需的信息被預(yù)先計算并作為注釋標(biāo)記到字節(jié)碼上，然后由 JIT 系統(tǒng)使用以協(xié)助其工作。
Plezbert 和 Cytron?[44]?提出并評估了 Java 的 “連續(xù)編譯” （continuous compilation）的想法，其中解釋器和編譯器將同時執(zhí)行，最好是在不同的處理器上執(zhí)行。
# JIT 系統(tǒng)的分類
Aycock 將 JIT 分為四類：
觸發(fā)方式 Invocation
如果用戶必須明確地采取一些行為來調(diào)用運(yùn)行時的編譯，那么 JIT 編譯器就是顯式調(diào)用的（explicitly invoked）。一個隱式調(diào)用的 JIT 編譯器對用戶來說是透明的。
執(zhí)行方式 Executability
若 JIT 的源語言和目標(biāo)語言是相同的，則 JIT 是單一執(zhí)行（monoexecutable）的。否則，該系統(tǒng)就是多執(zhí)行的（polyexecutable）。
即使 JIT 是單一執(zhí)行的，JIT 系統(tǒng)仍然會做 on-the-fly 的優(yōu)化。（on-the-fly 是指執(zhí)行過程中伴隨的過程，并不打斷執(zhí)行，或者說 on-the-fly 是一種無縫的切換。）?這種優(yōu)化是單一執(zhí)行的優(yōu)勢，它并不翻譯代碼到新的語言，只是做運(yùn)行時的 JIT 優(yōu)化。
還有一種 JIT 系統(tǒng)是多執(zhí)行（polyexecutable）的，這樣的 JIT 系統(tǒng)（注意不是編譯器）能夠執(zhí)行多于一種的語言。多執(zhí)行的 JIT 系統(tǒng)可以決定何時需要調(diào)用編譯器。例如，JVM 是一個典型的多執(zhí)行的 JIT 系統(tǒng)，其中的 Java 字節(jié)碼在 JIT 執(zhí)行時會被編譯為機(jī)器代碼，JVM 能夠執(zhí)行 Java 字節(jié)碼（解釋執(zhí)行）和機(jī)器代碼（JIT 后執(zhí)行）這兩種語言。
并發(fā)方式 Concurrency
如果程序需要暫停從而運(yùn)行 JIT 編譯器，這個 JIT 系統(tǒng)就不是并發(fā)的。如果 JIT 編譯器能夠在單獨(dú)的線程或者進(jìn)程甚至處理器上，與程序并發(fā)地執(zhí)行，則該 JIT 系統(tǒng)是個并發(fā)的 JIT 系統(tǒng)。
實(shí)時性 Real-time
即，如果 JIT 系統(tǒng)能夠提供實(shí)時的保證，也就是說 JIT 編譯器能夠保證在多長時間內(nèi)完成任務(wù)，就說這個 JIT 系統(tǒng)是實(shí)時保證的。
# JIT 編譯的挑戰(zhàn)
隨著 JIT 編譯的發(fā)展，一些問題和挑戰(zhàn)也隨之出現(xiàn)：
二進(jìn)制代碼生成
事實(shí)上，二進(jìn)制代碼的動態(tài)生成充滿了挑戰(zhàn)。比如，有些程序中會包含一些在最開始代碼生成階段無法獲取的信息，比如前向分支的目標(biāo)（可以參考《編譯原理》紫龍書對于 if 語句翻譯為 goto 回填的問題），我們需要知道后面的代碼塊后才能回填（Backpatch）到合適的位置上。
緩存
在緩存問題上，緩存一致性問題已經(jīng)有協(xié)議來保證，那么最重要的是提高 JIT 代碼加載的速度。能夠在執(zhí)行之前把 JIT 代碼從內(nèi)存載入 Cache 加快執(zhí)行速度，并且能夠合理劃分需要 JIT 部分的大小，不要使得 JIT 生成后的二進(jìn)制代碼被頻繁地?fù)Q入換出 Cache。
除此之外，JVM 等現(xiàn)代 JIT 系統(tǒng)在內(nèi)存中開辟了代碼緩存，這個區(qū)域負(fù)責(zé)存儲編譯為本機(jī)代碼的字節(jié)碼，代碼緩存具有固定的大小。如果這個區(qū)域滿，JVM 會停止編譯。而對于每個編譯的方法，JVM 提供一個熱度計數(shù)器，如果計數(shù)器的值小于閾值，JVM 就釋放這段預(yù)編譯代碼?[45]。
執(zhí)行
可執(zhí)行的代碼存放的位置可能會被操作系統(tǒng)所限制。比如，生成的 JIT 代碼如果存放在數(shù)據(jù)區(qū)還要顯式地聲明數(shù)據(jù)區(qū)的可執(zhí)行屬性，這時的代碼區(qū)和數(shù)據(jù)區(qū)的界限就變得不明晰。舉例來說，在安全領(lǐng)域經(jīng)常使用的 shellcode 就是放在數(shù)據(jù)區(qū)的一段可執(zhí)行代碼，用來發(fā)送到服務(wù)器利用特定漏洞的代碼，一般可以獲取權(quán)限。
# Runtime 的未來 #
由于程序靜態(tài)分析和優(yōu)化的局限性，JIT 編譯兼具靜態(tài)編譯和動態(tài)優(yōu)化的優(yōu)勢就更加明顯。在深度學(xué)習(xí)等技術(shù)催生的各種領(lǐng)域特定語言涌現(xiàn)的當(dāng)下，如果拓寬傳統(tǒng) JIT 編譯的應(yīng)用范圍，適配更多不同的語言也是一個重要的問題。GraalVM?[46]?是一個把傳統(tǒng)的編譯技術(shù)與云環(huán)境結(jié)合起來的項目，給云原生編譯器也開了一扇新的天窗。
參 考
[1] The magic mix: interpreter, compiler, specializer. https://www.cs.dartmouth.edu/~doug/cs118/mix.html
[2] Jiaqi Gao, Ennan Zhai, Hongqiang Harry Liu, Rui Miao, Yu Zhou, Bingchuan Tian, Chen Sun, Dennis Cai, Ming Zhang, and Minlan Yu. 2020. Lyra: A Cross-Platform Language and Compiler for Data Plane Programming on Heterogeneous ASICs. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication (SIGCOMM '20). Association for Computing Machinery, New York, NY, USA, 435–450. DOI: https://doi.org/10.1145/3387514.3405879
[3] Interactive Program Synthesis by Augmented Examples https://tianyi-zhang.github.io/files/uist2020-interactive-program-synthesis.pdf
[4] PYNQ - Python productivity for Zynq - Home http://www.pynq.io/
[5] Charles N. Fischer, Ronald K. Cytron, and Richard J. LeBlanc. 2009. Crafting A Compiler (1st. ed.). Addison-Wesley Publishing Company, USA.
[6] John Aycock. 2003. A brief history of just-in-time. ACM Comput. Surv. 35, 2 (June 2003), 97–113. DOI: https://doi.org/10.1145/857076.857077
[7] Just in Time Compilation Explained https://www.freecodecamp.org/news/just-in-time-compilation-explained/
[8] Hiroshi Inoue etc. Adaptive Multi-Level Compilation in a Trace-based Java JIT Compiler.
[9] MCCARTHY, J. 1960. Recursive functions of symbolic expressions and their computation by machine, part I. Commun. ACM 3, 4, 184–195. http://www-formal.stanford.edu/jmc/recursive.pdf
[10] UNIVERSITY OF MICHIGAN. 1966b. The “University of Michigan Assembly Program” (“UMAP”). In University of Michigan Executive System for the IBM 7090 Computer, Vol. 2. University of Michigan, Ann Arbor, MI.
[11] UNIVERSITY OF MICHIGAN. 1966a. The System Loader. In University of Michigan Executive System for the IBM 7090 Computer, Vol. 1. University of Michigan, Ann Arbor, MI.
[12] THOMPSON, K. 1968. Regular expression search algorithm. Commun. ACM 11, 6 (June), 419–422.
[13] APL - Wikipedia https://en.wikipedia.org/wiki/APL_(programming_language)
[14] ABRAMS, P. S. 1970. An APL machine. Ph.D. dissertation. Stanford University, Stanford, CA. Also, Stanford Linear Accelerator Center (SLAC) Rep. 114.
[15] THE DYNAMIC INCREMENTAL COMPILER OF APL\3000. http://www.softwarepreservation.org/projects/apl/Papers/DYNAMICINCREMENTAL
[16] DAKIN, R. J. AND POOLE, P. C. 1973. A mixed code approach. The Comput. J. 16, 3, 219–222.
[17] DAWSON, J. L. 1973. Combining interpretive code with machine code. The Comput. J. 16, 3, 216–219.
[18] PITTMAN, T. 1987. Two-level hybrid interpreter/native code execution for combined space-time program efficiency. In Proceedings of the SIGPLAN Symposium on Interpreters and Interpretive Techniques. ACM Press, New York, NY, 150–152.
[19] JONES, N. D., GOMARD, C. K., AND SESTOFT, P. 1993. Partial Evaluation and Automatic Program Generation. Prentice Hall, Englewood Cliffs, NJ.
[20] Partial Evaluation - Wikipedia https://en.wikipedia.org/wiki/Partial_evaluation
[21] BROWN, P. J. 1976. Throw-away compiling. Softw.—Pract. Exp. 6, 423–434. https://doi.org/10.1002/spe.4380060316
[22] HAMMOND, J. 1977. BASIC—an evaluation of processing methods and a study of some programs. Softw.—Pract. Exp. 7, 697–711.
[23] HANSEN, G. J. 1974. Adaptive systems for the dynamic run-time optimization of programs. Ph.D. dissertation. Carnegie-Mellon University, Pittsburgh, PA. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.376.3638&rep=rep1&type=pdf
[24] SmallTalk - Wikipedia https://en.wikipedia.org/wiki/Smalltalk
[25] GOLDBERG, A. AND ROBSON, D. 1985. Smalltalk-80:The Language and its Implementation. AddisonWesley, Reading, MA.
[26] UNGAR, D. AND SMITH, R. B. 1987. Self: The power of simplicity. In Proceedings of OOPSLA ’87. 227–242.
[27] SMITH, R. B. AND UNGAR, D. 1995. Programming as an experience: The inspiration for Self. In Proceedings of ECOOP ’95.
[28] HOLZLE, U. 1994. Adaptive optimization for Self: Reconciling high performance with exploratory programming. Ph.D. dissertation. CarnegieMellon University, Pittsburgh, PA.
[29] HOLZLE, U. AND UNGAR, D. 1994a. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of PLDI ’94. 326–336.
[30] FRANZ, M. 1994. Code-generation on-the-fly: A key to portable software. Ph.D. dissertation. ETH Zurich, Zurich, Switzerland.
[31] FRANZ, M. AND KISTLER, T. 1997. Slim binaries. Commun. ACM 40, 12 (Dec.), 87–94. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.1711&rep=rep1&type=pdf
[32] Oberon - Wikipedia https://en.wikipedia.org/wiki/Oberon_(programming_language)
[33] Carles Consel. A General Approach for Run-Time Specialization and its Application to C.
[34] Erlang - HiPE http://erlang.org/documentation/doc-10.3/lib/hipe-3.18.3/doc/html/HiPE_app.html
[35] REMY, D., LEROY, X., AND WEIS, P. 1999. Objective Caml—a general purpose high-level programming language. ERCIM News 36, 29–30.
[36] PIUMARTA, I. AND RICCARDI, F. 1998. Optimizing direct threaded code by selective inlining. In Proceedings of PLDI ’98. 291–300.
[37] Prolog - Wikipedia https://en.wikipedia.org/wiki/Prolog
[38] HAYGOOD, R. C. 1994. Native code compilation in SICStus Prolog. In Proceedings of the Eleventh International Conference on Logic Programming. 190–204. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.6147&rep=rep1&type=pdf
[39] Mats Carlsson, Per Mildner: SICStus Prolog -- the first 25 years. CoRR abs/1011.5640 (2010) https://arxiv.org/abs/1011.5640
[40] CRAMER, T., FRIEDMAN, R., MILLER, T., SEBERGER, D., WILSON, R., AND WOLCZKO, M. 1997. Compiling Java just in time. IEEE Micro 17, 3 (May/June), 36–43.
[41] BURKE, M. G., CHOI, J.-D., FINK, S., GROVE, D., HIND, M., SARKAR, V., SERRANO, M. J., SREEDHAR, V. C., AND SRINIVASAN, H. 1999. The Jalapeno dynamic optimizing compiler for Java. In Proceedings of JAVA ’99. 129–141.
[42] AGESEN, O. 1997. Design and implementation of Pep, a Java just-in-time translator. Theor. Prac. Obj. Syst. 3, 2, 127–155.
[43] AZEVEDO, A., NICOLAU, A., AND HUMMEL, J. 1999. Java annotation-aware just-in-time (AJIT) compilation system. In Proceedings of JAVA ’99. 142–151.
[44] PLEZBERT, M. P. AND CYTRON, R. K. 1997. Does “just in time” = “better late then never”? In Proceedings of POPL ’97. 120–131.
[45] jvm-code-cache https://www.baeldung.com/jvm-code-cache
[46] GraalVM - Wikipedia https://en.wikipedia.org/wiki/GraalVM
原文轉(zhuǎn)載自?編程語言Lab-從 JIT 編譯看 Runtime 的過去與未來
總結(jié)
以上是生活随笔為你收集整理的从 JIT 编译看 Runtime 的过去与未来的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： IOS7毛玻璃效果
- 下一篇： 淘宝 Android 端图片体验优化实践