Подтвердить что ты не робот

Стоимость вложенных методов

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

Например:

class AggregatedPerson extends HashSet[PersonRecord] {
  def mostFrequentName: String = {
    type NameCount = (String, Int)
    def moreFirst(a: NameCount, b: NameCount) = a._2 > b._2
    def countOccurrences(nameGroup: (String, List[PersonRecord])) =
      (nameGroup._1, nameGroup._2.size) 

    iterator.toList.groupBy(_.fullName).
      map(countOccurrences).iterator.toList.
      sortWith(moreFirst).head._1
  }
}

Есть ли какая-либо стоимость выполнения из-за определения вложенного метода, о котором я должен знать?

Отличается ли ответ на закрытие?

4b9b3361

ОТВЕТЫ

Ответ 1

Во время компиляции вложенные функции moveFirst и countOccurences выходят на тот же уровень, что и mostFrequentName. Они получают синтезированные имена компилятора: moveFirst$1 и countOccurences$1.

Кроме того, когда вы ссылаетесь на один из этих методов без списка аргументов, он поднимается в функцию. Итак, map(countOccurences) совпадает с записью map((a: (String, List[PersonRecord])) => countOccurences(a)). Эта анонимная функция скомпилирована в отдельный класс AggregatedPerson$$anonfun$mostFrequentName$2, который делает не более, чем переадресацию на countOccurences$.

