Javaコードの診断: Javaコードのパフォーマンスを向上させる

末尾再帰変換はアプリケーションの速度を向上させる可能性はあるが、すべてのJVMで可能な操作ではない

Comments

末尾再帰と変換

多くのプログラムにはループが含まれており、これが合計処理時間のかなりの部分を占めます。多くの場合、これらのループは複数の変数を繰り返し更新し、また各変数の更新は更新される他の変数の値に依存します。

これらの変数は、反復が末尾再帰関数 として表現されている場合、関数に渡されるパラメーターとして表現されます。(注意: ある再帰呼び出しの戻り値が、その関数を呼び出す側の関数の値として直接戻される場合、その呼び出しを末尾再帰呼び出しと言います。呼び出しを行うときに呼び出し元関数のコンテキストを記憶している必要はありません。)

こうした特性があるため、末尾再帰関数とループの間にはちょうどよい対応関係があります。つまり、それぞれの再帰呼び出しは、単純に、ループをもう1回反復することであると考えることができます。しかし、変数パラメーターの値は一度に再帰呼び出しに送られるため、ループの場合よりも簡単にそれらの値を更新することができます。さらに、多くの場合、使いにくいブレーク・ステートメントの代わりに、関数からの単純な戻り値を使用することができます。

しかしJavaプログラミングでは、この方法で反復を表現すると、大量の再帰呼び出しによってスタックがオーバーフローする恐れがあるため、効率が悪くなる可能性があります。

解決策は比較的単純です。これらの末尾再帰関数は、実際には、ループをより簡単に書くため手段にすぎないので、コンパイラーによって末尾再帰関数が自動的にループに変換されればよいのです。それにより、両方の方法の良いところを十分に活用できます。

しかし、末尾再帰関数を単純なループに自動的に変換する方法はよく知られているにもかかわらず、Java仕様ではこの変換を行うことが要件となっていません。おそらく、これが要件となっていない理由の1つは、一般にオブジェクト指向言語ではこの変換を静的に行うことができないためであると思われます。したがって、末尾再帰関数から単純なループへの変換は、JITコンパイラーによって動的に行う必要があります。

なぜこのようになるのかを理解するために、次に、複数の整数からなる集合に、反復子のエレメントを乗算するサンプルのバグをあげます。

次のプログラムにはバグが含まれているため、実行時に例外がthrowされます。しかし、このシリーズの以前の多くの記事で示したように、プログラムがthrowする例外は、(バグの種類を識別する手掛かりであるのと同時に) バグがプログラムのどこにあるのかを判断するための貴重な手掛かりであるので、コンパイラーによってプログラムが変更されて、その変更されたコードが異なる例外をthrowするようになることは望ましくありません。

リスト1. 複数の整数 (Integer) の集合Iteratorのエレメントの乗算の失敗
import java.util.Iterator;

public class Example {

  public int product(Iterator i) {
    return productHelp(i, 0);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}

product メソッドのバグに注意してください。このメソッドはaccumulatorの値 "0" で productHelp を呼び出しています。accumulatorの値は "1" でなければなりません。そうしないと、クラス Example のどのインスタンスで product を呼び出しても、どのようなIteratorが渡されたかにかかわらず、結果が "0" になってしまいます。

リスト2に示すように、このバグはたまたま修正され、一方でクラス Example のサブクラスが作成されていたとします。

リスト2. リスト1のタイプの不適切な呼び出しを捕そくする試み
import java.util.*;

class Example {

  public int product(Iterator i) {
    return productHelp(i, 1);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}


// And, in a separate file:

import java.util.*;

public class Example2 extends Example {
  int productHelp(Iterator i, int accumulator) {
    if (accumulator < 1) {
      throw new RuntimeException("accumulator to productHelp must be >= 1");
    }
    else {
      return super.productHelp(i, accumulator);
    }
  }

