2014年10月26日星期日

法家

真不明白那些權貴何以能夠臉不紅,眼不眨地說佔領行動「破壞法治」。他們口中所謂法治,根本不是法治,而是最極端的法家治術吧?佔領街頭就叫搞亂香港,那麼佔領香港,或佔據了香港行政首長的位置,壟斷了香港的政治、經濟權力,又叫甚麼?

2014年10月17日星期五

OCaml vs C++

人人皆說 functional programming (FP) 乃科學計算的未來,但夠快速的 FP 語言實在不多。以 quant 為例,那些用超級電腦計算期權價格的公司,現時仍是使用 C++ 居多。用 FP 語言的,主要用 Scala、OCaml 及 F#。Scala 要靠 JVM,而 F# 話就話 open-source,實際上仍要靠 Microsoft,兩個平台都對用家造成一些麻煩。OCaml 和 F# 都是 ML 的變種,但 OCaml 歷史非常悠久,自九十年代發展至今,已相當成熟。多處有報告說其表現與 C/C++ 不相伯仲,甚至猶有過之,令我很感興趣。前日從網上看到一篇比較 OCaml 與 C++ 表現的文章,就想在自己的機器上跑一下當中程式。

image source: www.ffconsultancy.com/ocaml/ray_tracer/index.html
 程式所做的,是 raytracing。比起那些 microbenchmarks,raytracing 總算是比較現實兼且 nontrivial 的任務。我用的電腦是今年年中買的 MacBook Air,Intel i7,8GB RAM。編譯器方面,ocamlopt 及 GNU g++ 都是用執筆時最新版本。ocamlopt 的 compiler options 與文章所載相同,g++ 則只用 -O3,沒有加上 -ffast-math 或 -funroll-all-loops。結果如下:



這個 raytracing 程式有點像那些搞碎形 (fractals) 的程式那樣,會先從一個球體中生出幾個球體,再逐層衍生出更多球體(見圖),然後計算光線。上表中最左一列的 level,就是指衍生了幾多層新球體。level 愈高,工作愈繁重。之後兩列是文章所附的 OCaml 及 C++ 程度編譯後運行所需秒數(愈細愈好)。將 C++ 的運行時間除以 OCaml 的運行時間,就得到右邊第一列的 ratio。

文章中,OCaml 與 C++ 之間互有勝負,但我這裏則除了 level 12 之外,都是 C++ 較快,不過整體來說,拿 OCaml 與 C++ 的速度,多數時候相差不夠 15%。這種程度的差距,往往隨編譯器版本而逆轉。故此我同意文章所說,兩者表現可視作相同,最少於 level 10 或以下如此。

這是相當了不起的。一直以來,不少人都相信,論執行速度的話,平均來說,用 C/C++ 所寫程式,除了僅次於用 Fortran (或 assembly language) 寫的以外,再無敵手,但正如本文文首所說,許多報告都說 OCaml 的表現與 C++ 不相伯仲(用 C++ 做科學計算的其中一個利器 FFTW library,更是用 OCaml 撰寫的)。由於 OCaml 較高階,程式遠較 C++ 的簡短,故此,使用 OCaml 應該更 productive。

之前粗略學過 Scala、Haskell 及 Julia,都是玩票性質,我覺得今次應該認真學一學 OCaml,並想一想將來會否將一部份工作改用它來做了。

不過話說回來,即使我認同 OCaml 的表現,仍是對於文章中做 benchmark 所耍的小手段感到不耐煩。

首先,不知作者有心抑或無意,於 Group 的 ctor 中 copy 了整個 std::list:

Group(Sphere b, Scenes c) : bound(b), child(c) {}

由於變數 c 實際上是用過就丟的 temporary variable,實在無必要 copy。若用 C++11 的話,只需將以上一行改為

Group(Sphere b, Scenes & c) : bound(b), child(move(c)) {}

或者若是 C++98,可寫為

Group(Sphere b, Scenes & c) : bound(b) {child.swap(c);}

這並非甚麼 premature optimization,我們本來就應該叫電腦別做多餘的事。經過以上改寫之後(只多了一個 & 符號及多了一個 move 或 swap),就有上表中以 move 標列的結果,當中可見從 level 10 開始,C++ 逐漸拋離 OCaml。

其次,文章作者說,他用的是最 "natural" 的 implementation。我覺得這實在不大對頭。若要說自然的話,程式中凡用到 std::list 的場合,都只是 push_back 以及用 iterator 從頭到尾 traverse 一次。這種情況,最自然的 implementation 並非用 std::list,而是用 std::vector。此外,文章中 C++ 的程式用了一個自製的三維向量 "Vec",但現在基本上人人都是用 Eigen3 (self-contained template headers, no BLAS needed) 或 armadillo (BLAS needed) 兩個程式庫的向量。考慮到該文章成文時,連 Eigen2 都未有,這倒是情有可原,但若用 Eigen3 的話,就可以省去文章中十幾行用來實作 Vec 結構及 unitise() 函數的程式。儘管結果仍比 OCaml 的程式長,但也沒有現在那麼誇張。OCaml 好像也有 dynamic array (DynArray ?),不知用 dynamic array 的話,相較又如何。

將 std::list 及 Vec 改為 std::vector 及 Eigen::Vector3d 之後,就有上表中用 "vectors" 標示的結果。當 level 較低的時候,由於 allocate 一枝 std::vector 比 allocate 一個 std::list 用上更多記憶體,故此所用時間可能較長。然而,level 高的時候,進出 std::vector 較快的優勢就變得明顯了。

最後,也是我最討厭的一點,就是文章作者避重就較,避談對 OCaml 不利的程況。FP 強調 immutable data,因此往往要抄寫更多記憶體。當記憶體用量夠大的時候,FP languages 的弱點就完全暴露了。文章只計算到 level 12,原因是作者的電腦不夠記憶體。這也許是事實,但若用擁有更多記憶體的電腦來跑程式的話,我們就會看到,Ocaml 的程式從 level 10 開始,表現下降得很可怕。上表中 level 14 那一行就展示得清楚。再者,FP 強調 immutable data,最大的優點是便利平行計算,可是從網上其他敘述所見,OCaml 似乎是不支援真正的平行計算的,而文章作者亦避談此缺失。

這並無改變我對OCaml 的興趣或評價,只不過這個 benchmark 再次提醒我,世上並無各方面都完美的程式語言。