Pourquoi un interrupteur n'est-il pas optimisé de la même manière qu'un if else enchaîné en c/c++?

Question

La mise en œuvre suivante de square produit une série d'instructions cmp/je comme je m'y attendrais d'une déclaration if enchaînée :

int square(int num) {
    if (num == 0){
        return 0;
    } else if (num == 1){
        return 1;
    } else if (num == 2){
        return 4;
    } else if (num == 3){
        return 9;
    } else if (num == 4){
        return 16;
    } else if (num == 5){
        return 25;
    } else if (num == 6){
        return 36;
    } else if (num == 7){
        return 49;
    } else {
        return num * num;
    }
}

Et ce qui suit produit un tableau de données pour le retour :

int square_2(int num) {
    switch (num){
        case 0: return 0;
        case 1: return 1;
        case 2: return 4;
        case 3: return 9;
        case 4: return 16;
        case 5: return 25;
        case 6: return 36;
        case 7: return 49;
        default: return num * num;
    }
}

Pourquoi gcc n'arrive-t-il pas à optimiser le premier en le transformant en le deuxième ?

Désassemblage à titre de référence : https://godbolt.org/z/UP_igi

ÉDIT : Curieusement, MSVC génère une table de saut au lieu d'un tableau de données pour le switch case. Et étonnamment, clang les optimise tous les deux pour le même résultat.

Answer 1

Le code généré pour la convention switch-case utilise conventionnellement une table de saut. Dans ce cas, le retour direct à travers une table de recherche semble être une optimisation utilisant le fait que chaque cas ici implique un retour. Bien que la norme ne garantisse pas cet effet, je serais surpris qu'un compilateur génère une série de comparaisons au lieu d'une table de saut pour un switch-case conventionnel.

En passant au if-else, c'est exactement l'opposé. Alors que switch-case s'exécute en temps constant, quel que soit le nombre de branches, if-else est optimisé pour un plus petit nombre de branches. Ici, vous vous attendriez à ce que le compilateur génère essentiellement une série de comparaisons dans l'ordre que vous les avez écrites.

Donc si j'avais utilisé if-else parce que je m'attends à ce que la plupart des appels à square() soient pour 0 ou 1 et rarement pour d'autres valeurs, alors 'optimiser' ceci pour une table de recherche pourrait en fait rendre mon code plus lent que prévu, contrecarrant mon intention d'utiliser un if au lieu d'un switch. Donc bien que cela soit discutable, je pense que GCC fait la bonne chose et que clang est trop agressif dans son optimisation.

Quelqu'un avait, dans les commentaires, partagé un lien où clang effectue cette optimisation et génère également du code basé sur une table de recherche pour if-else. Quelque chose de notable se produit lorsque nous réduisons le nombre de cas à seulement deux (et un default) avec clang. Il génère à nouveau un code identique pour les if et switch, mais cette fois-ci, passe aux comparaisons et déplacements au lieu de l'approche de la table de recherche, pour les deux. Cela signifie que même clang, qui privilégie switch, sait que le modèle 'if' est plus optimal lorsque le nombre de cas est petit!

En résumé, une séquence de comparaisons pour if-else et une table de saut pour switch-case est le modèle standard que les compilateurs ont tendance à suivre et les développeurs ont tendance à attendre lorsqu'ils écrivent du code. Cependant, pour certains cas spéciaux, certains compilateurs pourraient choisir de rompre ce modèle s'ils estiment qu'il offre une meilleure optimisation. D'autres compilateurs pourraient tout simplement choisir de suivre le modèle de toute façon, même s'il est apparemment sous-optimal, faisant confiance au développeur pour savoir ce qu'il veut. Les deux approches sont valides avec leurs propres avantages et inconvénients.

Answer 2

Une justification possible est que si les faibles valeurs de num sont plus probables, par exemple toujours 0, le code généré pour le premier pourrait être plus rapide. Le code généré pour le switch prend un temps égal pour toutes les valeurs.

En comparant les meilleurs cas, selon ce tableau. Voir cette réponse pour l'explication du tableau.

Si num == 0, pour le "if" vous avez xor, test, je (avec saut), ret. Latence: 1 + 1 + saut. Cependant, xor et test sont indépendants donc la vitesse d'exécution réelle serait plus rapide que 1 + 1 cycles.

Si num < 7, pour le "switch" vous avez mov, cmp, ja (sans saut), mov, ret. Latence: 2 + 1 + pas de saut + 2.

Une instruction de saut qui ne résulte pas en un saut est plus rapide qu'une qui en résulte. Cependant, le tableau ne définit pas la latence pour un saut, il n'est donc pas clair pour moi lequel est meilleur. Il est possible que le dernier soit toujours meilleur et que GCC ne soit simplement pas capable de l'optimiser.