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++ 表現的文章，就想在自己的機器上跑一下當中程式。
程式所做的，是 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:
由於變數 c 實際上是用過就丟的 temporary variable，實在無必要 copy。若用 C++11 的話，只需將以上一行改為
或者若是 C++98，可寫為
這並非甚麼 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 再次提醒我，世上並無各方面都完美的程式語言。
 |
| image source: www.ffconsultancy.com/ocaml/ray_tracer/index.html |
這個 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 再次提醒我，世上並無各方面都完美的程式語言。