基于即時編譯的GNU Octave性能優(yōu)化*

莫舒恒,盧圣有,黃 聃,盧宇彤

(1.中山大學系統(tǒng)科學與工程學院，廣東 廣州 510006；2.中山大學計算機學院，廣東 廣州 510006)

1 引言

隨著科學技術的迅猛發(fā)展，數(shù)值計算成為科學研究、工程設計和金融建模等領域的重要手段。GNU Octave是一款免費、開源，且兼容MATLAB語言的數(shù)值計算軟件，在教學、研究和商業(yè)應用中使用廣泛。然而，運行效率低下一直是Octave發(fā)展面臨的重要問題，同樣的代碼在Octave上的執(zhí)行時間可達MATLAB的幾十倍乃至幾百倍。

對于Octave這類動態(tài)解釋型語言，解釋器的性能往往是其瓶頸所在。使用高效的即時JIT(Just-In-Time)編譯器是提高程序運行效率的一種重要手段,當源代碼被轉(zhuǎn)換為中間語言后，由JIT編譯器讀取全部或部分中間語言，并將其即時編譯成機器語言。機器語言可被緩存并在以后重用，這大大提升了JIT編譯器的效率。許多解釋型語言都具有成熟高效的JIT編譯器，例如Java虛擬機JVM(Java Virtual Machine)[1]和JavaScript語言的V8引擎[2]及Microsoft.NET Framework中的JIT編譯器[3]。一些成熟的編譯器框架也提供了對JIT編譯技術的支持。GCC(GNU Compiler Collection)提供了libgccjit庫[4]，用戶可以調(diào)用該庫的C/C++ API接口，以GCC作為后端動態(tài)生成機器指令；LLVM項目同樣提供了JIT引擎[5]，且該引擎已歷經(jīng)3次迭代更新，由最初的JIT引擎進化至MCJIT引擎，再到如今的ORC JIT引擎。使用LLVM JIT引擎不僅可以調(diào)用C/C++ API接口完成，還可以直接生成LLVM機器無關的中間表示IR(Intermediate Representation)，由LLVM后端完成LLVM IR到機器語言的翻譯。

MATLAB的JIT編譯技術一直在不斷發(fā)展。2002年，MATLAB?官方在MATLAB 6.5版本中引入被設計為對MATLAB解釋器進行補充的JIT加速器(JIT-Accelerator)，以支持MATLAB語言有限子集的JIT編譯。相比于MATLAB 6.1版本，新版本在多種測試場景下均表現(xiàn)出了高達百倍的性能提升[6]；MATLAB R2015b重新設計了MATLAB的執(zhí)行引擎，重點在于重構JIT編譯器部分。新的執(zhí)行引擎不再是僅支持MATLAB語言的有限子集，而是能夠編譯整個語言；也不只在特定情況(如存在循環(huán)語句的情況)下使用JIT編譯，而是對所有的MATLAB代碼均進行JIT編譯。對76個性能敏感程序的測試結果表明，相比于R2015a版本，新的執(zhí)行引擎性能平均提高了40%[7]。

Octave內(nèi)部存在一個基于LLVM的實驗性JIT編譯器[8]，只能對少部分Octave語句進行JIT編譯加速，且適用范圍不明。因而，Octave 的官方二進制發(fā)行版并未包含這一功能。迄今為止，Octave JIT編譯器的實現(xiàn)仍是基于Brister[9]在OctConf2012研討會上提出的雛形。目前Octave JIT編譯器的相關研究已停滯，若要從源碼編譯安裝并正常運行包含JIT編譯功能的Octave較為困難，甚至自6.1.0版本起已放棄對該JIT編譯器的兼容。

本文對Octave JIT編譯器的整體功能和性能進行了評估，結果表明Octave JIT編譯器對提升Octave執(zhí)行效率的效果明顯，但是該JIT編譯器適用的代碼范圍十分有限，幾乎無法在實際應用場景中給Octave帶來明顯的效率提升。面對Octave JIT編譯器缺乏后續(xù)更新和優(yōu)化的現(xiàn)狀，本文基于Octave JIT編譯器對Octave的性能優(yōu)化方案進行了探究。本文貢獻主要有以下4點：

(1)分析了Octave JIT編譯器的工作流程，評估了Octave JIT編譯器的性能和適用范圍，為基于JIT編譯器的性能優(yōu)化方案指明了方向。

(2)提出了融合漸進式調(diào)試輸出與白名單機制的調(diào)試輸出完善方案，改進了JIT編譯失敗時的異常發(fā)生機制，從而增強了Octave Debug系統(tǒng)對Octave JIT編譯器編譯過程的調(diào)試輔助功能。

