¿Existe una penalización de la eficacia cuando se utilizan funciones internas de Scala dentro de funciones recursivas sin cola?

Question

Soy bastante nuevo en Scala y todavía estoy tratando de desarrollar una idea de qué enfoques son eficientes y cuáles pueden contener costos de rendimiento ocultos.

Si defino una función recursiva (sin cola) que contiene una función interna. ¿Se crean instancias de múltiples copias del objeto funcional de la función interna para cada llamada recursiva?

Por ejemplo, en lo siguiente:

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

... cuántas copias del objeto dbl existen en la pila para una llamada a sumDoubles(15)?

Answer 1

A nivel de código de bytes

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

es exactamente el mismo que

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

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

Pero no tome mi palabra para ella

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

} 

Si una función interna capta una inmutable variable entonces hay una traducción.Este código

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

se traduce en

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    
} 

Una vez más, las herramientas están ahí para usted

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

} 

Si la variable mutable es capturado entonces tiene que ser en caja que puede ser más caro .

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

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

se traduce en algo así como

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 

} 

Editar: la adición de funciones de primera clase

para obtener asignaciones de objetos que necesita para utilizar las funciones de una manera más de primera clase

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 en desugars en algo un poco como

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

Aquí está el código de bytes

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

} 

La clase anónima recibe una gran cantidad de código copiado desde el rasgo Función1. Eso tiene un costo en términos de carga de carga de clase, pero no afecta el costo de asignar el objeto o ejecutar el código. El otro costo es el boxeo y el desempaquetado del entero. Existe la esperanza de que ese costo desaparezca con la anotación especializada de 2.8.

Answer 2

En este caso especial, el compilador posiblemente podría optimizar esto, pero tenga en cuenta lo siguiente (pseudocódigo).

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

En la mayoría de los casos, la función interna tiene que acceder a las variables de la función externa, por lo que tiene que ser re-crea una instancia en cada llamada.

Answer 3

Si le preocupa el rendimiento de Scala, es bueno estar familiarizado con 1) cómo funciona el bytecode de Java, y 2) cómo Scala se traduce a bytecode de Java. Si se siente cómodo mirando códigos de bytes crudos o descompilando, le sugiero que lo haga en áreas donde pueda estar preocupado por el rendimiento. Pronto comprenderá cómo Scala traduce a bytecode. De lo contrario, puede usar el indicador scalac -print, que imprime una versión "totalmente desacralizada" de su código Scala. Básicamente es una versión de tu código tan cerca de Java como sea posible, justo antes de que se convierta en bytecode.

He hecho un archivo Performance.scala con el código que envió:

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

Cuando corro scalac -print en ella puedo ver la Scala desazucaradas:

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

entonces te Observe que dbl ha sido "levantado" en un método final private[this] del mismo objeto al que pertenece sumDoubles. Tanto dbl como sumDoubles son en realidad métodos en su objeto contenedor, no en funciones. Llamarlos sin recurrir a la cola podría hacer crecer tu pila, pero no creará instancias de objetos en tu montón.