Comment le filtrage en Scala est-il implémenté au niveau du bytecode ?

Question

Comment le filtrage en Scala est-il implémenté au niveau du bytecode ?

Est-ce que c'est comme une série de if (x instanceof Foo) des constructions, ou autre chose ? Quelles sont ses implications en termes de performance ?

Par exemple, avec le code suivant (tiré de Scala par exemple pages 46-48), comment le code Java équivalent pour l'application eval ressemble-t-elle ?

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. Je peux lire le bytecode Java, donc une représentation en bytecode serait suffisante pour moi, mais il serait probablement mieux pour les autres lecteurs de savoir à quoi cela ressemblerait en tant que code Java.

P.P.S. Est-ce que le livre Programmation en Scala donner une réponse à cette question et à d'autres questions similaires sur la façon dont Scala est implémenté ? J'ai commandé le livre, mais il n'est pas encore arrivé.

Answer 1

Le bas niveau peut être exploré avec un désassembleur mais la réponse courte est qu'il s'agit d'un tas de if/eles où le prédicat dépend du modèle

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

Il est possible de faire beaucoup plus avec les motifs, comme les motifs ou et les combinaisons comme "case Foo(45, x)", mais en général, ce ne sont que des extensions logiques de ce que je viens de décrire. Les patrons peuvent aussi avoir des gardes, qui sont des contraintes supplémentaires sur les prédicats. Il y a aussi des cas où le compilateur peut optimiser la correspondance des motifs, par exemple lorsqu'il y a un certain chevauchement entre les cas, il peut coalescer un peu les choses. Les modèles avancés et l'optimisation sont un domaine de travail actif du compilateur. Ne soyez donc pas surpris si le code d'octet s'améliore considérablement par rapport à ces règles de base dans les versions actuelles et futures de Scala.

En plus de tout cela, vous pouvez écrire vos propres extracteurs personnalisés en plus ou à la place de ceux que Scala utilise par défaut pour les classes de cas. Si vous le faites, le coût de la correspondance des motifs est le coût de ce que fait l'extracteur. Un bon aperçu se trouve dans http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

Answer 2

James (ci-dessus) l'a bien dit. Cependant, si vous êtes curieux, c'est toujours un bon exercice de regarder le bytecode désassemblé. Vous pouvez également invoquer scalac avec le -print qui imprimera votre programme en supprimant toutes les caractéristiques spécifiques à Scala. Il s'agit en fait de Java dans les vêtements de Scala. Voici la version pertinente scalac -print pour l'extrait de code que vous avez donné :

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

Answer 3

Depuis la version 2.8, Scala dispose de la fonction @switch annotation. L'objectif est de s'assurer que le filtrage de motifs sera compilé dans l'annotation tableswitch ou lookupswitch au lieu d'une série de conditionnels if déclarations.

Answer 4

Pour développer le commentaire de @Zifre : si vous lisez ceci dans le futur et que le compilateur scala a adopté de nouvelles stratégies de compilation et que vous voulez savoir ce qu'elles sont, voici comment découvrir ce qu'il fait.

Copier-coller votre match dans un fichier d'exemple autonome. Exécuter scalac sur ce fichier. Ensuite, exécutez javap -v -c theClassName$.class .

Par exemple, j'ai mis ce qui suit dans /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)
  }
}

Puis j'ai couru scalac question.scala qui a produit un tas de *.class des fichiers. En farfouillant un peu, j'ai trouvé l'instruction match à l'intérieur de question$.class . Le site javap -c -v question$.class est disponible ci-dessous.

Puisque nous recherchons une construction de flux de contrôle de condition, la connaissance du jeu d'instructions du bytecode java suggère que la recherche de "if" devrait être un bon point de départ.

A deux endroits, nous trouvons une paire de lignes consécutives sur la forme isinstanceof <something>; ifeq <somewhere> ce qui signifie que si la valeur la plus récemment calculée est no une instance de something then goto somewhere . ( ifeq es jump if zero y isinstanceof vous donne un zéro pour représenter le faux).

Si vous suivez le flux de contrôle, vous verrez qu'il est conforme à la réponse donnée par @Jorge Ortiz : nous faisons if (blah isinstanceof something) { ... } else if (blah isinstanceof somethingelse) { ... } .

Voici le javap -c -v question$.class sortie :

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)