Как замечание, процесс подъема метода к функции называется Eta Expansion. Он запускается, если вы опустите список аргументов в контексте, где ожидается тип функции (как в вашем примере), или если вы используете _ вместо всего списка аргументов или вместо каждого аргумента (val f1 = countOccurences _ ; val f2 = countOccurences(_).

Если код был непосредственно в закрытии, у вас будет меньше вызовов метода в вашем стеке, а еще один синтетический метод будет сгенерирован. В большинстве случаев воздействие на производительность может быть нулевым.

Я считаю, что это фантастически полезный инструмент для структурирования кода, и рассмотрим ваш пример очень идиоматический Scala.

Другим полезным инструментом является использование небольших блоков для инициализации val:

val a = {
   val temp1, temp2 = ...
   f(temp1, temp2)
}

Вы можете использовать scalac -print, чтобы увидеть, как именно код Scala переводится в форму, готовую к JVM. Получает вывод из вашей программы:

[[syntax trees at end of cleanup]]// Scala source: nested-method.scala
package <empty> {

  class AggregatedPerson extends scala.collection.mutable.HashSet with ScalaObject {
    def mostFrequentName(): java.lang.String = AggregatedPerson.this.iterator().toList().groupBy({
      (new AggregatedPerson$$anonfun$mostFrequentName$1(AggregatedPerson.this): Function1)
    }).map({
      {
        (new AggregatedPerson$$anonfun$mostFrequentName$2(AggregatedPerson.this): Function1)
      }
    }, collection.this.Map.canBuildFrom()).$asInstanceOf[scala.collection.MapLike]().iterator().toList().sortWith({
      {
        (new AggregatedPerson$$anonfun$mostFrequentName$3(AggregatedPerson.this): Function2)
      }
    }).$asInstanceOf[scala.collection.IterableLike]().head().$asInstanceOf[Tuple2]()._1().$asInstanceOf[java.lang.String]();
    final def moreFirst$1(a: Tuple2, b: Tuple2): Boolean = scala.Int.unbox(a._2()).>(scala.Int.unbox(b._2()));
    final def countOccurrences$1(nameGroup: Tuple2): Tuple2 = new Tuple2(nameGroup._1(), scala.Int.box(nameGroup._2().$asInstanceOf[scala.collection.SeqLike]().size()));
    def this(): AggregatedPerson = {
      AggregatedPerson.super.this();
      ()
    }
  };

  @SerialVersionUID(0) @serializable final <synthetic> class AggregatedPerson$$anonfun$mostFrequentName$1 extends scala.runtime.AbstractFunction1 {
    final def apply(x$1: PersonRecord): java.lang.String = x$1.fullName();
    final <bridge> def apply(v1: java.lang.Object): java.lang.Object = AggregatedPerson$$anonfun$mostFrequentName$1.this.apply(v1.$asInstanceOf[PersonRecord]());
    def this($outer: AggregatedPerson): AggregatedPerson$$anonfun$mostFrequentName$1 = {
      AggregatedPerson$$anonfun$mostFrequentName$1.super.this();
      ()
    }
  };

  @SerialVersionUID(0) @serializable final <synthetic> class AggregatedPerson$$anonfun$mostFrequentName$2 extends scala.runtime.AbstractFunction1 {
    final def apply(nameGroup: Tuple2): Tuple2 = AggregatedPerson$$anonfun$mostFrequentName$2.this.$outer.countOccurrences$1(nameGroup);
    <synthetic> <paramaccessor> private[this] val $outer: AggregatedPerson = _;
    final <bridge> def apply(v1: java.lang.Object): java.lang.Object = AggregatedPerson$$anonfun$mostFrequentName$2.this.apply(v1.$asInstanceOf[Tuple2]());
    def this($outer: AggregatedPerson): AggregatedPerson$$anonfun$mostFrequentName$2 = {
      if ($outer.eq(null))
        throw new java.lang.NullPointerException()
      else
        AggregatedPerson$$anonfun$mostFrequentName$2.this.$outer = $outer;
      AggregatedPerson$$anonfun$mostFrequentName$2.super.this();
      ()
    }
  };
  @SerialVersionUID(0) @serializable final <synthetic> class AggregatedPerson$$anonfun$mostFrequentName$3 extends scala.runtime.AbstractFunction2 {
    final def apply(a: Tuple2, b: Tuple2): Boolean = AggregatedPerson$$anonfun$mostFrequentName$3.this.$outer.moreFirst$1(a, b);
    <synthetic> <paramaccessor> private[this] val $outer: AggregatedPerson = _;
    final <bridge> def apply(v1: java.lang.Object, v2: java.lang.Object): java.lang.Object = scala.Boolean.box(AggregatedPerson$$anonfun$mostFrequentName$3.this.apply(v1.$asInstanceOf[Tuple2](), v2.$asInstanceOf[Tuple2]()));
    def this($outer: AggregatedPerson): AggregatedPerson$$anonfun$mostFrequentName$3 = {
      if ($outer.eq(null))
        throw new java.lang.NullPointerException()
      else
        AggregatedPerson$$anonfun$mostFrequentName$3.this.$outer = $outer;
      AggregatedPerson$$anonfun$mostFrequentName$3.super.this();
      ()
    }
  }
}

Ответ 2

Существует небольшая стоимость исполнения. Вы можете увидеть его здесь (извинения за длинный код):

object NestBench {
  def countRaw() = {
    var sum = 0
    var i = 0
    while (i<1000) {
      sum += i
      i += 1
      var j = 0
      while (j<1000) {
        sum += j
        j += 1
        var k = 0
        while (k<1000) {
          sum += k
          k += 1
          sum += 1
        }
      }
    }
    sum
  }
  def countClosure() = {
    var sum = 0
    var i = 0
    def sumI {
      sum += i
      i += 1
      var j = 0
      def sumJ {
        sum += j
        j += 1
        var k = 0
        def sumK {
          def sumL { sum += 1 }
          sum += k
          k += 1
          sumL
        }
        while (k<1000) sumK
      }
      while (j<1000) sumJ
    }
    while (i<1000) sumI
    sum
  }
  def countInner() = {
    var sum = 0
    def whileI = {
      def whileJ = {
        def whileK = {
          def whileL() = 1
          var ksum = 0
          var k = 0
          while (k<1000) { ksum += k; k += 1; ksum += whileL }
          ksum
        }
        var jsum = 0
        var j = 0
        while (j<1000) {
          jsum += j; j += 1
          jsum += whileK
        }
        jsum
      }
      var isum = 0
      var i = 0
      while (i<1000) {
        isum += i; i += 1
        isum += whileJ
      }
      isum
    }
    whileI
  }
  def countFunc() = {
    def summer(f: => Int)() = {
      var sum = 0
      var i = 0
      while (i<1000) {
        sum += i; i += 1
        sum += f
      }
      sum
    }
    summer( summer( summer(1) ) )()
  }
  def nsPerIteration(f:() => Int): (Int,Double) = {
    val t0 = System.nanoTime
    val result = f()
    val t1 = System.nanoTime
    (result , (t1-t0)*1e-9)
  }
  def main(args: Array[String]) {
    for (i <- 1 to 5) {
      val fns = List(countRaw _, countClosure _, countInner _, countFunc _)
      val labels = List("raw","closure","inner","func")
      val results = (fns zip labels) foreach (fl => {
        val x = nsPerIteration( fl._1 )
        printf("Method %8s produced %d; time/it = %.3f ns\n",fl._2,x._1,x._2)
      })
    }
  }
}

Существует четыре разных метода суммирования целых чисел:

  • Необработанный цикл while ( "raw" )
  • В то время как внутренние методы цикла, которые замыкаются над переменной суммы
  • В то время как внутренние методы цикла, возвращающие частичную сумму
  • Вложенная функция while и sum

И мы видим результаты на моей машине с точки зрения наносекунд, взятых во внутреннем цикле:

scala> NestBench.main(Array[String]())
Method      raw produced -1511174132; time/it = 0.422 ns
Method  closure produced -1511174132; time/it = 2.376 ns
Method    inner produced -1511174132; time/it = 0.402 ns
Method     func produced -1511174132; time/it = 0.836 ns
Method      raw produced -1511174132; time/it = 0.418 ns
Method  closure produced -1511174132; time/it = 2.410 ns
Method    inner produced -1511174132; time/it = 0.399 ns
Method     func produced -1511174132; time/it = 0.813 ns
Method      raw produced -1511174132; time/it = 0.411 ns
Method  closure produced -1511174132; time/it = 2.372 ns
Method    inner produced -1511174132; time/it = 0.399 ns
Method     func produced -1511174132; time/it = 0.813 ns
Method      raw produced -1511174132; time/it = 0.411 ns
Method  closure produced -1511174132; time/it = 2.370 ns
Method    inner produced -1511174132; time/it = 0.399 ns
Method     func produced -1511174132; time/it = 0.815 ns
Method      raw produced -1511174132; time/it = 0.412 ns
Method  closure produced -1511174132; time/it = 2.357 ns
Method    inner produced -1511174132; time/it = 0.400 ns
Method     func produced -1511174132; time/it = 0.817 ns

Итак, нижняя строка: функции вложенности действительно не повредят вам вообще в простых случаях - JVM выяснит, что вызов может быть встроен (при этом raw и inner дают одинаковые времена). Если вы используете более функциональный подход, вызов функции не может быть полностью пренебрегнут, но время, затрачиваемое на исчезновение, незначительно (приблизительно 0,4 нс при каждом вызове). Если вы используете много замыканий, то их закрытие дает накладные расходы на что-то вроде 1 нс на звонок по крайней мере в этом случае, когда записывается одна изменяемая переменная.

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

(P.S. Для сравнения, создание одного маленького объекта занимает около 4 нс на моей машине.)

Ответ 3

По состоянию на январь 2014 года

Текущий тест составляет ~ 3 лет, а Hotspot и компилятор значительно развились. Я также использую Google Caliper для выполнения тестов.

Код

import com.google.caliper.SimpleBenchmark

class Benchmark extends SimpleBenchmark {
    def timeRaw(reps: Int) = {
        var i = 0
        var result = 0L
        while (i < reps) {
            result += 0xc37e ^ (i * 0xd5f3)
            i = i + 1
        }
        result
    }

    def normal(i: Int): Long = 0xc37e ^ (i * 0xd5f3)
    def timeNormal(reps: Int) = {
        var i = 0
        var result = 0L
        while (i < reps) {
            result += normal(i)
            i = i + 1
        }
        result
    }

    def timeInner(reps: Int) = {
        def inner(i: Int): Long = 0xc37e ^ (i * 0xd5f3)

        var i = 0
        var result = 0L
        while (i < reps) {
            result += inner(i)
            i = i + 1
        }
        result
    }

    def timeClosure(reps: Int) = {
        var i = 0
        var result = 0L
        val closure = () => result += 0xc37e ^ (i * 0xd5f3)
        while (i < reps) {
            closure()
            i = i + 1
        }
        result
    }

    def normal(i: Int, j: Int, k: Int, l: Int): Long = i ^ j ^ k ^ l 
    def timeUnboxed(reps: Int) = {
        var i = 0
        var result = 0L
        while (i < reps) {
            result += normal(i,i,i,i)
            i = i + 1
        }
        result
    }

    val closure = (i: Int, j: Int, k: Int, l: Int) => (i ^ j ^ k ^ l).toLong 
    def timeBoxed(reps: Int) = {
        var i = 0
        var result = 0L
        while (i < reps) {
            closure(i,i,i,i)
            i = i + 1
        }
        result
    }
}

Результаты

benchmark     ns linear runtime
   Normal  0.576 =
      Raw  0.576 =
    Inner  0.576 =
  Closure  0.532 =
  Unboxed  0.893 =
    Boxed 15.210 ==============================

Что удивительно, так это то, что тест на закрытие был завершен на 4ns быстрее, чем другие. Это, по-видимому, идиосинкразия Hotspot вместо среды исполнения, несколько запусков вернули ту же тенденцию.

Использование закрытия, которое выполняет бокс, является огромным хитом производительности, требуется около 3.579ns для выполнения одного unboxing и reboxing, достаточного для выполнения множества примитивных математических операций. В этой конкретной ситуации все может улучшиться благодаря работе над новым оптимизатором . В общем случае бокс может быть смягчен miniboxing.

Edit: Новый оптимизатор здесь действительно не помогает, он Closure 0,1 нс медленнее и Boxed 0,1 нс быстрее:

 benchmark     ns linear runtime
       Raw  0.574 =
    Normal  0.576 =
     Inner  0.575 =
   Closure  0.645 =
   Unboxed  0.889 =
     Boxed 15.107 ==============================

Выполняется с 2.11.0-20131209-220002-9587726041 от magarciaEPFL/scala

Версия

JVM

java version "1.7.0_51"
Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
Java HotSpot(TM) 64-Bit Server VM (build 24.51-b03, mixed mode)

Scalac

Scala compiler version 2.10.3 -- Copyright 2002-2013, LAMP/EPFL