談 VM 設計: Ruby YARV 與 PHP Zend Enginec9sBlockedUnblockFollowFollowingFeb 6昨晚空閒時間讀完了一本談 Ruby VM (Virtual Machine) 的書。其實程式語言的虛擬機 （Language Virtual Machine） 的設計大多類似，不過還是有許多思想上的不同。YARV 的設計者為 笹田 耕一 (Koichi Sasada)，當時在 2003–2004 年讀碩士時分開發 Ruby VM (YARV) ，後來 Matz 在 2007 年左右讓 Ruby 1.
9 採用 YARV 這套 Virtual machine。發展時間來看，YARV 比 PHP 第二代的 Zend Engine 的推出晚了幾年 (Zend Engine 為 2004 年左右)。在 Ruby 1.
9 之前，Ruby 開發者們使用的 Ruby 直譯器是一個被稱為 MRI 的直譯器，MRI 為 Matz’s Ruby Interpreter 之簡稱。 MRI 的運作方式比起 VM 簡單很多，將 Ruby 代碼編譯為 AST (Abstract Syntax Tree) 之後，MRI 直接拜訪 AST 中的每個節點做運算，因此效能非常差，在採用 YARV 之後，執行效能因此有很大的進展。設計以 YARV (Yet Another Ruby VM) 的設計來說，比起 PHP 的 Zend Engine ，更貼近 Stack-based Machine 的運作方式，大多數的操作是將參數推進堆疊，然後運算。 Zend Engine 則偏向以虛擬的記憶體位址做操作，讓 op code 直接存取記憶體裡的變數來做運算。在 YARV 裡，所謂的 op code 被稱為 YARV Instruction，而一連串的 op code 被稱為 iseq (instruction sequence)。 在 Zend Engine 裡，op code 就叫做 op code，一連串的 op code 被放在一個 op_array 裡。YARV 的設計使用了兩種不同的堆疊 (Stack)，第一種堆疊為計算用，用來虛擬一般 Stack-based machine 的運算，第二個堆疊用來處理 Function Call 的 Frame，稱為 Control Frame。每個 Control Frame 基本上對應的就是每個執行區段的 Scope，譬如說 Block, Function, Method 等等。 Control Frame 裡面還會儲存 SP (Stack Pointer), EP (Environment Pointer) 甚至 PC (Program Counter) 以及一個用來查找 Local Variable 專用的 Symbol Table 稱作 Local Table。 最後，會有一個 CFP (Current Frame Pointer) 指向到現在這個 Control Frame 的位址。由於 Ruby 語法的多樣性，Control Frame 本身為了支援各種不同的 Invocation，共有 11 種呼叫類型。指令執行YARV 在運算的時候，首先會利用 getlocal 將 Control Frame 裡面的變數，推送到堆疊上，接著使用 send instruction 去觸發運算，計算完的結果會存在 Stack 裡，要修改 Stack 上的變數，則使用 setlocal。然而，這樣的缺點在於，需要運算的參數越多，就需要執行更多的指令，來將數據推上堆疊，才可以運算。Zend Engine 對運算的操作省略了 YARV 的第一種計算用堆疊，編譯後的 Instruction 採用 SSA (single static assignment) 的方式產生中間碼 (Intermediate Representation)。這邊和讀者解釋一下，所謂 SSA 的方式是以 three address code 為基礎做的變化，three address code 將每個 instruction 分成三個位址，兩個位址用來儲存運算數的位址，一個位址用來儲存計算結果的位置。SSA 就是這個結果位址的分配絕對不會重複使用，方便用以分析優化。 在 Zend Engine 裡面的 instruction 可以直接存取真實對應的變數，或是存取 CV (Compiled Variable) 編譯後的暫存變數位址做計算，因此比起 YARV，省去了不少 op code 做堆疊的操作。因為 YARV 有越多變數要存取，就必須要執行更多的 instruction 來將變數存入堆疊。從另外一方面來說，雖然說是虛擬的堆疊操作，但在做 JIT (Just-in time) 編譯的時候，更方便能編譯為 native machine 的 native instruction。上面提到， YARV 使用了 Control Frame 的概念，其實在 Zend Engine 與 JVM 裡也是一樣，在 Zend Engine 裡面也有所謂 Call Frame 的 C 語言結構，其目的與 YARV 是一樣的。Zend Engine 與 YARV 的最大差異在於 Zend Engine 的 Call Frame 裡，沒有 EP (Environment Pointer)。YARV 因為不是 Memory-based Machine，需要所謂的 Environment Pointer 來指向到不同的 Control Frame ，用以存取變數。 YARV 使用 Environment Pointer 的這個概念最早是從 Lisp 來的，Sussman and Steele 在 1975 年定義了 Closure:In order to solve this problem we introduce the notion of a closure [11, 14] which is a data structure containing a lambda expression, and an environment to be used when that lambda expression is applied to arguments.
而 YARV 在使用 getlocal instruction 時，第二個參數就是 environment pointer 的 offset，透過這個 offset 可以存取到 parent control frame 裡的 Stack 的變數。 也就是，Ruby Block 執行時，Block 底層的結構 rb_block_t 可藉由 EP 來存取 parent scope 變數。雖然在實作函數呼叫上， Ruby 的 Control Frame 與 Zend Engine 的 Call Frame 很類似，但是還是有不少不同的地方： Ruby 支援所謂的 keyword arguments，顧名思義就是除了使用傳統的參數傳遞 (positional arguments)，使用者還可以使用參數的名稱來傳遞參數。不幸的是， Ruby 並沒有針對 keyword arguments 加入些魔法，當你使用 keyword arguments 來呼叫函數時，實際上 Ruby 的 YARV 會將程式碼編譯成多個 instruction，並另外建立一個 Ruby Object 來操作這個 keyword arguments。 簡單的說，Ruby keyword arguments 是儲存在 Ruby Object 裡，如果再加上 argument 的 default value，就需要再多幾道指令 (instruction) 來檢查 key 是否存在。根據試驗，一個兩個參數的函數，第二個參數使用 keyword argument 並加上 default value，則產生出來的指令數量會比不使用 keyword argument 多 出 13 道指令。物件系統在物件系統的設計上，雖然兩者因為語言設計的極度不同，但底層實作還是有非常相似的地方。 Virtual machine 在實作物件系統上，基本上都逃避不了使用大量的雜湊表 (Hash table) 來做方法查找 (method lookup) 與屬性查找 (property lookup)。 不過 Ruby 本身為了達到萬物皆物件的理想，簡單型別 (Simple Type) 也是物件，為了要能夠有效率的讓簡單型別的數據也可以快速做運算，YARV 採用了不同的方式做處理。 在 Ruby 裡，簡單數值 (Simple value) 都被存放在 RValue 的結構中，通過特殊旗標 (Flag bits) 的設定，讓 Simple value 可以直接對應到 YARV 內建的基礎類別，譬如 FIXNUM 提供了 times 的 method… 等等。在 Hash Table 方面，YARV 採用的 Hash algorithm 為 Peter Moore 於 1980 年在柏克萊寫的 C library，Ruby core team 以此為基礎另外做了修改。而將 Ruby Value 轉為 Hash 的部分， YARV 採用了 Austin Appleby 於 2008 寫的一個稱為 MurmurHash 的函數。 Ruby 1.
9 and 2.
0 會在 VM 啟動時，重新產生這個雜湊種子，因此每次重新啟動，同樣的 Ruby Value 都會產生出不同的雜湊值。動態方法查找多數的 Language Virtual Machine 之所以慢，其實最主要最主要還是在動態方法查找上消耗了太多時間 (Class 的 method lookup 需要層層遞迴查找)，也因此 YARV 也實作了 method lookup cache，基本上 cache 分為兩種，一種是 Global method cache，另一種是 Inline Method Cache。Global method cache 顧名思義，就是全域的 method lookup cache，其實演算法沒有什麼太複雜的地方，就是查過的 key，就將其對應的 pointer 儲存起來，下次可直接使用。 而 Inline method cache 則是將找到的 method 位址，直接儲存在 YARV Instruction 裡面。最後，本來還想要寫一下 Zend Engine 對於 method lookup 的優化 (optimization)，不過筆電快沒電了，等下次有機會再說吧。#全域一直被打成痊癒有夠煩 #倉頡大易學了幾百年一直都沒有學到能派上用場 LOL.