2015年3月2日 星期一

Lars Bak 談 JavaScript V8 virtual machine 的設計

Lars Bak 談 JavaScript V8 virtual machine 的設計:
其中 Lars 有談到 V8 不使用 byte code,你能夠執行 JavaScript 唯一的方式就是透過 native code,所有的程式都是先編譯後執行,沒有解譯:
"There is no interpretation and no bytecode."
V8 不像其他 VM 是透過 bytecode 或是像 JVM 有 HotSpot 有多種方式執行程式,如在 interpreter 或 native code 之間切換。Lars Bak 開玩笑的說,Developer 在改 V8 compiler 的時候,他們看到這些 native code ... will be horrified.
直接在執行期間 compile 成 native code 執行的這個設計與一般 VM 大相逕庭,因為不管是 JVM, PHP, Python, Ruby, C# 都是透過 Byte code 做 interpretation,而這點引起了 Erik Meijer 不理解而提出質疑。
Lars Bak 解釋道 「若我們設計了 IR (Intermediate Representation) 中介表示,我們就必須對這些 IR 做驗證 (validation),然而驗證 IR 是非常複雜的,譬如驗證 Byte code 是否有 Violation 等等。 譬如說 JMP,你必須驗證 JMP 的位址是正確的,否則會有安全顧慮。 」
而我認為這是沒錯的,一般 Interpreter 儲存 op list 於 HEAP 中,只需 RW 權限即可竄改 op list,但 V8 是在用戶端執行的,你很難保證在用戶端的環境的安全性是足夠的,我猜這是 Lars Bak 過去在 Sun microsystem 做 JVM 以來的經驗。 Lars Bak 不僅為了高效能設計 V8 而也兼顧了安全性。
話說,翻了幾個 VM 的 source code,不管是 cpython, perl, cruby ,目前覺得還是 V8 的架構最優、workaround 最少、最簡潔,完全是不同等級的實作

同步刊載於 C9S 開源電台

2015年2月27日 星期五

asmjit 與 libjit

大略翻了 asmjit [1] 與 libjit [2] 的實作,大概簡介一下兩者差異:
asmjit 是針對 x86 平台所做的 just-in-time toolkit,可以在 runtime 進行組語編譯並執行,分成兩種 compilation method:
.
1. Assembler: 直接使用 x86 instruction 撰寫編譯,必須寫清楚 register, memory 等 operand。
2. Compiler: 使用抽象化語法進行編譯,不需自己管理暫存器。
.
其中抽象化語法可直接使用 Variable 並且由 Compiler 自行分配暫存器,超出的部分會自動使用 Stack 的空間。

而其語法其實就是 C++,通過調用 FunctionBuilder 來建置 Function ,最後丟給 Compiler 編譯後即可使用,但 Register Allocation 的部分分析能力不強,因此作者建議若有自己做 Analysis 的話,建議還是直接使用 Assembler。 由於是 C++ 實作,asmjit 語法簡潔有力。對 x86 機器的實作算很完整。

而 libjit 較為複雜些,libjit 使用 C 語言實作,編譯單元為 Function,用法類似 asmjit 定義 Function 的方式,但定義起來較為繁瑣。 除了抽象化 opcode 來達到跨平台的目的 (目前支援 arm, x86, x86-64),還實作了 data flow analysis, control flow analysis 來做優化,優化的部分則可以指定等級。

其中 CodeGen 的部分,居然自己定義了一套 DSL 的 parser 來產生類似 LLVM Instruction Table 的定義檔... 完全不容小覷。 據我與 Marttia Barbon 通信內容了解,libjit 產生的 machine code 並不太優。

libjit 中 x86 instruction assembler 的部分,是直接使用 C function 來達成 position independent instruction 的編譯:

    x86_mov_reg_reg(buf, X86_EBP, X86_ESP, 4);

要使用 libjit 來建置一套 language VM 應該是足夠的,只不過 libjit 最近較無積極開發,最近一年的 commit 幾乎都是修正。

2015年2月25日 星期三

CLIFramework - Table Generator

CLIFramework 現在內建 Table Generator,只要輸入 Array,可自動依照不同的 Style 產生 Console 用表格,甚至能輸出成 Markdown 格式表格 (使用 MarkdownStyleTable class)

此套件是參考 Symfony/Console 的 Table Helper 部分功能的重寫及加強,除了 Symfony/Console 現有功能之外:

還可透過指定格屬性 (Cell Attribute),針對單一格或一整列設定色彩、文字對齊或數字格式 (Currency, Number, Duration .. etc)

