Имеет ли значение порядок следования альтернатив в выражениях Scala с точки зрения производительности?

Question

В частности, в отношении сопоставления с образцом и классами дел. Учтите следующее:

abstract class Expr
case class Var(name: String) extends Expr
case class Number(num: Double) extends Expr
case class UnOp(operator: String, arg: Expr) extends Expr
case class BinOp(operator: String, left: Expr, right: Expr) extends Expr

object Expr {
  def simplify(expr: Expr): Expr = expr match {
    // Some basic simplification rules...
    case UnOp("-", UnOp("-", e)) => simplify(e) // Double negation
    case BinOp("+", e, Number(0)) => simplify(e) // Adding zero
    case BinOp("-", e, Number(0)) => simplify(e) // Subtracting zero
    case BinOp("*", e, Number(1)) => simplify(e) // Multiplying by one
    case BinOp("*", e, Number(0)) => Number(0) // Multiplying by zero
    case _ => expr // Default, could not simplify given above rules
  }
}

При любом вызове образца, скажем, simplify(UnOp("-", UnOp("-", UnOp("-", UnOp("-", Var("x")))))) (что приводит к Var("x")), имеет ли значение порядок альтернатив в выражении соответствия для производительности?

Дополнительное замечание, вроде как (мое собственное наблюдение): Одна вещь, которая действительно поражает меня в simplify, это то, что это рекурсивная функция, хотя в отличие от других рекурсивных функций, которые я написал / имел дело с, базовый случай стоит последним, чтобы избежать преждевременного завершения.

Answer 1

Операторы соответствия, подобные приведенным выше, преобразуются в набор операторов if в байт-коде:

public Expr simplify(Expr);
  Code:
   0:   aload_1
   1:   astore_3
   2:   aload_3
   3:   instanceof  #17; //class UnOp
   6:   ifeq    110
   . . .

   110: aload_3
   111: instanceof  #35; //class BinOp
   114: ifeq    336
   . . .

Так что это действительно эквивалентно запуску набора операторов if по порядку.Как и в случае с утверждениями if, в первую очередь может помочь размещение часто встречающихся случаев.Компилятор довольно неплохо справляется со сложением подобных тестов, но он не идеален, поэтому иногда он лучше работает для отлова нескольких случаев (или даже для использования вложенных операторов if) и получения какого-то дерева решений, которое вы используете.Тем не менее, компилятор делает довольно хорошую работу, поэтому не тратьте свое время, если вы не знаете, что это узкое место.

Answer 2

Теоретически да, потому что тесты на соответствие проводятся по порядку.

Но на практике разница может быть незначительной.Я провел микро-тест, используя Caliper и ваш пример.Я сделал префикс Var("x") с 100'000 Unop с, чтобы увеличить его.

Результаты следующие:

[info]  0% Scenario{vm=java, trial=0, benchmark=ForFirst} 240395.82 ns; σ=998.55 ns @ 3 trials
[info] 50% Scenario{vm=java, trial=0, benchmark=ForLast} 251303.52 ns; σ=2342.60 ns @ 5 trials
[info] 
[info] benchmark  us linear runtime
[info]  ForFirst 240 ============================
[info]   ForLast 251 ==============================

В первом тесте случай UnOp является первым,во втором тесте это последний (непосредственно перед регистром по умолчанию).

Как видите, это не имеет значения (менее чем на 5% медленнее).Возможно, с огромным списком дел, порядок имеет значение, но он также будет кандидатом на рефакторинг.

Полный код здесь: https://gist.github.com/1152232 (запускается через scala-benchmarking-шаблон ).

Answer 3

Порядок, в котором вы перечисляете ваши дела, не обязательно является порядком, в котором они проверяются. Константы, включая ноль, сортируются компилятором для быстрого поиска среди них. Поэтому бессмысленно упорядочивать случаи по частоте использования при работе с константами. Однако при сопоставлении типов порядок имеет решающее значение: первый тип, который соответствует, будет использоваться, даже если они лучше соответствуют (менее универсальны) позже. Следовательно, наиболее конкретные типы должны стоять на первом месте.