レベル: 中級 Jack Shirazi (jack@JavaPerformanceTuning.com), Director, JavaPerformanceTuning.com
Kirk Pepperdine (kirk@JavaPerformanceTuning.com), CTO, JavaPerformanceTuning.com
2004年 9月 28日 Troveはオープン・ソースのJavaコレクション・パッケージですが、特にキーや値がプリミティブ・タイプであるようなコレクションを実装する場合には、コアのJavaコレクション・クラスの効率的な置き換えとなります。今回のパフォーマンスの目では、パフォーマンスの導師Jack ShiraziとKirk Pepperdineが、皆さんが慣れているJavaコレクションとTroveクラスがどのように異なるのか、どのような場合に使うべきかについて見て行きます。
しばらく前の2001年終わり頃、私達はEric Friedmanからのeメールを受け取りました。彼はjava.utilクラスを置き換える、オープン・ソースのコレクション・クラスを作ろうと決心したと言うのです。それだけに止まらず、新しいコレクション・クラスはより早く軽量で、より柔軟になります。そう、Ericは600万ドルの（*1）コレクションを作ろうというわけです！
（*1）参考：600万ドルの男（The Six Million Dollar Man）・・・1970年代のテレビドラマ
実を言うと当時私達はJavaプラットフォームのコレクション・クラスを直接置き換えられるという機能に関して、それほど興味を持っていませんでした。一方Joshua Blochは便利で高速、そして拡張性のある汎用のコレクション・クラスを作るという、素晴らしい仕事をしました。しかし汎用性と最適効率とは、しばしば相反するものとなります。2001年の時点でさえ、intやbooleanなどのようなプリミティブ・タイプを処理する特別なコレクション・クラスを作るのは、珍しいことではありませんでした。そうしないとJavaプラットフォームの汎用コレクションにプリミティブ・タイプを保存するコレクションには、IntegerやBooleanのようなラッパー・クラスでラップしたりアンラップしたりすることが必要になります。これは面倒な上に、ラップやアンラップを何度も行うような場合には、すぐにパフォーマンスのボトルネックになってしまいます。
ここで、ちょっと話題を変えます。
夢か悪夢か
Ericはラッピング、アンラッピング無しに直接データ・プリミティブを扱うコレクション・クラスを何バージョンも作ることを提案しました。これは正にパフォーマンス調整者にとっては夢がかない、しかもタイプ・セーフが向上するのですが、設計者にとっては悪夢です。つまりMapを考えてみてください。これにはキーも値もあります。それぞれのキーや値はObjectであるか、または8つの基本データ・タイプ（byte,short,char,int,long,float,double,boolean）のうち、どれか一つです。
これは9種類のキーと9種類の値なので、81種類のMapができることになります！ もっと悪いことに、そのうちの1つにバグがあると、残りの80にもバグがある可能性が高くなります。しかし各データ・タイプを効率的に操作するためにはアルゴリズムを別々に実装する必要があるので、共通コードベースは限られ、これを維持管理するのは膨大な作業となります。私はEricを大いに称賛しました。しかし、彼のコレクションを待ちかまえていたわけではありません。こうしたコレクションの開発やデバッグには時間がかかるのです。
2001年当時、私達はEricをサポートするために、ごく僅かのことしかしませんでした。つまり「Java Performance Tuning」ニュースレター12号の冒頭にEricのTroveプロジェクト宣言を載せたのです。おかしなバグ修正の以外にも、気の毒なEricは全く独りぼっちで、こうした様々なバージョンのコレクションをこつこつと作り続けたのです。そして、素晴らしい仕事を成し遂げました。今日私達はEricの懸命な努力の成果を手にすることができます。Troveコレクションは使用可能なものとしてできあがっており、しかも、非常に使いやすいのです。
膨大なコレクション
さて、以上は経過としては面白いのですが、Troveから何が得られるのでしょうか？ 効率的なコレクションが、とにかく膨大な数あるのです。81バージョンもある多くのHashMap（例えばTIntIntHashMapやTIntObjectHashMapなど）とは別に、プリミティブ（例えばTIntHashSetやTFloatArrayListなど）を保存できるListクラスやSetクラスがあります。しかも、自分独自のデータ・セットに対して、より効率の良さそうな（そしてより柔軟そうな）ハッシュもできるように、自分独自のハッシュ戦略をプラグインとしてつなぎ込むこともできるように、アーキテクチャーが構成されているのです。もちろん、柔軟なハッシュをサポートするためには、パフォーマンスとの兼ね合いを考える必要があります。ハッシュ・マップがボトルネックになるのは、ハッシュ・マップが激しく使われることによる場合が多いのですが、これは普通、ハッシュ機能が何度も何度も呼ばれるということを意味します。ですからハッシュ機能にある僅かなオーバーヘッドも、ボトルネックになる可能性があります。（とは言うものの、もしハッシュ機能がごく単純であれば、JITコンパイラーはそれをインライン化できるかもしれません。そうれば、柔軟なハッシュ戦略をサポートしつつ余分なオーバーヘッドが無くなることになります。）
さらにEricは、コレクションがその要素に対してプロシージャーを実行するSmalltalkパラダイムも実装しています。このプロセスは通常Javaプラットフォームでコレクション要素を横断する方法とは逆なので、少し説明が必要でしょう。Javaプログラミングでコレクションの全要素を処理したいのであれば、リスト1に示すように、通常はイテレーター(Iterator)を取得して各要素にアクセスし、それから各要素を処理します。
リスト1. コレクションを繰り返す
Iterator iterator = collection.iterator();
while (iterator.hasNext())
{
Object o = iterator.next();
... //do something with 'o'
}
|
Troveでは、この繰り返しパターンをサポートするだけではなく、コレクションに対してプロシージャーを渡せるようにもなっています。そうするとコレクションは内部的にこの要素を繰り返し、各要素に対して、順にプロシージャーを適用します。この手法では、イテレーター・オブジェクトが（コレクション自体が繰り返すほどには）効率的に要素を繰り返せない場合には効率が良くなる可能性がありますが、必ずしも何かが効率的になるわけではありません。しかし、明瞭さと柔軟性が増すという利点があります。リスト2は、先の繰り返しの例がどうなるかを示しています。
リスト2. コレクションに対してプロシージャーを渡す
Procedure procedure = new DoSomethingWithOProcedure();
collection.forEach(procedure);
|
オープンなアドレッシング
Troveのmapはチェーニング(連鎖：chaining)の代わりにオープン・アドレス法を使うことで実装されています。Javaのコアコレクション・クラス内では、大部分のマップはチェーニングを使って実装されています。これは、表の中の同じインデックス位置に対して一つ以上のキーがマップする場合には、その位置に対してマップする全要素のリンク付きリストを、そのインデックス位置が保持するように動作します。オープン・アドレス・マップはこれとは異なり、おそらく表の中には空いたインデックスが近くにあるだろう、と想定するのです。こうすることによって、理想的なスロットが一杯の場合には、マップ実装はその隣にある幾つかのスロットのうち、空いているものを見つけるのです。この手法を使うと、リンク付きリスト・ノードの必要性がなくなるので、Troveのマップは同等なコアのコレクション・クラスよりもメモリーの消費量が少なくて済む場合が多いのです。オープン・アドレス法を使用する場合には、パフォーマンスの低下を防ぐため、充分なインデックスの空きを確保できるだけのマップ・サイズを維持するように注意する必要があります。（Troveはロード・ファクターを0.5以下に保持することで、この離れ業を成し遂げています。）そうした点を除けば、オープン・アドレス法はチェーニングと同じくらい効率的であり、多くの場合、むしろ効率が高い可能性があります。
オープン・アドレス法のもう一つの利点は、オープン・アドレス実装はチェーニング実装に必要な、リンク付きリストのノード・オブジェクトを必要としないことです。なぜこれが重要なのでしょう？ ほとんどどのJavaリリースでも、リリース毎にオブジェクト生成とガーベジ・コレクションのパフォーマンスが改善されています。しかし、（より少ないオブジェクトではなく）より多くのオブジェクトを持つということによって、やはりオーバーヘッドが生じるのです。Javaプログラミングでは一般的にどんな問題に対しても、オブジェクトの数を減らすような解決方法が、より効率的です。このトレードオフは、パフォーマンス調整に熟練した人なら誰でも知っていることです。オープン・アドレス法では、より少ないオブジェクトを使ってマップ構造を維持します。これは多くの場合、コアJavaマップよりもTroveマップは小さいのみならず効率的なものになる、ということです。ごく最近のJavaのコアMap実装ではオープン・アドレス法を使っている（例えばIdentityHashMapクラス）ことをここで言ってくべきでしょう。余分な作業になるので現実的には考えられませんが、既存のコアMap実装をオープン・アドレス法を使うように修正することも、できなくはありません。しかし、オープン・アドレス法が必要であれば、Troveが使えるのです！
Trove自体には小さなベンチマーク・テストがついており、コアのJavaコレクションとパフォーマンス比較ができます。スピードとサイズがどの程度改善する可能性があるかは、Dion Almaerによる独立の比較テスト（参考文献）で知ることができます。これらによると、TroveはMap.put()に対して3倍の速さで実行し、またメモリー量も、コアMapが要求するメモリー量の半分より少し多い程度しか必要としないことが分かります。
Autoboxing
Java 5.0プラットフォームではgenericsとautoboxingを導入しています。これは、リスト3に示すようなコードを書けることを意味します。
リスト3. Autoboxingの実際
mymap.put("201",201);
mymap.put("202",202);
int sum = mymap.get("201") + mymap.get("202")
mymap.put("sum",sum);
|
mymapはgenericsを使うと、Integerオブジェクトのみしか保持できないように、さらに制限されるかも知れないことには注意してください。ただし、見えないところでautoboxingが行われていること、つまりリスト3にあるintの一つ一つが、ランタイムではIntegerオブジェクト（普通はその都度新しいオブジェクト）を使ってラップされ、アクセサー・メソッドを使ってアクセスされることにも注意してください（ただしJITコンパイラーがアクセスをインライン化するはずです）。
この点は強調しておく必要があります。つまりJava 5.0プラットフォームのautoboxingは効率に関して間違った印象を与えかねないのです。コード・レベルではプリミティブ・データ・タイプを効率的に使っているように見えるものが、ランタイムに関してはプリミティブ・データ・ラッパー・タイプを非常に効率悪く使ってしまっている可能性があります。Dr Heinz Kabutzの最近の記事によると、autoboxingを不注意にループで使うと、パフォーマンスが一桁遅くなります（参考文献）。
Autoboxingは、プリミティブ・データ・タイプを直接保持するコレクション、例えばint値をラップしたりアンラップしたりせずにint値やObjectキーを保持するTroveのTObjectIntHashMapなどのようなコレクションを使うほどには効率的になりません。Troveは他のプリミティブ・データ・タイプや、TIntIntHashMap（intキーとint値）やTLongArrayList（longを保持するリスト）、TIntSet（intを保持するセット）などのような他のコレクション組み合わせに対する同等なコレクションを保持します。Dion AlmaerのテストでのTIntIntHashMapとHashMapの比較でも、Troveは一桁早いことが示されています。
より柔軟に
皆さんのプロジェクトにもぜひTroveを加えてください。ただし、皆さんが必要とするコレクション全てに対してTroveを使うことは推奨できません。何と言ってもTroveはまだ若く、あまり使われていないので、まだしばらくは幾つかバグが出るでしょう。しかしTroveを使うことで、必要があればクラスをより効率的に使えるという選択肢が生まれることになります。アプリケーションを調整する時には、そういうものこそ必要なのです。
参考文献
著者について
 | | | Kirk PepperdineはJava Performance Tuning.comのCTO（Chief Technical Officer）であり、過去15年間、オブジェクト技術やパフォーマンス調整に注力してきました。Ant Developer's Handbook（MacMillan刊）の共著者でもあります。 |
記事の評価
| 
