Javaの理論と実践: 欠陥マイクロベンチマークを分析する

他にはありませんか?

ソフトウェア技術者は、時には異常なほどパフォーマンスに固執することで有名です。もちろん時には、高速スイッチ用にプロトコル・ルーティング・ソフトウェアを開発する場合のように、ソフトウェア・プロジェクトにおいてパフォーマンスが最も重要な要求事項であることもありますが、ほとんどの場合にはパフォーマンスは他の要求事項、つまり機能性や信頼性、維持管理のしやすさ、拡張性、市場導入までの時間、その他ビジネス上、技術上の要求事項と釣り合いを取る必要があります。今回のJavaの理論と実践では、コラムニストのBrian Goetzが、Java言語構成体のパフォーマンス測定が見かけよりもずっと難しいのはなぜなのかを解説します。

Brian Goetz, Principal Consultant, Quiotix

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



2005年 2月 22日

自分が取り組んでいるプロジェクトでパフォーマンスが重要な要求事項ではない場合、あるいは要求事項にも上がっていない場合であっても、パフォーマンスに関する懸念を無視するのは困難なものです。なぜなら、無視してしまうと、あなたは「悪い技術者」と見なされると思ってしまうからです。ハイ・パフォーマンスのコードを書き終わる頃になると、開発者は小さなベンチマーク・プログラムを書き、ある手法と別の手法のパフォーマンス差を測定しようとします。残念ながら、以前の記事、動的コンパイルとパフォーマンス測定で学んだように、Java言語のイディオムや構成体のパフォーマンスを評価することは、静的にコンパイルされる言語での場合よりも、ずっと困難なのです。

欠陥マイクロベンチマーク

以前の記事「JDK 5.0における、より柔軟でスケーラブルなロック」を公開した後、ある人が、SyncLockTestというベンチマークを送ってきました(リスト1に示します)。これを使えばsynchronizedプリミティブと、新しいReentrantLockクラスのどちらが「速い」かを判定できるというのです。この人は自分のラップトップでこれを実行した後、記事での結論とは逆に、同期の方が速いと結論し、このベンチマークを「証拠」として提示したのです。しかしこのプロセス全体に、つまりマイクロベンチマークの設計から実装、実行、そして結果の解釈まで、幾つかの点に欠陥があるのです。この人は非常に鋭い人であり、これまでも何度か登場しているのですが、そういう人にとっても、こうしたベンチマークは手ごわいのです。

リスト1. 欠陥のあるSyncLockTestマイクロベンチマーク
interface Incrementer {
  void increment();
}
class LockIncrementer implements Incrementer {
  private long counter = 0;
  private Lock lock = new ReentrantLock();
  public void increment() {
    lock.lock();
    try {
      ++counter;
    } finally {
      lock.unlock();
    }
  }
}
class SyncIncrementer implements Incrementer {
  private long counter = 0;
  public synchronized void increment() {
    ++counter;
  }
}
class SyncLockTest {
  static long test(Incrementer incr) {
    long start = System.nanoTime();
    for(long i = 0; i < 10000000L; i++)
      incr.increment();
    return System.nanoTime() - start;
  }
  public static void main(String[] args) {
    long synchTime = test(new SyncIncrementer());
    long lockTime = test(new LockIncrementer());
    System.out.printf("synchronized: %1$10d\n", synchTime);
    System.out.printf("Lock:         %1$10d\n", lockTime);
    System.out.printf("Lock/synchronized = %1$.3f",
      (double)lockTime/(double)synchTime);
  }
}

SyncLockTestは、あるインターフェースの2つの実装を定義しており、System.nanoTime() を使って各実装を10,000,000回実行する時間を測定しています。各実装は、スレッド・セーフな方法でカウンターを増加します。つまり一方は組み込みの同期を使い、他方は新しいReentrantLockクラスを使います。目標としているのは、「同期とReentrantLockのどちらが速いか」という質問に答えることです。一見問題なく見えるこのベンチマークが、なぜ測定に失敗しているのか、あるいは、そもそも何か有用なものを測っているのかを見てみることにしましょう。

着想の欠陥

とりあえず実装上の欠陥は無視するとして、SyncLockTestには、より深刻な、概念上の欠陥があります。つまり質問そのものを誤解しているのです。SyncLockTestは、複数スレッドのアクションを調整するための手法として、同期とReentrantLockのパフォーマンス・コストを比較することになっています。ところが、このプログラムには一つのスレッドしかなく、従って競合は絶対起こり得ません。そもそもロックが問題となる、正にその状況をテストしていないのです!

