Javaの理論と実践: パフォーマンスに関する都市伝説を再検証する

アロケーションは思ったよりも速く、しかも、さらに速くなりつつあります

Java言語には、パフォーマンスに関する迷信が山のようにあります。その幾つかは当を得たものですが、掲示板やニュースグループでJavaのパフォーマンスに関する話題を見ると、JVM(Java Virtual Machine)の実際の動作に関して、非常に大きな誤解があるようです。今回の『Javaの理論と実践』では、JVMではアロケーションが遅いという、繰り返し伝えられているパフォーマンスの迷信に対して、Brian Goetzが風穴を開けます。

ちょっとしたクイズがあります。生のアロケーション・パフォーマンスとして速いのは、Java言語でしょうか、それともC/C++でしょうか。この答えに、多くの人は驚くでしょう。最近のJVMのアロケーションは、最高パフォーマンスのmalloc実装よりも、ずっと高速なのです。HotSpot 1.4.2以降でのnew Object() 用の一般的なコード・パスは、約10マシン命令(Sun提供のデータより。参考文献を参照)ですが、Cで最高パフォーマンスのmalloc実装では、1つのコールあたり平均60から100の命令が必要です(Detlefsなどのデータによる。参考文献を参照)。しかもアロケーションのパフォーマンスは、全体的なパフォーマンスのコンポーネントとして小さなものではありません。ベンチマークによると、PerlやGhostscriptなど実世界でのCプログラムやC++プログラムでは、実行時間全体の20%から30%がmallocやfreeに費やされています。これは、健全なJavaアプリケーションでのアロケーションやガーベジ・コレクションのオーバーヘッドよりも、はるかに大きな数字です(Zornのデータによる。参考文献)。

Brian Goetz (brian@quiotix.com), Principal Consultant, Quiotix

Brian Goetz は18 年間以上に渡って、専門的ソフトウェア開発者として働いています。彼はカリフォルニア州ロスアルトスにあるソフトウェア開発コンサルティング会社、Quiotixの主席コンサルタントであり、またいくつかのJCP Expert Groupの一員でもあります。2005年の末にはAddison-Wesleyから、Brianによる著、Java Concurrency In Practiceが出版される予定です。Brian著による有力業界紙に掲載済みおよび掲載予定の記事のリストを参照してください。



2005年 9月 27日

進め、そして散らかしてやれ

ブログやSlashdotのポスティングを数多く検索しなくても、「ガーベジ・コレクションは、決して直接メモリー管理と同じほど効率的ではない」というような自信に満ちた発言が簡単に見つかるでしょう。ある意味で、こうした発言は正しいと言えます。つまり動的メモリー管理は「同じほどの速さ」ではありません。多くの場合は「ずっと高速」なのです。malloc/freeによる方法では、何ブロックかのメモリーを一度に処理しますが、ガーベジ・コレクションでの方法はメモリー管理を大きなバッチとして行うため、より高い最適化を行える可能性があるのです(ただし、予測のために幾らかの損失は生じますが)。

1日中かかって塵を一つ一つ拾い上げるよりも、1つの大きな塊としてゴミを片づけた方が簡単、という、もっともらしい理屈は、確かにデータでも裏付けられています。ある研究によると(Zornによる。参考文献)、幾つかの一般的なC++アプリケーションに対して、mallocを、控え目なBDW(Boehm-Demers-Weiser)ガーベジ・コレクターで置き換えたところ、これらのアプリケーションの多くは、伝統的なアロケーターではなくガーベジ・コレクターを使って実行した時の方が高速化されたということです。(しかもBDWは、控え目な、非移動型ガーベジ・コレクターのため、アロケーションやスペース再利用の最適化機能や、メモリー局所性を改善するための機能が非常に制限されています。JVMで使われているような、具体的に再配置を行うコレクターの方が、ずっと優れています。)

