Есть ли снижение эффективности при использовании внутренних функций 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)
}

Это превращает в нечто похожее на

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

}

Анонимный класс получает много кода, скопированного из черты Function1. Это имеет стоимость с точки зрения накладных расходов на загрузку класса, но не влияет на стоимость выделения объекта или выполнения кода. Другая стоимость - упаковка и распаковка целого числа. Есть надежда, что эта стоимость исчезнет с @specialized аннотацией 2.8.

Answer 2

Если вы беспокоитесь о производительности 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 был "поднят" в метод final private[this] того же объекта, к которому принадлежит sumDoubles. И dbl, и sumDoubles на самом деле являются методами для содержащего их объекта, а не функциями. Вызов их нерекурсивно может увеличить ваш стек, но он не будет создавать экземпляры объектов в вашей куче.

Answer 3

В этом особом случае компилятор может оптимизировать это, но учтите следующее (псевдокод).

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

В большинстве случаев внутренняя функция должна обращаться к переменным своей внешней функции, поэтому ее необходимо повторно создавать в каждом вызове.