初期のJVM実装では、競合のない同期が遅いことは広く知られていました。ところがそれ以来、競合のない同期は大幅に改善されているのです。(参考文献には、競合のない同期のパフォーマンスを最適化するためにJVMが使用している手法の幾つかを解説した論文を挙げてあります。)その一方、競合のある同期はこれまで、そして今でも相変わらず、競合のない同期よりもずっと高価なままです。ロックが競合すると、JVMは待ちスレッドのキューを維持するだけではなく、即座にロックを取得できないでいるスレッドを、システム・コールを使ってブロックしたりブロック解除したりする必要があります。また、アプリケーションに高度の競合が起きるとスループットが低下します。これは、より多くの時間がスレッドのスケジューリングに費やされ、実際の作業に使われる時間が減少するためばかりではなく、スレッドがロックを待つためにブロックされている間は、CPUはアイドル状態になる可能性があるためです。同期プリミティブのパフォーマンスを測定するベンチマークであれば、現実的な競合度合いを考慮に入れる必要があります。

手法の欠陥

この、設計上の欠陥に加えて、実行上に少なくとも2つの欠陥があります。つまりこのテストは、単一プロセッサー・システム上で、単一プラットフォーム上でしか実行されていないのです(単一プロセッサー・システムの環境は並行性の高いプログラムでは考えにくく、またマルチ・プロセッサー・システムとは同期パフォーマンスが大きく異なる可能性があります)。あるプリミティブやイディオムのパフォーマンスをテストする時には、特に、下にあるハードウェアとの相互動作が顕著なプリミティブやイディオムをテストする場合は、パフォーマンスに関する結論に至る前に、様々なプラットフォームでベンチマークを実行する必要があります。並行性のように複雑なものをテストする場合には、複数種類のプロセッサーを使用し、しかもそれぞれプロセッサーの使用個数が異なる、何種類ものテスト・システムで試すことによって、対象イディオムの全体的パフォーマンスを把握するのが賢明なのです(メモリー構成やプロセッサーの世代まで考慮すべきなのは言うまでもありません)。

実装上の欠陥

実装面では、SyncLockTestは動的コンパイルに関する幾つかの面を無視しています。以前の記事で説明した通り、HotSpot JVMは最初にインタープリター・モードでコード・パスを実行し、ある回数を実行した後でないと、マシンコードにコンパイルしません。適切にJVMを「ウォームアップ」しないと、2つの面からパフォーマンス測定の結果が大きく歪むのです。まず、テストのランタイムには、コード・パスを分析してコンパイルするためにJITが費やす時間が含まれています。もっと重要こととして、テスト実行の最中にコンパイルが実行されると、テスト結果には解釈実行の時間の一部に加えてJITコンパイル時間、それに最適化実行の時間の一部が加わることになり、実際のコード・パフォーマンスを知るための情報としてはあまり役に立ちません。しかも、もしテストの実行前にコードがコンパイルされておらず、テスト中にもコンパイルされないとすると、テスト実行全体がインタープリターで処理されてしまい、やはり対象としているイディオムの現実的なパフォーマンスを知るための情報としては役に立たないことになります。

SyncLockTestはまた、以前の記事で解説したインライン化(inlining)とデオプティマイゼーション(deoptimization)の犠牲にもなっています。つまり最初のタイミング・パスでは、単一型コール変換(monomorphic call transformation)で積極的にインライン化されたコードを測定し、2番目のパスでは、同じベース・クラスまたはインターフェースを拡張する別のクラスをJVMがロードしたためデオプティマイズされたコードを測定しているのです。SyncIncrementerのインスタンスでタイミング・テスト・メソッドが呼ばれると、ランタイムはIncrementerを実装するクラスが一つだけロードされていると認識し、increment() への仮想メソッド・コールを、SyncIncrementerへの直接メソッド・コールへと変換します。次にLockIncrementerのインスタンスでタイミング・テスト・メソッドが実行されると、test()は仮想メソッド・コールを使うように再コンパイルされます。これではtest()ハーネス・メソッドを通した2番目のパスは、繰り返しの度に最初のパスよりも多くの作業をすることになり、このテストは(リンゴとオレンジを比較するように)全く別物の比較になってしまいます。これでは大きく結果を歪めることになり、どのような組み合わせでも、最初に実行するものの方が速く見えてしまいます。


現実とかけ離れたベンチマーク・コード

