C'è una penalità di efficienza quando si usano le funzioni interne di Scala all'interno di funzioni ricorsive non tail?

Question

Sono abbastanza nuovo su Scala e sto ancora cercando di sviluppare un'idea per quali approcci sono efficienti e che potrebbero contenere costi di prestazioni nascosti.

Se si definisce una funzione ricorsiva (non a coda) che contiene una funzione interna. Sono state istanziate più copie dell'oggetto funzionale della funzione interna per ogni chiamata ricorsiva?

Ad esempio, nel seguente:

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

... quante copie dell'oggetto dbl esiste nello stack per una chiamata a sumDoubles(15)?

Answer 1

A livello bytecode

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

è esattamente lo stesso di

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

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

ma non prendere la mia parola per

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

} 

Se una funzione interna cattura un immutabile variabile quindi c'è una traduzione.Questo codice

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

si traduce in

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    
} 

Nuovamente, gli strumenti sono lì per voi

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

} 

Se variabile mutabile viene catturato, allora deve essere confezionato che può essere più costoso .

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

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

si traduce in qualcosa di simile

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: l'aggiunta di funzioni di prima classe

Per ottenere allocazioni devi utilizzare le funzioni in modo più di prima classe

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 a desugars in qualcosa di un po 'come

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

Ecco il codice di 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 

} 

La classe anonima ottiene un sacco di codice copiato nel tratto dal Function1. Questo ha un costo in termini di overhead di caricamento delle classi, ma non influenza il costo dell'allocazione dell'oggetto o dell'esecuzione del codice. L'altro costo è il pugilato e l'unboxing del numero intero. C'è speranza che quel costo andrà via con l'annotazione @specialized di 2.8.

Answer 2

In questo caso speciale, il compilatore potrebbe eventualmente ottimizzarlo, ma considerare quanto segue (pseudo-codice).

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

Nella maggior parte dei casi, la funzione interna deve accedere alle variabili della sua funzione esterna, quindi deve essere nuovamente un'istanza in ogni chiamata.

Answer 3

Se si è preoccupati delle prestazioni di Scala, è utile conoscere 1) come funziona bytecode Java e 2) come Scala si converte in bytecode Java. Se sei a tuo agio nel guardare il codice byte grezzo o decompilarlo, ti suggerisco di farlo per le aree in cui potresti essere preoccupato per le prestazioni. Prenderai subito un'idea di come Scala si converte in bytecode. In caso contrario, è possibile utilizzare il flag scalac -print, che stampa una versione "completamente desugared" del proprio codice Scala. È fondamentalmente una versione del tuo codice il più vicino possibile a Java, proprio prima che venga trasformato in bytecode.

Ho fatto un file Performance.scala con il codice che avete inviato:

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

Quando eseguo scalac -print su di esso posso vedere la Scala private degli zuccheri:

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

Allora ti si noti che dbl è stato "sollevato" in un metodo final private[this] dello stesso oggetto a cui appartiene sumDoubles. Sia dbl e sumDoubles sono in realtà metodi sul loro oggetto contenitore, non funzioni. Chiamandoli in modo non ricorsivo in coda potresti far crescere lo stack, ma non istanzia gli oggetti sul tuo heap.