JVMでのアロケーションは、常に速かったわけではありません。確かに初期のJVMでは、アロケーションやガーベジ・コレクションでのパフォーマンスは貧弱であり、これが例の伝説の起源となっているのは確かでしょう。非常に初期の頃には、「アロケーションは遅い」という助言を頻繁に目にしました。実際ロケーションに限らず、初期のJVMではすべてが遅かったのです。そしてパフォーマンスの導師達は、オブジェクト・プーリングなど、アロケーションを避けるための様々な細工を主張しました。(ご注意: オブジェクト・プーリングは今や、最重量級のオブジェクトに使用する場合を除いて、深刻なパフォーマンス損失となります。たとえ最重量級オブジェクトに使用する場合であっても、並行性のボトルネックを生ずることなく正しく使用するのは簡単ではありません。)しかしJDK 1.0の頃から、非常に多くのことが起きました。JDK 1.2で導入された世代別(generational)コレクターによって、アロケーションをずっと簡単に扱えるようになり、パフォーマンスが大幅に改善されたのです。

世代別GC(Generational garbage collection)

世代別GCは、ヒープを複数の世代に分割します。大部分のJVMでは、「young」と「old」という2つの世代を使います。オブジェクトはyoung世代に割り振られます。これらのオブジェクトが一定回数のガーベジ・コレクションを生き延びると、「長生きした」と見なされ、「old」世代に昇格されます。

HotSpotでは、young世代コレクターとして3つの選択肢(シリアル・コピー、パラレル・コピー、パラレル・スカベンジ(scavenge))がありますが、これらは皆、「コピー型」のコレクターであり、幾つか重要な特徴が共通しています。コピー型コレクターは、メモリー・スペースを半分に分割し、1度に半分しか使いません。最初使われる半分は、使用可能なメモリーを、1つの大きな塊として構成します。アロケーターは、使われていない部分の最初のNバイトを返し、「使用中」部分と「空き」部分を分離しているポインターを移動することによって、アロケーション・リクエストに対応します。これをリスト1の擬似コードで示します。使用中の半分が一杯になると、ガーベジ・コレクターは生きているオブジェクト(ガーベジではないもの)すべてを、もう一方の半分のボトムに(ヒープを圧縮して)コピーします。そして今度は、もう一方の半分にアロケーションを開始します。

リスト1.  コピー型コレクターがある場合のアロケーターの振る舞い
void *malloc(int n) {
    if (heapTop - heapStart < n)
        doGarbageCollection();

    void *wasStart = heapStart;
    heapStart += n;
    return wasStart;
}

この擬似コードを見ると、なぜコピー型コレクターのアロケーションが速いのかが分かるでしょう。新しいオブジェクトを割り振る、ということは、単にヒープに充分なスペースが残っているかをチェックし、残っていればポインターを叩く、ということに過ぎないのです。フリー・リストの検索や、最適リスト、最初に適合するもののリスト、索引リスト(lookaside list)などの検索は必要ありません。単にヒープから最初のNバイトをつかみさえすれば、それで終わりなのです。

デアロケーション(deallocation)はどうなのか

しかし、アロケーションは、メモリー管理の半分でしかありません。残りの半分はデアロケーションです。大部分のオブジェクトでは、直接ガーベジ・コレクションのコストは、ゼロであることが分かります。これは、コピー型コレクターでは死んだオブジェクトを訪ねたりコピーしたりする必要はなく、生きたオブジェクトだけを相手にすればよいためです。ですからアロケーションのすぐ後にガーベジとなったオブジェクトは、コレクション・サイクルにとっては何ら作業負荷にはなりません。

典型的なオブジェクト指向プログラムでは、大部分のオブジェクト(様々な研究によると、92から98%)は「若くして死ぬ」、つまり、割り振られるとすぐに(多くの場合、次のガーベジ・コレクションの前に)ガーベジとなります。(この性質は世代仮説(generational hypothesis)と言われ、実験でもテストされており、多くのオブジェクト指向言語に当てはまることが確認されています。)従って、アロケーションが高速なだけではなく、ほとんどのオブジェクトにとって、デアロケーションにもコストがかからないのです。

スレッド・ローカルなアロケーション

もしアロケーターが本当にリスト1に示すように実装されたとすると、共有されるheapStartフィールドは、すぐに並行性にとって大きなボトルネックになります(このフィールドを保護するためのロック取得が、アロケーション毎に必要なため)。この問題を避けるために、大部分のJVMでは、『スレッド・ローカルなアロケーション・ブロック(thread-local allocation block)』を使います。ここでは、各スレッドがヒープから大きなメモリーの塊を割り振り、スレッド・ローカルなブロックの中で小さなアロケーション・リクエストを連続的に処理します。その結果、スレッドが共有ヒープ・ロックを取得すべき回数が大幅に減り、並行性が改善されるのです。(この問題に対して、伝統的なmalloc実装のコンテキストによって対応するのは難しく、コストもかかります。プラットフォームの中にスレッド・サポートとガーベジ・コレクション両方を組み込むことにより、前記のシナジー効果を得ることができます。)


