Стоимость вложенных методов - PullRequest
47 голосов
/ 20 марта 2010

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

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

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

Ответы [ 3 ]

56 голосов
/ 20 марта 2010

Во время компиляции вложенные функции 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 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();
      ()
    }
  }
}
14 голосов
/ 20 марта 2010

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

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")
  • В то время как внутренние методы цикла являются замыканиями над переменной суммы
  • В то время как внутренние методы цикла возвращают частичную сумму
  • Вложенная функция "время-и-сумма"

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

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 нс.)

7 голосов
/ 19 января 2014

По состоянию на январь 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 ==============================

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

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

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

Версия

1034 * 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
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...