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 的關係?

2014年5月10日 星期六

動態語言裡設計函式介面越要彈性簡單好用,就需要實作 Runtime 的 type checking,執行時期會增加更多的計算成本。

程式語言如 C++, Haskell 可以透過 Parametric polymorphism 多型的方式提高介面易用度,編譯時期就可以確定要呼叫哪個符合類型的函式。

很不幸的,動態語言如 PHP, JavaScript, Ruby 不支援多型,就只能用 instanceof, typeof, is_a? 等方式來檢查型別,這時候 trade off 就來了,你希望函式要 "Less is more" 還是要 "說清楚吃雞豬牛或鴨" ?

前者好用但計算成本高,後者麻煩但計算成本低。這就是 jQuery 為什麼慢,而有些人堅持用 document.getElementById 的原因。

2014年5月8日 星期四

利用通勤等零碎時間讀張榮發回憶錄,內心澎湃不已。張總裁從蘇澳貧困的家中出生,歷經語言隔閡,18歲喪父,扛起扶養弟妹的責任,拼命苦讀考取船副,之後創立船公司,準確預測國際趨勢,並成為成為國際中首度使用貨櫃輪的船公司,在 GPS 還在美軍試驗時,就率先採用 GPS 作為貨櫃輪的導航系統;搭飛機的時候還用皮尺帳量機內座位間距、尺寸等..一直做到七八十歲才退休!長榮國際企業的成功真的不是偶然,誰有資格說企業家成功都是靠爸?

發現所謂有決心、超強意志、有智慧的企業家,是絕不提”夢想”兩字,他們只專注當下,對未來沒有妄想,克服眼前的困境,紮實的走好每一步路。

自我期許之

2014年5月7日 星期三

重構 PHP 引擎並大幅改善效能 - PHP Mailing List


譯文 Hackpad: https://hackpad.com/-PHP--HRY9UYvrArM

原文網址: http://news.php.net/php.internals/73888

認識我的人們都知道我在 Zend 主要的責任及熱情都放在 PHP 效能這個主題上。 事實上,從 PHP 5.0 版本開始,我們已經在綜合性效能評比 (Benchmark) 上改善了六倍的速度,並且讓一般使用 PHP 撰寫的應用程式達到了兩倍速度改善。

我們不停的改善 PHP 引擎以及 OPCache (PHP 5.5 版的核心套件,用於快取)。 然而,當時對於 PHP 5.5 版本的釋出,我們並無顯著的發展,除了別的事情之外,我們也試驗了一些記憶體管理, JIT 技術等其他可能的辦法。

我花了相當多的時間試驗 JIT 的想法,並證實這是可行的 (以 LLVM 為基礎的 JIT 編譯器,然後嵌入 OPCache)。 由 bench.php 得到的結果相當驚人 -- (由原本的 2.175 秒改善為 0.219 秒 -- PHP 5.5 近十倍速度的改善),但在現實的應用程式中,我們只得到了一些加速。 但這讓我們更深入的探索 PHP 引擎執行時期 (Runtime) 的特性以及那些真正的瓶頸,來取得巨大的進展。

很明顯的 VM 幾乎已經高度優化了,但是卻內部所使用的資料結構卻需要使用大量的記憶體調用 (Allocation)、釋放 (Deallocation)、參照計算 (Reference Counting)。

一般來說,現實生活中的 PHP 應用程式花了約 20% 的 CPU 實在在記憶體管理 (memory management)、10% 做雜湊表 (Hash Table) 操作、30% 呼叫內部函式 (Internal functions) 且只有 30% 花在虛擬機器 (VM) 上。

當然,我們嘗試了將 VM code 用 JIT-only 的方式運行,在大多數的狀況下,他還是花了同樣多的記憶體配置。因此,我們決定著重在最主要的效能瓶頸上。 主要的想法是修改內部的資料類型 (data types) 並最小化堆積 (Heap) 的用量。

這是一個相當困難的決定,因為我們必須重構相當大量的程式碼,而且我們完全不知道重構之後是否會造成其他問題或衝擊。

現在我可榮幸的向您們展示這四個月以來的工作成果。這次的 PHP 引擎重構大量的改善了效能、記憶體用量,並且為未來的效能改善及 JIT 建立了穩固的基礎。我會避免技術細節(更多細節將會在 http://wiki.php.net/phpng <http://wiki.php.net/phpng>* 發佈),簡單的說 - 我們改變了整棟建築物的地基並且盡量保持建築本身不改變。現在新的引擎已經達成了 *10-30% 左右的加速,且不只是在效能評比 (Benchmark) 中,在現實應用程式也達成了相同的加速!

以下是我們目前所達成的效能改善:
  • Wordpress 3.6 – 20.0% gain (253 vs 211 req/sec)
  • Drupal 6.1 – 11.7% gain (1770 vs 1585 req/sec
  • Qdig – 15.3% gain (555 vs 482 req/sec)
  • ZF test app – 30.5% gain (217 vs 166 req/sec)
在某些應用程式中,我們相較於其他 PHP 實作得到了更好的結果。 若有其他人能夠測試他們的應用程式,並且與目前使用的 PHP 版本的效能比較,整理更多的效能差異結果,那就更好了。

這次的重構還未完成,因為我們一開始只是測試這樣的修改是否能得到改善。 目前並不是所有的延伸套件 (Extension) 都得到支持,有一些單元測試是失敗的,此外,我們對於其他改善也還有更多想法。

但我們覺得,現有的結果已經足以證實改善的方向,且可以開放出來讓大家檢視、回饋或協助,如我們現在有了正確的方向,我們也想儘快讓社群參與。

因為,要支持所有的延伸套件 (Extension) 以及持續的做出更多改善,還有許多工作需要完成,這些也需要社群的協助。
請嘗試這個重構過的 PHP 引擎並且提供我們意見或結果,像是: 效能, 記憶體用量或任何的想法。 你可以在 php.net 上的 *phpng* 這個開發分支上找到這個新版的 PHP。

建置步驟則在: http://wiki.php.net/phpng

如同我們上面提到的,有一些 Extension 還未被支援,因此並不是所有的東西都可以運作。

我想要感謝 Xhinchin 以及 Nikita ,他們完成了這次的成果許多重要的部份。

謝謝。 Dmitry。


-- 林佑安譯於 2014 五月