(3)針對當前Octave JIT編譯器的功能和性能缺陷，優(yōu)化了JIT編譯器中的函數(shù)調(diào)用、索引運算與算術邏輯運算，并在此基礎上進行Octave優(yōu)化效果驗證與展示。

(4)分類總結了Octave JIT編譯器的現(xiàn)有缺陷，為未來Octave JIT編譯器的功能完善和性能優(yōu)化奠定基礎。

2 Octave JIT編譯流程分析

本節(jié)從工作原理角度出發(fā)，對Octave JIT編譯器及其類型推斷系統(tǒng)的工作原理進行分析。

2.1 Octave JIT編譯器整體設計

Octave JIT編譯器以Octave解釋器為前端，以LLVM編譯框架為后端。在Octave解釋器完成詞法分析、語法分析和語義分析的工作后，由Octave JIT編譯器完成Octave解釋器與LLVM后端的交互，之后的工作由LLVM編譯框架所提供的JIT執(zhí)行引擎完成。

如圖1所示，在JIT編譯過程中，JIT編譯器將解釋器語義分析階段得到的抽象語法樹AST(Abstract Syntax Tree)通過逐一編寫的中間代碼生成規(guī)則轉(zhuǎn)換為原始的Octave JIT IR，在此基礎上構造靜態(tài)單賦值SSA(Static Single Assignment)形式的Octave JIT IR，并通過類型推斷得到含中間類型信息的Octave JIT IR。接著將該JIT IR通過逐一編寫的對應規(guī)則利用LLVM的MCJIT引擎轉(zhuǎn)換為LLVM IR，隨后由LLVM完成代碼優(yōu)化和目標代碼生成等編譯器中、后端工作。JIT編譯完畢的代碼將以機器指令的形式存儲于被標記為可讀、可執(zhí)行狀態(tài)的內(nèi)存中，以指針的形式返回函數(shù)入口地址供Octave調(diào)用。

Figure 1 Overall workflow of Octave JIT compiler

Octave JIT編譯器目前僅支持循環(huán)代碼編譯。Octave代碼通過調(diào)用jit_enable函數(shù)控制JIT編譯器的開關。Octave解釋器在執(zhí)行代碼時，會將循環(huán)代碼轉(zhuǎn)交給JIT編譯器。若JIT編譯未開啟，則JIT編譯器把工作流交還給解釋器，循環(huán)代碼的運行時間為解釋器用時，即解釋器執(zhí)行代碼的時間。若JIT編譯已開啟，則JIT編譯器對循環(huán)代碼進行JIT編譯，循環(huán)代碼的運行時間為JIT編譯用時及機器指令執(zhí)行用時。若JIT編譯后代碼運行時間比解釋器用時少，則JIT編譯為循環(huán)代碼執(zhí)行帶來了加速效果。

此外，JIT Debug系統(tǒng)與JIT編譯的各個階段均有交互，故Debug系統(tǒng)可獲得JIT編譯過程中包括AST、Octave JIT IR、LLVM IR和Optimized LLVM IR在內(nèi)的各類中間信息。

2.2 類型推斷系統(tǒng)

Octave語言是一種弱類型語言，而LLVM IR是強類型的中間表示。故在將Octave語言轉(zhuǎn)化為LLVM IR的過程中需進行類型推斷，以尋找各變量引用點的類型信息，從而將AST轉(zhuǎn)化為強類型的Octave JIT IR。本節(jié)對Octave JIT編譯器的類型推斷系統(tǒng)進行介紹，首先介紹其中的類型系統(tǒng)，然后介紹類型推斷過程。

2.2.1 數(shù)據(jù)類型

如表1所示，Octave JIT編譯器的類型系統(tǒng)中定義了JIT編譯器內(nèi)部使用的數(shù)據(jù)類型。這些數(shù)據(jù)類型實質(zhì)為中間數(shù)據(jù)類型，用于把Octave解釋器中的數(shù)據(jù)類型轉(zhuǎn)換為LLVM中對應的數(shù)據(jù)類型。

Table 1 Data types supported by the type system of Octave JIT compiler

除此之外，該類型系統(tǒng)會為每一個已支持JIT編譯的Octave內(nèi)置函數(shù)創(chuàng)建一個對應的數(shù)據(jù)類型，使得函數(shù)調(diào)用語句的實現(xiàn)可復用小括號索引運算的實現(xiàn)。

2.2.2 類型格

格是滿足每對元素都存在最小上界和最大下界的偏序集。類型格(Type Lattice)是在類型系統(tǒng)中的格模型[9]，其中元素表示數(shù)據(jù)類型，偏序關系對應數(shù)據(jù)類型之間由抽象到具體的繼承關系。

