Does the order of alternatives in a Scala match expression matter in terms of performance?

Question

In particular with respect to pattern matching and case classes. Consider the following:

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
  }
}

Given any sample call, say, simplify(UnOp("-", UnOp("-", UnOp("-", UnOp("-", Var("x")))))) (which results in Var("x")), does the order of the alternatives in the match expression matter for performance?

Side note, kind of related (my own observation): One thing that really strikes me about simplify is that it is a recursive function, although unlike other recursive functions I've written / dealt with, the base case comes last in order to avoid terminating early.

Answer 1

Theoretically yes, because matching tests are done in order.

But in practice the difference can be unsignificant. I've run a micro-benchmark using Caliper and your example. I prefixed Var("x") with 100'000 Unops to make it bigger.

The results are:

[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 ==============================

In first test, UnOp case is the first one, in second test its the last one (just before the default case).

As you can see, it does not really matter (less than 5% slower). Perhaps that, with a huge list of case the order matters, but it would also be a candidate for refactoring.

Full code is here: https://gist.github.com/1152232 (runs via scala-benchmarking-template).

Answer 2

Match statements like the above are translated into a bunch of if statements in bytecode:

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
   . . .

So it's really equivalent to running a bunch of if-statements in order. So as with if-statements, putting commonly-encountered cases first can help. The compiler does a fairly good job at collapsing similar tests, but it's not perfect, so sometimes it works better to catch multiple cases (or even use nested if-statements) and have some sort of decision tree that you go down. Still, the compiler does do a fairly good job, so don't waste your time unless you know that this is the bottleneck.