Czym tak naprawdę jest Lambda w Javie 0 (0)

Jak dobrze pamiętamy, największym osiągnięciem w Javie 8 było wprowadzenie wyrażeń lambda. W tym poście skupię się na tym czym one technicznie są oraz jak one działają.

Pierwsze spostrzeżenia

Jeśli spojrzeć w przeszłość, to przed Javą 8 wyrażenia lambda były emulowane wewnętrznymi klasami anonimowymi. Przykładowo w dla wcześniejszych wersji Javy dla przetwarzania funkcyjnego stworzono klasę Iterables. A w niej zalecanym podejściem było tworzenie anonimowych klas wewnętrznych implementujące interfejsy z jedną metoda. Jakkolwiek było to dość toporne rozwiązanie trzeba było tworzyć dużo zbędnego kodu…

Czy może zatem lambda jest zwykłą wewnętrzna klasa anonimową? Wskazywałby na to również stacktrace zrobiony wewnątrz lambdy w którym widać charakterystyczny dla klas anonimowych znak $, a po nim numer klasy.

public class LambdaExperiment {
    public static void main(String[] args) {
        Function lambda = s -> { throw new RuntimeException(s); };
        lambda.apply("String");
    }
}
Exception in thread "main" java.lang.RuntimeException: String
        at dev.jgardo.jvm.miscellaneous.lambda.LambdaExperiment.lambda$main$0(LambdaExperiment.java:7)
        at dev.jgardo.jvm.miscellaneous.lambda.LambdaExperiment.main(LambdaExperiment.java:8)

I teoria ta miałaby szanse, gdyby nie to, że wśród skompilowanych plików .class nie ma żadnych dodatkowych klas, a każda klasa anonimowa tworzy osobny plik o sufiksie $

Gdzie zatem jest ta lambda?

Cóż… trzeba zajrzeć do kodu bajtowego, może tam coś znajdziemy…

  Last modified 27 wrz 2019; size 1461 bytes
  MD5 checksum f165faff2e94d85a93129e64e8cd7403
  Compiled from "LambdaExperiment.java"
public class dev.jgardo.jvm.miscellaneous.lambda.LambdaExperiment
  minor version: 0
  major version: 55
  flags: (0x0021) ACC_PUBLIC, ACC_SUPER
  this_class: #6                          // dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment
  super_class: #7                         // java/lang/Object
  interfaces: 0, fields: 0, methods: 3, attributes: 3
