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
switchnaEnumiString(o tym dużo w internecie) - zamianie kolejności
ifów przy konwersjiswitch -> ifw 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.