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