Octave目前的類型格如圖2所示，其中,any類型可指代任何數(shù)據(jù)類型，是類型格的最小上界;unknown指代類型推斷前的未知數(shù)據(jù)類型，是類型格的最大下界。Octave的類型推斷過程基于類型格實現(xiàn)類型轉(zhuǎn)換，為此需要尋找每個變量引用點的數(shù)據(jù)類型在類型格中所組成的子集的最小上界。

Figure 2 Type lattices of current Octave JIT compiler

2.2.3 類型推斷過程

由于LLVM的JIT引擎以函數(shù)為單位對代碼進行JIT編譯，Octave JIT編譯器的類型推斷系統(tǒng)也以函數(shù)為基礎。因當前的Octave JIT編譯器僅對循環(huán)代碼進行JIT編譯，故除循環(huán)體中調(diào)用的函數(shù)外，循環(huán)本身也被包裝成一個函數(shù)。循環(huán)函數(shù)的輸入?yún)?shù)為循環(huán)體中用到的上級作用域中的變量，而循環(huán)尾部的變量將作為循環(huán)函數(shù)的返回值返還Octave解釋器。

Octave JIT編譯器類型推斷系統(tǒng)的核心思想可歸納為2點：(1)所有類型信息的根源來自常量，通過按照程序順序模擬執(zhí)行進行常量的類型傳播，將其數(shù)據(jù)類型傳播至每一個變量引用點，使得每個變量引用點均含有該變量的數(shù)據(jù)類型在類型格中所組成的子集信息。(2)因為迭代會改變同一個變量引用點在不同迭代輪次中的類型信息，故對同一個函數(shù)，可迭代進行類型推斷，直到基本塊中所有變量引用點的類型信息收斂至不再發(fā)生變化的穩(wěn)定點為止。

通常情況下，編寫得較好的Octave程序中很少發(fā)生固有類型的變化，類型推斷過程幾乎立即收斂。另外，Octave中還規(guī)定了類型推斷迭代次數(shù)的閾值，若迭代次數(shù)超過閾值時函數(shù)中各點的變量類型仍未達到穩(wěn)定點，則類型推斷失敗，JIT編譯器將輸出異常。

3 Octave JIT編譯器功能和性能分析

本節(jié)從工作現(xiàn)狀角度出發(fā)，對Octave JIT編譯器的功能和性能進行測試及分析，為基于JIT 編譯器的Octave性能優(yōu)化方案指明方向。

3.1 Octave與JIT編譯模塊的編譯兼容性研究

編譯安裝包含JIT編譯器的Octave，需要在目標環(huán)境配置LLVM運行環(huán)境。

通過對目前較新版本的Octave和LLVM的編譯兼容性研究發(fā)現(xiàn)，Octave 6.1.0及更高版本無法成功與LLVM組合編譯。原因是自Octave 6.1.0起解釋器的語法分析樹(Parse Tree)被更改，但并未同步更新JIT編譯器的中間代碼生成部分。

而Octave 6.1.0的前一個版本Octave 5.2.0無法成功與非LLVM 4.0.1版本組合。由于LLVM C++ API變更頻繁，該版本與高于LLVM 4.0.1的版本無法成功組合編譯，且與低于LLVM 4.0.1的版本組合編譯后運行閃退。

因此，本文以Octave 5.2.0為研究對象，同時修改其源代碼，使其兼容LLVM 13.0.1這一新版本的C++ API。

3.2 JIT Debug系統(tǒng)的調(diào)試輸出與異常定位優(yōu)化

JIT Debug系統(tǒng)作用于JIT編譯的代碼。Octave通過啟動參數(shù)——debug-jit來控制Debug系統(tǒng)的開關。JIT編譯器開啟后，將對所有while循環(huán)代碼塊和大于迭代次數(shù)閾值(默認閾值為1 000)的for循環(huán)代碼塊進行JIT編譯。如圖3所示，如果循環(huán)代碼塊中存在一處不支持JIT編譯的語句，則JIT編譯器放棄對所有語句的JIT編譯，轉(zhuǎn)而由Octave解釋器執(zhí)行這些代碼。

Figure 3 Debug output process of current Octave JIT compiler

Debug系統(tǒng)會根據(jù)JIT編譯結果的成功與否，輸出不同的調(diào)試信息。當JIT編譯成功時，Debug系統(tǒng)首先在Compiling tree字段中輸出經(jīng)過JIT編譯的代碼段，隨后將會對JIT編譯器生成的Octave JIT IR、LLVM IR和Optimized LLVM IR 3個中間表示字段進行調(diào)試輸出。而當JIT編譯失敗時，Debug系統(tǒng)的調(diào)試輸出僅有模糊的JIT fail字段，該字段中僅包含導致編譯失敗的錯誤類型，難以定位錯誤位置并對其進行修復。