  public static void main(String[] args) {
    LinkedList l = new LinkedList();
    l.add(new Integer(0));
    new Example2().product(l.listIterator());
  }
}

クラス Example2 のオーバーライドされた productHelp メソッドは、accumulatorが "1" 未満の場合に実行時例外をthrowすることにより、 productHelp に対する上記のような不適切な呼び出しを捕そくしようとします。残念ながら、このようにすることにより新しいバグが生まれます。 Iterator に "0" のインスタンスが含まれていると、 productHelp は再帰呼び出しを行ったときにクラッシュしてしまいます。

ここで、クラス Example2 のメイン・メソッドで Example2 のインスタンスが作成され、その product メソッドが呼び出されていることに注意してください。このメソッドに渡される Iterator には "0" が含まれるので、このプログラムはクラッシュすることになります。

ただし、クラス Example 内の productHelp は、確かに末尾再帰的であることはわかります。1つの静的コンパイラーが、リスト3のように、このメソッドの本体をループに変換したとします。

リスト3. 例: 静的コンパイルでは末尾呼び出しを最適化できない
  int productHelp(Iterator i, int accumulator) {
    while (i.hasNext()) {
      accumulator *= ((Integer)i.next()).intValue();
    }
    return accumulator;
  }

変換の後、productHelp に対して最初の呼び出しを行うと、スーパー・メソッドが呼び出されます。スーパー・メソッドは、単に、その結果を計算するためにIteratorをループします。例外はthrowされません。

このコードを2つの異なる静的コンパイラーでコンパイルして、一方の場合には生成されるコードが例外をthrowし、もう一方の場合には例外をthrowしない、ということになると非常に混乱します。

JITが変換を行うかどうか?

リスト3の例で示されているように、静的コンパイラーがJava言語のセマンティクスを維持しながらJavaコードで末尾再帰の変換を行うことは期待できません。静的コンパイルではなく、JITによる動的コンパイルが必要となります。JVMによって、JITがこれを行う場合と行わない場合があります。

使用しているJITが末尾再帰メソッドを変換するかどうかは、次の小さなテスト・クラスをコンパイルして実行してみるとわかります。

リスト4. 末尾再帰を変換を行うJITかどうかの判別
public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

このクラスの loop メソッドについて、しばらく考えてみましょう。このメソッドは、それ自体を可能な限り、再帰的に呼び出します。このメソッドは戻ることがなく、外部の変数にどのような影響も与えることがないため、リスト5のように本体を置き換えても、プログラムのセマンティクスが保持されます。

リスト5. 動的変換
public class TailRecursionTest {

  private static int loop(int i) {
    while (true) {
    }
  }

  public static void main(String[] args) {
    loop(0);
  }
}

これは、実際に、十分な機能を持つコンパイラーならば行える変換そのものです。

使用しているJITコンパイラーが末尾再帰呼び出しを反復に変換する場合は、このプログラムはいつまでも同じように実行され続けます。このプログラムに必要なメモリーは少なく、時間がたっても増えません。

一方、JITが変換を行わない場合は、プログラムはすぐにスタック・スペースを使い尽くして、スタック・オーバーフロー・エラーを報告します。

このプログラムをいくつかのJava SDKで実行したところ、驚くべき結果が得られました。SunのHotspot JVMのバージョン1.3で実行してみると、Hotspotはこの変換を行わないことが分かりました。デフォルト設定の場合、私のマシンではスタック・スペースが1秒足らずで使い尽くされてしまいました。

一方、IBMのJVMのバージョン1.3は問題なく実行されました。つまり、この方法でコードを変換するこということになります。

まとめ

私たちの書いたコードが、常に、末尾再帰呼び出しを変換するJVMで実行されることは期待できない、ということは覚えておかなければなりません。したがって、さまざまなJVMで納得できるパフォーマンスが得られるようにするには、末尾再帰的パターンを、反復のスタイルに適合するようなコードとして書くことを、常に心がける必要があります。

しかし、注意が必要です。上記の例が示すように、この方法でのコード変換は、人間の手によって行う場合にも、ソフトウェアによって行う場合にも、バグを発生させる恐れがきわめて高いからです。


ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Java technology
ArticleID=219672
ArticleTitle=Javaコードの診断: Javaコードのパフォーマンスを向上させる
publish-date=05012001