Switch

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).

Niestety nie zawsze w case szukamy kolejnych liczb porządkowych zaczynając od zera. Czasem są to różne wartości, które nie są w żaden sposób uporządkowane, ani powiązane. Dla takich wartości została stworzona instrukcja lookupswitch. Na etapie kompilacji wszystkie wartości są sortowane. Następnie w runtimie szukamy odpowiedniej wartości używając algorytmu wyszukiwania binarnego znajdywana jest odpowiednia wartość. Dzięki takiemu mechanizmowi możemy znaleźć odpowiednią wartość w czasie logarytmicznym tzn. O(log2(n)).

Oczekiwania vs rzeczywistość

Wydaje się, że taka optymalizacja ma szanse prowadzić do szybszego działania kodu. Oszczędzamy przede wszystkim na wielokrotnym porównywaniu.

A jaka jest rzeczywistość?
Uruchomiłem odpowiednie wspomniane na początku metody jako benchmarki (kod na moim githubie). Mierzyłem przepustowość, czyli ilość operacji na sekundę (im więcej tym lepiej).
Wyniki na moim lapku na JVM OpenJDK w wersji 8 (java-8-openjdk-amd64) są następujące:

SwitchBenchmark.ifInt33      thrpt   10  22022234,398 ± 247287,924  ops/s
SwitchBenchmark.switchInt33  thrpt   10  20090372,745 ± 105013,436  ops/s

SwitchBenchmark.ifInt9       thrpt   10  28632436,517 ± 107714,521  ops/s
SwitchBenchmark.switchInt9   thrpt   10  27754974,543 ± 177176,911  ops/s

Okazuje się, że ciąg if elseów jest szybszy, aniżeli sprawdzenie w tabeli miejsca do instrukcji skoku. Dlaczego?

Otóż taka implementacja switch miała sens w początkach Javy – w drugiej połowie lat 90. Wtedy procesory były dość wolne jak na dzisiejsze standardy, a odczyty z pamięci RAM były względem procesorów całkiem szybkie. Jeśli odczyt z pamięci trwał wówczas kilka cykli procesora wówczas miało to sens. Z biegiem lat wymyślono takie mechanizmy jak wielordzeniowość, pipelining, branch prediction, które znacznie przyspieszyły wykonywanie instrukcji kodu maszynowego nie przyspieszając taktowania (a równocześnie taktowanie zwiększyło się kilku(nasto)krotnie).

O ile skoki warunkowe if mogły w miarę bezboleśnie podlegać tym usprawnieniom, o tyle skok bezwarunkowy do adresu odczytanego z tabeli pod indexem wyliczonym w poprzedniej instrukcji dość skutecznie blokuje owe usprawnienia. Zatem zaleta stała się wadą, co skutkuje gorszą wydajnością…

Jeśli spojrzymy na kod maszynowy skompilowany przezc2 w openjdk8 zauważymy wspomniany fragment kodu maszynowego (skok pod adres wskazany przez wartość w rejestrze)

  0x00007f872101185d: jmpq    *(%r8,%r10)       ;*tableswitch
                                                ; - dev.jgardo.jvm.miscellaneous.switches.SwitchBenchmark::switchInt33@6 (line 96)

OpenJDK vs OracleJDK

Szczęśliwie twórcy OracleJdk 8 stwierdzili, że to może być pewien mało wydajny mechanizm w dzisiejszych czasach, więc po kompilacji c2 instrukcje switch case zostają zamienione na ciąg if elseów (w końcu za coś każą płacić za licencję komercyjną :p).

Niestety switch jest zamieniany na ify dla 9 case, gdy dla 33 caseów dalej jest domyślna implementacja switch

Myśli ostateczne

Wiele o switch można by jeszcze mówić. Można wspomnieć o:

  • implementacji switch na Enum i String (o tym dużo w internecie)
  • zamianie kolejności ifów przy konwersji switch -> if w zależności od statystyki wywołań
  • switch expression
  • i bazującym na nim pattern matching

No nic… Koniec postu, zostawcie łapkę w górę i kliknijcie dzwoneczek, czy inne takie 😉

Oceń wpis

Autor: jgardo

Programista Java od 2013 roku. Interesuje się niskopoziomową Javą, ekosystemem Jvm i jego wydajnością. Co jednak nie przeszkadza w przywiązywaniu uwagi do czystości kodu w życiu codziennym ;) Pracuje w PayU.

3 myśli w temacie “Switch”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *