在Scala的匹配表达式中，备选项的顺序是否影响性能？

Question

特别是在模式匹配和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 的一个显著特点印象深刻，那就是它是一个递归函数，但不同于我编写/处理过的其他递归函数，基本情况是最后出现以避免过早终止。

- knpwrs

---

我认为，需要更多的情况和更长的测试用例来测量可重复的差异。 - user unknown

Answer 1

从理论上讲，是的，因为匹配测试是按顺序进行的。

但在实际操作中，差异可能微不足道。我使用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-template运行）。

- paradigmatic

Answer 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语句。因此，与if语句一样，将常见情况放在前面可以有所帮助。编译器会尽力折叠类似的测试，但并不完美，因此有时捕获多个情况（甚至使用嵌套的if语句）并拥有某种决策树可以更好地解决问题。尽管如此，编译器确实做得很好，因此除非您知道这是瓶颈，否则不要浪费时间。

- Rex Kerr

---

除非你确定这是瓶颈，否则不要浪费时间。 - paradigmatic

Answer 3

在匹配类型时，顺序至关重要：第一个匹配的类型将被使用，即使后面有更好的匹配（不够通用）。因此，最具体的类型应该排在第一位，以此类推。

排序测试的第二标准是首先评估最有可能成功的测试，这样平均而言您可以减少失败的测试数量。只有第二个标准在您的示例中才有意义。

- Profiterole