夏到来ですね! 開放的な気分で新しいジブンにチャレンジしたくなりますね!
なんだか人類史上最速の wavefront .obj パーサを作りたくなりたくなってきますね! 夏休みの自由研究にぴったりですね!
できました!
大体 10 ~ 15 倍くらい早くなりました.
概要
戦略としては, マルチスレッドで行単位データのパース処理 + 各種最適化です.
CSV のパースを GPU で行うのを参考にしました https://github.com/antonmks/nvParse
- mmap で .obj ファイルをリニアなメモリ空間にマップする.
- 改行コードを探し, 行ごとの情報をつくる(並列で処理する)
- 行の情報をもとに, 各行をパースする(並列で処理する)
- 最終的な形状データ構造を復元する(だいたい並列で処理する)
計測する!
まずはボトルネックがどこにあるか, 計測するところから始めましょう.
MacOSX の場合は XCode に付属の Instruments を使うのが便利です.
Linux の場合は perf でしょうか(検索しづらい名前です...).
Instruments で計測したところ, pow などの数学関数が想定通り重かったです. 以外なところでは atoi, strspn などの文字列関数とかも. あとは STL 周りでした(std::vector と std::string のインスタンス生成とか, push_back とか)
C++11 の機能を使う.
とりあえずマルチスレッド化は必須なので, C++11 だと thread, atomic があるので, C++11 を使うことにしました.
また, emplace_back, std::move などの機能を使いました. ちょっぴり早くなりました.
メモリ確保
std::vector は内部でロックをかけてメモリ確保するので, マルチスレッド環境では結構ボトルネックになります.
(STL のデフォルトメモリアロケータの実装に依存するが, 大体多くの実装(GNU STL)では普通の pthread mutex でロックをかけて... みたいになっているので遅い)
小規模な動的メモリ確保が必要であれば, あらかじめスタックに領域を確保するようなアロケータを自作するなどしましょう. 今回は, Google の StackVector や, ltalloc を使いました.
vector などの STL の挙動を極める.
GNU STL 系だと...
std::vector<int> a(100000, 0)
とかして大きな要素を確保して初期値で初期化, とかやると遅いです. また, resize() も確保に時間がかかり遅いです.
配列のゼロクリアも std::fill は大きな要素数では遅かったです(普通に for 文で回しているだけだから?). それなりに要素数が多い場合は memset 使いましょう.
一度十分な領域を reserve() しておき, 都度 push_back or emplace_back するのが一番効率的でした.
成果
Instruments でプロファイルを取りつつ, 上記最適化を進めた結果, 最終的に以下となりました.
Rungholt scene(6M triangles, 263 MB) で計測しました http://graphics.cs.williams.edu/data/meshes.xml
gcc(MacOS X) or clang 3.8(linux) を使い, -O3 オプションをつけてビルドしています.
最初に数回パーサプログラムを走らせ, データがメモリにキャッシュされているようにしています.
最適化前は, この記事を書いている時点での master ブランチのものです(v0.9.24) https://github.com/syoyo/tinyobjloader
単位はミリ秒(ms)です.
| 最適化前 | 最適化後 | |
|---|---|---|
| MacBook 12(1.2 GHz Core m5) | 15500 | 1500 |
| Xeon E3 1245 3.3 GHz(Sandy Bridge 4 cores, Linux) | 10151 | 692 |
MacBook 12 インチで 10 倍, 4 コア Xeon で 14.7 倍 となりました.
以下は 4 core Desktop PC での結果です. ロードしたのち, OpenGL で描画するようにデータ変換するほうが時間かかりました :-)
Experimental optimized&multi-threaded .obj parser! Rungholt just 0.9 sec on 4c 3.2GHz PC! https://t.co/JKsgliTjsd pic.twitter.com/SpXVw7Yj1b
— Syoyo Fujita (@syoyo) May 15, 2016
TODO
- SIMD 命令を使ってよりパースを高速にする(Intel が SSE/AVX, IBM が Cell/SPE を使って XML のパースを高速にする, とかやってました)
- メモリアクセス, 動的メモリ確保周りはまだまだ最適化の余地あり.
- 高速化のためにいくらか余分にメモリ確保しているので, 速度を維持しつつメモリ減らしたい.
- TLS(thread local storage)に
std::vectorなどを割り当て, 変数をスレッドごとに割り当てることで効率化できないか?(clang 3.8 くらいからできるっぽい?) - Windows(Visual Studio) での最適化戦略を極める(Intel VTune や AMD CodeXL?)
- よりコア数の多い CPU で試す.
- GPU でパースする
- 優秀な wavefront .obj パーサ若人を育成し, 優秀な若人が日々 .obj パーサの最適化に切磋琢磨するスキームを確立したい