Switch – czy na pewno wiesz jak to działa?

Czy zdarzyło Ci się użyć switch’a? A wiesz dokładniej jak on działa? A czy nazwa LookUpSwitch coś Ci mówi? Ciekawa jestem ile osób wie o poniższych ciekawostkach. 

Kilka słów o switch’u

Pewnie nie raz zdarzyło Ci się skorzystać z konstrukcji switch’a w javie. Sprawa wydaje się prosta – w zależności od wyniku porównania następuje skok w odpowiednie miejsce w kodzie.

Rozważmy prosty kod:

switch (i) {
    case 0: System.out.println("Zero"); break;
    case 1: System.out.println("Jeden"); break;
    case 2: System.out.println("Dwa"); break;
} 

Bardzo proste porównanie, które jednak daje dość duże pole do popisu, jeśli chodzi o wydajność. Żeby to zrozumieć musimy zajrzeć jak może wyglądać kod maszynowy przeznaczony dla procesora. W „ludzkim” formacie można by zapisać powyższy kod następująco:

1. Porównaj czy i == 0, jeśli tak to skocz do 5
2. Porównaj czy i == 1, jeśli tak to skocz do 7
3. Porównaj czy i == 2, jeśli tak to skocz do 9
4. Skocz do 10
5. Wypisz „Zero”
6. Skocz do 10
7. Wypisz „Jeden”
8. Skocz do 10
9. Wypisz „Dwa”
10.  Koniec

Czy tylko mi się wydaje, czy podzielasz moją opinię, że zamiast serii porównań można by się pokusić o zapisanie indeksów kolejnych instrukcji w tablicy i pobrać adres skoku na podstawie wartości zmiennej.

A może da się inaczej?

To może pokuśmy się o rozważenie powyższej zmiany? Powyższa operacja zostałaby zastąpiona przez tablicę (TableSwitch):

Indeks tabeli / Wartość zmiennej „i”	Adres instrukcji
0	2
1	4
2	6

Oraz kod:

1. Skocz do instrukcji o numerze TableSwitch[i]
2. Wypisz „Zero”
3. Skocz do 7
4. Wypisz „Jeden”
5. Skocz do 7
6. Wypisz „Dwa”
7. Koniec

Niewielkim dodatkowym kosztem (nowa tablica), skróciliśmy kod. Dodatkowo zamiast trzech kolejnych porównań wystarczy tylko pobrać numer kolejnej instrukcji z tablicy i tam od razu przejść. Daje to nam duże przyśpieszenie, szczególnie przy dużych switch’ach. Ale co jeśli wartości zmiennej „i” nie są bliskie sobie? Załóżmy, że zamiast wartości 0, 1 i 2 tym razem mamy wartości 0, 2017 i 24384848. Tablica nie może mieć „dziur”, indeks 24384848 oznacza, że w tablicy musi być przynajmniej 24384849 wartości ( z czego większość będzie pusta). Zakładając, że indeks instrukcji jest rozmiaru 4 bajtów to 24384849 liczbowych wartości oznacza prawie 100MB pamięci… Niewykorzystanej pamięci… Czyli żeby zaoszczędzić 2 operacje zużyliśmy ogromne ilości pamięci, która w zasadzie nie jest używana (użycie wynosi 0,0000123%). Chyba nie o to nam chodziło? W takiej sytuacji lepiej jest jednak pozostawić kilka instrukcji więcej niż nadgorliwie optymalizować kosztem pamięci.

Alternatywne rozwiązanie

Mądrzy ludzie tworzący javę przewidzieli taką sytuację i wprowadzili… drugą implementację switcha – LookUpSwitch. Jest bardzo zbliżony do TableSwitch’a jednak wymaga trochę więcej porównań. Tym razem mamy trochę bardziej skomplikowaną tabelę niż w przypadku TableSwitcha:

Indeks tabeli	Wartość zmiennej „i”	Adres instrukcji
0	0	2
1	2017	4
2	24384848	6

Sam kod pozostaje bez większych zmian:

1. Znajdź Adres instrukcji na podstawie wartości zmiennej w LUT (LookUpTable)
2. Wypisz „Zero”
3. Skocz do 7
4. Wypisz „Dwa tysiące siedemnaście”
5. Skocz do 7
6. Wypisz „Dwadzieścia cztery miliony trzysta osiemdziesiąt cztery tysiące osiemset czterdzieści osiem”
7.  Koniec

Tabela LUT jest przeszukiwania przy pomocy wyszukiwania binarnego w tablicy, więc ma złożoność log2(n). Oznacza to, że dla powyższej tabeli zostaną wykonane maksymalnie dwa porównania. Udało się stworzyć coś pośredniego, gdzie występuje nieduże zużycie pamięci i jest zapewniona wystarczająco dobra wydajność.

Switch kontra String

To tyle, jeśli chodzi o liczby… A jak działa switch dla Stringów (wprowadzony w javie 1.7)?
Ciągów znaków nie można porównać tak jak liczby – trzeba za każdym razem porównywać znak po znaku co oznacza niską wydajność przy dużej liczbie porównań. Tutaj twórcy javy połączyli obie implementacje switcha (TableSwitch oraz LookUpSwitch)i skorzystali ze standardowego mechanizmu hashCode. Oznacza to tyle, że wstępnie do porównania stringów wykorzystywane są liczby, a dopiero po wstępnym dopasowaniu następuje pełne porównanie.

 
switch (var) {
    case "a": System.out.println("Przypadek pierwszy"); break;
    case "b": System.out.println("Przypadek drugi"); break;
    case "c": System.out.println("Przypadek trzeci"); break;
}

Powyższy kod można zapisać jako sekwencję następujących instrukcji:

int idx;
// Najpierw LookUpSwitch
switch (var.hashCode()){
    case 97: 
        if (var.equals("a")) idx = 0;
    case 98: 
        if (var.equals("b")) idx = 1;
    case 99: 
        if (var.equals("c")) idx = 2;
}

// Następnie TableSwitch
switch (idx) {
    case 0: System.out.println("Przypadek pierwszy"); break;
    case 1: System.out.println("Przypadek drugi"); break;
    case 2: System.out.println("Przypadek trzeci"); break;
}

Dodatkowo wewnątrz pierwszego switch’a jest pełne porównanie napisów ze względu na to, że funkcja hashCode może zwrócić takie same wyniki dla różnych napisów. Przykładowo:

"JG".hashCode() = "If".hashCode() = 2365

Gdzie JG jest jak JavaGirl

Gdyby pojawiły się takie wartości, to pierwszy switch przyjąłby następującą postać:

switch (var.hashCode()){
    case 2365: 
        if (var.equals("JG")) idx = 0;
        else if (var.equals("If")) idx = 1;
    [...]
}
[...]

To w końcu co wybrać?

I tak nie masz tutaj wyboru… Kompilator wybierze najrozsądniejszą, według niego, wersję :). Można pisać oczywiście kod, tak aby przypominał jedną bądź drugą wersję, ale nasuwa się pytanie: Czy jest tego warte?

---

Źródła:
1. Wiedza własna
2. https://stackoverflow.com/questions/10287700/difference-between-jvms-lookupswitch-and-tableswitch
3. http://javarevisited.blogspot.com/2014/05/how-string-in-switch-works-in-java-7.html