夏到来! 人類史上最速の wavefront .obj ローダを作ろう

夏到来ですね! 開放的な気分で新しいジブンにチャレンジしたくなりますね!

なんだか人類史上最速の wavefront .obj パーサを作りたくなりたくなってきますね! 夏休みの自由研究にぴったりですね!

できました!

https://github.com/syoyo/tinyobjloader/tree/develop/experimental

大体 10 ~ 15 倍くらい早くなりました.

## 概要

戦略としては, マルチスレッドで行単位データのパース処理 + 各種最適化です.

CSV のパースを GPU で行うのを参考にしました https://github.com/antonmks/nvParse

* mmap で .obj ファイルをリニアなメモリ空間にマップする.
* 改行コードを探し, 行ごとの情報をつくる(並列で処理する)
* 行の情報をもとに, 各行をパースする(並列で処理する)
* 最終的な形状データ構造を復元する(だいたい並列で処理する)

## 計測する!

まずはボトルネックがどこにあるか, 計測するところから始めましょう.

MacOSX の場合は XCode に付属の Instruments を使うのが便利です. 

https://developer.apple.com/library/watchos/documentation/DeveloperTools/Conceptual/InstrumentsUserGuide/index.html

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 を使いました.

https://src.chromium.org/chrome/trunk/src/base/containers/stack_container.h

https://github.com/r-lyeh/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 で描画するようにデータ変換するほうが時間かかりました :-)

<blockquote class="twitter-tweet" data-lang="en"><p lang="en" dir="ltr">Experimental optimized&amp;multi-threaded .obj parser! Rungholt just 0.9 sec on 4c 3.2GHz PC! <a href="https://t.co/JKsgliTjsd">https://t.co/JKsgliTjsd</a> <a href="https://t.co/SpXVw7Yj1b">pic.twitter.com/SpXVw7Yj1b</a></p>&mdash; Syoyo Fujita (@syoyo) <a href="https://twitter.com/syoyo/status/731793292577280000">May 15, 2016</a></blockquote> <script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>


## 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 パーサの最適化に切磋琢磨するスキームを確立したい**