Scala pattern matching performance

Question

I encountered this problem while doing homework from coursera "scala specialization" (this is simplified version and doesn't contain any homework details, it's just array traversal)

val chars: Array[Char] = some array

def fun1(idx:Int):Int = {
    some code here (including the stop condition)

    val c = chars(idx)
    c match{
      case '(' => fun1(idx+1)
      case  _  => fun1(idx+1)
    }

}

This code is 4 times slower than

def fun2(idx: Int):Int = {
    some code here (including the stop condition)

    val c = chars(idx)
    (c == '(') match{
      case true => fun2(idx+1)
      case  _  => fun2(idx+1)
    }
}

All I am doing is changing the pattern matching (I am running it using ScalMeter so I believe in the statistics).

Can anyone explain this behavior?

Answer 1

I can only confirm that the first match is ~50% slower, not 4x (2.11.8). Anyway if you look at the bytecode you can find that the first match is translated to tableswitch instruction, which is normally used for Java switch statement with multiple choices and is basically a lookup goto, while the second one is translated to if. So the second match is simply:

if (c == '(') fun2(idx+1) else fun2(idx+1)

Answer 2

Update the below is wrong (the majority of time in these tests was spent generating the data, so the difference in actual traversal times was not noticeable. Running this same benchmark with constant input shows ~125ms per 100 million entries for case ')' case vs. ~35ms for the other case.)

I am not seeing the difference you are describing. Not sure how ScalaMeter does it, but running it in repl (after letting "warm up" by running "dry" a few times), I get virtually the same performance:

def func(s: Seq[Char], idx: Int): String = 
  if(idx == s.length) "foo" else s(idx) match {
    case ')' => func(s, idx+1)
    case _ => func(s, idx+1)
  }

def func1(s: Seq[Char], idx: Int): String = 
  if(idx == s.length) "foo" else (s(idx) == '(') match {
    case true  => func(s, idx+1)
    case _ => func(s, idx+1)
  }

import scala.util.Random
def randy = Stream.continually(Random.nextPrintableChar)


def doit(n: Int)(f: (Seq[Char], Int) => String) = {
 val start = System.currentTimeMillis;       
 f(randy.take(n).toIndexedSeq, 0); 
 System.currentTimeMillis - start
}


scala> doit(1000000)(func)
res9: Long = 231

scala> doit(1000000)(func1)
res10: Long = 238

scala> doit(1000000)(func)
res11: Long = 234

scala> doit(1000000)(func1)
res12: Long = 201

Etc. As you can see, no sizable difference.