Constant pool:
   #1 = Methodref          #7.#29         // java/lang/Object."":()V
   #2 = InvokeDynamic      #0:#35         // #0:apply:()Ljava/util/function/Function;
   #3 = String             #36            // String
   #4 = InterfaceMethodref #37.#38        // java/util/function/Function.apply:(Ljava/lang/Object;)Ljava/lang/Object;
   #5 = Methodref          #39.#40        // java/lang/String.toUpperCase:()Ljava/lang/String;
   #6 = Class              #41            // dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment
   #7 = Class              #42            // java/lang/Object
   #8 = Utf8               
   #9 = Utf8               ()V
  #10 = Utf8               Code
  #11 = Utf8               LineNumberTable
  #12 = Utf8               LocalVariableTable
  #13 = Utf8               this
  #14 = Utf8               Ldev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment;
  #15 = Utf8               main
  #16 = Utf8               ([Ljava/lang/String;)V
  #17 = Utf8               args
  #18 = Utf8               [Ljava/lang/String;
  #19 = Utf8               lambda
  #20 = Utf8               Ljava/util/function/Function;
  #21 = Utf8               LocalVariableTypeTable
  #22 = Utf8               Ljava/util/function/Function;
  #23 = Utf8               lambda$main$0
  #24 = Utf8               (Ljava/lang/String;)Ljava/lang/String;
  #25 = Utf8               s
  #26 = Utf8               Ljava/lang/String;
  #27 = Utf8               SourceFile
  #28 = Utf8               LambdaExperiment.java
  #29 = NameAndType        #8:#9          // "":()V
  #30 = Utf8               BootstrapMethods
  #31 = MethodHandle       6:#43          // REF_invokeStatic java/lang/invoke/LambdaMetafactory.metafactory:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
  #32 = MethodType         #44            //  (Ljava/lang/Object;)Ljava/lang/Object;
  #33 = MethodHandle       6:#45          // REF_invokeStatic dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment.lambda$main$0:(Ljava/lang/String;)Ljava/lang/String;
  #34 = MethodType         #24            //  (Ljava/lang/String;)Ljava/lang/String;
  #35 = NameAndType        #46:#47        // apply:()Ljava/util/function/Function;
  #36 = Utf8               String
  #37 = Class              #48            // java/util/function/Function
  #38 = NameAndType        #46:#44        // apply:(Ljava/lang/Object;)Ljava/lang/Object;
  #39 = Class              #49            // java/lang/String
  #40 = NameAndType        #50:#51        // toUpperCase:()Ljava/lang/String;
  #41 = Utf8               dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment
  #42 = Utf8               java/lang/Object
  #43 = Methodref          #52.#53        // java/lang/invoke/LambdaMetafactory.metafactory:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
  #44 = Utf8               (Ljava/lang/Object;)Ljava/lang/Object;
  #45 = Methodref          #6.#54         // dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment.lambda$main$0:(Ljava/lang/String;)Ljava/lang/String;
  #46 = Utf8               apply
  #47 = Utf8               ()Ljava/util/function/Function;
  #48 = Utf8               java/util/function/Function
  #49 = Utf8               java/lang/String
  #50 = Utf8               toUpperCase
  #51 = Utf8               ()Ljava/lang/String;
  #52 = Class              #55            // java/lang/invoke/LambdaMetafactory
  #53 = NameAndType        #56:#60        // metafactory:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
  #54 = NameAndType        #23:#24        // lambda$main$0:(Ljava/lang/String;)Ljava/lang/String;
  #55 = Utf8               java/lang/invoke/LambdaMetafactory
  #56 = Utf8               metafactory
  #57 = Class              #62            // java/lang/invoke/MethodHandles$Lookup
  #58 = Utf8               Lookup
  #59 = Utf8               InnerClasses
  #60 = Utf8               (Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
  #61 = Class              #63            // java/lang/invoke/MethodHandles
  #62 = Utf8               java/lang/invoke/MethodHandles$Lookup
  #63 = Utf8               java/lang/invoke/MethodHandles
{
  public dev.jgardo.jvm.miscellaneous.lambda.LambdaExperiment();
    descriptor: ()V
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."":()V
         4: return
      LineNumberTable:
        line 5: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       5     0  this   Ldev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment;

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=2, args_size=1
         0: invokedynamic #2,  0              // InvokeDynamic #0:apply:()Ljava/util/function/Function;
         5: astore_1
         6: aload_1
         7: ldc           #3                  // String String
         9: invokeinterface #4,  2            // InterfaceMethod java/util/function/Function.apply:(Ljava/lang/Object;)Ljava/lang/Object;
        14: pop
        15: return
      LineNumberTable:
        line 7: 0
        line 8: 6
        line 9: 15
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      16     0  args   [Ljava/lang/String;
            6      10     1 lambda   Ljava/util/function/Function;
      LocalVariableTypeTable:
        Start  Length  Slot  Name   Signature
            6      10     1 lambda   Ljava/util/function/Function;

  private static java.lang.String lambda$main$0(java.lang.String);
    descriptor: (Ljava/lang/String;)Ljava/lang/String;
    flags: (0x100a) ACC_PRIVATE, ACC_STATIC, ACC_SYNTHETIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokevirtual #5                  // Method java/lang/String.toUpperCase:()Ljava/lang/String;
         4: areturn
      LineNumberTable:
        line 7: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       5     0     s   Ljava/lang/String;
}
SourceFile: "LambdaExperiment.java"
InnerClasses:
  public static final #58= #57 of #61;    // Lookup=class java/lang/invoke/MethodHandles$Lookup of class java/lang/invoke/MethodHandles
BootstrapMethods:
  0: #31 REF_invokeStatic java/lang/invoke/LambdaMetafactory.metafactory:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
    Method arguments:
      #32 (Ljava/lang/Object;)Ljava/lang/Object;
      #33 REF_invokeStatic dev/jgardo/jvm/miscellaneous/lambda/LambdaExperiment.lambda$main$0:(Ljava/lang/String;)Ljava/lang/String;
      #34 (Ljava/lang/String;)Ljava/lang/String;

W listingu javap -p -v znaleźliśmy ciało wyrażenia lambda w osobnej, wygenerowanej metodzie o nazwie lambda$main$0 (linia 114), które przyjmuje takie same argumenty jak nasza poszukiwana lambda oraz posiada nazwę, którą widzieliśmy w stacktrace. Jest tam również pewna rzadka instrukcja invokedynamic wprowadzona w Javie 7 (linia 95).

Wciąż jednak nie mamy tej wewnętrznej klasy anonimowej…

Teoria

W projekcie Lambda, twórcy Javy stwierdzili, że jest wiele możliwości implementacji lambd, a każda ma zalety i wady (anonimowa klasa wewnętrzna, dynamiczne proxy, MethodHandle). Nie chcieli się wiązać z żadną implementacją, żeby mieć w przyszłości ewentualną swobodę zmiany koncepcji. Dlatego też stwierdzili, dostarczeniem odpowiedniej implementacji lambdy zajmie się JVM w czasie wykonywania.

Implementacja lambd używa mechanizmu wprowadzonego w poprzedniej wersji Javy – wersji 7 – invokedynamic.
Gdy JVM po raz pierwszy dojdzie do danej instrukcji invokedynamic musi „dowiedzieć się” jaką metodę ma wykonać (w przeciwieństwie do pozostałych instrukcji bytecode z rodziny invoke, na etapie kompilacji nie znamy docelowej wywoływanej metody; znamy tylko metodę, która wskaże co trzeba robić). W przypadku definiowania lambdy, aby się tego dowiedzieć, wywoływana jest metoda java.lang.invoke.LambdaMetafactory.metafactory (linia 132 listingu). W parametrach przekazywane są m. in. uchwyt do wygenerowanej na etapie kompilacji metody tworzącej treść lambdy, jej sygnatura, sygnatura metody interfejsu funkcyjnego, którego implementacji szukamy. Metoda generuje docelową klasę z lambdą, ładuje ją oraz zwraca „fabrykę” obiektów tej klasy.

Po stworzeniu fabryki jest ona przypisywana do danej instrukcji invokedynamic.

Raz stworzona i związana z daną instrukcją invokedynamic fabryka jest następnie używana do uzyskania obiektu implementującego interfejs funkcyjny (lambdę).

Takie podejście ma swoje zalety:– nie wiążemy się z implementacją wyrażeń lambd (ewentualnie można je zmienić)– mniejszy rozmiar bytecode’u pozbawionego klas wewnętrznych oraz mniejsza ilość osobnych plików d0 załadowania– brak możliwości ingerowania w kod lambd – nikt nie będzie grzebał w bytecodzie, którego nie ma 😉

– możliwość cache’owania bezstanowych lambd – nie trzeba zawsze tworzyć nowych obiektów.

Switch 0 (0)

Pierwsze, co może kojarzyć się ze switch-case to szereg następujących po sobie bloków if else. Z pewnością taki blok switch case jest bardziej czytelny aniżeli szereg if else. Jednak każdy zna jakąś sytuację, w której jakiś znajomy w pracy zapomniał dodać break na koniec bloku case, co prowadziło do błędów biznesowych, technicznych lub błędów bezpieczeństwa. A skoro ten break jest przeważnie konieczny, to nie do końca pasuje do teorii o ciągu if elseów. Jaka jest prawda o switch?

Code

Ok, czas na trochę kodu. Zacznijmy od prostej metody, która w zależności od argumentu zwraca różne wartości. Zaimplementowana będzie dwukrotnie – najpierw za pomocą switch, następnie z użyciem ifów.

    public int switchInt9(CountToNine countToNine) {
        int i = countToNine.i;
        switch (i) {
            case 0: return 0;
            case 1: return 8;
            case 2: return 16;
            case 3: return 24;
            case 4: return 32;
            case 5: return 40;
            case 6: return 48;
            case 7: return 56;
            default:
                return 64;
        }
    }

    public int ifInt9(CountToNine countToNine) {
        int i = countToNine.i;
        if (i == 0) {
            return 0;
        } else if (i == 1) {
            return 8;
        } else if (i == 2) {
            return 16;
        } else if (i == 3) {
            return 24;
        } else if (i == 4) {
            return 32;
        } else if (i == 5) {
            return 40;
        } else if (i == 6) {
            return 48;
        } else if (i == 7) {
            return 56;
        } else  {
            return 64;
        }
    }

Stworzyłem też analogiczne metody z 33 wpisami zamiast 9.

Po skompilowaniu takich metod, a następnie zdekompilowaniu z użyciem javap -v widzimy obydwie metody. Pierwsza z użyciem switch wygląda tak:

  public int switchInt9(dev.jgardo.jvm.miscellaneous.switches.SwitchBenchmark$CountToNine);
    descriptor: (Ldev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine;)I
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=1, locals=3, args_size=2
         0: aload_1
         1: invokestatic  #22                 // Method dev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine.access$000:(Ldev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine;)I
         4: istore_2
         5: iload_2
         6: tableswitch   { // 0 to 7
                       0: 52
                       1: 54
                       2: 57
                       3: 60
                       4: 63
                       5: 66
                       6: 69
                       7: 72
                 default: 75
            }
        52: iconst_0
        53: ireturn
        54: bipush        8
        56: ireturn
        57: bipush        16
        59: ireturn
        60: bipush        24
        62: ireturn
        63: bipush        32
        65: ireturn
        66: bipush        40
        68: ireturn
        69: bipush        48
        71: ireturn
        72: bipush        56
        74: ireturn
        75: bipush        64
        77: ireturn

W tym przypadku widzimy instrukcję kodu bajtowego tableswitch z pożądanymi wartościami podawanymi przy case i numerem instrukcji do której ma „skoczyć” jeśli wartość się zgadza. (o tableswitch więcej poniżej)

Dla ifów bytecode wygląda następująco:

  public int ifInt9(dev.jgardo.jvm.miscellaneous.switches.SwitchBenchmark$CountToNine);
    descriptor: (Ldev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine;)I
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=2, locals=3, args_size=2
         0: aload_1
         1: invokestatic  #22                 // Method dev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine.access$000:(Ldev/jgardo/jvm/miscellaneous/switches/SwitchBenchmark$CountToNine;)I
         4: istore_2
         5: iload_2
         6: ifne          11
         9: iconst_0
        10: ireturn
        11: iload_2
        12: iconst_1
        13: if_icmpne     19
        16: bipush        8
        18: ireturn
        19: iload_2
        20: iconst_2
        21: if_icmpne     27
        24: bipush        16
        26: ireturn
        27: iload_2
        28: iconst_3
        29: if_icmpne     35
        32: bipush        24
        34: ireturn
        35: iload_2
        36: iconst_4
        37: if_icmpne     43
        40: bipush        32
        42: ireturn
        43: iload_2
        44: iconst_5
        45: if_icmpne     51
        48: bipush        40
        50: ireturn
        51: iload_2
        52: bipush        6
        54: if_icmpne     60
        57: bipush        48
        59: ireturn
        60: iload_2
        61: bipush        7
        63: if_icmpne     69
        66: bipush        56
        68: ireturn
        69: bipush        64
        71: ireturn

W przypadku ciągu if elseów widzimy… ciąg if elseów… Czyli na poziomie bytecode’u switch nie jest ukrytą opcją if elseową.

Trochę teorii

Otóż w zamyśle do obsługi słowa kluczowego switch stworzono specjalnie dwie instrukcje bytecodu – tableswitch oraz lookupswitch. Zamysł był prosty: zamiast wielokrotnie porównywać z coraz innymi wartościami, na etapie kompilacji stworzymy tablicę par „wartość-adres skoku do instrukcji”. Następnie wystarczyłoby poszukać odpowiedniej wartości w tablicy i skoczyć do tej instrukcji, którą wskazuje.

Dla tableswitch wyszukiwanie jest proste – wystarczy spojrzeć pod index tablicy, której wartości szukamy. Jeśli szukamy wartości 5, to skaczemy do tej instrukcji, którą wskazuje tablica pod indeksem 5. Wówczas czas obliczenia miejsca kolejnej instrukcji jest stały tzn. O(1).