Różnica między LookupSwitch JVM i TableSwitch?

Różnica polega na tym, że

• lookupswitch używa tabeli z kluczami i etykietami
• tableswitch używa tabeli tylko z etykietami .

Podczas wykonywania tableswitch, wartość int na stosie jest bezpośrednio używana jako indeks do tabeli, aby pobrać miejsce docelowe skoku i natychmiast wykonać skok. Cały proces lookup+jump jest operacją O(1) , co oznacza, że jest szybko.

Podczas wykonywania lookupswitch , wartość int na szczycie stosu jest porównywana z kluczami w tabeli, dopóki nie zostanie znalezione dopasowanie, a następnie miejsce docelowe skoku obok tego klucza jest używane do wykonania skoku. Ponieważ tabela lookupswitch zawsze musi być posortowana tak, aby keyX O(log n) , ponieważ klucz będzie przeszukiwany za pomocą binarnego algorytmu wyszukiwania (nie jest konieczne porównywanie wartość int względem wszystkich możliwych kluczy, aby znaleźć dopasowanie lub określić, że żaden z kluczy nie pasuje). O (log n) jest nieco wolniejszy niż o(1), ale nadal jest w porządku, ponieważ wiele dobrze znanych algorytmów to o(log n) i są one zwykle uważane za szybkie; nawet O(n) lub O(n * log N) jest nadal uważany za całkiem dobry algorytm (powolne/złe algorytmy mają O(N^2), O(N^3), lub nawet gorzej).

Decyzję jaką instrukcję użyć podejmuje kompilator w oparciu o to, jak zwarta Instrukcja switch jest, np.

switch (inputValue) {
  case 1:  // ...
  case 2:  // ...
  case 3:  // ...
  default: // ...
}

Przełącznik powyżej jest idealnie zwarty, nie ma numerycznych "dziur". Kompilator utworzy tableswitch w następujący sposób:

 tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

Pseudo kod ze strony Jasmin wyjaśnia to całkiem dobrze:

int val = pop();                // pop an int from the stack
if (val < low || val > high) {  // if its less than <low> or greater than <high>,
    pc += default;              // branch to default 
} else {                        // otherwise
    pc += table[val - low];     // branch to entry in table
}

Ten kod jest dość jasny, jak działa taki przełącznik tableswitch. val jest inputValue, low będzie to 1 (najmniejsza wielkość liter w przełączniku), a high będzie to 3 (najwyższa wielkość liter w przełączniku).

Nawet z kilkoma dziurami przełącznik może być zwarte, np.

switch (inputValue) {
  case 1:  // ...
  case 3:  // ...
  case 4:  // ...
  case 5:  // ...
  default: // ...
}

Przełącznik powyżej jest "prawie zwarty", ma tylko jeden otwór. Kompilator może wygenerować następującą instrukcję:

 tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

  ; <...code left out...>

  FakeTwoLabel:
  DefaultLabel:
    ; default code

Jak widzisz, kompilator musi dodać fake case dla 2, FakeTwoLabel. Ponieważ 2 nie jest rzeczywistą wartością przełącznika, {[11] } jest w rzeczywistości etykietą, która zmienia przepływ kodu dokładnie tam, gdzie znajduje się domyślna wielkość liter, ponieważ wartość 2 powinna w rzeczywistości wykonać domyślną wielkość liter.

Więc przełącznik nie musi być idealnie compact dla kompilatora do tworzenia przełącznika tableswitch, ale powinien być przynajmniej dość zbliżony do zwartości. Teraz rozważ następujący przełącznik:

switch (inputValue) {
  case 1:    // ...
  case 10:   // ...
  case 100:  // ...
  case 1000: // ...
  default:   // ...
}

Ten przełącznik nie jest zbliżony do zwartości, ma ponad sto razy więcej otworów niż wartości . Można by to nazwać rzadkim przełącznikiem. Kompilator musiałby wygenerować prawie tysiąc fałszywych przypadków , aby wyrazić ten przełącznik jako przełącznik tableswitch. Rezultatem byłaby ogromna tabela, powiększająca Rozmiar pliku klasy dramatycznie. To nie jest praktyczne. Zamiast tego wygeneruje lookupswitch:

lookupswitch
    1       : Label1
    10      : Label10
    100     : Label100
    1000    : Label1000
    default : DefaultLabel

Ta tabela zawiera tylko 5 wpisów, zamiast ponad tysiąca. Tabela ma 4 wartości rzeczywiste, o (log 4) to 2 (log jest tu logiem do Bazy 2 BTW, a nie do bazy 10, ponieważ komputer operuje na liczbach binarnych). Oznacza to, że potrzeba maszyny wirtualnej co najwyżej dwóch porównań, aby znaleźć etykietę dla wartości wejściowej lub dojść do wniosku, że wartość nie znajduje się w tabeli, a zatem wartość domyślna musi być stracony. Nawet jeśli tabela zawiera 100 wpisów, znalezienie właściwej etykiety przez maszynę wirtualną zajmie najwyżej 7 porównań lub zdecyduje się przejść do domyślnej etykiety (a 7 porównań to o wiele mniej niż 100 porównań, nie sądzisz?).

Więc to nonsens, że te dwie instrukcje są wymienne lub że przyczyna dwóch instrukcji ma przyczyny historyczne. Istnieją dwie instrukcje dla dwóch różnych sytuacji, jedna dla przełączników o zwartych wartościach (dla maksymalnej prędkości) i jedna dla przełączników o ograniczonych wartościach (Nie prędkości maksymalnej, ale wciąż dobrej prędkości i bardzo zwartej reprezentacji tabeli niezależnie od otworów liczbowych).