类成员方法的尾递归优化限制

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)) 
...
}
...

执行结果如下,这次尾递归和循环两种方式所花时间就基本差不多了。

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的。

评论

3 楼 RednaxelaFX 2009-10-27  

嗯不错，这个细节注意得好

2 楼 fineqtbull 2009-10-27  

呵呵，看来没白写。
为此我还专门学了一点JVM呢。

1 楼 night_stalker 2009-10-27  

(⊙o⊙)哦，原来如此！
前几天有个栈溢出代码重写了有点纠结，原来是没加 final 的原因 ……