Почему переключение быстрее, чем если бы

Во многих книгах по Java switchоператор описывается как более быстрый, чем if elseоператор. Но нигде не узнал, почему switch быстрее if .

пример

У меня есть ситуация, когда я должен выбрать один из двух пунктов. Я могу использовать либо использовать

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

или

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

учитывая элемент, а ХЛЕБ - постоянное значение типа int.

Что в приведенном выше примере работает быстрее и почему?

Потому что существуют специальные байт-коды, которые позволяют эффективно оценивать оператор switch при большом количестве случаев.

Если реализовано с помощью IF-операторов, у вас будет проверка, переход к следующему предложению, проверка, переход к следующему предложению и так далее. С переключателем JVM загружает значение для сравнения и просматривает таблицу значений, чтобы найти совпадение, что в большинстве случаев быстрее.

switchУтверждение не всегда быстрее , чем ifзаявление. Он масштабируется лучше, чем длинный список if-elseоператоров, так как switchможет выполнять поиск по всем значениям. Однако для кратковременных условий это не будет быстрее, а может быть медленнее.

Текущая JVM имеет два типа байтовых кодов переключателей: LookupSwitch и TableSwitch.

Каждый case в операторе switch имеет целочисленное смещение, если эти смещения являются смежными (или в основном смежными без больших промежутков) (case 0: case 1: case 2, и т. Д.), То используется TableSwitch.

Если смещения разбросаны с большими промежутками (case 0: case 400: case 93748: и т. Д.), То используется LookupSwitch.

Короче говоря, разница в том, что TableSwitch выполняется в постоянное время, потому что каждому значению в диапазоне возможных значений дается определенное смещение байтового кода. Таким образом, когда вы задаете оператору смещение 3, он знает, что нужно перейти на 3, чтобы найти правильную ветвь.

Переключатель поиска использует двоичный поиск для поиска правильной ветки кода. Это выполняется за время O (log n), что все еще хорошо, но не лучше.

Дополнительные сведения об этом см. Здесь: Разница между LookupSwitch и TableSwitch JVM?

Итак, какой из них самый быстрый, используйте этот подход: если у вас есть 3 или более случаев, значения которых являются последовательными или почти последовательными, всегда используйте переключатель.

Если у вас 2 случая, используйте оператор if.

В любой другой ситуации переключение, скорее всего, будет быстрее, но это не гарантируется, поскольку двоичный поиск в LookupSwitch может привести к неудачному сценарию.

Также имейте в виду, что JVM будет запускать JIT-оптимизацию для операторов if, которые будут пытаться разместить самую горячую ветвь первой в коде. Это называется «Прогнозирование ветвления». Для получения дополнительной информации об этом см. Здесь: https://dzone.com/articles/branch-prediction-in-java.

Ваш опыт может отличаться. Я не знаю, что JVM не выполняет аналогичную оптимизацию для LookupSwitch, но я научился доверять оптимизации JIT и не пытаться перехитрить компилятор.

Так что, если вы планируете иметь много пакетов, память в наши дни не является большой затратой, а массивы работают довольно быстро. Вы также не можете полагаться на оператор switch для автоматического создания таблицы переходов, и поэтому проще создать сценарий таблицы переходов самостоятельно. Как вы можете видеть в приведенном ниже примере, мы предполагаем максимум 255 пакетов.

Чтобы получить приведенный ниже результат, вам нужна абстракция. Я не собираюсь объяснять, как это работает, поэтому, надеюсь, вы это понимаете.

Я обновил это, чтобы установить размер пакета на 255, если вам нужно больше, чем вам нужно будет выполнить проверку границ для (id <0) || (id> длина).

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);
}

Редактировать, поскольку теперь я часто использую таблицу переходов в C ++, я покажу пример таблицы переходов указателя функций. Это очень общий пример, но я запустил его, и он работает правильно. Имейте в виду, что вы должны установить указатель на NULL, C ++ не будет делать это автоматически, как в Java.

#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;
}

Еще один момент, который я хотел бы затронуть, - это знаменитый «Разделяй и властвуй». Таким образом, моя идея с массивом выше 255 может быть уменьшена до 8 операторов if как наихудший сценарий.

То есть, но имейте в виду, что это становится беспорядочным и трудно управляемым быстро, и мой другой подход, как правило, лучше, но он используется в тех случаях, когда массивы просто не справляются. Вы должны выяснить свой вариант использования и когда каждая ситуация работает лучше всего. Точно так же, как вы не захотите использовать любой из этих подходов, если у вас есть всего несколько проверок.

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 {

                              }
                          }
                      }
                  }
             }      
        }
   }
}

На уровне байт-кода субъектная переменная загружается в регистр процессора только один раз из адреса памяти в структурированном файле .class, загруженном средой выполнения, и это в операторе switch; тогда как в операторе if другая инструкция jvm создается компилирующим код DE, и для этого требуется, чтобы каждая переменная была загружена в регистры, хотя используется та же переменная, что и в следующем предыдущем операторе if. Если вы знаете кодирование на языке ассемблера, это было бы обычным делом; хотя java-скомпилированные coxes не являются байт-кодом или прямым машинным кодом, условная концепция здесь по-прежнему согласована. Что ж, при объяснении я попытался избежать более глубоких технических деталей. Надеюсь, я прояснил эту концепцию и развенчал ее тайну. Спасибо.