在非尾遞歸函數中使用Scala內部函數時會有效嗎？

Question

我對Scala相當陌生，現在仍在努力探索哪些方法是高效的，哪些方法可能包含隱藏的性能成本。

如果我定義一個包含內部函數的（非尾）遞歸函數。爲每次遞歸調用實例化內部函數的功能對象的多個副本？

例如在以下幾點：

def sumDoubles(n: Int): Int = { 
    def dbl(a: Int) = 2 * a; 
    if(n > 0) 
     dbl(n) + sumDoubles(n - 1) 
    else 
     0    
} 

...怎麼dbl對象的多個副本在堆棧上存在以sumDoubles(15)打個電話？

Answer 1

在字節碼級

def sumDoubles(n: Int): Int = { 
    def dbl(a: Int) = 2 * a; 
    if(n > 0) 
    dbl(n) + sumDoubles(n - 1) 
    else 
    0    
} 

是完全一樣的

private[this] def dbl(a: Int) = 2 * a; 

def sumDoubles(n: Int): Int = { 
    if(n > 0) 
    dbl(n) + sumDoubles(n - 1) 
    else 
    0    
} 

但是，不要把我的話

~/test$ javap -private -c Foo 
Compiled from "test.scala" 
public class Foo extends java.lang.Object implements scala.ScalaObject{ 
public Foo(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."":()V 
    4: return 

private final int dbl$1(int); 
    Code: 
    0: iconst_2 
    1: iload_1 
    2: imul 
    3: ireturn 

public int sumDoubles(int); 
    Code: 
    0: iload_1 
    1: iconst_0 
    2: if_icmple 21 
    5: aload_0 
    6: iload_1 
    7: invokespecial #22; //Method dbl$1:(I)I 
    10: aload_0 
    11: iload_1 
    12: iconst_1 
    13: isub 
    14: invokevirtual #24; //Method sumDoubles:(I)I 
    17: iadd 
    18: goto 22 
    21: iconst_0 
    22: ireturn 

} 

如果內部函數捕獲不變然後有一個翻譯。此代碼

def foo(n: Int): Int = { 
    def dbl(a: Int) = a * n; 
    if(n > 0) 
     dbl(n) + foo(n - 1) 
    else 
     0    
} 

被轉換爲

private[this] def dbl(a: Int, n: Int) = a * n; 

def foo(n: Int): Int = { 
    if(n > 0) 
    dbl(n, n) + foo(n - 1) 
    else 
    0    
} 

此外，這些工具是有你

~/test$ javap -private -c Foo 
Compiled from "test.scala" 
public class Foo extends java.lang.Object implements scala.ScalaObject{ 
public Foo(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."":()V 
    4: return 

private final int dbl$1(int, int); 
    Code: 
    0: iload_1 
    1: iload_2 
    2: imul 
    3: ireturn 

public int foo(int); 
    Code: 
    0: iload_1 
    1: iconst_0 
    2: if_icmple 22 
    5: aload_0 
    6: iload_1 
    7: iload_1 
    8: invokespecial #23; //Method dbl$1:(II)I 
    11: aload_0 
    12: iload_1 
    13: iconst_1 
    14: isub 
    15: invokevirtual #25; //Method foo:(I)I 
    18: iadd 
    19: goto 23 
    22: iconst_0 
    23: ireturn 

} 

如果可變變量被捕獲，然後它必須被裝箱從而可以更昂貴。

def bar(_n : Int) : Int = { 
    var n = _n 
    def subtract() = n = n - 1 

    if (n > 0) { 
     subtract 
     n 
    } 
    else 
     0 
} 

被轉換成類似

private[this] def subtract(n : IntRef]) = n.value = n.value - 1 

def bar(_n : Int) : Int = { 
    var n = _n 
    if (n > 0) { 
     val nRef = IntRef(n) 
     subtract(nRef) 
     n = nRef.get() 
     n 
    } 
    else 
     0 
} 

 
~/test$ javap -private -c Foo 
Compiled from "test.scala" 
public class Foo extends java.lang.Object implements scala.ScalaObject{ 
public Foo(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."":()V 
    4: return 

private final void subtract$1(scala.runtime.IntRef); 
    Code: 
    0: aload_1 
    1: aload_1 
    2: getfield #18; //Field scala/runtime/IntRef.elem:I 
    5: iconst_1 
    6: isub 
    7: putfield #18; //Field scala/runtime/IntRef.elem:I 
    10: return 

public int bar(int); 
    Code: 
    0: new #14; //class scala/runtime/IntRef 
    3: dup 
    4: iload_1 
    5: invokespecial #23; //Method scala/runtime/IntRef."":(I)V 
    8: astore_2 
    9: aload_2 
    10: getfield #18; //Field scala/runtime/IntRef.elem:I 
    13: iconst_0 
    14: if_icmple 29 
    17: aload_0 
    18: aload_2 
    19: invokespecial #27; //Method subtract$1:(Lscala/runtime/IntRef;)V 
    22: aload_2 
    23: getfield #18; //Field scala/runtime/IntRef.elem:I 
    26: goto 30 
    29: iconst_0 
    30: ireturn 

} 

編輯：將第一類函數

要得到你需要在多個第一類方式使用函數對象分配

def sumWithFunction(n : Int, f : Int => Int) : Int = { 
    if(n > 0) 
    f(n) + sumWithFunction(n - 1, f) 
    else 
    0    
} 

def sumDoubles(n: Int) : Int = { 
    def dbl(a: Int) = 2 * a 
    sumWithFunction(n, dbl) 
} 

Th在desugars到的東西有點像

def sumWithFunction(n : Int, f : Int => Int) : Int = { 
    if(n > 0) 
    f(n) + sumWithFunction(n - 1, f) 
    else 
    0    
} 

private[this] def dbl(a: Int) = 2 * a 

def sumDoubles(n: Int) : Int = { 
    sumWithFunction(n, new Function0[Int,Int] { 
    def apply(x : Int) = dbl(x) 
    }) 
} 

這裏的字節碼

 
~/test$ javap -private -c Foo 
Compiled from "test.scala" 
public class Foo extends java.lang.Object implements scala.ScalaObject{ 
public Foo(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."":()V 
    4: return 

public final int dbl$1(int); 
    Code: 
    0: iconst_2 
    1: iload_1 
    2: imul 
    3: ireturn 

public int sumDoubles(int); 
    Code: 
    0: aload_0 
    1: iload_1 
    2: new #20; //class Foo$$anonfun$sumDoubles$1 
    5: dup 
    6: aload_0 
    7: invokespecial #23; //Method Foo$$anonfun$sumDoubles$1."":(LFoo;)V 
    10: invokevirtual #29; //Method sumWithFunction:(ILscala/Function1;)I 
    13: ireturn 

public int sumWithFunction(int, scala.Function1); 
    Code: 
    0: iload_1 
    1: iconst_0 
    2: if_icmple 30 
    5: aload_2 
    6: iload_1 
    7: invokestatic #36; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer; 
    10: invokeinterface #42, 2; //InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object; 
    15: invokestatic #46; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I 
    18: aload_0 
    19: iload_1 
    20: iconst_1 
    21: isub 
    22: aload_2 
    23: invokevirtual #29; //Method sumWithFunction:(ILscala/Function1;)I 
    26: iadd 
    27: goto 31 
    30: iconst_0 
    31: ireturn 

} 

~/test$ javap -private -c "Foo\$\$anonfun\$sumDoubles\$1" 
Compiled from "test.scala" 
public final class Foo$$anonfun$sumDoubles$1 extends java.lang.Object implements scala.Function1,scala.ScalaObject,java.io.Serializable{ 
private final Foo $outer; 

public Foo$$anonfun$sumDoubles$1(Foo); 
    Code: 
    0: aload_1 
    1: ifnonnull 12 
    4: new #10; //class java/lang/NullPointerException 
    7: dup 
    8: invokespecial #13; //Method java/lang/NullPointerException."":()V 
    11: athrow 
    12: aload_0 
    13: aload_1 
    14: putfield #17; //Field $outer:LFoo; 
    17: aload_0 
    18: invokespecial #20; //Method java/lang/Object."":()V 
    21: aload_0 
    22: invokestatic #26; //Method scala/Function1$class.$init$:(Lscala/Function1;)V 
    25: return 

public final java.lang.Object apply(java.lang.Object); 
    Code: 
    0: aload_0 
    1: getfield #17; //Field $outer:LFoo; 
    4: astore_2 
    5: aload_0 
    6: aload_1 
    7: invokestatic #37; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I 
    10: invokevirtual #40; //Method apply:(I)I 
    13: invokestatic #44; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer; 
    16: areturn 

public final int apply(int); 
    Code: 
    0: aload_0 
    1: getfield #17; //Field $outer:LFoo; 
    4: astore_2 
    5: aload_0 
    6: getfield #17; //Field $outer:LFoo; 
    9: iload_1 
    10: invokevirtual #51; //Method Foo.dbl$1:(I)I 
    13: ireturn 

public scala.Function1 andThen(scala.Function1); 
    Code: 
    0: aload_0 
    1: aload_1 
    2: invokestatic #56; //Method scala/Function1$class.andThen:(Lscala/Function1;Lscala/Function1;)Lscala/Function1; 
    5: areturn 

public scala.Function1 compose(scala.Function1); 
    Code: 
    0: aload_0 
    1: aload_1 
    2: invokestatic #60; //Method scala/Function1$class.compose:(Lscala/Function1;Lscala/Function1;)Lscala/Function1; 
    5: areturn 

public java.lang.String toString(); 
    Code: 
    0: aload_0 
    1: invokestatic #65; //Method scala/Function1$class.toString:(Lscala/Function1;)Ljava/lang/String; 
    4: areturn 

} 

匿名類獲取了大量的代碼從功能1特質複製英寸在類加載開銷方面確實存在成本，但不會影響分配對象或執行代碼的成本。其他成本是整數的裝箱和拆箱。希望這個成本會隨着2.8的@特殊註解而消失。

Answer 2

在這種特殊情況下，編譯器可能會對此進行優化，但請考慮以下內容（僞代碼）。

def func(n) = { 
    def nTimes(a) = n * a 
    if (n <= 1) 
     1 
    else 
     nTimes(func(n - 1)) 
} 

在大多數情況下，內部功能需要訪問其外部函數的變量，所以它在每個呼叫被重新實例化。

Answer 3

如果您擔心Scala性能，那麼熟悉1）Java字節碼的執行方式以及2）Scala如何轉換爲Java字節碼是很好的。如果您願意查看原始字節碼或反編譯它，我建議您在可能關注性能的領域這樣做。你很快就會體會到Scala是如何轉換爲字節碼的。如果沒有，您可以使用scalac -print標誌，該標誌打印出Scala代碼的「完全脫毛」版本。它基本上是一個儘可能接近Java的代碼版本，就在它變成字節碼之前。

我做了一個文件Performance.scala與您發佈的代碼：

jorge-ortizs-macbook-pro:sandbox jeortiz$ cat Performance.scala 
object Performance { 
    def sumDoubles(n: Int): Int = { 
     def dbl(a: Int) = 2 * a; 
     if(n > 0) 
      dbl(n) + sumDoubles(n - 1) 
     else 
      0    
    } 
} 

當我在上面運行scalac -print我可以看到脫斯卡拉：

jorge-ortizs-macbook-pro:sandbox jeortiz$ scalac Performance.scala -print 
[[syntax trees at end of cleanup]]// Scala source: Performance.scala 
package <empty> { 
    final class Performance extends java.lang.Object with ScalaObject { 
    @remote def $tag(): Int = scala.ScalaObject$class.$tag(Performance.this); 
    def sumDoubles(n: Int): Int = { 
     if (n.>(0)) 
     Performance.this.dbl$1(n).+(Performance.this.sumDoubles(n.-(1))) 
     else 
     0 
    }; 
    final private[this] def dbl$1(a: Int): Int = 2.*(a); 
    def this(): object Performance = { 
     Performance.super.this(); 
    () 
    } 
    } 
} 

然後你就注意dbl已被「提升」爲sumDoubles所屬的同一對象的final private[this]方法。 dbl和sumDoubles實際上都是它們包含對象的方法，而不是函數。以非尾遞歸方式調用它們可能會增加你的堆棧，但它不會在你的堆上實例化對象。