Eigen的速度為什麼這麼快？

01-07

NewQuant數值線性代數模塊的開發已經接近完成，簡單地和Eigen比較了一下，我的代碼真是卑賤的如同草芥螻蟻一般。想要提高效率的話我能想到兩條路：一是演算法層面上加速；二是使用特殊的C++編程技巧。關於演算法，我的演算法大多直接來自《Matrix Computation 3rd》，那麼特殊的加速演算法要從哪些文獻里找？關於編程技巧，我以自己的方式實現了「表達式延遲賦值（expression lazy evaluation）」，類似於純粹的表達式模板，不過使用了多態機制，那麼Eigen里使用了哪些特殊技巧加速計算呢？

以前也覺得 Eigen 很快，感覺和 mkl 可以媲美。但是昨天 debug 時一行一行看時間，發現這樣一個矩陣乘法 $mathbf{A}^{ extrm{T}}mathbf{A}$ 要算將近一秒（ $mathbf{A} in mathbb{R}^{4800 imes{}1000}$ ），而同樣的計算用 MATLAB 只需要肉眼不可察覺的時間。

我 google 了一下，在 StackOverflow 上（How to speed up Eigen library"s matrix product?）有人討論說是 MATLAB 內部自動會調用多線程版的 mkl 里的矩陣乘法，而 Eigen 在通常狀態下是單線程的，需要在編譯時加上 $mathtt{-fopen}$ 參數使用 openmp 開啟多線程。我在自己的 Mac 上嘗試了一下，在線程數為 4 的情況下，時間縮短為 0.57 秒，但相比 MATLAB 的肉眼不可察覺還是有差距。

我對計算機底層的硬體不是很熟，只是最近突然覺得處理起這種可以高度矢量化的問題時，（不是非常 wisely 地）使用Eigen 還是沒有經過優化的 MATLAB 快。

P.S.: 最開始的單線程版本我使用的是 OS X 自帶的 $exttt{g++}$ 編譯器，優化參數為 $exttt{-Ofast}$ . 測試過加上 $exttt{-msse2}$ 沒有明顯區別。這個 $exttt{g++}$ 實際上是Apple 封裝後的 $exttt{clang++}$ ，很可惜的是不支持 openmp. 所以為了開啟多線程我安裝了 GNU $exttt{g++}$ 編譯器。其它編譯參數不變。

=================更新==================

剛才又上 StackOverflow 上看了別人的幾個帖子（Eigen vs Matlab: parallelized Matrix-Multiplication）學習了一下，發現了幾個新的 trick：

首先之前線程數我設置錯誤了。我的 CPU physically 應該只有兩個核，四線程是 hyper－thread 的結果，多出來的兩個線程並不能加速。我把 OMP_NUM_THREADS 改為 2 以後，速度變為 0.55s 左右；
如果計算矩陣乘法，使用 $mathbf{B} exttt{.noalias()} = mathbf{A}^{ extrm{T}}mathbf{A}$ 是個不錯的 trick，它可以避免生成 temporary 的矩陣存儲中間結果。使用這個後縮短為 0.50s 左右；
對 Eigen 3.3 或以上的版本可以加上 $exttt{-mavx}$ 和 $exttt{-mfma}$ 兩個參數，進一步縮短為 0.40s 左右。

這樣總的下來提速了約 30％.

感覺Eigen相比於其他線性代數庫最突出的特點是，「不是效率高的事情不做，不是最快的演算法就不提供」。

看下Eigen自己說的，

Eigen: What happens inside Eigen, on a simple example

總結來說Eigen做了這麼幾件事：

1. 不用中間變數

2. 小矩陣和大矩陣根據實際情況選用

3. 特殊的賦值處理

4. 矢量化 SSE指令

市面上Eigen庫最快，對於Armadillo+數學庫的組合速度取決於數學庫的速度，Armadillo本身數學庫就不用提了。

模板，模板元

--------------------------------------------------------

我是都沒用過，閉眼答得、、

還有，動態多態（繼承，虛函數）只會降低執行速度的、、

Armadillo+Openblas的組合比Eigen要快很多

通過並行指令集將演算法並行化，比如矢量運算，底層合理並行，速度就快了幾倍。一言以蔽之，結合硬體的編程技巧