Dlaczego zmiana jest szybsza niż gdyby

Wiele książek na temat języka Java opisuje to switchstwierdzenie jako szybsze niż if elseoświadczenie. Ale nigdzie się nie dowiedziałem, dlaczego zmiana jest szybsza niż gdyby .

Przykład

Mam sytuację, w której muszę wybrać jedną z dwóch pozycji. Mogę użyć albo użyć

switch (item) {
    case BREAD:
        //eat Bread
        break;
    default:
        //leave the restaurant
}

lub

if (item == BREAD) {
    //eat Bread
} else {
    //leave the restaurant
}

biorąc pod uwagę pozycję i CHLEB jest stałą wartością int.

W powyższym przykładzie, który jest szybszy w działaniu i dlaczego?

Ponieważ istnieją specjalne kody bajtowe, które umożliwiają wydajną ocenę instrukcji przełącznika, gdy jest wiele przypadków.

Gdyby zaimplementowano ją za pomocą instrukcji IF, miałbyś kontrolę, skok do następnej klauzuli, sprawdzenie, skok do następnej klauzuli i tak dalej. Za pomocą przełącznika maszyna JVM ładuje wartość do porównania i wykonuje iterację w tabeli wartości, aby znaleźć dopasowanie, co w większości przypadków jest szybsze.

switchStwierdzenie nie zawsze jest szybsze niż ifstwierdzeniem. Skaluje się lepiej niż długa lista if-elseinstrukcji, ponieważ switchmoże przeprowadzić wyszukiwanie na podstawie wszystkich wartości. Jednak w krótkim stanie nie będzie szybszy i może być wolniejszy.

Bieżąca maszyna JVM ma dwa rodzaje kodów bajtów przełączających: LookupSwitch i TableSwitch.

Każdy przypadek w instrukcji switch ma przesunięcie w postaci liczby całkowitej, jeśli te przesunięcia są ciągłe (lub przeważnie ciągłe bez dużych przerw) (przypadek 0: przypadek 1: przypadek 2 itd.), To używany jest TableSwitch.

Jeśli przesunięcia są rozłożone z dużymi przerwami (przypadek 0: przypadek 400: przypadek 93748: itp.), Używany jest LookupSwitch.

Krótko mówiąc, różnica polega na tym, że TableSwitch jest wykonywany w stałym czasie, ponieważ każda wartość w zakresie możliwych wartości ma określone przesunięcie kodu bajtowego. Tak więc, kiedy podasz instrukcję przesunięcie o wartości 3, będzie ona wiedziała, że ​​ma przeskoczyć do przodu o 3, aby znaleźć właściwą gałąź.

Przełącznik wyszukiwania używa wyszukiwania binarnego, aby znaleźć właściwą gałąź kodu. Działa to w czasie O (log n), co jest nadal dobre, ale nie najlepsze.

Więcej informacji na ten temat można znaleźć tutaj: Różnica między LookupSwitch i TableSwitch maszyny JVM?

Jeśli chodzi o to, który z nich jest najszybszy, zastosuj następujące podejście: jeśli masz 3 lub więcej obserwacji, których wartości są następujące po sobie lub prawie następujące po sobie, zawsze używaj przełącznika.

Jeśli masz 2 przypadki, użyj instrukcji if.

W każdej innej sytuacji najprawdopodobniej nastąpi zmiana szybsze, ale nie jest gwarantowane, ponieważ wyszukiwanie binarne w LookupSwitch może trafić w zły scenariusz.

Należy również pamiętać, że JVM przeprowadzi optymalizacje JIT w instrukcjach if, które będą próbowały umieścić najgorętszą gałąź jako pierwszą w kodzie. Nazywa się to „Przewidywaniem gałęzi”. Więcej informacji na ten temat można znaleźć tutaj: https://dzone.com/articles/branch-prediction-in-java

Twoje doświadczenia mogą się różnić. Nie wiem, czy JVM nie uruchamia podobnej optymalizacji na LookupSwitch, ale nauczyłem się ufać optymalizacjom JIT i nie próbować przechytrzyć kompilatora.