為此，本文提出融合漸進式調(diào)試輸出與白名單機制的方案，如圖4所示，對JIT Debug系統(tǒng)的調(diào)試輸出進行了優(yōu)化，同時完善了編譯失敗時的異常產(chǎn)生機制，以實現(xiàn)明晰的錯誤原因闡釋及精確的錯誤代碼定位。

Figure 4 Debug output process of the improved Octave JIT compiler

對于中間表示字段的完全缺失問題，由于JIT編譯失敗時無法保證從AST到Optimized LLVM IR的轉(zhuǎn)換過程中的3個階段都成功完成，因而本文對Octave JIT 編譯器的一次調(diào)試便輸出4個字段的過程進行拆分，按過程的先后順序分4步漸進輸出當前階段的調(diào)試信息，并采取白名單機制確定某一字段是否能正常輸出調(diào)試信息。因JIT編譯失敗時會輸出字符串形式的異常，本文通過實驗確定異常信息和調(diào)試信息字段的匹配關系，并將這一關系加入白名單中，以實現(xiàn)漸進式調(diào)試輸出。

對于編譯失敗時錯誤診斷輸出功能羸弱的問題，本文針對JIT編譯失敗時的異常處理機制，對每一處可能產(chǎn)生異常的代碼位置進行異常信息完善，使異常信息所描述的錯誤更為精確，同時攜帶導致該異常的Octave源代碼位置及用戶代碼位置信息。

3.3 JIT編譯器功能和性能評估

目前Octave JIT編譯器僅可對循環(huán)語句進行JIT編譯。本文從循環(huán)類型和循環(huán)體內(nèi)容2個方面對JIT編譯器進行測試。循環(huán)類型包括次數(shù)固定的循環(huán)與次數(shù)不定的循環(huán)，而循環(huán)體內(nèi)容包括3個方面：

(1)順序語句、條件語句和循環(huán)語句3種基本的流程控制語句；

(2)對實數(shù)標量和復數(shù)標量、實數(shù)矩陣和復數(shù)矩陣的操作，如算術邏輯運算操作、索引操作等；

(3)函數(shù)調(diào)用，包括內(nèi)置函數(shù)和用戶定義函數(shù)。

本文針對上述分類編寫了測試樣例，對Octave JIT編譯器的功能和性能進行評估。測試結果顯示，一部分樣例可以進行JIT編譯并正常運行，其他樣例則在編譯或運行中出現(xiàn)了錯誤。

成功編譯的樣例的測試結果如表2所示。其中，樣例的JIT編譯前用時指在未經(jīng)過JIT編譯時，樣例代碼由Octave解釋器執(zhí)行的運行時間。樣例的JIT編譯后用時指經(jīng)過JIT編譯后樣例的運行時間，包括樣例代碼的JIT編譯用時和JIT編譯后的機器指令執(zhí)行用時。樣例獲得的加速比由其JIT編譯前、后用時的比值得出。表2中的數(shù)據(jù)均保留3位小數(shù)。

Table 2 Running time and speedups before and after JIT compilation

JIT編譯成功并正常運行的樣例根據(jù)測試內(nèi)容分為4類：

(1)順序語句、條件語句和循環(huán)語句3種基本的流程控制語句；

(2)對實、復數(shù)標量的算術邏輯運算操作；

(3)對矩陣的單維索引操作；

(4)對極少數(shù)內(nèi)置函數(shù)的調(diào)用操作。

根據(jù)測試結果中的加速比將樣例分為4類，如圖5所示。

Figure 5 Classification of test case speedups

加速比在均值140倍左右的情況，可視為JIT編譯消除了代碼解釋開銷所獲得的普遍性能提升。加速比達240倍以上的最佳情況對應于條件判斷有關的測試。取得了比均值情況更佳的加速效果，原因是JIT編譯不但去除了代碼解釋開銷，而且代碼被JIT編譯成機器語言后可以充分利用現(xiàn)代處理器的分支預測技術。加速比僅有20～50倍的情況對應于乘方和索引有關的測試。這是由于乘方和索引計算本身開銷更大，JIT編譯所消除的代碼解釋開銷帶來的整體加速效果弱于均值。加速比小于10倍的樣例則與內(nèi)置函數(shù)調(diào)用操作有關。由于當前Octave JIT編譯器對內(nèi)置函數(shù)調(diào)用的低效實現(xiàn)方式，導致了JIT編譯對內(nèi)置函數(shù)調(diào)用操作的加速效果十分有限。

4 Octave JIT編譯器性能優(yōu)化

本節(jié)基于前述工作對Octave JIT編譯器進行優(yōu)化，然后以優(yōu)化特性實驗和LU分解實驗來驗證性能優(yōu)化效果,最后分類總結優(yōu)化后的Octave JIT編譯器的缺陷，為未來工作指明方向。

4.1 內(nèi)置函數(shù)調(diào)用優(yōu)化

