(2010/02/02 追記)
Android 2.1 EclairのソースにJITが追加されました。
まだプロトタイプのため実機のDalvikVMに入っておりませんが、自分でコンパイルすることでJITをオンにできます。
id:linuzauさんがベンチマークを取ってくださっています。
(2009/05/14 追記)
こんな日記を書いてたら偶然にも、株式会社イーフローの久納(ひさのう)さんが世界初のDalvik VM JITコンパイラを組込みシステム開発技術展で展示するとのことです!
https://www.exhibitor.jp/SODEC/ja/index.php?ID=PUB詳しくは日本Androidの会より、以下のご本人様からの投稿をご欄下さい。
Google グループ
以下、いつもの「である」調にて書いておりますが、素人の戯言なので信用しないでください。
androidzaurus様、お体のほうはいかがでしょうか。
季節の変わり目で、新型でなくとも風邪をひいた方が多いです。
皆様もどうぞご自愛ください。
Android上におけるSQLiteとJDBMの実行時間の比較
SKK開発においてSQLiteの遅さに失望し、JDBMを採用した。
この件に関し、androidzaurus様がプロファイルを行ってくださった。
JNI遅くないよ。SQLite悪くないよ。TraceViewかわいいよ。 - Android Zaurusの日記
この記事はとても参考になった。
私はtraceviewを使ったことがなかったので、早速traceviewについて調べてみた。
traceviewはSDKに標準で付属してくるツールだ。
解説はSDK付属のドキュメントにも付いてくる。
http://developer.android.com/guide/developing/tools/traceview.html
使い方は非常に簡単で以下のように測定したい部分を囲むだけだ。
// start tracing to "/sdcard/calc.trace" Debug.startMethodTracing("calc"); // ... // stop tracing Debug.stopMethodTracing();
これでトレースファイルが作成される。
上記のandroidzaurus様の記事にはSQLiteの計測に用いたテストプログラムのソースが付いてくるのでダウンロードして読んでみることをお勧めする。
トレースファイルはバイナリなのでエディタでは読めない。
一旦、adb pullでPCに落し、traceviewを使う。
traceviewはWindowsではtraceview.batになるので注意が必要。
またtraceview.batはファイルを編集するか、環境変数を設定するか、SDKをインストールした$ANDROID_HOME/toolsをカレントディレクトリにして起動しなければならない。
traceviewの本体は実行可能なjarであり、batは皮である。
引数としてトレースファイルを指定する。
また-rを付けることでテキスト出力も可能だ。
traceviewで表示される時間はトレースファイルを記録する時間を数に入れない時間であり、実際の実行時間に比べるとかなり小さい。
また実行は1回しか行わないので統計的に有用な時間ではなく、あくまでもそのタイミングにおける参考値程度に考えたほうが良いことがドキュメントにも記されている。
SQLiteとJDBMの比較
SQLiteの計測結果についてandroidzaurus様のまとめは以下になる。
- JNI経由でintの値を取るgetIntJNIのオーダーは、40μ秒〜50μ秒のオーダーでJNIは十分早い。
- SQLiteの実行そのものよりも、Cursorで結果を受け取る部分のオーバーヘッドが大きい。
- Androidのフレームワークとしてデータベースを使いやすくする部分のオーバーヘッドが重い
1番については、より詳細な考察が必要だと思われる。
この部分ではJNIメソッドの正確な「呼び出しコスト」を計測している訳ではない。
traceviewにて表示される計測時間はメソッドの実行時間であり、exclusiveでも子メソッドの実行時間を除いた自身の実行時間である。
より正確には比較対象として同処理内容のpure Javaメソッドを用意する必要がある。
しかし確かに50μ秒は、正確性は期待できないが、実用に対して十分に短かい。
そして2番、3番は全くそのとおりだ。
筆者のPCにて計測した結果は以下の図となった。
ここでJDBMに関しても計測を行ってみた。
結果は以下のとおりである。
何かおかしなことに気付かないだろうか?
なんとSQLiteのほうが10倍速い。
SQLiteでは、データベースに接続し、以下のselect文を行っている。
SELECT VALUE FROM DICTIONARY WHERE KEY = 'a';
対してJDBMでは以下のコードを用いている。
@Override protected String doInBackground(String... params) { Debug.startMethodTracing("/sdcard/jdbm.trace"); try { final String DICTIONARY = "/sdcard/skk_dict_btree"; final String BTREE_NAME = "skk_dict"; // Open Dictionary RecordManager recman; long recid; Properties props; BTree mBTree; props = new Properties(); recman = RecordManagerFactory.createRecordManager(DICTIONARY, props); // try to reload an existing B+Tree recid = recman.getNamedObject(BTREE_NAME); if (recid == 0) { Log.d("TEST", "Dictionary not found: " + DICTIONARY); } mBTree = BTree.load(recman, recid); String value = (String) mBTree.find(params[0]); if (value == null) { Log.d("TEST", "Dictoinary: Can't find Kanji for " + params[0]); return null; } Debug.stopMethodTracing(); Log.d("SQLiteTest", value); return null; } catch (Exception e) { throw new RuntimeException(e); } }
この差はどこから生まれるのか?
筆者はSQLiteが速いことには納得がいく。
Android SDK 1.5にはJITがない。
JNIで書かれたSQLiteとJIT無しで動かしたJDBMとでこのくらいの差がなければGoogleがJNIを選択した甲斐がない。
だが実際の使用ではこれほどまでにひどい差も今まで体験したことがない。
現在のAndroidSKKはファイルからBTreeへのloadは最初に1回起こなうだけでそれ以降の検索はLogで記録しているが、一桁[msec]から二桁前半で大抵終了している。
SQLiteのLIKE節の利用とJDBMとの比較
さて問題はここからである。
androidzaurus様が計測したSQL文は上記のリザルトが必ず1行になるものだ。
では、SQLを次のようにしたら(rev.3のソースのfindKeys())どうなるだろうか?
SELECT KEY FROM DICTIONARY WHERE KEY LIKE 'a%';
結果は5秒を越えている。
これでANRの制限によりこのIME、ではなく、入力対象のActivityが強制終了の対象となる。*1
このようにLIKE文を利用して複数行を獲得するとSQLiteは非常に遅くなる。*2
これはandroidzaurus様が指摘するように、SQLiteのCursor周りは非常に遅いからである。
特にCursorは使用するかしないかに関わらず、最初のCursorからの値取得時に全ての結果の行をJavaオブジェクトに変換する。このため二回目移行の行取得は非常に速くなるが初回の実行時間がひどく、メモリ消費量も多い。
対してJDBMは値の全てをJavaオブジェクトには変換しない。
プログラムも以下のように最初の値のポインタを得ると次回移行はnextにてB-Tree上を遷移するだけですむ。
browser = mBTree.browse( key ); if (browser.getNext(tuple) == false) return; // 最初の一つがkeyと同じ場合listに追加しない String first = (String)tuple.getKey(); if (!first.equals(key)) list.add(first); if (mInputMode == ENG2JAP) { for (int i = 0; i < 5; i++) { if (browser.getNext(tuple) == false) break; list.add((String)tuple.getKey()); } return; }
このため、JDBMは連続する結果に対するアクセスがSQLiteに比べ非常に軽い。
JITがないAndroidでも入力補完表示に全く実行時間を感じない。
これは前回のビデオにて確認してほしい。
SQLiteは今回のような用途には向かないと思われる。
ではSQLiteにて多数の行を処理するにはどうすれば良いであろうか。
SQLiteではRowIDを使用することが可能だ。
列がソートされており、各行にRowIDが振られているのならば、RowIDをキーに1行づつ処理してみてはどうだろうか。
筆者は試していないのでどなたかの報告を待つ。
もう1点としてLIMIT節にて結果の行数制限を行なうことが可能である。
これを行なうと同じSQLでも2桁msecで終了する。
しかし、結果は全体をソートした上位の結果でないので注意が必要だ。
JNIとpure Java、JITの比較
androidzaurus様は件の記事にて以下のようにまとめられている。
で、結論。チュートリアルのNotePadが、すべてのエントリを一度に読み出し、すべてのエントリを一度に書き戻す実装になっているのは、こまめなDBアクセスは、かえって重くなるというAndroidの特質。逆に言うと、データはクラウドに置け、という御託宣。
この結論には修正が必要であると考える。
「こまめなDBアクセスは、かえって重くなるというAndroidの特質」はAndroidの特質ではなく、SQLiteのAndroid向けのラッパーの特質である。Android SDK 1.5でもSQLiteの使用をやめればこの特質には当たらない。
従ってデータはクラウドに置けというのは必須事項ではない。
筆者はクラウド関連技術を好むが、同時にその危険性も非常に危惧している。
AndroidのIMEは使用を許可する場合に、安全性の確認を行なうダイアログが必ず開かれる。
クラウドに提供する情報は常にユーザーの選択と、ユーザー以上に危険性に詳しい設計者による保護が必要であるだろう。
JNIの呼出コストは一般的に通常のJavaがそうであるように重い。
これは測定できなかったが以下の記事が参考になる。
JNIが遅いというパラドックス
Androidアプリで高速描画チューニングをするコツ (3/3):インタビュー特集:Google直伝!(1) - @IT
この記事にて、
JNIを用いた場合の関数呼び出しが、通常のJava内に比べて、倍程度かかってしまうことが分かる。理由は、JNIを介してC/C++にブリッジする際、関数をルックアップするため、ほかの処理を一度止めて関数ポインタを探しているからではないかと考えられる。
と説明されている。
次にJITの将来製について指摘したい。
JDK1.0が単純なバイトコードインタプリタであったことを考えれば、Androidは現在DalvikVMがJDK1.0相当でしかない。
JDK1.1にてJITが付き、さらに全てのメソッドをコンパイルすることは逆に遅くなることがわかり、JDK1.2にてHotSpotが開発された。
JITはJDKのバージョンが上がるごとに改良が行われ、現在では静的コンパイラより動的なコンパイラのほうが速いと言われている。これはGCCが現在では動的プロファイラを装備し、C/C++でも先に実行を行い動的プロファイルを取得し、その結果を用いて再コンパイルする機能が実装されたことを考えても納得がいく。
SKKでもそうであるが、コンピュータの静的推論は誤りが多い。動的に統計を取りその結果に従いチューニングを行ったほうがプログラムの実行は速くなる。現在のJavaのJITはこれを行っている。
JITの効果は非常に高い。
Javaの歴史は既に10年を越え、10年前のPCには既にJITが載っていた。
10年前のPCを調べてみたところPentiumの600MHz相当の時代である。
これは520MHzのG1や、次期600MHzと言われるiPhoneと変わらない。
当時のメモリは256MByte相当が多く、バッテリーを除けばAndroidにJITを載せない理由はないと考える。
次にGCだ。
androidzaurus様は件の記事にて以下のように記述している。
この記述は現行のAndroid1.5において全く正しい。
現在のAndroidのDalvikVMはGCがStopTheWorldと呼ばれるmark&compactionしかない。
しかしJavaはJDK1.4から既に世代別GCと呼ばれるGCを装備している。
これはGCの生存時間によりGCの方法を変えるものであり、これが実装されるとGCに対して考慮するのはオブジェクトを作らないことではなく、オブジェクトのライフタイムを短時間にすることとなり、オブジェクトを積極的に使うことが可能になる。
この世代別GCにはある程度のメモリが必要になるが、メモリは現在でも容量開発のスピードが速く、容量の点では問題がない。バッテリーの問題さえ解決すればAndroidに世代別GCが搭載されるのはすぐだと思われる。
さて、仮にAndroidにJITが実装されたとしよう。
するとJNIメソッドが邪魔になることがSQLiteのトレース結果のグラフからはっりとわかる。
pureJavaのメソッドはJITにより10倍以上速くなる。しかしJNIメソッドは全く速くならないばかりか、JNI呼出とJNIメソッドにおけるオブジェクトの生成はGCに対して非常に高いコストを要求する。
上記のSQLiteの実行時間のビジュアライズを見てほしい。
実行時間をほとんど閉めるメソッドはJNIである。
SQLiteは将来JITが実装されたとしてもその恩恵を受けることができない。
対してpureJavaで書かれたJDBMはその恩恵を多いに受けることができる。
もちろん、現在のAndroidにはJITがない。GCも最低限のものしかない。
このため初期のJ2MEやJDK1.0のような全くオブジェクト指向らしからぬプログラムを書くことが実行速度の高速化に繋がる。
しかし、Javaで長いこと開発していた筆者としては現行Androidのためだけにプログラムの書き方を変えてしまうことは将来の後悔の元となることを指摘したい。
DeveloperWorksにおけるBrian Goetz氏*3の解説記事が参考になるのでぜひ一読してみてほしい。
http://www.google.co.jp/search?hl=en&q=Java+理論と実践+site:ibm.com