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

9

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!

LambdaBeta
la source
4
Je soupçonne que la réponse est "Les compilateurs ne font pas toujours des choix sensés". Je viens de compiler votre code en un objet avec GCC 8.3.0 avec -O3, et il a compilé cen quelque chose de probablement pire que aou b( cavait deux sauts conditionnels plus quelques manipulations de bits, contre un seul saut conditionnel et une manipulation de bits plus simple pour b), mais toujours mieux que des tests élément par élément. Je ne sais pas vraiment ce que vous demandez ici; le simple fait est qu'un compilateur d'optimisation peut transformer n'importe lequel de ces éléments en l' un des autres s'il le souhaite, et il n'y a pas de règles strictes pour ce qu'il fera ou ne fera pas.
ShadowRanger
Mon problème est que j'en ai besoin pour être rapide, mais la solution if n'est pas trop maintenable. Existe-t-il un moyen pour que le compilateur optimise suffisamment une solution plus propre? Quelqu'un peut-il expliquer pourquoi il ne peut pas le faire dans ce cas?
LambdaBeta
Je commencerais par définir au moins les fonctions comme étant statiques ou, mieux encore, en les intégrant.
Wildplasser
@wildplasser accélère, mais ifbat toujours switch(la recherche étrange devient encore plus rapide) [TIO à suivre]
LambdaBeta
@LambdaBeta Il n'y a aucun moyen de dire à un compilateur d'optimiser d'une manière spécifique. Vous remarquerez que clang et msvc génèrent un code complètement différent pour ceux-ci. Si vous ne vous souciez pas et que vous voulez simplement ce qui fonctionne le mieux sur gcc, choisissez-le. Les optimisations du compilateur sont basées sur des heuristiques, et celles-ci ne fournissent pas la solution optimale dans tous les cas; Ils essaient d'être bons dans le cas moyen, pas optimaux dans tous les cas.
Cubic

Réponses:

6

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.

Alain Merigot
la source
1
@LambdaBeta Vous devriez envisager de ne pas accepter ma réponse et d'accepter celle-ci, car les processeurs Intel modernes peuvent effectuer deux lectures / cycles de mémoire indexée parallèle alors que le débit de mon astuce est probablement de 1 recherche / cycle. D'un autre côté, mon hack est peut-être plus adapté à la vectorisation à 4 voies avec SSE2 pslld/ psradou leurs équivalents AVX2 à 8 voies. Cela dépend beaucoup des autres particularités de votre code.
Iwillnotexist Idonotexist
4

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").

Kaz
la source
Je sais, c'est pourquoi j'ai commencé avec l'interrupteur. Cependant, la solution if est beaucoup plus rapide dans mon cas. Je demande essentiellement s'il existe un moyen de convaincre le compilateur d'utiliser une meilleure solution pour le commutateur, car il a pu trouver le modèle dans les if, mais pas le commutateur. (Je n'aime pas les if spécifiquement parce qu'ils ne sont pas aussi clairs ou
faciles à
Surévalué mais non accepté car le sentiment est exactement la raison pour laquelle j'ai posé cette question. Je veux utiliser le commutateur, mais il est trop lent dans mon cas, je veux éviter le ifplus possible.
LambdaBeta
@LambdaBeta: Y a-t-il une raison d'éviter la table de recherche? Faites-le staticet utilisez les initialiseurs désignés par C99 si vous voulez rendre un peu plus clair ce que vous attribuez, et c'est clairement parfaitement bien.
ShadowRanger
1
Je commencerais au moins par éliminer le bit bas afin qu'il y ait moins de travail à faire pour l'optimiseur.
R .. GitHub STOP HELPING ICE
@ShadowRanger Malheureusement, c'est encore plus lent que le if(voir modifier). @R .. J'ai élaboré la solution complète au niveau du bit pour le compilateur, ce que j'utilise pour l'instant. Malheureusement dans mon cas, ce sont des enumvaleurs, pas des entiers nus, donc les hacks au niveau du bit ne sont pas très maintenables.
LambdaBeta
4

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.

Iwillnotexist Idonotexist
la source
Ce pourrait être la façon la plus propre de le faire avec un magiccommentaire expliquant comment le régénérer. Pourriez-vous expliquer comment vous en êtes arrivé à cela?
LambdaBeta du
Accepté car cela peut être rendu «propre» tout en étant rapide. (via la magie du préprocesseur :) < xkcd.com/541 >)
LambdaBeta
1
Bat ma tentative sans branche:!!(12336 & (1<<x))-!!(771 & (1<<x));
technosaurus
0

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;
}
KevinZ
la source