Javaでの末尾再帰の最適化

長い間、関数型プログラミングの世界の特定のものが非関数型言語に浸透しています。 ラムダ式がJavaに統合できたのは奇妙に思えるかもしれませんが、テール再帰の最適化（同等のループへの再帰の変換）はまだ簡単ではありませんが、まだ行われていません。 どうして彼女じゃないの？

理由を理解し、自分の手で何ができるかを見てみましょう。

まず、例。 今回は不幸な階乗を苦しめず、別の関数を使用することをお勧めします。

static int add(int x, int y) { if (y == 0) return x; return add(x ^ y, (x & y) << 1); } 

これは、2つの整数を再帰的に追加する方法です。 これは、末尾再帰の定義に適合します。各再帰呼び出しの直後にreturn操作が続きます。 最適化とは、再帰呼び出し中に新しいスタックフレームを作成するのではなく、現在のスタックフレームを再利用することです。 これを行うには、古いパラメーターの代わりに新しいパラメーターを配置し、メソッドの最初の命令への無条件遷移を実行します。 擬似コードでは、次のようになります。

 static int add(int x, int y) { start: { if (y == 0) return x; (x, y) = (x ^ y, (x & y) << 1); goto start; } } 

さらに、さまざまな文体のバリエーションが可能ですが、一般に、手動最適化後のコードは次のようになります（ここでは、わかりやすくするために、より美しく、冗長性を高めています）。

 static int add(int x, int y) { while (true) { if (y == 0) return x; int _x = x ^ y; int _y = (x & y) << 1; x = _x; y = _y; } } 

末尾再帰の手動最適化のマイナスはすぐに明らかになります。特に、複数の再帰呼び出しがある場合、コードは悪化します。 最適化が自動的に行われるようにします。

そして、すべては問題ありませんが、1つあります。最適化はプログラム実行のセマンティクスを破壊します。 これは、Javaでは、コールスタックに関する情報がコード内のどこからでも利用できるためです。 また、インラインメソッドの場合、JITがすべてを解決できる場合、再帰呼び出しをGOTOに置き換えると、仕様に従って必要なエントリポイントに関する情報を含む多くのスタックフレームが失われます。

これは不快であり、おそらくJavaでこの最適化が行われないことを示唆しています。

研究を続けるために、スタックトレースからいくつかの行が消えるという事実に我慢します。 パフォーマンスの向上（またはコードの美しさ）がより重要であるとします。 最適化を妨げる可能性のある他の要因を特定します。

• 多型：
  
  GOTOを実装するには、実際には同じメソッドを呼び出す必要があることを確実に知る必要があります。 この要件は以下について満たされます。
  
  -静的メソッド。
  -プライベートメソッド。
  - finalクラスのメソッド;
  -明示的なinvokespecial呼び出し。 invokespecialはスーパークラスメソッドの呼び出しにのみ使用可能なため、コンパイラはソースJavaコードからこのオプションを作成できません。
  
  
• 例外：
  
  tryブロック内で突然再帰呼び出しが発生した場合、このブロック自体の外部の命令に制御を移して転送することはできません。 以下に例を示します。
  
  

   static int f(boolean shouldThrow) { if (shouldThrow) throw new RuntimeException(); try { f(!shouldThrow); } catch (Exception e) { } return -1; } 

  
  f(false)呼び出すと-1が返されますが、再帰呼び出しの場所でGOTOを実行すると、 RuntimeExceptionが発生します。これは、最適化が正しい場合に起こるべきこととは明らかに異なります。

Javaクラスのバイトコードを変更するには、少なくとも2つの実績のある方法があります。

• プリプロセッサ-コンパイラに組み込まれているため、バイトコードの変更はクラスファイルに分類されます。
• ツールキットClassLoaderに統合され、変更はランタイムでのみ表示されます。

2番目のオプションを選択し、末尾再帰を最適化する単純なJavaエージェントを作成しました。 彼は、上記の条件下でのみ最適化を実行できます。

• static method / final method / final class 。
• 再帰呼び出しはtryブロックの外側にあります。

せっかちな人のために、githubへのリンク： github.com/ibessonov/java-tailrec-agent
カスタマイズされたIDEAプロジェクトがあり、それらのプロジェクトで遊ぶ例があります。 そして、患者のために-例について少し説明します。

別の説明でアクセス修飾子をチェックする場合、その実装の証拠の力は必要ありません。 したがって、これを省略して、典型的な方法を検討し、何が起こるかを追跡します。

 static int gcd(int n, int m) { try { if (m == 0) return n; } catch (Throwable t) { // do nothing } return gcd(m, n % m); } 

コンパイル後、メソッドは次のようになります（読みやすくするために簡略化されています。一部の情報は意図的に省略されています）。

 static gcd(II)I TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable TryBlockStart: ILOAD 1 IFNE ElseBlock ILOAD 0 TryBlockEnd: IRETURN CatchBlockStart: ASTORE 2 //      -    ElseBlock: ILOAD 1 ILOAD 0 ILOAD 1 IREM INVOKESTATIC Main.gcd(II)I IRETURN 

各メソッドには、 tryブロックの説明の配列が含まれています。 各説明には、ブロック開始ラベル、ブロック終了ラベル、例外ハンドララベル、例外クラスハンドルの4つのコンポーネントがあります。 この情報により、 tryブロック内の命令を明確に識別し、最適化することはできません。

次に、メソッド自体に一致するメソッド記述子を持つすべてのINVOKE*命令を検索する必要があります（この場合、 Mainクラスメソッドのgcd(II)I記述子が検索されます）。次に、 RETURN型の命令が直接続きます。

見つかったINVOKESTATICは、呼び出しから無条件ジャンプに変換する必要があります。 スタックの呼び出し時点ではすべてのパラメーターであることが知られています。 静的メソッドの場合、すべてが単純であるため、これらのパラメーターをローカル変数に保存し直し、無条件で最初にジャンプする必要があります。

 static gcd(II)I TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable StartLabel: TryBlockStart: ILOAD 1 IFNE ElseBlock ILOAD 0 TryBlockEnd: IRETURN CatchBlockStart: ASTORE 2 ElseBlock: ILOAD 1 ILOAD 0 ILOAD 1 IREM ISTORE 1 ISTORE 0 GOTO StartLabel 

非静的メソッドの場合、興味深い問題が1つ発生します。メソッドはオブジェクトで呼び出されますが、一般に、 thisに一致する必要はありません。 バイトコードでこのオブジェクトの計算場所を見つけ、この計算がALOAD 0と等しい場合にのみ最適化を実行することは技術的に可能です。

私はASTORE 0 、現在のthis代わりに目的のクラスの計算値を保存しました（ ASTORE 0作成することにより）。 奇妙なことに、このアプローチは機能しますが、知識が不足しているため、この状況でJITが正しく動作することを保証できません。 コメントで答えを知りたい-ここにリスクはありますか。

簡単なテストに加えて、エージェントを既存のアプリケーションに接続してみました。 Tomcatには最適化するメソッドが見つかりませんでした。 IntelliJ IDEAには、このようなメソッドが少なくとも12個ありましたが、アプリケーションがクラッシュしました。 IDEAに複数のエージェントとクラスローダーの複雑なロジックが存在することを考えると、何がうまくいかなかったかはあえて言いません。

その結果、セマンティクスに違反せずに実行できるすべてのメソッドで末尾再帰を最適化するツールが作成されました（呼び出しスタックの変更を除く）。 明らかな欠点のうち、デバッグの複雑さは注目に値します。 一方、デバッグはいつでもエージェントをオフにして実行できます。

どこかで使う価値はありますか-あなた次第です。