クラスメンバーメソッドの末尾再帰最適化の制限

PrgInScalaの8.9では,テール再帰(メソッドの再帰呼び出しはメソッド体の最後)メソッドScalaコンパイラがバイトコードをループに最適化し,性能を向上させることが述べられている.しかし、本の例を試してみると、想像していた最適化は起こらなかった.次はテストコードです.

package fineqtbull;
class Approx { 
    def isGoodEnough(guess:Double):Boolean = 
        if (guess < 1) true 
        else false 
    def improve(guess:Double): Double = guess - 1 
    def approximate(guess:Double):Double = 
        if (isGoodEnough(guess)) guess 
        else approximate(improve(guess)) 
    def approximateLoop(initialGuess:Double):Double = { 
        var guess = initialGuess 
        while (!isGoodEnough(guess)) 
            guess = improve(guess) 
        guess 
    } 
} 

object ApproxMain { 
    val app = new Approx() 
    def main(args:Array[String]) = { 
    	println(System.getProperty("java.class.path"))
        recursive(1) 
        iterate(1) 
        recursive(10) 
        iterate(10) 
        recursive(100) 
        iterate(100) 
    } 
    def recursive(n:Int) = { 
        val start = java.lang.System.currentTimeMillis() 
        for (i <- 0 to 10000000) { 
            app.approximate(n) 
        } 
        println(java.lang.System.currentTimeMillis() - start) 
    } 
    def iterate(n:Int) = { 
        val start = java.lang.System.currentTimeMillis() 
        for (i <- 0 to 10000000) { 
            app.approximateLoop(n) 
        } 
        println(java.lang.System.currentTimeMillis() - start) 
    } 
} 

以下に実行結果を示すと,再帰呼び出しの方式はループ方式よりもかなり遅く,回数が多ければ多いほど遅い幅が大きくなる傾向が見られる.

922
969
2406
2032
13578
8047

次にjavapでApproxクラスapproximateメソッドのバイトコードを見て、テール再帰が最適化されているかどうかを確認します.

public double approximate(double);
  Code:
   Stack=4, Locals=3, Args_size=2
   0:   aload_0
   1:   dload_1
   2:   invokevirtual   #18; //Method isGoodEnough:(D)Z
   5:   ifeq    12
   8:   dload_1
   9:   goto    21
   12:  aload_0
   13:  aload_0
   14:  dload_1
   15:  invokevirtual   #21; //Method improve:(D)D
   18:  invokevirtual   #30; //Method approximate:(D)D 
   21:  dreturn
  LineNumberTable:
   line 8: 0
   line 9: 12
   line 8: 21

バイトコードの18行でinvokevirtual命令でapproximateメソッドを呼び出すと,これは再帰呼び出しであり,コンパイラはテール再帰最適化を行っていないことがわかる.
テール再帰最適化を行わなかったものは何もありませんか?コードは本に書いてあるのと全く同じですね.Googleはちょっとして、原因を知って、もとはapproximate方法はfinal修飾子をプラスしていません.このapproximateメソッドは布団クラスoverrideの可能性があるため、コンパイラはそれをテール再帰的に最適化することはできません.次にapproximateメソッドの前にfinalを付けて、次のコードになります.

class Approx {
...
    final def approximate(guess:Double):Double = 
        if (isGoodEnough(guess)) guess 
        else approximate(improve(guess)) 
...
}
...

実行結果は以下の通りで,今回のテール再帰とループの2つの方式にかかる時間はほとんど差がない.

937
1000
1969
2109
8219
8328

バイトコードをもう一度見てください.

public final double approximate(double);
  Code:
   Stack=3, Locals=4, Args_size=2
   0:   aload_0
   1:   dload_1
   2:   invokevirtual   #18; //Method isGoodEnough:(D)Z
   5:   ifeq    10
   8:   dload_1
   9:   dreturn
   10:  aload_0
   11:  dload_1
   12:  invokevirtual   #21; //Method improve:(D)D
   15:  dstore_1
   16:  goto    0
  LineNumberTable:
   line 8: 0
   line 7: 9
   line 9: 10

もとの
   18:  invokevirtual   #30;//Method approximate:(D)D
   21:  dreturn
今は
   15:  dstore_1
   16:  goto    0
すなわち,バイトコード階層で元の再帰の代わりにループを用いることで,速度は自然にコード階層のループ実現に匹敵する.
原書では、Scalaは、直接再帰的で間接的ではなく、関数オブジェクト呼び出しによって実現される再帰的ではないなど、末尾再帰の最適化に多くの制限があることも述べている.以上より,本明細書で述べたクラスメンバーメソッドはfinalでなければならないことも制限条件の一つである.ちなみにobjectで定義されているメソッドであればfinal修飾子を付ける必要はありません.それはobjectのすべてのメソッドがデフォルトでfinalであるためです.