ここまで解説してきた欠陥は、ある程度ベンチマーク・コードに手を加えれば修正可能です。つまり競合度合いなどのテスト・パラメーターを導入したり、より広範な種類のシステム上で、テスト・パラメーターに複数の値を入れて実行したりすればよいわけです。ただし手法の欠陥は、いかに手を加えても解決できません。それがなぜかを理解するには、自分をJVMだと考え、SyncLockTestがコンパイルされる時に何が起きるかを理解すればよいのです。

Heisenbenchmark原則

同期のような、言語プリミティブのパフォーマンスを測定するマイクロベンチマークを書く場合には、Heisenbergの原則と格闘することになります。Xという操作がどれほど速いかを測りたいため、X以外のことは何もしたくないわけです。ところがこれは多くの場合、何もしないベンチマークになりがちなのです。つまり、あなたが気付かないうちに、コンパイラーが部分的あるいは完全に最適化を行い、予測よりもテストが速く実行されてしまうのです。そのベンチマークに何か外部的なコード、Yを追加すると、今度はX+Yのパフォーマンスを測っていることになり、Xの測定にノイズが入り込むことになります。もっと悪い場合には、Yの存在によって、JITがどのようにXを最適化するかにも影響を与えてしまいます。良質なマイクロベンチマークを書くためには、フィルターが効き過ぎないようにした上で、データフロー依存性との微妙な平衡点を見つける必要がありす。そうしないと、コンパイラーがプログラム全体を最適化しきってしまったり、フィルターが効き過ぎるために測定対象がノイズの中に消えてしまったりするのです。

ランタイム・コンパイルはプロファイル・データを使って最適化を進めるため、JITが実際のコードに対して行う最適化と、テスト・コードに対して行う最適化とは異なる可能性があります。どのベンチマークでも同じですが、実際には何もしない、あるいは何用にも使われない結果をベンチマーク・コードが生成している、ということをコンパイラーは(正しく)認識するため、コンパイラーはすべてを最適化してしまう、という危険性が非常に高いのです。効果的なベンチマークを書くためには、(実際には死んだコードであっても)死んだものとしてコードを切り取らないように、コンパイラーを「騙す」ことが必要なのです。Incrementerクラスでカウンター変数を使ってもコンパイラーを騙すことはできませんでしたが、死んだコードの除去という点では、コンパイラーは私達が思う以上に賢い場合が多いのです。

同期は言語に組み込まれた機能である、という事実のために、問題はさらに複雑になります。JITコンパイラーはパフォーマンス・コストを減らすために、同期ブロックの扱いに多少の融通をきかせます。同期が完全に除去され、同じモニター上で同期を行う隣接同期ブロックに統合される場合があります。同期のコストを測定している場合には、最適化によって幾つの同期が除去されるかが分からないため(この場合には全部かも知れません!)、こうした最適化は大きな障害になります。さらに悪いことに、JITは(SyncTest.increment()の中の)何もしないコードを、実際のプログラムを最適化するのとは非常に異なった方法で最適化するかも知れません。

事態はさらに悪くなります。このマイクロベンチマークを行う表向きの目的は、同期とReentrantLockのどちらが速いかをテストすることです。同期は言語の中に組み込まれている一方、ReentrantLockは通常のJavaクラスのため、コンパイラーは、何もしない同期と、何もしないReentrantLock取得とを異なった方法で最適化します。この最適化では、何もしない同期が速く見えることになります。コンパイラーはこの2つを別々な方法で最適化し、しかも現実的な状況で行うのとは異なる方法で最適化を行うため。このプログラムの結果からは、現実的な状況でのパフォーマンス差に関して、ほとんど何も分からないことになります。

死んだコードの除去

以前の記事では、ベンチマークにおける、死んだコード除去の問題を解説しました。つまりベンチマークは多くの場合、何ら価値のあることはしないため、コンパイラーがベンチマークの塊全体を除去してしまうことがよく起こり、時間測定の結果を歪めてしまうのです。先のベンチマークには、この問題が何カ所かに見られます。この場合、コンパイラーが一部のコードを死んだものとして除去してしまうという事実は必ずしも致命的ではありません。ここでの問題というのは、2つのコード・パスに対して適用される最適化の度合いが異なっており、測定結果がシステム的に歪められてしまう、ということです。

2つのIncrementerクラスは、何もしないという作業(変数を増加するのみ)をすることになっています。ところが賢いJVMはこのカウンター変数が決してアクセスされないことを認識し、従って、この変数を増加することと関連したコードを除去してしまう可能性があります。そして、ここで深刻な問題が発生するのです。今やSyncIncrementer.increment()メソッドのsynchronizedブロックは空であり、コンパイラーはこれを完全に除去できる一方で、LockIncrementer.increment()は相変わらずロック・コードを含んでおり、コンパイラーはこれを完全に除去できるかも知れませんが、除去できないかも知れないのです。このコードによると、皆さんは同期の方が有利だと思うかも知れません。つまりコンパイラーは、より容易に同期を除去できるわけです。ところがこれは、何もしないベンチマークにおいてずっと起こりやすく、よく書かれた実世界のコードでは、あまり起こらないのです。