在第3節(jié)的測試中，因調(diào)用內(nèi)置函數(shù)導致JIT編譯失敗的測試樣例可以分為2類：(1)JIT編譯成功，但執(zhí)行時產(chǎn)生段錯誤的樣例；(2)完全不支持JIT編譯的樣例。本節(jié)針對這2類樣例中存在的問題對Octave JIT編譯器進行優(yōu)化。

本文通過進一步研究發(fā)現(xiàn)，樣例執(zhí)行產(chǎn)生段錯誤是因為函數(shù)特化過程中出現(xiàn)了函數(shù)重名問題。內(nèi)置函數(shù)的JIT編譯支持的實現(xiàn)方式分為2種：(1)將函數(shù)特化為LLVM的內(nèi)置函數(shù)；(2)調(diào)用Octave解釋器來執(zhí)行其原有的內(nèi)置函數(shù)。函數(shù)被特化為Octave內(nèi)置函數(shù)時，由于函數(shù)名與LLVM內(nèi)置函數(shù)重名，被LLVM錯誤鏈接到了LLVM內(nèi)置函數(shù)的符號地址。在運行時，該函數(shù)的輸入輸出為Octave的數(shù)據(jù)類型且不被LLVM內(nèi)置函數(shù)所支持，因此出現(xiàn)了段錯誤。在函數(shù)被特化為Octave內(nèi)置函數(shù)時，可以通過在函數(shù)名上與LLVM內(nèi)置函數(shù)進行區(qū)分的方式來修復這一漏洞。

由于JIT編譯器直接調(diào)用解釋器內(nèi)置函數(shù)實現(xiàn)的加速效果有限，LLVM內(nèi)置函數(shù)的支持也有限，故利用C/C++編寫外部函數(shù)是為內(nèi)置函數(shù)添加JIT編譯支持的一種高效方式。

因此，本文新增了對內(nèi)置函數(shù)特化為C語言函數(shù)的支持。LLVM的JIT執(zhí)行引擎維護了一個全局映射表，可向全局映射表中添加指定的全局映射。故若要添加在JIT執(zhí)行引擎中可調(diào)用的C語言外部函數(shù)，可顯式地將外部函數(shù)指針作為全局符號地址添加至JIT執(zhí)行引擎中。

基于上述工作，本文完成了對更多內(nèi)置函數(shù)的JIT編譯支持，如表3的第1～21行所示。

4.2 索引運算與算術邏輯運算的類型支持擴展

本節(jié)以range類型的索引賦值運算實現(xiàn)為例，說明對索引運算的類型支持擴展；以range類型和標量的加法運算操作實現(xiàn)為例，說明對算術邏輯運算的類型支持擴展。

4.2.1 range類型索引賦值運算實現(xiàn)

因range類型可簡化向量化語句與固定步長的循環(huán)編寫，故支持range類型的索引操作意義重大。range類型是Octave中表示范圍的數(shù)據(jù)類型，以C++類的形式存儲，其設計如表4所示。

實現(xiàn)任意類型的索引操作的整體思想和注冊函數(shù)的思想一致。此處可分為2步：(1)編寫C++/LLVM形式的JIT函數(shù)，在其內(nèi)部完成對相應類型的索引操作；(2)將該函數(shù)添加至小括號索引取值運算符的重載函數(shù)列表中。

就range類型的索引賦值操作而言，其過程可分為索引值合法性檢查、range類型到matrix類型的類型轉(zhuǎn)換操作的支持和Octave JIT編譯器的類型格的修改3個部分。

依據(jù)range類的成員變量的當前設計，該類型并不實際存儲任何索引位置所對應的值，無法實現(xiàn)對任意位置的賦值操作。故在其索引賦值操作中，需在賦值前將range類型轉(zhuǎn)化為matrix類型，從而利用matrix類型支持隨機存取的特性完成這一操作。其中，索引值合法性檢查操作在索引值為非整數(shù)或小于1時報告無效索引值錯誤。特別地，索引值越界不會被視為錯誤，因為新生成的matrix長度可由原range類型的長度和索引值中的較大者決定。若索引值更大，以零填充的方式對matrix擴容部分的內(nèi)存空間進行初始化。

Table 3 Running time and speedups of optimization features before and after JIT compilation

Table 4 Member variables of range class

在將range類型變量轉(zhuǎn)換為matrix類型變量后，SSA形式的Octave JIT IR在循環(huán)體首部插入的φ函數(shù)將會對該變量的2處來源進行合并，即將循環(huán)外部得到的range類型和循環(huán)尾部回傳的matrix類型進行合并。然而，在當前Octave JIT類型系統(tǒng)的類型格中，matrix類型與range類型不存在偏序關系，這將導致類型合并后得到的最終類型為any類型，而非matrix類型。因此，需要對類型格進行相應修改，添加matrix類型與range類型的偏序關系，以支持range類型索引賦值操作。修改后的類型格如圖6所示。

