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

理论上是的,因为匹配测试是按顺序完成的.

但在实践中,差异可能无关紧要.我使用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 ==============================

在第一次测试中,UnOpcase是第一个,第二个测试是最后一个(在默认情况之前).

正如你所看到的,它并不重要(慢不到5%).或许这样,有了大量的案例,订单很重要,但它也是重构的候选人.

完整代码在这里:https://gist.github.com/1152232(通过scala-benchmark-template运行).

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语句),并且有一些你可以使用的决策树.尽管如此,编译器确实做得相当不错,所以不要浪费你的时间,除非你知道这是瓶颈.