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

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

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, заключается в том, что она является рекурсивной функцией, хотя, в отличие от других рекурсивных функций, я написал /, основной случай приходит последним, чтобы избежать раннего завершения.

Ответ 1

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

Но на практике разница может быть незначительной. Я запустил микро-бенчмарк с помощью суппорта и вашего примера. Я сделал префикс 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-template).

Ответ 2

Операторы соответствия, подобные приведенным выше, переводятся в кучу инструкций 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-statement по порядку. Так же, как и с if-утверждениями, первая проблема может быть решена. Компилятор делает неплохую работу по свертыванию аналогичных тестов, но это не идеально, поэтому иногда лучше работать с несколькими случаями (или даже использовать вложенные операторы if) и иметь какое-то дерево решений, которое вы опускаете. Тем не менее, компилятор делает неплохую работу, поэтому не тратьте свое время, если не знаете, что это узкое место.