Pourquoi les compilateurs C optimisent le commutateur et si différemment

Je travaillais sur un projet personnel récemment lorsque je suis tombé sur un problème étrange.

Dans une boucle très serrée, j'ai un entier avec une valeur comprise entre 0 et 15. J'ai besoin d'obtenir -1 pour les valeurs 0, 1, 8 et 9 et 1 pour les valeurs 4, 5, 12 et 13.

Je me suis tourné vers godbolt pour vérifier quelques options et j'ai été surpris de constater que le compilateur ne pouvait pas optimiser une instruction switch de la même manière qu'une chaîne if.

Le lien est ici: https://godbolt.org/z/WYVBFl

Le code est:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

J'aurais pensé que b et c produiraient les mêmes résultats, et j'espérais pouvoir lire les bit-hacks pour trouver une implémentation efficace moi-même puisque ma solution (l'instruction switch - sous une autre forme) était assez lente.

Curieusement, bcompilé en bit-hacks alors qu'il cétait à peu près non optimisé ou réduit à un cas différent en afonction du matériel cible.

Quelqu'un peut-il expliquer pourquoi il y a cet écart? Quelle est la manière «correcte» d'optimiser cette requête?

ÉDITER:

Clarification

Je veux que la solution de commutation soit la plus rapide ou une solution similaire "propre". Cependant, lorsqu'elle est compilée avec des optimisations sur ma machine, la solution if est beaucoup plus rapide.

J'ai écrit un programme rapide pour démontrer et TIO a les mêmes résultats que je trouve localement: Essayez-le en ligne!

Avec static inlinela table de recherche accélère un peu: essayez-le en ligne!

Si vous énumérez explicitement tous les cas, gcc est très efficace:

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

est simplement compilé dans une simple branche indexée:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Notez que s'il default:n'est pas commenté, gcc revient à sa version de branche imbriquée.

Les compilateurs C ont des cas particuliers pour switch, car ils s'attendent à ce que les programmeurs comprennent l'idiome de switchet l'exploitent.

Code comme:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

ne passerait pas l'examen par les codeurs C compétents; trois ou quatre examinateurs s'exclamaient simultanément "cela devrait être un switch!"

Cela ne vaut pas la peine pour les compilateurs C d'analyser la structure des ifinstructions pour la conversion en table de saut. Les conditions doivent être justes et la quantité de variation possible dans un tas de ifdéclarations est astronomique. L'analyse est à la fois compliquée et susceptible de se révéler négative (comme dans: "non, nous ne pouvons pas convertir ces ifs en switch").

Le code suivant calculera votre recherche sans branche, sans LUT, en ~ 3 cycles d'horloge, ~ 4 instructions utiles et ~ 13 octets de inlinecode machine x86 très performant.

Cela dépend de la représentation entière du complément à 2.

Vous devez cependant vous assurer que les u32et s32typedefs pointent vraiment vers des types entiers non signés et signés 32 bits. stdint.htypes uint32_tet int32_taurait été approprié mais je n'ai aucune idée si l'en-tête est disponible pour vous.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Voyez par vous-même ici: https://godbolt.org/z/AcJWWf

Sur la sélection de la constante

Votre recherche porte sur 16 très petites constantes comprises entre -1 et +1 inclus. Chacun tient dans 2 bits et il y en a 16, que nous pouvons présenter comme suit:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

En les plaçant avec l'index 0 le plus proche du bit le plus significatif, un seul décalage de 2*numplacera le bit de signe de votre nombre à 2 bits dans le bit de signe du registre. Décaler à droite le nombre de 2 bits de 32-2 = signe de 30 bits le prolonge au maximum int, complétant l'astuce.

Vous pouvez créer le même effet en utilisant uniquement l'arithmétique:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Même si, techniquement, il s'agit toujours d'une recherche (au niveau du bit).

Si ce qui précède semble trop mystérieux, vous pouvez également faire:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}