Figure 6 Modified type lattics of Octave JIT compiler

4.2.2 range類型與標量的加法運算操作實現(xiàn)

對雙目運算符AST進行代碼生成的過程可分為3個步驟：首先，將訪問者模式與遞歸技術結合，為該AST節(jié)點的左子樹和右子樹進行代碼生成，從而得到該雙目運算符的左值和右值；然后，查找記錄運算符與具體操作的映射信息，得到當前雙目運算符對應操作函數(shù)；最后，將上述左值和右值作為對應操作函數(shù)的參數(shù)，生成對該函數(shù)調(diào)用的語句，即可生成該雙目運算符對應的Octave JIT IR。

因此，新增的雙目運算操作可分為以下2步：(1)實現(xiàn)該雙目運算符對應的操作函數(shù)；(2)記錄該雙目運算符與上述函數(shù)的映射信息。

利用LLVM IR Builder編寫LLVM函數(shù)，可以實現(xiàn)range與標量的加法運算。在該函數(shù)中，僅需實現(xiàn)成員變量base和limit與標量的加法，并保持inc不變即可。函數(shù)編寫完畢后，記錄該函數(shù)與雙目加法操作符的映射信息。此外，應進行溢出檢查。當成員變量base、limit和inc3者之一的值為inf時，應先將range轉(zhuǎn)換成matrix，再計算其與標量的和。此時部分未溢出的元素正常計算得到結果，而溢出部分的元素標記為inf。

同理可實現(xiàn)range的其他運算操作，如表3的第28～35行所示。

4.3 優(yōu)化特性實驗結果與分析

實驗環(huán)境的系統(tǒng)架構中，包含了2個關閉超線程的18核Intel(R)Xeon(R)Gold 6150 CPU，所有核心鎖定2.70 GHz主頻；共享192 GB內(nèi)存；操作系統(tǒng)為CentOS Linux release 7.6.1810。

本文對優(yōu)化特性分別進行迭代測試，迭代次數(shù)為213～224。測試重復執(zhí)行10次，將其中得到的最小JIT編譯前用時、最小JIT編譯后用時分別保留，并由二者的比值得到加速比。測試參數(shù)中，矩陣均為10階方陣，range值為1∶1000。表3展示了迭代次數(shù)為224的測試結果。圖7～圖9分別展示了JIT編譯前用時、JIT編譯后用時、加速比的測試結果。其中圖7～圖9的樣例編號所對應的測試內(nèi)容如表3所示，圖中的橫縱坐標軸是以2為底數(shù)的對數(shù)坐標軸。

如圖7所示，每個樣例的JIT編譯前用時與迭代次數(shù)呈線性關系。此時樣例代碼由解釋器執(zhí)行，解釋器執(zhí)行每條語句的時間恒定，從而每輪迭代的時間恒定，樣例的執(zhí)行效率不會隨著迭代次數(shù)增加而出現(xiàn)明顯變化。

Figure 7 Running time of optimization features without JIT compilation

JIT編譯后用時由JIT編譯用時和機器指令執(zhí)行用時組成。如圖8所示，隨著迭代次數(shù)的增加，機器指令執(zhí)行用時增加，而JIT編譯用時不變，使得JIT編譯后用時增加。若迭代次數(shù)較少，此時JIT編譯用時遠大于機器指令執(zhí)行用時，則迭代次數(shù)增多導致的機器指令執(zhí)行用時增加，對樣例總運行時間的影響十分微小。若迭代次數(shù)足夠多，使得機器指令執(zhí)行用時遠大于JIT編譯用時，則樣例總運行時間與迭代次數(shù)在對數(shù)坐標系下幾乎呈線性關系。

Figure 8 Running time of optimization features with JIT compilation

從圖9可看出，JIT編譯所帶來的加速效果隨迭代次數(shù)的增加逐漸提升且最終趨于穩(wěn)定。當?shù)螖?shù)增加至224時，可視為對每個樣例的JIT編譯均達到了最佳效率。此時JIT編譯的加速效果如表3所示，表3所展示的數(shù)據(jù)均保留了3位小數(shù)。其中，“實現(xiàn)方式”和“加速比”2列預示使用LLVM和C++編寫的JIT函數(shù)取得的加速效果相近。例如，樣例1和樣例3是特化為LLVM內(nèi)置函數(shù)的實現(xiàn)，樣例10是使用C++編寫的函數(shù)作為外部函數(shù)的實現(xiàn)，二者均取得了260倍以上的加速效果。因而本文額外將樣例1和樣例3等使用LLVM實現(xiàn)的標量操作改為使用C++標準庫函數(shù)實現(xiàn)，得到了與使用LLVM實現(xiàn)相近的JIT編譯后用時與加速比。

