Pourquoi changer est plus rapide que si

De nombreux livres Java décrivent l' switchinstruction comme étant plus rapide que l' if elseinstruction. Mais je n'ai trouvé nulle part pourquoi le changement est plus rapide que si .

Exemple

J'ai une situation où je dois choisir un élément sur deux. Je peux utiliser soit utiliser

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

ou

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

considérant l'élément et le PAIN est une valeur int constante.

Dans l'exemple ci-dessus, lequel est le plus rapide en action et pourquoi?

Parce qu'il existe des bytecodes spéciaux qui permettent une évaluation efficace des instructions de commutation dans de nombreux cas.

Si elle est implémentée avec des instructions IF, vous auriez une vérification, un saut à la clause suivante, une vérification, un saut à la clause suivante et ainsi de suite. Avec le commutateur, la machine virtuelle Java charge la valeur à comparer et parcourt la table des valeurs pour trouver une correspondance, ce qui est plus rapide dans la plupart des cas.

Une switchinstruction n'est pas toujours plus rapide qu'une ifinstruction. Il s'adapte mieux qu'une longue liste d' if-elseinstructions car il switchpeut effectuer une recherche basée sur toutes les valeurs. Cependant, pour une condition courte, ce ne sera pas plus rapide et pourrait être plus lent.

La machine virtuelle Java actuelle possède deux types de codes d'octet de commutation: LookupSwitch et TableSwitch.

Chaque cas dans une instruction switch a un offset entier, si ces décalages sont contigus (ou pour la plupart contigus sans grands espaces) (cas 0: cas 1: cas 2, etc.), alors TableSwitch est utilisé.

Si les décalages sont répartis avec de grands écarts (cas 0: cas 400: cas 93748 :, etc.), alors LookupSwitch est utilisé.

La différence, en bref, est que TableSwitch est effectué en temps constant car chaque valeur dans la plage de valeurs possibles reçoit un décalage de code d'octet spécifique. Ainsi, lorsque vous donnez à l'instruction un décalage de 3, il sait sauter 3 pour trouver la branche correcte.

Le commutateur de recherche utilise une recherche binaire pour trouver la branche de code correcte. Cela fonctionne en temps O (log n), ce qui est toujours bon, mais pas le meilleur.

Pour plus d'informations à ce sujet, voir ici: Différence entre LookupSwitch et TableSwitch de JVM?

Donc, pour déterminer lequel est le plus rapide, utilisez cette approche: si vous avez 3 cas ou plus dont les valeurs sont consécutives ou presque consécutives, utilisez toujours un commutateur.

Si vous avez 2 cas, utilisez une instruction if.

Pour toute autre situation, le changement est probablement plus rapide, mais ce n'est pas garanti, car la recherche binaire dans LookupSwitch pourrait rencontrer un mauvais scénario.

De plus, gardez à l'esprit que la JVM exécutera des optimisations JIT sur les instructions if qui tenteront de placer la branche la plus chaude en premier dans le code. C'est ce qu'on appelle la «prédiction de branche». Pour plus d'informations à ce sujet, voir ici: https://dzone.com/articles/branch-prediction-in-java

Vos expériences peuvent varier. Je ne sais pas que la JVM n'exécute pas une optimisation similaire sur LookupSwitch, mais j'ai appris à faire confiance aux optimisations JIT et à ne pas essayer de déjouer le compilateur.

Donc, si vous prévoyez d'avoir des tonnes de paquets, la mémoire n'est pas vraiment un coût élevé de nos jours et les tableaux sont assez rapides. Vous ne pouvez pas non plus compter sur une instruction switch pour générer automatiquement une table de saut et en tant que tel, il est plus facile de générer le scénario de table de saut vous-même. Comme vous pouvez le voir dans l'exemple ci-dessous, nous supposons un maximum de 255 paquets.

Pour obtenir le résultat ci-dessous, vous avez besoin d'abstraction ... je ne vais pas expliquer comment cela fonctionne, donc j'espère que vous avez compris cela.

J'ai mis à jour ceci pour définir la taille du paquet à 255 si vous avez besoin de plus que vous devrez faire une vérification des limites pour (id <0) || (id> longueur).

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

Edit puisque j'utilise beaucoup une table de saut en C ++, je vais maintenant montrer un exemple de table de saut de pointeur de fonction. C'est un exemple très générique, mais je l'ai exécuté et cela fonctionne correctement. Gardez à l'esprit que vous devez définir le pointeur sur NULL, C ++ ne le fera pas automatiquement comme en 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;
}

Je voudrais également évoquer un autre point: le fameux Divide and Conquer. Donc, mon idée de tableau ci-dessus de 255 pourrait être réduite à pas plus de 8 déclarations if comme le pire des cas.

C'est-à-dire, mais gardez à l'esprit que cela devient compliqué et difficile à gérer rapidement et que mon autre approche est généralement meilleure, mais cela est utilisé dans les cas où les tableaux ne le coupent tout simplement pas. Vous devez déterminer votre cas d'utilisation et quand chaque situation fonctionne le mieux. Tout comme vous ne voudriez pas utiliser l'une ou l'autre de ces approches si vous n'avez que quelques vérifications.

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 {

                              }
                          }
                      }
                  }
             }      
        }
   }
}

Au niveau du bytecode, la variable subject est chargée une seule fois dans le registre du processeur à partir d'une adresse mémoire du fichier .class structuré chargé par Runtime, et ceci dans une instruction switch; alors que dans une instruction if, une instruction jvm différente est produite par votre DE de compilation de code, et cela nécessite que chaque variable soit chargée dans les registres bien que la même variable soit utilisée que dans l'instruction if précédente. Si vous connaissez le codage en langage assembleur, ce serait courant; bien que les coxes compilés en java ne soient pas du bytecode ou du code machine direct, le concept conditionnel de celui-ci est toujours cohérent. Eh bien, j'ai essayé d'éviter des détails techniques plus profonds en expliquant. J'espère avoir rendu le concept clair et démystifié. Je vous remercie.