Więc jeśli planujesz mieć dużo pamięci pakietów, obecnie nie jest to duży koszt, a tablice są dość szybkie. Nie można również polegać na instrukcji switch, która automatycznie generuje tabelę skoków i jako taka łatwiej jest samodzielnie wygenerować scenariusz tabeli skoków. Jak widać w poniższym przykładzie, zakładamy maksymalnie 255 pakietów.

Aby uzyskać poniższy wynik, potrzebujesz abstrakcji ... Nie będę wyjaśniał, jak to działa, więc mam nadzieję, że masz to rozumieć.

Zaktualizowałem to, aby ustawić rozmiar pakietu na 255, jeśli potrzebujesz więcej, to będziesz musiał sprawdzić granice (id <0) || (id> długość).

Packets[] packets = new Packets[255];

static {
     packets[0] = new Login(6);
     packets[2] = new Logout(8);
     packets[4] = new GetMessage(1);
     packets[8] = new AddFriend(0);
     packets[11] = new JoinGroupChat(7); // etc... not going to finish.
}

public void handlePacket(IncomingData data)
{
    int id = data.readByte() & 0xFF; //Secure value to 0-255.

    if (packet[id] == null)
        return; //Leave if packet is unhandled.

    packets[id].execute(data);
}

Edytuj, ponieważ często używam tabeli skoków w C ++, teraz pokażę przykład tabeli skoków wskaźnika funkcji. To jest bardzo ogólny przykład, ale uruchomiłem go i działa poprawnie. Pamiętaj, że musisz ustawić wskaźnik na NULL, C ++ nie zrobi tego automatycznie, jak w Javie.

#include <iostream>

struct Packet
{
    void(*execute)() = NULL;
};

Packet incoming_packet[255];
uint8_t test_value = 0;

void A() 
{ 
    std::cout << "I'm the 1st test.\n";
}

void B() 
{ 
    std::cout << "I'm the 2nd test.\n";
}

void Empty() 
{ 

}

void Update()
{
    if (incoming_packet[test_value].execute == NULL)
        return;

    incoming_packet[test_value].execute();
}

void InitializePackets()
{
    incoming_packet[0].execute = A;
    incoming_packet[2].execute = B;
    incoming_packet[6].execute = A;
    incoming_packet[9].execute = Empty;
}

int main()
{
    InitializePackets();

    for (int i = 0; i < 512; ++i)
    {
        Update();
        ++test_value;
    }
    system("pause");
    return 0;
}

Kolejną kwestią, którą chciałbym poruszyć, jest słynny Divide and Conquer. Więc mój pomysł na tablicę powyżej 255 można zredukować do nie więcej niż 8 instrukcji if jako najgorszy scenariusz.

To znaczy, pamiętaj, że jest to bałaganiarskie i trudne do szybkiego zarządzania, a moje inne podejście jest ogólnie lepsze, ale jest to wykorzystywane w przypadkach, gdy tablice po prostu tego nie radzą. Musisz określić swój przypadek użycia i kiedy każda sytuacja działa najlepiej. Tak jak nie chciałbyś używać żadnego z tych podejść, jeśli masz tylko kilka sprawdzeń.

If (Value >= 128)
{
   if (Value >= 192)
   {
        if (Value >= 224)
        {
             if (Value >= 240)
             {
                  if (Value >= 248)
                  {
                      if (Value >= 252)
                      {
                          if (Value >= 254)
                          {
                              if (value == 255)
                              {

                              } else {

                              }
                          }
                      }
                  }
             }      
        }
   }
}

Na poziomie kodu bajtowego zmienna podmiotu jest ładowana tylko raz do rejestru procesora z adresu pamięci w ustrukturyzowanym pliku .class ładowanym przez Runtime i jest to instrukcja switch; podczas gdy w instrukcji if, inna instrukcja jvm jest tworzona przez DE kompilującego kod, a to wymaga, aby każda zmienna była załadowana do rejestrów, chociaż ta sama zmienna jest używana jak w następnej poprzedzającej instrukcji if. Jeśli znasz kodowanie w języku asemblera, byłoby to powszechne; chociaż sterniki skompilowane w Javie nie są kodem bajtowym ani bezpośrednim kodem maszynowym, koncepcja warunkowa jest nadal spójna. Cóż, wyjaśniając, starałem się unikać głębszych szczegółów technicznych. Mam nadzieję, że przedstawiłem koncepcję jasną i zdemistyfikowaną. Dziękuję Ci.