How fast is pattern matching in Scala

Question

I'm new to Scala. When I am learning it by reading Scala code written by others, one of the most distinguishing feature I find in Scala code that is different from other languages is its pattern matching.

At the same time I feel the convenience and expressiveness it brings, I can't help being curious of the potential performance cost behind it -- generally speaking, how fast is match?

Firstly, without "advanced" features such as matching parameters of constructors, match in Scala, IMO, is the counterpart of switch-case in other languages. For instance,

color match {
  0 => println "color is red!"
  1 => println "color is green!"
  2 => println "color is blue!"
}

As a novice, I want to know if the code above is exactly as fast as equivalent code in if-else statement?

Secondly, now taking those "advanced" features back, for instance:

expr match {
  Animal(name) => ...
  Animal(name, age) => ...
  Animal(_, _, id) => ...
}

As for the code above or other features of match(list matching, pair matching, etc.), I am curious about how Scala implemented these fancy usage? And most importantly, how fast can I expect these code to be? (Say, are they still as fast as the match in the first case? Or maybe slightly slower? Or extremely slow owing to the use of some technology such as reflection?)

Thanks in advance!

Depends on the context: in limited cases involving constants, it'll be like a java switch. In cases involving pattern matching on the builtin case class patterns, it'll just be an instanceof check and then member lookups for the fields. In the general case, the full `unapply` method gets called (and yes, that is slower). — Alec, Sep 14 '16 at 14:01

dveim · Accepted Answer · 2016-09-14T13:28:40.017

First snippet is translated to bytecode's TableSwitch (or LookupSwitch) and is as fast as Java's switch/case:

scala> def foo(i: Int) = i match {
     | case 1 => 2
     | case 2 => 10
     | case 3 => 42
     | case _ => 777
     | }
foo: (i: Int)Int

scala> :javap -c foo
Compiled from "<console>"
public class  {
  public static final  MODULE$;

  public static {};
    Code:
       0: new           #2                  // class
       3: invokespecial #12                 // Method "<init>":()V
       6: return

  public int foo(int);
    Code:
       0: iload_1
       1: istore_2
       2: iload_2
       3: tableswitch   { // 1 to 3
                     1: 44
                     2: 39
                     3: 34
               default: 28
          }
      28: sipush        777
      31: goto          45
      34: bipush        42
      36: goto          45
      39: bipush        10
      41: goto          45
      44: iconst_2
      45: ireturn

  public ();
    Code:
       0: aload_0
       1: invokespecial #18                 // Method java/lang/Object."<init>":()V
       4: aload_0
       5: putstatic     #20                 // Field MODULE$:L;
       8: return

Second snipped is translated to bunch of unapply/isInstanceOf/null checks calls, and is (obviously) slower than tableswitch. But it has same (or better, if compiler can optimize something) performance as manual checking via isInstanceOf (no reflection or similar stuff):

scala> case class Foo(s: String, i: Int)
defined class Foo

scala> def bar(foo: Foo) = foo match {
     | case Foo("test", _) => 1
     | case Foo(_, 42) => 2
     | case _ => 3
     | }
bar: (foo: Foo)Int

scala> :javap -c bar
Compiled from "<console>"
public class  {
  public static final  MODULE$;

  public static {};
    Code:
       0: new           #2                  // class
       3: invokespecial #12                 // Method "<init>":()V
       6: return

  public int bar(Foo);
    Code:
       0: aload_1
       1: astore_2
       2: aload_2
       3: ifnull        26
       6: aload_2
       7: invokevirtual #20                 // Method Foo.s:()Ljava/lang/String;
      10: astore_3
      11: ldc           #22                 // String test
      13: aload_3
      14: invokevirtual #26                 // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
      17: ifeq          26
      20: iconst_1
      21: istore        4
      23: goto          52
      26: aload_2
      27: ifnull        49
      30: aload_2
      31: invokevirtual #30                 // Method Foo.i:()I
      34: istore        5
      36: bipush        42
      38: iload         5
      40: if_icmpne     49
      43: iconst_2
      44: istore        4
      46: goto          52
      49: iconst_3
      50: istore        4
      52: iload         4
      54: ireturn

  public ();
    Code:
       0: aload_0
       1: invokespecial #34                 // Method java/lang/Object."<init>":()V
       4: aload_0
       5: putstatic     #36                 // Field MODULE$:L;
       8: return
}

Not very fair to just look at pattern matching the case constructor pattern since it gets its own special treatment - if you were to write your own `unapply` pattern, I reckon the `javap` dump would be much uglier. — Alec, Sep 14 '16 at 14:03
Well, not so ugly. It would be similar to second bytecode snippet (`isInstanceOf`, null checks), but without possible optimizations. "Scala compiler can optimize patterns over case classes much better than patterns over extractors. This is because the mechanisms of case classes are fixed, whereas an unapply or unapplySeq method in an extractor could do almost anything" (from "Programming in Scala"). — dveim, Sep 14 '16 at 14:10
I would've guessed that at least some of the `Option[(..)]` option tuple objects would stick around unoptimized (since the pattern can be refuted, unlike constructor patterns that only requires the instanceof and null check), and that seems comparatively inefficient. — Alec, Sep 14 '16 at 14:26
Yes, per my knowledge. Also you might want to see https://github.com/scala/scala/pull/2848 (paragraph about `OptInt`). — dveim, Sep 14 '16 at 14:42

How fast is pattern matching in Scala

1 Answers1