Figure 9 Speedups of optimization features with JIT compilation

從表3可以看出，直接調(diào)用Octave解釋器原有函數(shù)實現(xiàn)的JIT函數(shù)取得的加速效果不佳。實際上，此類優(yōu)化特性在JIT編譯前后調(diào)用的是同一個內(nèi)置函數(shù)實現(xiàn)，因而開銷最大的函數(shù)體執(zhí)行時間是相同的，只是因為JIT編譯減小了解釋開銷，從而取得了一定的性能提升。此外，以上優(yōu)化特性中部分函數(shù)的C++實現(xiàn)與Octave解釋器原有實現(xiàn)相同，將此類函數(shù)的JIT實現(xiàn)方式改為直接調(diào)用Octave解釋器函數(shù)，后者的JIT函數(shù)加速比最高僅為10倍，這表示當前Octave JIT編譯器調(diào)用解釋器函數(shù)的實現(xiàn)方式并不高效。

總之，測試結果說明了JIT編譯器的加速規(guī)律：將Octave內(nèi)置函數(shù)特化為LLVM函數(shù)的加速比，與特化為C++實現(xiàn)的外部函數(shù)的加速比相似，且遠遠大于調(diào)用原有的Octave內(nèi)置函數(shù)得到的加速比。該規(guī)律也為未來的工作指明了方向：為取得更好的JIT加速效果，應把原本直接調(diào)用Octave內(nèi)置函數(shù)實現(xiàn)的JIT函數(shù)改為使用LLVM或C++實現(xiàn)。

4.4 LU分解實驗結果與分析

矩陣LU分解是常見的基準測試之一，MATLAB[10]和Linpack[11]均使用LU分解進行性能測試。本節(jié)以LU分解作為基準測試，對上述Octave JIT編譯器性能優(yōu)化進行驗證。由于Octave內(nèi)置的LU分解函數(shù)通過調(diào)用LAPACK庫函數(shù)實現(xiàn)，使用Octave內(nèi)置的LU分解函數(shù)無法有效驗證Octave JIT編譯器性能優(yōu)化的效果。為此本文使用Octave代碼實現(xiàn)了LU分解函數(shù)，并以此為基準測試，驗證本文對Octave JIT編譯器的性能優(yōu)化效果。

上述LU分解函數(shù)采用杜爾里特算法(Doolittle algorithm)[12]實現(xiàn)，對于n階方陣，該算法的時間復雜度為O(n3)。基準測試分為2部分:(1)固定矩陣階數(shù)為10階，改變實驗的迭代次數(shù)，實驗結果如圖10所示；(2)固定迭代次數(shù)為2 048次，改變實驗的矩陣階數(shù)，實驗結果如圖11所示。與前述實驗不同，由于LU分解計算量大，單次迭代用時長，故采用以固定步長遞增的迭代次數(shù)，而非以指數(shù)形式遞增的迭代次數(shù)。因此，本節(jié)實驗結果的展示使用普通坐標。

Figure 10 Running time and speedups of LU decomposition with different number of iterations

Figure 11 Running time and speedups of LU decomposition with different matrix order

圖10展示的不同迭代次數(shù)下的實驗結果與4.3小節(jié)的優(yōu)化特性實驗結果相符。圖10a表明，LU分解函數(shù)的JIT編譯前、后用時與迭代次數(shù)均呈線性關系，且JIT編譯后用時遠小于編譯前用時。圖10b表明，隨著迭代次數(shù)的增加，JIT編譯的加速比從43倍上升到了62倍，并最終趨于穩(wěn)定。

為便于實驗結果分析，圖11a中展示的JIT編譯前、后用時采用了立方根用時。圖11a表明，LU分解函數(shù)的JIT編譯前、后的立方根用時與矩陣階數(shù)呈線性關系。這是由于對該函數(shù)實現(xiàn)而言，增加矩陣規(guī)模實際上是增加迭代次數(shù)，且該函數(shù)的時間復雜度為O(n3)。圖11b說明，隨著矩陣階數(shù)的增加，JIT編譯加速比從3倍增加到了66倍，并最終趨于穩(wěn)定，且穩(wěn)定值高于圖10b中的穩(wěn)定值62倍。其原因為：當矩陣規(guī)模變大時，該算法內(nèi)部的迭代次數(shù)增多，對最外層的單次迭代而言，解釋器執(zhí)行用時與JIT編譯后的機器指令執(zhí)行用時均增加，但解釋器執(zhí)行用時的增加速度大于機器指令執(zhí)行用時的增加速度。

4.5 Octave JIT編譯器現(xiàn)有缺陷

