Unoptimized code generated for Enum dispatch

[nmichael44]

When generating code for a simple Enum, the compiler generates a huge chain of if-else-if statements instead of a tableswitch. The same problem exists for more general ADTs of course (and it's more complicated to fix this for those since we would have to generate a hidden tag etc), but for just plain enums I would expect this to work. Everything is there for you - just detect this case (of a simple Enum), call ordinal() on it and index into the table. Even Kotlin does this.

Compiler version

"3.6.4"

Minimized code

  enum Z:
    case A, B, C, D, E, F, G

  def f(n: Z): Int =
    import Z.*
    n match {
      case A => 23
      case B => 12
      case C => -1
      case D => 4
      case E => 12
      case F => -11
      case G => 21
    }

Output

  public f(Lapp/Main$Z;)I
    // parameter final  n
   L0
    LINENUMBER 47 L0
    ALOAD 1
    ASTORE 2
   L1
    LINENUMBER 48 L1
    GETSTATIC app/Main$Z$.A : Lapp/Main$Z;
    ALOAD 2
    ASTORE 3
    DUP
    IFNONNULL L2
    POP
    ALOAD 3
    IFNULL L3
    GOTO L4
   L2
    ALOAD 3
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L4
   L3
    BIPUSH 23
    IRETURN
   L4
    LINENUMBER 49 L4
    GETSTATIC app/Main$Z$.B : Lapp/Main$Z;
    ALOAD 2
    ASTORE 4
    DUP
    IFNONNULL L5
    POP
    ALOAD 4
    IFNULL L6
    GOTO L7
   L5
    ALOAD 4
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L7
   L6
    BIPUSH 12
    IRETURN
   L7
    LINENUMBER 50 L7
    GETSTATIC app/Main$Z$.C : Lapp/Main$Z;
    ALOAD 2
    ASTORE 5
    DUP
    IFNONNULL L8
    POP
    ALOAD 5
    IFNULL L9
    GOTO L10
   L8
    ALOAD 5
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L10
   L9
    ICONST_M1
    IRETURN
   L10
    LINENUMBER 51 L10
    GETSTATIC app/Main$Z$.D : Lapp/Main$Z;
    ALOAD 2
    ASTORE 6
    DUP
    IFNONNULL L11
    POP
    ALOAD 6
    IFNULL L12
    GOTO L13
   L11
    ALOAD 6
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L13
   L12
    ICONST_4
    IRETURN
   L13
    LINENUMBER 52 L13
    GETSTATIC app/Main$Z$.E : Lapp/Main$Z;
    ALOAD 2
    ASTORE 7
    DUP
    IFNONNULL L14
    POP
    ALOAD 7
    IFNULL L15
    GOTO L16
   L14
    ALOAD 7
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L16
   L15
    BIPUSH 12
    IRETURN
   L16
    LINENUMBER 53 L16
    GETSTATIC app/Main$Z$.F : Lapp/Main$Z;
    ALOAD 2
    ASTORE 8
    DUP
    IFNONNULL L17
    POP
    ALOAD 8
    IFNULL L18
    GOTO L19
   L17
    ALOAD 8
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L19
   L18
    BIPUSH -11
    IRETURN
   L19
    LINENUMBER 54 L19
    GETSTATIC app/Main$Z$.G : Lapp/Main$Z;
    ALOAD 2
    ASTORE 9
    DUP
    IFNONNULL L20
    POP
    ALOAD 9
    IFNULL L21
    GOTO L22
   L20
    ALOAD 9
    INVOKEVIRTUAL java/lang/Object.equals (Ljava/lang/Object;)Z
    IFEQ L22
   L21
    BIPUSH 21
    IRETURN
   L22
    NEW scala/MatchError
    DUP
    ALOAD 2
    INVOKESPECIAL scala/MatchError.<init> (Ljava/lang/Object;)V
    ATHROW
   L23
    LOCALVARIABLE this Lapp/Main$; L0 L23 0
    LOCALVARIABLE n Lapp/Main$Z; L0 L23 1
    MAXSTACK = 3
    MAXLOCALS = 10

Expectation

[som-snytt]

A long-standing request, which is to say, an old request for a contribution. Is GSOC set for this year?

[odersky]

The Java version is described here: #5537 (comment). It uses a table switch, but is a lot more complex than a simple switch on ordinal. What exactly does Kotlin do? As I understand it, there's a trade-off between code simplicity and speed vs separate compilation guarantees.

[nmichael44]

@odersky @som-snytt Here is the same function in Kotlin and the code generated.

enum class Z {
    A, B, C, D, E, F, G
}

fun f(n: Z): Int =
  when (n) {
      Z.A -> 23
      Z.B -> 12
      Z.C -> -1
      Z.D -> 4
      Z.E -> 12
      Z.F -> -11
      Z.G -> 21
  }

Generated code for f:

  public final static f(Lneo/org/app/Z;)I
    // annotable parameter count: 1 (invisible)
    @Lorg/jetbrains/annotations/NotNull;() // invisible, parameter 0
   L0
    ALOAD 0
    LDC "n"
    INVOKESTATIC kotlin/jvm/internal/Intrinsics.checkNotNullParameter (Ljava/lang/Object;Ljava/lang/String;)V
   L1
    LINENUMBER 116 L1
    ALOAD 0
    GETSTATIC neo/org/app/AppKt$WhenMappings.$EnumSwitchMapping$1 : [I
    SWAP
    INVOKEVIRTUAL neo/org/app/Z.ordinal ()I
    IALOAD
    TABLESWITCH
      1: L2
      2: L3
      3: L4
      4: L5
      5: L6
      6: L7
      7: L8
      default: L9
   L2
    LINENUMBER 117 L2
    BIPUSH 23
    GOTO L10
   L3
    LINENUMBER 118 L3
    BIPUSH 12
    GOTO L10
   L4
    LINENUMBER 119 L4
    ICONST_M1
    GOTO L10
   L5
    LINENUMBER 120 L5
    ICONST_4
    GOTO L10
   L6
    LINENUMBER 121 L6
    BIPUSH 12
    GOTO L10
   L7
    LINENUMBER 122 L7
    BIPUSH -11
    GOTO L10
   L8
    LINENUMBER 123 L8
    BIPUSH 21
    GOTO L10
   L9
    LINENUMBER 116 L9
    NEW kotlin/NoWhenBranchMatchedException
    DUP
    INVOKESPECIAL kotlin/NoWhenBranchMatchedException.<init> ()V
    ATHROW
   L10
    LINENUMBER 124 L10
    IRETURN
   L11
    LOCALVARIABLE n Lneo/org/app/Z; L0 L11 0
    MAXSTACK = 2
    MAXLOCALS = 1

[odersky]

Thanks for reporting this! So Kotlin does use a simple table switch based on ordinal. Whereas Java jumps through a lot of hoops, involving one inner class for each enum switch, to ensure that reorderings of enums don't break binary compatibility.

Personally, I am not convinced binary compatibility under re-orderings is necessary here. Reordering an enum changes the ordinal values of enum constants. That's a semantic change, which should be done only if all clients can be inspected to not rely on precise ordinal values. So it seems strange to require a manual verification of client code but not require a recompile. Seen in another way, no public library should re-order enums, because clients could break. So why insist on that change being binary compatible?

[nmichael44]

@odersky I agree with your reasoning. Doing this optimization is a good change.

[He-Pin]

@nmichael44 @odersky maybe #23264 can help sometime?
And in Java 17 there is a https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/runtime/SwitchBootstraps.html#enumSwitch(java.lang.invoke.MethodHandles.Lookup,java.lang.String,java.lang.invoke.MethodType,java.lang.Object...)

[som-snytt]

Kotlin does the same as Java. The $EnumSwitchMapping$1 is the extra table that associates ordinal with "switch order".

The static construction of that table is laborious but happens once.

My naive understanding is that it's a small price compared to a code comment

// Don't remove or reorder this enum because that would break the world until next release

There is such a code comment to preserve "error ID" for compiler ErrorMessageID. The standard Josh Bloch advice is don't use ordinal for semantics. The JavaDoc is "Most programmers will have no use for this method." For that use case, it would be nice to have a mechanism that "preserves history", that is, generate a static table that preserves historical order (because we have git history) the way the SwitchMapping preserves the order of a particular switch at a point in time.

[nmichael44]

@odersky Here is the decompiled code for the Kotlin jar file. @som-snytt is correct that Kotlin does the same as Java, except that it's not a class per enum, it's one array per enum and one class per file (I had more enums in my kotlin file and all the arrays were constructed in the same class WhenMappings class -- see below).

   public static final int f(@NotNull Z n) {
      Intrinsics.checkNotNullParameter(n, "n");
      byte var10000;
      switch(AppKt.WhenMappings.$EnumSwitchMapping$1[n.ordinal()]) {
      case 1:
         var10000 = 23;
         break;
      case 2:
         var10000 = 12;
         break;
      case 3:
         var10000 = -1;
         break;
      case 4:
         var10000 = 4;
         break;
      case 5:
         var10000 = 12;
         break;
      case 6:
         var10000 = -11;
         break;
      case 7:
         var10000 = 21;
         break;
      default:
         throw new NoWhenBranchMatchedException();
      }

      return var10000;
   }

   // $FF: synthetic class
   @Metadata(
      mv = {2, 1, 0},
      k = 3,
      xi = 48
   )
   public class WhenMappings {
      // $FF: synthetic field
      public static final int[] $EnumSwitchMapping$1;

        var0 = new int[Z.values().length];

         try {
            var0[Z.A.ordinal()] = 1;
         } catch (NoSuchFieldError var8) {
         }

         try {
            var0[Z.B.ordinal()] = 2;
         } catch (NoSuchFieldError var7) {
         }

         try {
            var0[Z.C.ordinal()] = 3;
         } catch (NoSuchFieldError var6) {
         }

         try {
            var0[Z.D.ordinal()] = 4;
         } catch (NoSuchFieldError var5) {
         }

         try {
            var0[Z.E.ordinal()] = 5;
         } catch (NoSuchFieldError var4) {
         }

         try {
            var0[Z.F.ordinal()] = 6;
         } catch (NoSuchFieldError var3) {
         }

         try {
            var0[Z.G.ordinal()] = 7;
         } catch (NoSuchFieldError var2) {
         }

         $EnumSwitchMapping$1 = var0;
      }
   }
}

[odersky]

// Don't remove or reorder this enum because that would break the world until next release

That is there for a completely different reason. The authors of the file wanted to use an enum and ensure at the same time that the printed error number stays the same forever. It's certainly a dubious idiom, I was not a fan when it was introduced.

I am also very skeptical about not using ordinal in enums. If that's so bad, why is it not deprecated?

[som-snytt]

There is no construct for "deprecated if you don't know what you're doing." A lint could ask, "Did you intend to use notify and wait?" (as an example of API that is not deprecated but is not intended for casual usage).