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

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

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.