Có một hình phạt hiệu quả khi sử dụng các hàm bên trong Scala trong các hàm đệ quy không đuôi không?

Question

Tôi khá mới đối với Scala và tôi vẫn cố gắng phát triển cảm giác về cách tiếp cận nào hiệu quả và có thể chứa chi phí hiệu suất ẩn.

Nếu tôi xác định hàm đệ quy (không đuôi) có chứa hàm bên trong. Có nhiều bản sao của đối tượng chức năng của hàm bên trong được khởi tạo cho mỗi cuộc gọi đệ quy không?

Ví dụ trong những điều sau đây:

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

... có bao nhiêu bản sao của đối tượng dbl tồn tại trên ngăn xếp cho một cuộc gọi đến sumDoubles(15)?

Answer 1

Ở cấp bytecode

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

là chính xác giống như

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

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

Nhưng đừng dùng từ ngữ của tôi cho nó

~/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 

} 

Nếu một chức năng bên trong chụp một bất biến biến thì có bản dịch.Đây đang

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

Gets dịch sang

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    
} 

Một lần nữa, công cụ này là ở đó đợi em

~/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 

} 

Nếu biến có thể thay đổi được chụp sau đó nó phải được đóng hộp mà có thể tốn kém hơn .

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

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

Gets dịch sang cái gì đó như

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 

} 

Edit: thêm chức năng hạng nhất

Để có được phân bổ đối tượng bạn cần phải sử dụng các chức năng một cách lớp đầu tiên hơn

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 tại desugars vào một cái gì đó hơi giống

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

Dưới đây là các mã byte

 
~/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 

} 

Lớp vô danh nhận được rất nhiều mã được sao chép từ các đặc điểm Function1. Điều đó có chi phí về chi phí tải lớp, nhưng không ảnh hưởng đến chi phí phân bổ đối tượng hoặc thực thi mã. Các chi phí khác là boxing và unboxing của số nguyên. Hy vọng rằng chi phí đó sẽ biến mất với chú thích @specialized của 2.8.

Answer 2

Trong trường hợp đặc biệt này, trình biên dịch có thể tối ưu hóa việc này đi, nhưng hãy xem xét phần sau (mã giả).

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

Trong hầu hết các trường hợp, hàm bên trong cần truy cập các biến hàm ngoài của nó, vì vậy nó phải được tạo lại trong mỗi cuộc gọi.

Answer 3

Nếu bạn lo lắng về hiệu năng của Scala, bạn nên làm quen với 1) cách mã Java bytecode thực hiện và 2) cách Scala dịch sang mã Java bytecode. Nếu bạn cảm thấy thoải mái khi nhìn vào bytecode thô hoặc giải mã nó, tôi khuyên bạn nên làm như vậy cho các lĩnh vực mà bạn có thể quan tâm về hiệu suất. Bạn sẽ nhanh chóng có được một cảm giác về cách Scala dịch sang bytecode. Nếu không, bạn có thể sử dụng cờ scalac -print, sẽ in một phiên bản "hoàn toàn tuyệt đối" của mã Scala của bạn. Về cơ bản nó là một phiên bản mã của bạn càng gần Java càng tốt, ngay trước khi nó được chuyển thành bytecode.

Tôi đã thực hiện một tập tin Performance.scala với mã bạn được đăng:

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

Khi tôi chạy scalac -print trên đó tôi có thể thấy Scala khử đường:

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(); 
    () 
    } 
    } 
} 

Sau đó, bạn sẽ chú ý rằng dbl đã được "nâng" thành phương thức final private[this] của cùng một đối tượng mà sumDoubles thuộc về. Cả hai dbl và sumDoubles thực sự là phương pháp trên đối tượng chứa của chúng, chứ không phải các hàm. Gọi chúng không theo đuôi đệ quy có thể phát triển ngăn xếp của bạn, nhưng nó sẽ không khởi tạo các đối tượng trên heap của bạn.