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



Answers

Ce sont des macros qui donnent des indications au compilateur sur la façon dont une branche peut aller. Les macros s'étendent aux extensions spécifiques de GCC, si elles sont disponibles.

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

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

return x;

Ensuite, il peut restructurer ce code pour être quelque chose de plus:

if (!x) {
  return x;
}

dosomething();
return x;

L'avantage de ceci est que lorsque le processeur prend une branche la première fois, il y a un surcoût significatif, car il peut avoir été chargé de manière spéculative et avoir exécuté le code plus loin. Quand il détermine qu'il prendra la branche, alors il doit invalider cela, et commencer à la cible de 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à parcouru 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 la façon dont les prédicteurs de branche à Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Question

J'ai creusé à travers certaines parties du noyau Linux, et trouvé des appels comme ceci:

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

ou

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

J'ai trouvé la définition d'eux:

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

Je sais qu'ils sont pour l'optimisation, mais comment fonctionnent-ils? Et combien de performance / taille diminuer peut-on attendre de les utiliser? Et vaut-il la peine (et perdre la portabilité probablement) au moins dans le code de goulot d'étranglement (dans l'espace utilisateur, bien sûr).




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 osgx souligne dans la sémantique de l'attribut chaud , n'importe quelle fonction hot ou cold appelée dans un bloc peut automatiquement laisser entendre que la condition est probable ou non. Par exemple, dump_stack() est marqué cold donc c'est redondant,

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

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




Ils sont des indications pour le compilateur pour générer les préfixes d'indice sur les branches. Sur x86 / x64, ils prennent un octet, donc vous obtiendrez au plus une augmentation d'un octet pour chaque branche. En ce qui concerne les 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 où ils peuvent vraiment aider. Il peut permettre au compilateur de réorganiser le graphe du flux de contrôle pour réduire le nombre de branches prises pour le chemin 'probable'. Cela peut améliorer considérablement les boucles lorsque vous vérifiez plusieurs cas de sortie.




Ils amènent le compilateur à émettre les conseils de branche appropriés là où le matériel les prend en charge. Cela signifie généralement juste 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édit, et vider le pipeline et recommencer 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 combien cela affecte la performance du code dépendra de la proportion de l'indice de temps est correcte.

Par exemple, sur une CPU PowerPC, une branche non représentée peut prendre 16 cycles, une 8 correctement insérée et une incorrecte 24. Dans les boucles les plus profondes, une bonne indication peut faire une énorme différence.

La portabilité n'est pas vraiment un problème - la définition est probablement dans un en-tête par plate-forme; vous pouvez simplement définir "probable" et "improbable" pour les plates-formes qui ne supportent pas les indications de branchement statiques.




Ce sont des fonctions GCC pour que le programmeur donne un indice au compilateur sur ce que sera 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 plus petit nombre d'instructions à exécuter.

La construction des instructions de branchement dépend de l'architecture du processeur.




Links