スタック・アロケーション

C++では、オブジェクトをヒープ上に割り振るか、スタック上に割り振るかを選択することができます。スタック・ベースのアロケーションは、より効率的です。アロケーションのコストは安く、デアロケーションのコストは本当にゼロです。また、オブジェクトの存続時間を区切るための機構がC++には用意されており、オブジェクトを解放することを忘れる危険性が少なくなっています。その一方で、C++でスタック・ベースのオブジェクトへの参照を公開したり共有したりする場合には、十分に注意する必要があります。(スタック・ベースのオブジェクトは、スタック・フレームが解除されると自動的に解放されるので、ぶら下がりポインターが発生しがちなため。)

スタック・ベースのアロケーションの、もう一つの利点は、非常にキャッシュしやすいことです。最近のプロセッサーでは、キャッシュ・ミスによる損失は重大です。そのため、言語やランタイムにデータの局所性を実現できるような機構がある場合には、パフォーマンスを改善することができます。スタックの一番上は、ほとんど必ずキャッシュの中で「hot」であり、一方ヒープの一番上は、ほとんど必ず「cold」です(そのメモリーが使われてから長い時間が経っている可能性が高いため)。そのため、オブジェクトをヒープ上に割り振ると、スタック上に割り振る場合よりも、キャッス・ミスが起こりやすくなります。

もっと悪いことに、ヒープ上にオブジェクトを割り振る場合のキャッシュ・ミスは、とんでもないメモリー対話動作を引き起こします。ヒープからメモリーを割り振る場合には、そのメモリーの内容は(そのメモリーが最後に使われた後に何が残っているにせよ)すべてガーベジです。既にキャッシュの中にあるものではないメモリー・ブロックをヒープ上に割り振ると、そのメモリー内容がキャッシュに運び込まれる間、実行は停止されます。次に、わざわざキャッシュに持ち込んだ値を、即座にゼロ、あるいは他の初期値で上書きするため、メモリー動作が大量に浪費されるのです。(AzulのVegaのような一部のプロセッサーでは、ヒープ・アロケーションを加速するハードウェアが含まれています。)

エスケープ分析(Escape analysis)

Java言語では、スタック上にオブジェクトを割り振るための明示的な方法は用意されていませんが、だからといってJVMがスタック・アロケーションを使えないわけではありません。JVMでは、エスケープ分析(escape analysis)と言われる手法を使うことができます。エスケープ分析を利用すると、あるオブジェクトが存続時間中ずっと1つのスレッドにとどまること、そしてその存続時間が、対象となるスタック・フレームの存続時間によって制限されていることが分かるのです。そうしたオブジェクトは、ヒープ上ではなくスタック上に安全に割り振ることができます。さらに良いことに、小さなオブジェクトの場合は、JVMは最適化によってアロケーションそのものを無くしてしまい、単純にオブジェクトのフィールドをレジスターに入れてしまうのです。

リスト2は、最適化してヒープ・アロケーションを無くすためにエスケープ分析を使っているところを示しています。Component. getLocation() メソッドは、呼び出し側がコンポーネントの実際の場所を誤って変更できないように、コンポーネント位置をディフェンシブ・コピー(defensive copy)しています。最初にgetDistanceFrom() を呼ぶと、もう一方のコンポーネントの位置を取得できます(これにはオブジェクト・アロケーションが含まれます)。それからgetLocation() が返すPointのxフィールドとyフィールドを使って、2つのコンポーネント間の距離を計算することができます。

リスト2.  典型的なディフェンシブ・コピー手法を使って複合値を返す
public class Point {
  private int x, y;
  public Point(int x, int y) {
    this.x = x; this.y = y;
  }
  public Point(Point p) { this(p.x, p.y); }
  public int getX() { return x; }
  public int getY() { return y; }
}

public class Component {
  private Point location;
  public Point getLocation() { return new Point(location); }

  public double getDistanceFrom(Component other) {
    Point otherLocation = other.getLocation();
    int deltaX = otherLocation.getX() - location.getX();
    int deltaY = otherLocation.getY() - location.getY();
    return Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  }
}