基于前文的分析和評估工作，本文對Octave JIT編譯器完成了部分優(yōu)化工作，未來工作中將進一步對Octave JIT編譯器進行性能優(yōu)化。為此，本文分類總結了Octave JIT編譯器的現(xiàn)有缺陷，如表5所示。

Table 5 Defects summary of Octave JIT compiler

缺陷1：指Octave JIT編譯器不支持對命令窗口(含控制臺)中執(zhí)行的語句進行JIT編譯，而僅支持“.m”文件的JIT編譯。

缺陷2：指原Octave內(nèi)置的JIT編譯器代碼組織凌亂、雜糅，將本不耦合的代碼置于同一個代碼塊中。加之缺陷3中描述的文檔與注釋的缺乏，源碼分析過程存在很大阻礙。

缺陷4：指Octave JIT編譯器僅支持對循環(huán)語句進行JIT編譯，僅利用循環(huán)語句自身的信息會喪失大量編譯優(yōu)化空間。

缺陷5：指Octave JIT編譯器不支持“parfor”循環(huán)并行語句。Octave解釋器已在語義分析階段生成“parfor”語句對應的Octave AST，但Octave JIT編譯器并未對該AST進行代碼生成。

缺陷6：指Octave JIT編譯器在對循環(huán)進行JIT編譯時，其邊界檢查條件冗余，在一定情況下可以消除或簡化。

缺陷7：指Octave JIT編譯器在循環(huán)的入口和出口處，均會對矩陣一類的大型對象進行拷貝構造，這是無意義的內(nèi)存拷貝。

缺陷8：指Octave解釋器與JIT編譯器均存在內(nèi)存泄漏問題。借助內(nèi)存泄漏檢測工具Valgrind，可發(fā)現(xiàn)解釋器本身存在少量內(nèi)存泄漏，而JIT編譯器存在更多的內(nèi)存泄漏。

缺陷9：指Octave JIT編譯器僅支持對矩陣和range類型的單維索引，多維索引、切片索引和cell類型的索引操作均不支持。

缺陷10：指Octave JIT編譯器無法充分利用上下文信息對索引時的索引值檢查進行優(yōu)化，其合法性檢查在部分情況下可由LLVM本身實現(xiàn)，而目前的實現(xiàn)方式均是通過調(diào)用外部函數(shù)實現(xiàn)的。

缺陷11：指Octave JIT編譯器的類型支持并不完善，許多Octave原生數(shù)據(jù)類型并未得到JIT編譯器的支持。此外，當前類型系統(tǒng)的類型格并不符合類型的實際意義，例如在類型格中int類型與scalar、complex類型均不存在偏序關系。

缺陷12：指Octave JIT編譯器對2類Octave內(nèi)置函數(shù)的支持均十分有限。幾乎所有使用Octave語言實現(xiàn)的、以“.m”文件形式存在的內(nèi)置函數(shù)均無法進行JIT編譯；而JIT編譯器直接調(diào)用由C++實現(xiàn)的、硬編碼在Octave解釋器中的內(nèi)置函數(shù)取得的加速效果最高不過10倍，無法在具體實踐中應用。

缺陷13：指Octave JIT編譯器對大部分數(shù)據(jù)類型的運算操作支持有限，除本文完善的range類型運算外，僅對scalar類型的支持比較完善。

缺陷14：指Octave JIT編譯器未實現(xiàn)函數(shù)重載機制，無法基于類型格中的偏序關系完成隱式類型轉(zhuǎn)換。

缺陷15：指Octave JIT編譯器未完全實現(xiàn)AST到JIT IR的轉(zhuǎn)換。如異常處理中的try catch表達式、函數(shù)的多返回值、多返回值對應的多賦值等多種語句的轉(zhuǎn)換均不支持。

缺陷16：指Octave JIT編譯器未對體系結構進行檢測，而是完全假設目標環(huán)境為X86或X86_64。

5 結束語

本文探究了Octave內(nèi)置JIT編譯器的性能優(yōu)化方案，通過提高該JIT編譯器的性能，提升Octave整體的運行效率。本文首先對Octave的內(nèi)置JIT編譯器進行了整體編譯流程分析，并著重分析了該JIT編譯器的類型推斷系統(tǒng)。其次，通過不同類別的樣例對Octave JIT編譯器進行了功能和性能分析，指明了本文的優(yōu)化方向。然后，針對內(nèi)置函數(shù)調(diào)用、索引運算和算術邏輯運算的類型支持2個重點，對該JIT編譯器進行了優(yōu)化。實驗結果表明，本文的優(yōu)化工作擴展了Octave JIT編譯器對Octave代碼的適用范圍，從而有效提升了Octave數(shù)值計算的性能。最后，本文總結了Octave JIT編譯器的現(xiàn)有缺陷，未來將針對這些缺陷開展更多優(yōu)化工作。