challenge ciphertext

NyARToolkitの高速化メモ

高速化で気がついた事、やった事などのまとめと言うか記録。

Java的な高速化

Javaだからと言う事はないけれど。

やること

• new回数を減らす。基本。
• ループ終了条件は定数にする。可能ならデクリメントループにして、0比較にする。何命令か少なくなります。短いループになるほど有効です。
• double演算は出来るだけ減らす。テーブルを使って回数を減らすのが特に有効です。
• 配列操作は１次元でする。AALOADよりALOADの方がかなり高速です。
• 短いFor文は構造を壊さない程度に展開する。4命令くらい省略できます。
• 3回以上アクセスする変数はローカル変数に代入する。GETFIELD命令は遅いので…。
• 値コピー回数を減らす。特にdoubleの場合に顕著です。
• intで計算する。shortとbyteはできるだけ避けましょう。I2S命令が1個消えます。
• 1処理単位で100回以上呼ばれる関数はインライン展開するか、配列を使ってバッチ処理する。
• 最適化できたかは、必ずバイトコードを確認する。微妙な最適化をすると、コンパイラの最適化と干渉して、遅くなる場合があります。
• 大きな書換えを伴う最適化は、処理単位をinterfaceで別クラスに切り出して、派生クラスにして切り替えられるようにする。（後でﾆﾔﾆﾔするためにも重要）

やったらダメなこと

• INT演算のテーブル化。レジスタへのヒット率が下がって遅くなる事があります。
• 処理フローを著しく壊すような処理の展開。結局遅くなることが多いです。
• 最適化のために計算順序を入れ替える。積算除算で桁落ちが起きて結果が変わり、結果比較ができなくなります。
• クラス構造を無視した最適化。プログラムの寿命を縮めます。やるなら処理に最適化したクラス構造を作り直すべきです。

ARToolkitの高速化

オリジナルのARToolkitの高速化ポイント

• 参照ポインタの数が多いです。特にLabering処理の部分に多すぎる気がします。アセンブラに落ちた時に不利になるので、減らした方が早いです。レジスタの多いCPUだと早いのかもしれないけど…。
• 重複演算が多い。arTransmatからコールされる関数は演算ループ構造が冗長で、重複演算がかなりあります。この関数下で行われる演算は8割以上double演算なので、テーブルを使って重複演算部分を排除することで、高速化が可能です。
• 特に行列関係の演算の時に、ワークメモリのmalloc/allocが大量に行われます。何度も割当てるのは無駄なので、一回割当てたら使いまわすと良いかな？
• 画処理用のワークメモリが、静的にどんぶり勘定（超大盛）で取られてるため、メモリの利用効率が極端に良くありません。動的にワークメモリを拡大するシカケを入れると、使用量が1/10くらいに減ります。
• #defineと#ifndef等の静的なパラメータが多数あります。この辺はクラスを使って切り替えるようにすると、見通しが良くなって速度も上がります。

マトメ

ARToolkitの高速化ポイントは、Java化して処理構造を整理した事で見えた問題なので、オリジナルのCコードをそのまま追いかけたとしたら…、多分、気がつかなかったでしょうね。

とりあえず全部読んで書き直しましたが、未だにオリジナルのコードを安全に高速化できる自信は全くありません。（というか無理です。）

・・・、想像ですが、現在のNyARToolkitをC++に戻せば、オリジナルの1.5倍以上の演算性能がでるんじゃないかなと思います。

時間見つけてやってみようかな。