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 else
ową.
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 if
y 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
naEnum
iString
(o tym dużo w internecie) - zamianie kolejności
if
ów przy konwersjiswitch -> 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 😉
Nie mogę zostawić łapki w górę 🙁 albo nie umiem 😮
Dodam specjalnie jakiś plugin do Facebooka, będzie można szerować 😀
Bardzo ładnie.