これこそが問題なのです。つまりコンパイラーが一方を他方よりも大幅に最適化するにも関わらず、その差が明らになるのは、何もしないベンチマークの中だけなのです。ですから、この手法で同期とReentrantLockのパフォーマンス比較をすることは非常に困難なのです。

ループ・アンロールとロック合体

コンパイラーはカウンター管理を除去しなくても、やはり2つのincrement()メソッドを別々の方法で最適化しようとするかも知れません。標準的な最適化として、ループ・アンロール(loop unrolling)があります。これは、コンパイラーが分岐の数を減らすために、ループをアンロール(展開)するのです。何回の繰り返しをアンロールするかは、ループ本体内部にどのくらいのコードがあるかに依存しますが、LockIncrementer.increment()のループ本体にあるコードの方が、SyncIncrementer.increment()のループにあるコードよりも「多い」のです。さらに、SyncIncrementer.increment()がアンロールされ、メソッド・コールがインライン化されると、アンロールされたループは、ロック-増加-アンロックというグループの繰り返しになります。これらはどれも同じモニターをロックするので、コンパイラーはロック合体(lock coalescing)またはロック粗粒化(lock coarsening)と呼ばれる操作を行って、隣接するsynchronizedブロックを統合します。これはつまり、SyncIncrementerが行う同期の数は、想定よりも少なくなることを意味します。(しかも、これはさらに悪化するのです。ロックを合体した後は、同期本体には増加のシーケンスしかないため、その強さが、単なる一つの加算へと減じられてしまいます。そして、このプロセスが繰り返し行われると、ループ全体が、「counter=10000000」操作を一つ持つだけの単一同期ブロックへと縮小されてしまう可能性があります。そして、そうです。実世界のJVMは、こうした同期を行うのです。)

繰り返しますが、問題は、単にオプティマイザーがベンチマークを最適化しきってしまうというだけではありません。オプティマイザーがそれぞれの代替手段に対して別々の最適化を適用してしまい、しかもそうした最適化が、現実のコードには適用できない可能性がある、ということが問題なのです。

欠陥の一覧

下記のリストは膨大なものではありませんが、このベンチマークがなぜ、作った人が想定したことをしないのか、その理由を挙げています。

  • ウォームアップが行われておらず、JIT実行に要する時間を考慮に入れていない。
  • 単一型コール変換と、その結果としてのデオプティマイゼーションによって引き起こされるエラーの影響を受けやすい。
  • 同期ブロック、あるいはReentrantLockによって保護されたコードは実質的に死んでおり、これがJITの行うコード最適化を歪めている(JITが同期テスト全体を除去してしまう可能性がある)。
  • ロック・プリミティブのパフォーマンスを測ろうとしているが、競合の影響を考慮しておらず、しかも、単一プロセッサーのシステム上でしか実行されていない。
  • 広範なプラットフォーム上で実行されていない。
  • コンパイラーはReentrantLockテストよりも同期テストに対して、より多くの最適化を行うが、その最適化は、同期を使用する現実のプログラムで使うような種類のものではない。

質問が悪ければ、返ってくる答えも悪い

マイクロベンチマークで怖いのは、(たとえ数字が無意味であっても)必ず何らかの数字として結果を出すことです。何かしら測っているのですが、何を測っているのか私達には分からないのです。マイクロベンチマークは、単に特定なマイクロベンチマークのみを測り、それ以上のことは何もしないことが非常に多いのです。ところが私達はベンチマークが特定な構成体のパフォーマンスを測定していると信じ込み、その構成体のパフォーマンスについて誤った結論を出しがちなのです。

皆さんがたとえ素晴らしいベンチマークを書いたとしても、その結果というのは、実行したシステムの上で有効であるに過ぎないのです。少量のメモリーしか持たない、単一プロセッサーのラップトップでテストを実行しても、サーバー・システム上でのパフォーマンスに関しては何も結論できません。compare-and-swapのような下位レベルのハードウェア平行プリミティブは、ハードウェアの構成ごとに大きく異なるのです。

「同期パフォーマンス」のようなものを一つの数字だけで測るのは、とにかく不可能、というのが現実なのです。同期パフォーマンスは、JVMやプロセッサー、負荷やJITの動作状態、また、同期を使って実行されているコードの量や特性によって大きく変動します。ですから一連のベンチマークを一連の様々なプラットフォームで実行し、その結果から類似性を見つけるというのが最善なのです。そうした後に初めて、同期のパフォーマンスに関して何かを結論づけられるのです。

JSR 166(java.util.concurrent)テスト・プロセスの一部として実行するベンチマークでは、プラットフォームによってパフォーマンス曲線が大幅に異なります。CASのようなハードウェア構成体のコストは、プラットフォームによって、またプロセッサーの数によっても異なります(例えば、単一プロセッサーのシステムでは、CASフェールがありません)。ハイパー・スレッドを持つ、単一のIntel P4(1つのダイ(die)に2つのプロセッサー・コア)のメモリー・バリヤー・パフォーマンスは、2つのP4を使った場合よりも高速であり、しかも、どちらもSparcとは異なったパフォーマンス特性を示します。ですから、「典型的な」例を構築して「典型的な」ハードウェアで実行し、実際のハードウェア上でのプログラム・パフォーマンスを多少なりとも示す結果が得られるのを期待する、というのがせいぜいなのです。では「典型的」とはいったい何なのでしょう? 様々な計算方式やIO、同期や競合、メモリーの局所性、アロケーションの振る舞い、コンテキスト・スイッチ、システム・コール、スレッド間の通信など、あらゆるものを組み合わせた、実世界のアプリケーションを近似するもの、ということです。これはつまり、現実的なベンチマークは、実世界のプログラムと非常に似たものになる、ということを意味しています。


完全なマイクロベンチマークを書くにはどうすべきか

では、完璧なマイクロベンチマークを書くにはどうすべきなのでしょう? まず、良質な最適化を行うJITを書くことです。そして、その他の、良質な最適化JITを書いた人に会うことです(そうした人を見つけるのは簡単です。なぜなら、良質な最適化を行うJITは多くないからです!)。そうした人を夕食に招待し、可能な限り高速にJavaバイトコードを実行するためのパフォーマンス・トリックに関して情報交換するのです。また、何百とある、Javaコード実行最適化に関する資料を読み、自分でも幾つか書いてみることです。そうすれば、同期やオブジェクト・プール、仮想メソッド呼び出しなどのコストに関して、良質なマイクロベンチマークを書くだけのスキルが身に付くでしょう。

冗談を言っているのですか?

良質なマイクロベンチマークを書くために挙げた上記の処方箋は、あまりに控え目すぎると思われるかも知れません。しかし良質なマイクロベンチマークを書くためには、動的コンパイルや動的最適化、JVM実装手法などに関して、幅広い知識が要求されるのです。自分が思ったような動作を行うテスト・プログラムを書くためには、それに対してコンパイラーが何をするかを理解し、また、動的にコンパイルされたコードのパフォーマンス特性や、同じ構成体を使った典型的な実世界コードと生成されたコードとの違いを理解している必要があります。こうしたことを理解していないと、自分が想定したものをプログラムが確かに測定しているかどうかを判定できません。

ではどうすべきなのでしょう?

同期が代替ロック機構よりも速いかどうか、(あるいは類似のマイクロパフォーマンスに関する質問への答え)を本当に知りたいのであれば、どうすべきなのでしょう。一つの選択肢は(大部分の開発者には好まれませんが)、「エキスパートを信頼する」ことです。JSR 166 EGのメンバーはReentrantLockクラスの開発にあたって、何千時間とまでは言いませんが、何百時間にも渡るパフォーマンス・テストを非常に多くの様々なプラットフォーム上で実行し、JITが生成したマシン・コードを調べ、結論を引き出しています。しかもそれからコードに細工を加え、再度同じようなテストを行っているのです。このクラスの開発と分析には、熟練した技術と、JITやマイクロプロセッサーの振る舞いに関する詳細知識が惜しげもなく費やされています。残念ながらその結果は、いかに私達が努力しても、一つのベンチマーク・プログラムに要約できるものではありません。もう一つの選択肢は、「マクロ」ベンチマークに注目することです。実世界のプログラムを幾つか書き、両方の方法でコード化し、現実的な負荷生成戦略を開発し、現実的な負荷条件と現実的な展開構成の下で、2つの手法でアプリケーションのパフォーマンスを試すのです。大仕事になりますが、皆さんが求めている答えにずっと近いものが得られるはずです。

参考文献

コメント

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=218548
ArticleTitle=Javaの理論と実践: 欠陥マイクロベンチマークを分析する
publish-date=02222005