130

How is pattern matching in Scala implemented at the bytecode level?

Is it like a series of if (x instanceof Foo) constructs, or something else? What are its performance implications?

For example, given the following code (from Scala By Example pages 46-48), how would the equivalent Java code for the eval method look like?

abstract class Expr case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr def eval(e: Expr): Int = e match { case Number(x) => x case Sum(l, r) => eval(l) + eval(r) }

P.S. I can read Java bytecode, so a bytecode representation would be good enough for me, but probably it would be better for the other readers to know how it would look like as Java code.

P.P.S. Does the book Programming in Scala give an answer to this and similar questions about how Scala is implemented? I have ordered the book, but it has not yet arrived.

Improve this question
4
  • Why don't you just compile the example and disassemble it with a Java bytecode disassembler? Commented Apr 15, 2009 at 23:36
  • I'll probably do that, unless someone gives a good answer first. But right now I want to get some sleep. ;) Commented Apr 15, 2009 at 23:41
  • 30
    The question is useful to other readers! Commented Jul 3, 2011 at 12:52
  • 2
    @djondal: the best way to say that is just to upvote the question :-) Commented Feb 9, 2012 at 23:43

4 Answers 4

Reset to default
96

The low level can be explored with a disassembler but the short answer is that it's a bunch of if/elses where the predicate depends on the pattern

case Sum(l,r) // instance of check followed by fetching the two arguments and assigning to two variables l and r but see below about custom extractors case "hello" // equality check case _ : Foo // instance of check case x => // assignment to a fresh variable case _ => // do nothing, this is the tail else on the if/else

There's much more that you can do with patterns like or patterns and combinations like "case Foo(45, x)", but generally those are just logical extensions of what I just described. Patterns can also have guards, which are additional constraints on the predicates. There are also cases where the compiler can optimize pattern matching, e.g when there's some overlap between cases it might coalesce things a bit. Advanced patterns and optimization are an active area of work in the compiler, so don't be surprised if the byte code improves substantially over these basic rules in current and future versions of Scala.

In addition to all that, you can write your own custom extractors in addition to or instead of the default ones Scala uses for case classes. If you do, then the cost of the pattern match is the cost of whatever the extractor does. A good overview is found in http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I believe this is current link: infoscience.epfl.ch/record/98468/files/…
81

James (above) said it best. However, if you're curious it's always a good exercise to look at the disassembled bytecode. You can also invoke scalac with the -print option, which will print your program with all Scala-specific features removed. It's basically Java in Scala's clothing. Here's the relevant scalac -print output for the code snippet you gave:

def eval(e: Expr): Int = { <synthetic> val temp10: Expr = e; if (temp10.$isInstanceOf[Number]()) temp10.$asInstanceOf[Number]().n() else if (temp10.$isInstanceOf[Sum]()) { <synthetic> val temp13: Sum = temp10.$asInstanceOf[Sum](); Main.this.eval(temp13.e1()).+(Main.this.eval(temp13.e2())) } else throw new MatchError(temp10) };
Improve this answer

Comments

37

Since version 2.8, Scala has had the @switch annotation. The goal is to ensure, that pattern matching will be compiled into tableswitch or lookupswitch instead of series of conditional if statements.

Improve this answer

2 Comments

when to choose @switch over regular if else?
using @switch is more efficient than regular pattern matching. so if all the cases contain constant values, you should always use @switch (because the bytecode implementation will be the same as of java switch instead of many if-else)
1

To expand on @Zifre's comment: if you are reading this in the future and the scala compiler has adopted new compilation strategies and you want to know what they are, here's how you find out what it does.

Copy-paste your match code into a self-contained example file. Run scalac on that file. Then run javap -v -c theClassName$.class.

For example, I put the following into /tmp/question.scala:

object question { abstract class Expr case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr def eval(e: Expr): Int = e match { case Number(x) => x case Sum(l, r) => eval(l) + eval(r) } }

Then I ran scalac question.scala, which produced a bunch of *.class files. Poking around a bit, I found the match statement inside question$.class. The javap -c -v question$.class output is available below.

Since we're looking for a condition control flow construct, knowing about the java bytecode instruction set suggests that looking for "if" should be a good place to start.

In two locations we find a pair of consecutive lines on the form isinstanceof <something>; ifeq <somewhere>, which means: if the most recently computed value is not an instance of something then goto somewhere. (ifeq is jump if zero, and isinstanceof gives you a zero to represent false.)

If you follow the control flow around, you'll see that it agrees with the answer given by @Jorge Ortiz: we do if (blah isinstanceof something) { ... } else if (blah isinstanceof somethingelse) { ... }.

Here is the javap -c -v question$.class output:

Classfile /tmp/question$.class Last modified Nov 20, 2020; size 956 bytes MD5 checksum cfc788d4c847dad0863a797d980ad2f3 Compiled from "question.scala" public final class question$ minor version: 0 major version: 50 flags: (0x0031) ACC_PUBLIC, ACC_FINAL, ACC_SUPER this_class: #2 // question$ super_class: #4 // java/lang/Object interfaces: 0, fields: 1, methods: 3, attributes: 4 Constant pool: #1 = Utf8 question$ #2 = Class #1 // question$ #3 = Utf8 java/lang/Object #4 = Class #3 // java/lang/Object #5 = Utf8 question.scala #6 = Utf8 MODULE$ #7 = Utf8 Lquestion$; #8 = Utf8 <clinit> #9 = Utf8 ()V #10 = Utf8 <init> #11 = NameAndType #10:#9 // "<init>":()V #12 = Methodref #2.#11 // question$."<init>":()V #13 = Utf8 eval #14 = Utf8 (Lquestion$Expr;)I #15 = Utf8 question$Number #16 = Class #15 // question$Number #17 = Utf8 n #18 = Utf8 ()I #19 = NameAndType #17:#18 // n:()I #20 = Methodref #16.#19 // question$Number.n:()I #21 = Utf8 question$Sum #22 = Class #21 // question$Sum #23 = Utf8 e1 #24 = Utf8 ()Lquestion$Expr; #25 = NameAndType #23:#24 // e1:()Lquestion$Expr; #26 = Methodref #22.#25 // question$Sum.e1:()Lquestion$Expr; #27 = Utf8 e2 #28 = NameAndType #27:#24 // e2:()Lquestion$Expr; #29 = Methodref #22.#28 // question$Sum.e2:()Lquestion$Expr; #30 = NameAndType #13:#14 // eval:(Lquestion$Expr;)I #31 = Methodref #2.#30 // question$.eval:(Lquestion$Expr;)I #32 = Utf8 scala/MatchError #33 = Class #32 // scala/MatchError #34 = Utf8 (Ljava/lang/Object;)V #35 = NameAndType #10:#34 // "<init>":(Ljava/lang/Object;)V #36 = Methodref #33.#35 // scala/MatchError."<init>":(Ljava/lang/Object;)V #37 = Utf8 this #38 = Utf8 e #39 = Utf8 Lquestion$Expr; #40 = Utf8 x #41 = Utf8 I #42 = Utf8 l #43 = Utf8 r #44 = Utf8 question$Expr #45 = Class #44 // question$Expr #46 = Methodref #4.#11 // java/lang/Object."<init>":()V #47 = NameAndType #6:#7 // MODULE$:Lquestion$; #48 = Fieldref #2.#47 // question$.MODULE$:Lquestion$; #49 = Utf8 question #50 = Class #49 // question #51 = Utf8 Sum #52 = Utf8 Expr #53 = Utf8 Number #54 = Utf8 Code #55 = Utf8 LocalVariableTable #56 = Utf8 LineNumberTable #57 = Utf8 StackMapTable #58 = Utf8 SourceFile #59 = Utf8 InnerClasses #60 = Utf8 ScalaInlineInfo #61 = Utf8 Scala { public static final question$ MODULE$; descriptor: Lquestion$; flags: (0x0019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL public static {}; descriptor: ()V flags: (0x0009) ACC_PUBLIC, ACC_STATIC Code: stack=1, locals=0, args_size=0 0: new #2 // class question$ 3: invokespecial #12 // Method "<init>":()V 6: return public int eval(question$Expr); descriptor: (Lquestion$Expr;)I flags: (0x0001) ACC_PUBLIC Code: stack=3, locals=9, args_size=2 0: aload_1 1: astore_2 2: aload_2 3: instanceof #16 // class question$Number 6: ifeq 27 9: aload_2 10: checkcast #16 // class question$Number 13: astore_3 14: aload_3 15: invokevirtual #20 // Method question$Number.n:()I 18: istore 4 20: iload 4 22: istore 5 24: goto 69 27: aload_2 28: instanceof #22 // class question$Sum 31: ifeq 72 34: aload_2 35: checkcast #22 // class question$Sum 38: astore 6 40: aload 6 42: invokevirtual #26 // Method question$Sum.e1:()Lquestion$Expr; 45: astore 7 47: aload 6 49: invokevirtual #29 // Method question$Sum.e2:()Lquestion$Expr; 52: astore 8 54: aload_0 55: aload 7 57: invokevirtual #31 // Method eval:(Lquestion$Expr;)I 60: aload_0 61: aload 8 63: invokevirtual #31 // Method eval:(Lquestion$Expr;)I 66: iadd 67: istore 5 69: iload 5 71: ireturn 72: new #33 // class scala/MatchError 75: dup 76: aload_2 77: invokespecial #36 // Method scala/MatchError."<init>":(Ljava/lang/Object;)V 80: athrow LocalVariableTable: Start Length Slot Name Signature 0 81 0 this Lquestion$; 0 81 1 e Lquestion$Expr; 20 61 4 x I 47 34 7 l Lquestion$Expr; 54 27 8 r Lquestion$Expr; LineNumberTable: line 6: 0 line 7: 2 line 8: 27 line 6: 69 StackMapTable: number_of_entries = 3 frame_type = 252 /* append */ offset_delta = 27 locals = [ class question$Expr ] frame_type = 254 /* append */ offset_delta = 41 locals = [ top, top, int ] frame_type = 248 /* chop */ offset_delta = 2 } SourceFile: "question.scala" InnerClasses: public static #51= #22 of #50; // Sum=class question$Sum of class question public static abstract #52= #45 of #50; // Expr=class question$Expr of class question public static #53= #16 of #50; // Number=class question$Number of class question ScalaInlineInfo: length = 0xE (unknown attribute) 01 01 00 02 00 0A 00 09 01 00 0D 00 0E 01 Scala: length = 0x0 (unknown attribute)
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.