getLocation() メソッドには、自分が返すPointによって呼び出し側が何をしようとしているのかは分かりません。呼び出し側は参照を保持しようとしている(例えばその参照をコレクション(collection)の中に置くなど)ため、getLocation() が条件付きでコーディングされているのかも知れません。しかしこの例では、getDistanceFrom() はそれをしようとしているわけではありません。単にごく短時間Pointを使ってから廃棄しています。これでは、完璧に良いオブジェクトを浪費しているように見えます。

賢いJVMであれば、何が起きているかを判断でき、条件付きコピーによるアロケーションを、最適化して無くすことができます。最初にgetLocation() へのコールがインライン化され、またgetX() と getY() へのコールもインライン化され、その結果、getDistanceFrom() は実質的にリスト3のように振る舞うことになります。

リスト3.  getDistanceFrom() にインライン最適化を適用した結果を表す擬似コード
  public double getDistanceFrom(Component other) {
    Point otherLocation = new Point(other.x, other.y);
    int deltaX = otherLocation.x - location.x;
    int deltaY = otherLocation.y - location.y;
    return Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  }

この時点で、最初のラインで割り振られたオブジェクトはその基本ブロックから決して漏洩(escape)しないこと、そしてgetDistanceFrom() はotherコンポーネントの状態を決して変更しないことが、エスケープ分析によって分かります。(ここで漏洩というのは、それに対する参照がヒープに保存されたり、コピーを保持する可能性のある未知のコードに渡されたりしない、という意味です。)Pointは真にスレッド・ローカルであり、その存続時間は、それが割り振られている基本ブロックによって制約されていることが分かっているのだとすると、Pointはスタック上に割り振ることができます。あるいは、最適化によって完全に除去することができます。これをリスト4に示します。

リスト4.  getDistanceFrom() によって、最適化してアロケーションを除去した結果を示す擬似コード
  public double getDistanceFrom(Component other) {
    int tempX = other.x, tempY = other.y;
    int deltaX = tempX - location.x;
    int deltaY = tempY - location.y;
    return Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  }

結果は、(安全なコーディング手法が多数ある中で)カプセル化や条件付きコピーによって実現される安全性を保った上で、全フィールドがパブリックの場合に得られるパフォーマンスと、全く同じパフォーマンスが得られるのです。

Mustangでのエスケープ分析

エスケープ分析は、長年話題に上っていた最適化ですが、ついに登場したのです。Mustang(Java SE 6)の現在のビルドでは、エスケープ分析を行うことができ、適切と判断される場合にはヒープ・アロケーションをスタック・アロケーション(あるいはアロケーション無し)に変換することができます。エスケープ分析を使って一部のアロケーションを無くすことによって、平均アロケーション時間はさらに早くなり、メモリー占有スペースが減り、キャシュ・ミスも少なくなります。さらに、最適化によって一部のアロケーションを無くすことによって、ガーベジ・コレクターに対する圧力を減らすことができ、ガーベジ・コレクションの頻度も減らすことができます。

エスケープ分析によって、たとえ言語的にオプションが用意されていてもソースコードでは実際的でない場合であっても、スタック・アロケーションを実現できる可能性もあります。これは、ある特定なアロケーションを最適化によって無くせるかどうかは、オブジェクトを返すメソッドの結果が、ある特定なコード・パスで実際にどのように使われるかに依存するためです。getLocation() から返されるPointは、すべての場合のスタック・アロケーションには適していないかも知れませんが、いったんJVMがgetLocation() をインライン化すれば、JVMは各呼び出しを別々に最適化できるようになるため、2つが両方実現します。つまり、下位レベルのパフォーマンス調整に関する判断に費やす時間は少なくなり、しかも最適パフォーマンスが得られるのです。


まとめ

JVMは驚くほど良くなっており、これまで開発者しか知らないと思われていたことまで理解できるようになっています。スタック・アロケーションとヒープ・アロケーションのどちらが適切か、ケースバイケースでJVMに判断させることによって、スタック上に割り振るべきかヒープ上に割り振るべきかをプログラマーに悩ませることなく、スタック・アロケーションによるパフォーマンスの恩恵が受けられるのです。

参考文献

学ぶために

製品や技術を入手するために

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Java technology
ArticleID=218785
ArticleTitle=Javaの理論と実践: パフォーマンスに関する都市伝説を再検証する
publish-date=09272005