Pourquoi switch est plus rapide que if

Question

De nombreux livres sur Java décrivent l'instruction switch comme étant plus rapide que l'instruction if else. Mais je n'ai trouvé nulle part pourquoi switch est plus rapide que if.

Exemple

J'ai une situation où je dois choisir n'importe quel élément parmi deux. Je peux utiliser soit

switch (element) {
    case PAIN:
        //manger du pain
        break;
    default:
        //quitter le restaurant
}

ou

if (element == PAIN) {
    //manger du pain
} else {
    //quitter le restaurant
}

en considérant que element et PAIN sont des valeurs entières constantes.

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

Answer 1

Parce qu'il existe des bytecodes spéciaux qui permettent une évaluation efficace de l'instruction switch lorsqu'il y a beaucoup de cas.

Si elle était mise en œuvre avec des instructions IF, il faudrait une vérification, un saut vers la clause suivante, une vérification, un saut vers la clause suivante, etc. Avec l'instruction switch, la JVM charge la valeur à comparer et itère à travers le tableau de valeurs pour trouver une correspondance, ce qui est plus rapide dans la plupart des cas.

Answer 2

Une instruction switch n'est pas toujours plus rapide qu'une instruction if. Elle offre une meilleure évolutivité qu'une longue liste d'instructions if-else car switch peut effectuer une recherche basée sur toutes les valeurs. Cependant, pour une condition courte, elle ne sera pas plus rapide et pourrait être plus lente.

Answer 3

La JVM actuelle possède deux types de codes d'octets de commutation : LookupSwitch et TableSwitch.

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

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

La différence, en bref, est que TableSwitch se fait en temps constant car chaque valeur dans la plage de valeurs possibles se voit attribuer un décalage de code d'octets spécifique. Ainsi, lorsque vous donnez à l'instruction un décalage de 3, elle sait à quelle branche correcte sauter.

LookupSwitch utilise une recherche binaire pour trouver la bonne branche de code. Cela s'exécute en temps O(log n), ce qui est toujours bien, mais ce n'est pas le meilleur.

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

Donc en ce qui concerne celui qui 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 switch.

Si vous avez 2 cas, utilisez une instruction if.

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

Gardez également à l’esprit que la JVM exécutera des optimisations JIT sur les instructions if qui tenteront de placer la branche la plus utilisée en premier dans le code. Cela s'appelle la "Prédiction de branche". Pour plus d'informations à ce sujet, consultez ici : https://dzone.com/articles/branch-prediction-in-java

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

Answer 4

Donc, si vous prévoyez d'avoir un grand nombre de paquets de mémoire, ce n'est pas vraiment un grand coût de nos jours et les tableaux sont assez rapides. Vous ne pouvez pas non plus vous fier à une instruction switch pour générer automatiquement une table de sauts, il est donc plus facile de générer vous-même le scénario de la table de sauts. 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 en avez une compréhension.

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

Paquets[] paquets = new Paquets[255];

static {
     paquets[0] = new Connexion(6);
     paquets[2] = new Déconnexion(8);
     paquets[4] = new ObtenirMessage(1);
     paquets[8] = new AjouterAmi(0);
     paquets[11] = new RejoindreChatGroupe(7); // etc... je ne vais pas finir.
}

public void gérerPaquet(DonnéesEntrantes données)
{
    int id = données.lireByte() & 0xFF; //Valeur sécurisée à 0-255.

    if (paquets[id] == null)
        return; //Quitter si le paquet n'est pas traité.

    paquets[id].exécuter(données);
}

Édit depuis que j'utilise beaucoup une Table de Saut en C++, je vais donc montrer un exemple de table de sauts de pointeurs de fonction. C'est un exemple très générique, mais je l'ai exécuté et ça fonctionne correctement. Gardez à l'esprit que vous devez définir le pointeur sur NULL, C++ ne le fera pas automatiquement comme en Java.

#include 

struct Paquet
{
    void(*exécuter)() = NULL;
};

Paquet paquet_entrant[255];
uint8_t valeur_test = 0;

void A() 
{ 
    std::cout << "Je suis le 1er test.\n";
}

void B() 
{ 
    std::cout << "Je suis le 2ème test.\n";
}

void Vide() 
{ 

}

void MettreÀJour()
{
    if (paquet_entrant[valeur_test].exécuter == NULL)
        return;

    paquet_entrant[valeur_test].exécuter();
}

void InitialiserPaquets()
{
    paquet_entrant[0].exécuter = A;
    paquet_entrant[2].exécuter = B;
    paquet_entrant[6].exécuter = A;
    paquet_entrant[9].exécuter = Vide;
}

int main()
{
    InitialiserPaquets();

    for (int i = 0; i < 512; ++i)
    {
        MettreÀJour();
        ++valeur_test;
    }
    system("pause");
    return 0;
}

Un autre point que j'aimerais souligner est la célèbre technique de Diviser pour Régner. Ainsi, mon idée d'array de 255 ci-dessus pourrait être réduite à pas plus de 8 if statements en cas de pire scénario.

Par exemple, mais gardez à l'esprit que cela devient désordonné et difficile à gérer rapidement et mon autre approche est généralement meilleure, mais cela est utilisé dans des cas où les tableaux ne suffisent 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.

Si (Valeur >= 128)
{
   si (Valeur >= 192)
   {
        si (Valeur >= 224)
        {
             si (Valeur >= 240)
             {
                  si (Valeur >= 248)
                  {
                      si (Valeur >= 252)
                      {
                          si (Valeur >= 254)
                          {
                              si (valeur == 255)
                              {

                              } else {

                              }
                          }
                      }
                  }
             }      
        }
   }
}

Answer 5

Au niveau du bytecode, la variable de sujet est chargée uniquement une fois dans le registre du processeur à partir d'une adresse mémoire dans le fichier .class structuré chargé par Runtime, et cela se trouve dans une instruction switch ; tandis 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 dans l'instruction if précédente suivante. Si vous connaissez la programmation en langage d'assemblage, cela serait courant ; bien que les codes compilés en java ne soient pas du bytecode, ou du code machine direct, le concept conditionnel est toujours cohérent ici. Eh bien, j'ai essayé d'éviter une explication plus technique en expliquant. J'espère avoir rendu le concept clair et démystifié. Merci.