至於超出欄寬的文字,也可指定使用切斷 (clip), 省略符號 (ellipsis) 或換行 (wrap)

請見範例程式:
https://github.com/c9s/CLIFramework/blob/master/example/table.php


畫面:


2015年2月10日 星期二

閒暇時大致研究了幾個 JIT compiler 實作:

V8 當然不用說,不僅實作了好幾種 CPU 架構的 runtime assembler ,還做了 dynamic re-compilation (Crankshaft engine) 針對 hot code 做 re-compilation。

而 Steffen Müller (@tsee) 的 jit-experimental for Perl 則是將 Perl5 op tree 建構成 libjit 看得懂得 AST,接著丟改 libjit 翻譯回來拿到 machine code,細節沒有看很多,但我猜這個 runtime overhead 一定是很高...
其他使用的 libjit 的 project 則幾乎都是 experimental projects,沒有看到其他使用 libjit 成功的案例。

Reini Urban (@rurbanJit.pm 實作,是把固定幾個 x86 instruction 的 machine code 直接寫成 macro 來使用 (如: x86 prolog, epilog, call, jmp, pushl, popl 等等),然後在模組載入後,把 Perl 的 run op 函數指標 (function pointer) 換成 Jit.pm 自己的實作,接下來就是把一些簡單的 op code 換成預先準備好的 machine code 執行。 但 Jit.pm 一執行就 crash 了..... orz

不過 Jit.pm 也教我幾件事情:
1. memalign 要處理好,不然沒有辦法設置 memory protection
2. self-modifying code 需要呼叫 sys_mprotect 這個修改 page 的 flags ,才能在調用來的記憶體上執行 machine code。
3. Perl 5 有 ASYNC flag (看起來是做 JIT 特別難處理的地方)

現階段看起來,JIT 實作的最佳參考還是 V8
就這樣,有其他細節再繼續做整理...

(以前實在太弱,寫什麼 SIC/XE assembler... 現在覺得當時應該接著練習自幹 x86 assembler 比較實際...)

2015年2月8日 星期日

Getting Merged

昨天在 livehouse 的簡報。但有些內容是現場講的,沒報名到的朋友搜瑞了


libjit 的作者 Rhys Weatherley (dotGNU 的 member) 2009 年時寫到:
"LLVM seems to have been started as a "glorified" static compiler....which aims to (略).... It has been started in 2000, and as of today it is technologically outdated. "
哇....這不是睜眼說瞎話嗎? XD

2014年9月25日 星期四

HHVM 及 Hack 的相容性

最近筆者開始嘗試 HHVM 應用於 Production 環境,一些心得如下:


1. Linux

現有的 Linux Distribution 幾乎都有 pre-built 套件,可直接安裝,就算要自行編譯也沒有太大的問題。 Facebook 的 HHVM Team 主要都還是 Focus 在 Linux Server 上的相容性。在 Linux 平台上編譯,可參考官方的 WIKI 文件


2. Mac OS X

Mac OS X 上 HHVM 的相容性比以往提昇許多,過去要自行 patch 許多套件編譯,現在只需要 patch jemalloc 即可。且幾乎所有相依套件皆可用 Homebrew 或 Macports 安裝。

目前 HHVM 的版本 HHVM 3.2 確定可於 Mac OS X 上編譯,只不過需透過 GCC 4.8 而非 Mac OS X 內建的 clang,相依的 Boost 套件也需由 GCC 4.8 編譯才行。

至於 master branch 目前 third-party 的 folly package 由於使用了 Linux 上的 Futex,因此目前唯一可在 Mac OS X 上編譯的版本就只剩 3.2。 不過也有人開始了 Mac OS X 平台上的編譯修正,可參見 @mcuelenaere 的 HHVM osx-fixes 分支,以及 @bsampathfolly 修正

至於 3.2 版本 Mac OS X 上的編譯步驟,可參考此處


3. Hack Programming Language

至於 Facebook 的 Hack programming language 幾乎與 PHP 相容,原本的 PHP source code 只需要修改標頭,將 <?php 改為 <?hh 即可當做 Hack 執行,因此由 PHP 換用到 Hack 幾乎是無痛轉移。

至於使用 Hack 有何好處?一來是提供型別檢查,方便開發時及早發現問題,二來依照型別資訊可大幅提昇 VM 效能,三來可以提供準確的自動補齊並與編輯器或 IDE 做整合。

Hack 的剖析工具是用 OCaml 寫的,可直接和 IDE 整合,如 Vim plugin 有 vim-hack (https://github.com/hhvm/vim-hack) 可使用。Emacs 則有 hack mode 可用 (https://github.com/facebook/hhvm/tree/master/hphp/hack/editor-plugins/emacs)。

待續


2014年8月27日 星期三

談 Git 的 Graft Points 及 git-replace

git merge --squash [branch] 可以將分支的修改全數合併至同一個 commit 但不會保留合併資訊,不過若是該分支持續開發,勢必會再次合併至主幹,這時如果重新使用 git merge --squash ,則已經合併過的 commit 也會因為重新被合併而造成衝突。

這時,要讓 squashed commit 同時也有 merged commit 的性質,可以利用 .git/info/grafts 這個檔案或利用 git-replace 來手動定義合併資訊製作造假的合併資訊!

好用的地方在哪個? 假設你有兩個 perforce branch,分支之間不斷大量修改合併,但使用 git-p4 clone 後,你希望這兩個 branch 的合併基底 (merge base) 重新計算,減少合併衝突,就可以利用這個 graft point 來定義合併節點。

甚至是 git-svn 在處理樹狀目錄的合併資訊,也可以利用 graft points 來定義合併節點減少合併衝突。

當儲存倉越來越大時,你也可以將某個 commit 之前的 history 全數壓縮到另外一個儲存倉並把古老的 commit history 全數壓起來 (squash) 來節省空間...要查看細節時,再用 git-replace 將 commit history 接回來即可。

但 .git/info/grafts 只存在 local 端,並不會被 push 出去,因此若要能修改整個 commit tree 可利用 git replace --graft […] 直接將 commit 換掉 parent。

參見:

git-replace: http://git-scm.com/docs/git-replace.html

Graft Point: https://git.wiki.kernel.org/index.php/GraftPoint

#ThePowerfulGit

2014年7月4日 星期五

CLIFramework - Command-line application framework for PHP

還在苦惱用 PHP 寫 Command-line application 要支援 zsh completion 得自己寫困難的 zsh completion 嗎?

CLIFramework 提供一整套框架讓你用 PHP 快速架構一支 command-line application,還可自動產生 zsh completion script 讓你 Key in 無負擔 XD

所有的 option completion, argument completion 皆可以用純 PHP 撰寫

請看圖 XD



專案網址: https://github.com/c9s/CLIFramework

2014年6月26日 星期四

我為何仍繼續使用 Macports 而不用 Homebrew

很多人因為 Macports 在裝一些套件時,無法避免的另外編譯另外一套 Perl 裝至系統而跳槽使用 Homebrew。但身為一個前 Perl Developer,直接使用 System Perl as a dependency 其實並不太安全。

其一:  Mac OS 本身在升級時,會自動將 Perl 版本升級,如果你 link 至舊版的 Perl,升級之後你的 Homebrew 套件所有相依 System Perl 幾乎都要重新編譯才行。

但用 Macports 裝,則是將套件完全獨立一個空間出來,把套件跟 System library 的接觸面減到最小,就算是升級 Mac OS ,只要不是 32 位元轉 64 位元,原本編譯的套件幾乎都可以繼續使用。

其二:  Macports 現在提供 pre-built 好的套件安裝檔,安裝 package 幾乎不再需要重新編譯,Installer 自動下載解開就裝完了,完全不浪費 CPU。但目前 Homebrew 裝套件應該都是要重新編譯的。

其三:  安裝或升級套件,Macports 會自動幫你掃描是不是有 Broken library,若有問題也會自動重裝 library。(目前看起來 Homebrew 沒這個功能 ?)

其四: Homebrew 雖然 Formula 眾多,但安裝非官方的 Formula 有時容易引起套件衝突,舉例來說 PHP 編譯有各種 configure options,各家使用的 default configure options 又不一樣,安裝 extension 的時候還會彼此影響到... 有些 Formula 還必須先查看是否有 enable 某功能,不然裝了也是白裝。

其五: Homebrew 編譯套件不像 Macports 提供客製化 variants,你用某個 Formula 裝就是固定只能裝他預先指定好的 features,要客製化只能自己複製出來改,自己複製出來改就累了,你還得自己 maintain forumla 才行。 (更新: 據說 Homebrew 後來也支援了 option,不過升級套件要自己記住當初裝的 option 才行)


2014年6月14日 星期六

一些關於 API 設計的碎碎念

平常可能寫 API 寫久了沒什麼感覺,但最近對於 API 設計感想特別多...碎碎念罷了。

1. 各種參數的 naming 如果沒有 consistent,在不同的 context 下會很容易造成混淆,譬如說同一個參數名稱在 A context 是某種 Type,B context 卻是另外一種 Type。

這樣的命名混淆,在一整個 process flow 裡面,一旦遇到不同的呼叫使用相同名稱卻在不同 context 有不同意義的參數,就會成為杯具。

再怎麼樣想不到適合的名字也不該用混淆的名字

2. 命名歸類的一致性: 譬如說某某 method 是 A 相關,可以 A 作為 prefix,那就不要突然 A 突然 B 突然又 C,否則誰知道是在幹嘛(丟鍵盤)

3. 函式命名沒有這麼難,就算不知道怎麼命名也至少用動詞加受詞 (V+OBJ) 吧,然後 OBJ 的名稱一定要一致,不要一下 memberInfo 一下 memberData 的。

4. 此外 method name 本身的命名應該要讓人能讀出 read-only / write 等資訊,而不是一個看起來明明是 read-only 的 API 本身卻包含了 write 的行為。

5. 參數類型、可選不可選、臨界值、長度、不同值所代表的隱含行為在文件上寫清楚也是相當重要的,否則呼叫方若誤解了參數所帶來的隱含操作,則會造成系統不穩定。

6. 另外參數名稱也請不要用 1234567 當 suffix 呀,若是為了安全性,你好歹也用英文縮寫。

7. 最後,至少寫個 persistent layer 的 test 吧,curl 腳本也行,不要一下噴 HTML 一下 XML 的,明明都送 Accept: text/xml 啦!

2014年6月11日 星期三

Perl URL Router Benchmarks

To improve the overhead of URL routing, I developed a tiny URL routing library in C - R3, which is designed for high performance and low memory usage.

The implementation uses the trie data structure. Trie is an efficient information retrieval data structure, which uses a prefix tree to search inserted strings by their common prefix, thus it's pretty fast for matching routes.

The tricky part of R3 is that we need to support regular expression patterns in our routing definition to dispatch path dynamically, thus R3 implemented a variant of Trie by mixing some concepts of DFA, not just simply inserting plain string paths into the prefix tree.

There are several comparison types in R3: plain string, opcode or regular expression pattern. Each node have its own comparison type to dispatch the path to their own children.

For those simple regular expression patterns, R3 compiles the regular expressions into opcodes to enhance the comparison speed and it's twice faster than using PCRE library to match the path with the patterns.

And since there are a lot of things to do before the matching operation, the whole tree structure needs to be compiled before dispatching paths.

Here is the continuous benchmark result of R3 itself, The C version R3 can dispatch over 11 million plain string paths per second.

A talented Perl hacker - Cindy Wang developed a CPAN module based on R3 library - Router::R3, which has become the fastest routing module on CPAN. It's so fast that you just can't deny.

The Perl version R3 (Router::R3) can dispatch nearly 1 million paths per second while Journey (The Rails router) dispatches 9.9 thousand plain string paths per second.

We also used the routing path generator from the rails' pull request stevegraham/rails/pull/1 to benchmark the Perl URL routers on CPAN, including HTTP::Router, Router::Simple, Router::Boom and Router::R3

There are over 3 hundred generated routing paths in the benchmark script. we tested the "plain string matching" with the route in the middle of the list, and also the first route matching, regular expression matching.

Here comes the dispatching speed result:

Benchmarking 'plain string matching' by path '/corge/quux/bar'
===============================================================
                Rate  HTTP::Router Router::Simple  Router::Boom    Router::R3
HTTP::Router      203/s            --           -89%         -100%         -100%
Router::Simple   1782/s          779%             --          -99%         -100%
Router::Boom   168658/s        83094%          9365%            --          -82%
Router::R3     954407/s       470684%         53461%          466%            --
Benchmarking 'regexp string matching' by path '/post/2012/03'
===============================================================
                Rate  HTTP::Router Router::Simple  Router::Boom    Router::R3
HTTP::Router     1076/s            --           -88%          -99%         -100%
Router::Simple   9309/s          765%             --          -91%          -97%
Router::Boom   104387/s         9602%          1021%            --          -66%
Router::R3     306925/s        28426%          3197%          194%            --
Benchmarking 'first charactar matching' by path '/'
===============================================================
                    Rate  HTTP::Router Router::Simple Router::Boom    Router::R3
HTTP::Router      3839/s            --           -87%         -98%         -100%
Router::Simple   30545/s          696%             --         -83%          -98%
Router::Boom    180555/s         4603%           491%           --          -88%
Router::R3     1535999/s        39910%          4929%         751%            --

2014年6月10日 星期二

評 Microsoft Sculpt 人體工學鍵盤 (Microsoft Sculpt Ergonomic Keyboard)

Microsoft Sculpt Keyboard 在造型上及人體工學上的設計實在無懈可擊。 但有幾個缺點造成相當多的不便:

1. Dongle 只能貼在滑鼠上,所以如果要帶鍵盤外出,就得連滑鼠一起帶。不然就是得把 Dongle 放口袋或其他地方,加上 Dongle 太小了... 非常容易弄不見。

根據 HLB 的敘述,Dongle 弄不見之後竟然沒有辦法維修或另外購買!!! 就算你願意花錢買 Dongle 也不行!

2. 鍵盤帶著外出,由於完全沒有電源開關,所以只要壓到鍵盤,就會造成電量損失,放上一整天隔天就會沒電! 所以帶著外出時,還要先把電池全部卸下........

2014年5月21日 星期三

R3 - 極致效能的 URL Router Library

其實幾年前就有想用 DFA 做 URL router 的想法,只是為了有趣,所以當時用 PHP 寫了一個簡單的 RE parser,但是用 PHP 寫成的 parser 實在太醜了,而且在動態語言裡面這樣實作也不會快到哪裡去,於是後來就作罷。

當時也另外看了 Journey 的原始碼,發現 Rails/Journey 在處理 Regular Expression 的路徑比對也只是把一整個 Regular Expression 路徑放到另外一個 array 裡面去循序比對罷了,並不會塞到 DFA 裡面.... 看到這邊其實就想丟鍵盤了,如果你只有 字串拿來做 DFA,那倒不如就直接用 Ruby 內建的 Hash Table 查表算了。

後來一直沒有動機繼續把這個想法做完,一方面,用 C parsing regular expression 實在太累人,且就算實作了,考量到開發時間有限,也不可能完整支援所有的 RE features,所以就折衷先寫了一個非常 Tiny 的 library - Pux 來解決 PHP + Nginx/Apache routing overhead 的問題。

再後來,有次跟 Cindy 討論發現其實可以用 prefix/suffix tree 來做比對。而 prefix tree 很適合這個問題。但 RE 還是沒有辦法很完美的整合進來。

睡了一晚,想到 RE 其實可以拆成個別的 node 做 partial match 即可,這樣就可以用很簡單的資料結構的解決掉問題,不用自己做 Regular Expression 的引擎,只要把部分字串交給 PCRE 接手即可,而且還可以得到非常不錯的效能。

後來用了一些零零碎碎的時間總算把雛形寫完了,接著就拿 stevegraham/rails 的 PR 裡的測試資料簡單評測了一下。發現新引擎處理比對的速度,每秒約可以處理一千兩百萬到一千三百萬個路徑 (12M~13M) 比對 ( http://c9s.github.io/r3/bench.html ) ,而 Journey 約處理九千個路徑左右 (約一千多倍的差異)。

現在,只要是 3P 語言都可以透過跟 R3 binding 得到相當不錯的效能!歡迎大家來實作 R3  binding:

專案網址: http://github.com/c9s/r3


目前 Cindy 寫的 Perl 版本的 R3 CPAN module 已經放上 CPAN :https://metacpan.org/pod/Router::R3

當 Rails/Journey 還在 9326 i/s 繞,Perl 版的 R3 跑起來就有 1,662,383 i/s。

當然你可能會說,Router 有需要這麼快嗎?Well 其實這個專案基本上只是為了實驗加興趣而實作的,雖是實驗,但所有的 Feature 都透過 C 的 Check Unit Testing 做測試,使用 autotools 做 feature testing, project building。

R3 後續在 Hacker News 以及 Twitter 上引起討論。 如:



日本的 mattn san 也做了一份 Perl Router 的 Benchmark,與號稱最快的 Perl Router Module 比較:


2014年5月15日 星期四

Judy array 在 2003 年時似乎是當時最快的 associative array 實作.. 當時好像掀起了一番熱潮.. 查了一下現在好像也有其他 hash table / associative array 比 Judy array 快。

有翻到 benchmark project 測 PHP 內建的 Array, SplFixedArray, Judy Array,結果 Array 居然表現跟 Judy Array 不相上下?不知道是不是因為 Language runtime 轉型 overhead 的關係?