Comment fonctionnent les macros probables / improbables du noyau Linux et quel est leur avantage?

J'ai fouillé certaines parties du noyau Linux et j'ai trouvé des appels comme celui-ci:

if (unlikely(fd < 0))
{
    /* Do something */
}

ou

if (likely(!err))
{
    /* Do something */
}

J'en ai trouvé la définition:

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

Je sais qu'ils sont destinés à l'optimisation, mais comment fonctionnent-ils? Et quelle baisse de performances / taille peut-on attendre de leur utilisation? Et cela vaut-il la peine (et probablement de perdre la portabilité) au moins dans le code de goulot d'étranglement (dans l'espace utilisateur, bien sûr).

Ils suggèrent au compilateur d'émettre des instructions qui feront que la prédiction de branchement favorisera le côté "probable" d'une instruction de saut. Cela peut être une grande victoire, si la prédiction est correcte, cela signifie que l'instruction de saut est essentiellement gratuite et ne prendra aucun cycle. D'un autre côté, si la prédiction est fausse, cela signifie que le pipeline du processeur doit être vidé et cela peut coûter plusieurs cycles. Tant que la prédiction est correcte la plupart du temps, cela aura tendance à être bon pour les performances.

Comme toutes ces optimisations de performances, vous ne devriez le faire qu'après un profilage approfondi pour vous assurer que le code est vraiment dans un goulot d'étranglement, et probablement compte tenu de la nature micro, qu'il est exécuté en boucle serrée. En général, les développeurs Linux sont assez expérimentés, donc j'imagine qu'ils l'auraient fait. Ils ne se soucient pas trop de la portabilité car ils ne ciblent que gcc, et ils ont une idée très proche de l'assembly qu'ils veulent générer.

Décompilons pour voir ce que GCC 4.8 en fait

Sans pour autant __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        printf("%d\n", i);
    puts("a");
    return 0;
}

Compilez et décompilez avec GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Production:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

L'ordre des instructions en mémoire est resté inchangé: d'abord le printf, puis putsle retqretour.

Avec __builtin_expect

Remplacez maintenant if (i)par:

if (__builtin_expect(i, 0))

et nous obtenons:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

Le printf(compilé pour__printf_chk ) a été déplacé à la toute fin de la fonction, après putset le retour pour améliorer la prédiction de branche comme mentionné par d'autres réponses.

C'est donc essentiellement la même chose que:

int main() {
    int i = !time(NULL);
    if (i)
        goto printf;
puts:
    puts("a");
    return 0;
printf:
    printf("%d\n", i);
    goto puts;
}

Cette optimisation n'a pas été effectuée avec -O0 .

Mais bonne chance pour avoir écrit un exemple qui tourne plus vite avec __builtin_expectque sans, les processeurs sont vraiment intelligents de nos jours . Mes tentatives naïves sont là .

C ++ 20 [[likely]]et[[unlikely]]

C ++ 20 a normalisé ces éléments intégrés C ++: Comment utiliser l'attribut probable / improbable de C ++ 20 dans l'instruction if-else Ils vont probablement (un jeu de mots!) Faire la même chose.

Ce sont des macros qui donnent au compilateur des indications sur la direction que peut prendre une branche. Les macros s'étendent aux extensions spécifiques à GCC, si elles sont disponibles.

GCC les utilise pour optimiser la prédiction de branche. Par exemple, si vous avez quelque chose comme ce qui suit

if (unlikely(x)) {
  dosomething();
}

return x;

Ensuite, il peut restructurer ce code pour qu'il ressemble davantage à:

if (!x) {
  return x;
}

dosomething();
return x;

L'avantage de ceci est que lorsque le processeur prend une branche pour la première fois, il y a une surcharge importante, car il peut avoir été chargé et exécuté du code de manière spéculative plus loin. Lorsqu'il détermine qu'il prendra la branche, il doit l'invalider et commencer à la cible de la branche.

La plupart des processeurs modernes ont maintenant une sorte de prédiction de branche, mais cela n'aide que lorsque vous avez déjà traversé la branche, et que la branche est toujours dans le cache de prédiction de branche.

