Android Dev Phone 1 （G1）で AO bench に挑む

今日は長文です。

AO bench とは、syoyo さんが公開している Ambient Occlusion （AO）のデモプログラムです。ＡＯは、自然な環境光（アンビエント）の陰影を生成するためのレイトレーシング(パストレといったほうがいいのか？）みたいなものですが、物体表面から、様々な方向に対してレイを飛ばして、天空球に届く割合を調べることで、アンビエントの陰影を決定するものです。

なお、Direct3D のデモに入っているスクリーンスペースのAOとはちょっと違います。CGツールのレンダラに入っているAOはこんなアルゴリズムなのかな。

要は、ポリゴンベースの描画ではなく、レイトレベースなので、浮動小数演算の計算量が多く、携帯電話に入っているような　ARM の　CPU　などではちょっと厳しいということが言えます。

細かい説明はこれくらいにして、最近気になっていることがありました。

http://lucille.atso-net.jp/aobench/

に、様々な言語やプラットフォームでのベンチマーク結果が書かれています。

その中で、、、、

・iPhone 38 sec
・Android DalvikVM 2966 sec

というのが書かれています。

これは、Android （正確には、T-mobile G1 or Android Dev Phone 1 のことです。）は iPhone より、100 倍くらい遅いってことでしょうか、、、

まあ、iPhone よりも遅いのは確かですし、G1を使っている人はハードウェアの性能なども知っていると思うのですが、あまりに不憫な結果を載せたままにしておくのもなんですので、ちょっとだけ名誉挽回しておこうと思います。

まず、なぜ劇的に遅い結果となっているのかを考えますと、、、、

１．ループ計算の内部で、大量の動的メモリ確保(new)・解放をしている。
２．JITを持たないなどの理由で、DalvikVMが遅い。
３．FPUを持たないARM CPUを使っている　（iPhone はVFPを搭載している）
４．浮動小数といっても、float ではなくて、double。

と、いろいろありますが、今回の本質的なところは、1番でしょう。Cでは、ローカル変数となっている部分が、Javaで　new になっているのが問題でしょうか。

おそらく、あらかじめメモリを確保しておくようにして、動的なメモリ確保をなくしてしまえば、DalvikVM　でもかなり早くなると思いますが、Java　にはあまり興味がないので、、、今回やることはこの３点。

１．　Java ではなく、C　のコードを動かす。
２．　double のコードはすべて float に変換して動かす。
３．　float をさらに、固定小数にして　int で動かす。

さて、１は簡単です。AOBench のオリジナルコードはCです。計算結果のビットマップをppmとして出力するものです。android の場合は、shell から普通に動かしてもいいですし、JavaからJNI経由で計算した結果を取得して、画面に表示することもできます。

さて、オリジナルコードをコンパイルして動かしたところ、そのまま動きました。

その結果、、、、

・Android Dev Phone 1 (C version) 714　sec 　

なお、条件は、同じものを使っています。

• IMAGE_WIDTH = 256
• IMAGE_HEIGHT = 256
• NSUBSAMPLES = 2
• NAO_SAMPLES = 8

うーん、まだ20倍遅いな。

ここからは、コード自体を修正して、更なる高速化を試みます。

まず、double を　float に直しました。組み込み機器をやっていると、double は厳禁です。特にFPUを載せていても　float にしか対応できないので、double は大量の関数コールを吐き出します。

ただ、G1 には　FPU　がないので、float にしても劇的な性能向上とまではいきませんが、

・Android Dev Phone 1 (C version, float version) 229　sec

となりました。float にしてもそんなに絵は変わっていないと思います。（JNI経由で動かした写真です。）



ここからは精度を大幅に落とします。

すべて固定小数に変更しました。フォーマットは、16.16　ですが、まずは、高速化だけを考え、8.8 の精度しか保障しないようにしました。三角関数は１度単位のテーブルです。平方根は整数版の繰り返し計算を使います。


おっ、iPhone と同じレベル(38sec)にきました。しかし、残念ながら精度不足です。球が崩れてしまいました。（画像をクリックすると確認できると思います。）

次に、掛け算の計算だけをインラインアセンブラを使って、16.16を保障するようにしました。ARM のインラインアセンブラなどは、android でソフトウェアGLESなどを担当している、pixelflinger の ggl_fixed.h を参考にしました。

http://www.google.co.jp/codesearch/p?hl=ja#2wSbThBwwIw/include/private/pixelflinger/ggl_fixed.h&q=pointx&exact_package=git://android.git.kernel.org/platform/system/core.git

その結果、、、、


だいぶましになりました。やっぱり8.8ではオーバーフローしてたのかな。でも、思った以上に遅く（47sec）なってます。インライン展開できていないのかもしれません。

あと、割り算をやりたいところですが、掛け算みたいに簡単ではなかったので、今回はここまでにしました。これ以上遅くして動かしても意味なくなってきますし、、、

今日の結論をまとめますと、

オリジナルのベンチマークは、
・Android Dev Phone 1 (C version) 714　sec 　
すべて、float に置換したものは、
・Android Dev Phone 1 (C version, float version) 229　sec
固定小数にしたものは、
・iPhone 並みの速度（38sec～）になるが、描画結果に難あり。

ということで終了です。だいたい予想していた範囲になったのではないかと思います。ここまで読んでいただいた方は、長文にお付き合い頂き、お疲れ様でした。

なお、実際に固定小数でプログラムを書く場合は、精度を意識して書く必要があります。今回はデモプログラムなのであまり気にしてませんが、精度の違う複数の関数を準備して使い分けたりしたほうが高速になります。が、面倒なので、今さら固定小数なんて使いたくないです。最近は組み込み機器にもかなりＦＰＵが搭載されるようになっています。android も早く脱却して欲しいところです。

しかし、iPhone は　double のままうごかして、38sec　なのだろうか。早いな。コンパイラがfloatに直してくれるのだろうか。

最後に、float バージョンで全画面（320x480)を計算したものをつけて終わりとします。だいたい、面積比で遅くなっているのでしょうか。