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 再次提醒我,世上並無各方面都完美的程式語言。

3 則留言:

Nicky C 說...

經改寫的constructor仍有不妥。 Scenes& c 是lvalue reference,不應「移動」。lvalue reference只能綁上lvalue,意味着這constructor肯定在「移動」lvalue,而拒絕「移動」rvalue,違反move semantics的「國際標準」(ISO C++標準)、「立法原意」(C++委員會的設計)和「社會共識」(專家們的建議和社群的通常做法)。

應先以const lvalue reference同時接收lvalue和rvalue:

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

若事後確定須「optimize for move」,則加上rvalue reference的overload,以接收rvalue:

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

至於選用何者,應由caller決定。

由於 Sphere 純屬stack object,無法shallow copy,「移動」無用。但仍應以const lvalue reference避免額外複製。

最後,由於複製 Sphere 和移動 Scenes 皆無heap allocation,不會throw exception,可加上「noexcept」增加optimization。

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

其實C++98也可以hack出move semantics,參見 http://www.stroustrup.com/Programming/Matrix/Matrix.h ,留意「xfer」、「owns」等字眼。

The suffocated 說...

若要寫 reusabale code 的話,我想你說得有道理,不過在這個 benchmark 程式當中,就是於 create() 的 function body 內,先構作一個臨時用的 Scenes 物件(其實是一條 std::list,是有變數名稱的 lvalue),將它傳給 Group 的 ctor,讓 Group 複製,然後讓此臨時用的 Scenes 物件自生自滅。

因此,move 了這個 lvalue 並無所謂,原因是我們預先已知道這個 lvalue 再無第三者會用得著;Group 類別沒有 move ctor 也同樣無所謂,因為我們只會用 create() 函數內那個用完就丟的 lvalue 來構作 Group 物件。

Nicky C 說...

既然無所謂,就省去「Group(const Sphere& b, const Scenes& c)」,直接寫「Group(const Sphere& b, Scenes&& c) noexcept」好了,再由 create() 負責將 child 變成rvalue。才多幾個字母而已,依然很無所謂,卻更接近慣常做法。

Group 當然不須move constructor,因為 Group 只透過其base class的owning raw pointer使用,連 list 也是list of owning raw pointers,根本沒有移動過。然而,這個無所謂只是毒藥的糖衣。「list Scenes」令cache miss最大化,嚴重拖慢。