Il existe un certain nombre d'autres stratégies que le compilateur et le processeur peuvent utiliser dans ces scénarios. Vous pouvez trouver plus de détails sur le fonctionnement des prédicteurs de branche sur Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Ils obligent le compilateur à émettre les indications de branche appropriées là où le matériel les prend en charge. Cela signifie généralement simplement tordre quelques bits dans l'opcode instruction, donc la taille du code ne changera pas. L'UC commencera à récupérer les instructions à partir de l'emplacement prévu, puis videra le pipeline et recommencera si cela s'avère incorrect lorsque la branche est atteinte; dans le cas où l'indice est correct, cela rendra la branche beaucoup plus rapide - précisément combien plus rapide dépendra du matériel; et dans quelle mesure cela affecte les performances du code dépendra de la proportion de l'indice de temps qui est correcte.

Par exemple, sur un processeur PowerPC, une branche non suggérée peut prendre 16 cycles, une branche 8 correctement suggérée et une branche 24 incorrecte. Dans les boucles les plus internes, une bonne indication peut faire une énorme différence.

La portabilité n'est pas vraiment un problème - probablement la définition est dans un en-tête par plate-forme; vous pouvez simplement définir «probable» et «improbable» à rien pour les plates-formes qui ne prennent pas en charge les conseils de branche statiques.

long __builtin_expect(long EXP, long C);

Cette construction indique au compilateur que l'expression EXP aura très probablement la valeur C. La valeur de retour est EXP. __builtin_expect est destiné à être utilisé dans une expression conditionnelle. Dans presque tous les cas, il sera utilisé dans le contexte d'expressions booléennes, auquel cas il est beaucoup plus pratique de définir deux macros auxiliaires:

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

Ces macros peuvent ensuite être utilisées comme dans

if (likely(a > 1))

Référence: https://www.akkadia.org/drepper/cpumemory.pdf

(commentaire général - d'autres réponses couvrent les détails)

Il n'y a aucune raison de perdre la portabilité en les utilisant.

Vous avez toujours la possibilité de créer un simple "inline" ou macro à effet nul qui vous permettra de compiler sur d'autres plateformes avec d'autres compilateurs.

Vous ne bénéficierez tout simplement pas de l'optimisation si vous êtes sur d'autres plates-formes.

Selon le commentaire de Cody , cela n'a rien à voir avec Linux, mais c'est un indice pour le compilateur. Ce qui se passera dépendra de l'architecture et de la version du compilateur.

Cette fonctionnalité particulière sous Linux est quelque peu mal utilisée dans les pilotes. Comme le souligne osgx dans la sémantique de l'attribut hot , toute fonction hotou coldappelée avec dans un bloc peut automatiquement indiquer que la condition est probable ou non. Par exemple, dump_stack()est marqué colddonc c'est redondant,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Les versions futures de gccpourraient incorporer sélectivement une fonction en fonction de ces conseils. Il a également été suggéré que ce n'est pas le cas boolean, mais un score comme le plus probable , etc. En général, il devrait être préférable d'utiliser un autre mécanisme comme cold. Il n'y a aucune raison de l'utiliser dans n'importe quel endroit sauf les chemins chauds. Ce qu'un compilateur fera sur une architecture peut être complètement différent sur une autre.

Dans de nombreuses versions de Linux, vous pouvez trouver complier.h dans / usr / linux /, vous pouvez l'inclure pour une utilisation simple. Et une autre opinion, peu probable () est plus utile que probable (), car

if ( likely( ... ) ) {
     doSomething();
}

il peut également être optimisé dans de nombreux compilateurs.

Et au fait, si vous souhaitez observer le comportement détaillé du code, vous pouvez simplement faire comme suit:

gcc -c test.c objdump -d test.o> obj.s

Ensuite, ouvrez obj.s, vous pouvez trouver la réponse.

Ce sont des astuces pour le compilateur pour générer les préfixes d'indices sur les branches. Sur x86 / x64, ils occupent un octet, vous obtiendrez donc au plus une augmentation d'un octet pour chaque branche. Quant aux performances, cela dépend entièrement de l'application - dans la plupart des cas, le prédicteur de branche sur le processeur les ignorera de nos jours.

Edit: J'ai oublié un endroit avec lequel ils peuvent vraiment aider. Il peut permettre au compilateur de réorganiser le graphique de flux de contrôle afin de réduire le nombre de branches prises pour le chemin «probable». Cela peut avoir une nette amélioration dans les boucles où vous vérifiez plusieurs cas de sortie.

Il s'agit de fonctions GCC permettant au programmeur de donner au compilateur une indication sur la condition de branche la plus probable dans une expression donnée. Cela permet au compilateur de construire les instructions de branchement afin que le cas le plus courant prenne le moins d'instructions à exécuter.

La façon dont les instructions de branchement sont construites dépend de l'architecture du processeur.