Frais généraux d'une instruction switch en C
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis un programmeur Java assez compétent qui est très nouveau à C. J'essaie d'optimiser une routine qui a quatre modes de fonctionnement.
boucle de I sur tous les pixels dans une image, et calculer une nouvelle valeur de pixel en fonction du mode « » adopté.
Ma question concerne les frais généraux d'une instruction switch dans les deux boucles imbriquées pour. Je serais intéressé par des liens vers la documentation concernant l'efficacité relative des états C de base, les mathématiques et les opérations logiques.
Le code irait comme suit:
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
case 1:
weight = (float)x/width;
break;
case 2:
weight = (float)y/height;
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
// Calculate the new pixel value given the weight
...
}
}
Voulez-vous attendre à voir de frais généraux si cela était sur une image de 5000 x 5000 pixels? Je l'ai essayé de faire des tests, mais mes résultats sont dans tous les sens que le système (Mobile Device) a toutes sortes de choses en cours d'exécution en arrière-plan qui peuvent fausser les résultats.
L'autre option est d'avoir une méthode distincte pour chaque mode, chacun avec ses propres quatre boucles. Ce serait évidemment introduire du code redondant, mais l'efficacité est le nom du jeu ici.
Merci d'avance!
Gav
La solution
Instructions de commutation compilent à une table de saut pour les valeurs consécutives et à un tas de déclarations if-else pour les valeurs rares. Dans tous les cas, vous ne voulez pas une instruction switch dans votre boucle interne pour le traitement d'image si vous vous souciez de la performance. Vous voulez comme ci-dessous à la place.
Notez également que je déplacé le calcul du poids de la boucle interne (et échangé les boucles pour le cas 2 afin de réaliser cela). Ce type de pensée, des choses se déplaçant hors de la boucle intérieure, vous obtiendrez la performance que vous voulez sur C.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 1:
for (x = 0; x < width; x++) {
weight = (float)x/width;
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 2:
// note - the loops have been swapped to get the weight calc out of the inner loop
for (y = 0; y < height; y++) {
weight = (float)y/height;
for (x = 0; x < width; x++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 4:
weight = dTopRight / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
default:
weight = 1;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
// etc..
}
Autres conseils
Si l'efficacité est plus importante que la taille du code, alors oui, vous devez créer des routines redondantes. La déclaration de cas est l'une des choses aériennes plus bas que vous pouvez faire en C, mais il est différent de zéro - il va devoir se ramifier en fonction du mode, et il va prendre du temps. Si vous voulez vraiment la performance maximum, obtenir le cas de la boucle, même au prix de dupliquer la boucle.
Instructions de commutation sont à peu près aussi efficaces qu'ils peuvent être. Ils sont compilés à une table de saut. En fait, c'est pourquoi l'interrupteur est aussi limité que c'est: vous ne pouvez écrire un interrupteur pour lequel vous peut compiler une table de saut en fonction d'une valeur fixe
.Par rapport aux mathématiques que vous faites dans la boucle, la surcharge du commutateur sera probablement minime. Ceci étant dit, la seule façon d'être sûr est de créer des versions différentes pour les deux approches différentes, et le temps eux.
Switch / cas est extrêmement rapide par rapport à l'équivalent avec if / else: il est généralement mis en œuvre comme une table de saut. Cependant, il a toujours un coût.
Alors que vous optimisez les choses:
1) Essayez de boucler sur des lignes, et non sur des colonnes (commutateur x et y « pour » boucles), une solution peut être incroyablement plus rapide que l'autre, en raison de la gestion de la mémoire cache.
2) Remplacer toutes les divisions par multiplications de la (pré-calculée) inverse vous donnera un gain important, et probablement une perte de précision acceptable.
Par souci d'efficacité vous feriez mieux de passer switch en dehors de la boucle.
J'utiliser des pointeurs de fonction comme ceci:
double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */
double (*fun)(void);
switch (mode) /* select the type of calculation */
{
case 0: fun = fun0;
break;
case 1: fun = fun1;
break;
case 2: fun = fun2;
break;
case 3: fun = fun3;
break;
case 4: fun = fun3;
break;
default : fun = fun_default;
break;
}
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Il ajoute une surcharge d'appel de fonction, mais il ne devrait pas être trop grand que vous ne transmettez pas params à la fonction. Je pense qu'il est bon compromis entre la performance et la lisibilité.
EDIT: Si vous utilisez GCC, pour se débarrasser de la fonction appel, vous pouvez utiliser Commutateurs shouldnt produisent une surcharge importante, ils sont compilés dans une sorte de tableau de pointeurs à l'extrémité basse, il est un cas de manière efficace: JMP {} + baseaddress switchcasenum goto et
Cela dépendra probablement de la façon dont bon votre prédicteur de branchement de CPU est, et comment votre compilateur génère le code pour le commutateur. Pour un si petit nombre de cas, il peut générer un arbre de décision, auquel cas la prédiction de branchement CPU normale devrait être en mesure d'éliminer la plupart des frais généraux. Les choses pourraient être un peu plus mal si elle génère une table de commutation ...
Cela dit, la meilleure façon de le savoir est de profil et voir.
En plus de l'avis de Jim, essayez d'échanger l'ordre des boucles. Que ce soit en boucle swapping est idéal pour le cas 1 nécessiterait des tests, mais je soupçonne qu'il est. Vous voulez presque toujours vos coordonnées x dans votre boucle interne afin d'améliorer les performances d'échange, car cela provoque votre fonction d'avoir une meilleure tendance à rester dans la même zone de mémoire générale à chaque itération. Et un appareil mobile avec des ressources limitted pourrait avoir assez de RAM faible que cette différence sera souligné.
Désolé de remonter ce fil, mais il me semble que l'interrupteur est loin d'être le problème.
Le vrai problème avec l'efficacité dans ce cas sont les divisions. Il me semble que tous les dénominateurs des opérations de division sont des constantes (largeur, hauteur, max ...) et ceux-ci ne changera pas tout au long de l'image. Si je pense est juste, alors ce sont des variables simples qui peuvent changer en fonction de l'image chargée de sorte que toute image de taille peut être utilisée lors de l'exécution, maintenant cela permet une taille de l'image à charger, mais cela signifie aussi que le compilateur ne peut pas les optimiser dans l'opération de multiplication beaucoup plus simple qu'il pourrait faire si elles ont été déclarées « const ». Ma suggestion serait de pré-calculer les inverses de ces constantes et se multiplier. Pour autant que je me souvienne, l'opération de multiplication prend environ 10 cycles d'horloge, alors que la division prend environ 70. C'est une augmentation de 60 cycles par pixel, et mentionné ci-dessus 5000x5000, qui est une augmentation de la vitesse estimée de 1,5 seconde sur un 1 CPU GHz.
dépend de la carte et le compilateur et les détails du code, et ... mais cela sera mis en œuvre souvent comme une table de saut, qui devrait être assez rapide.
BTW-- Comprendre ce genre de chose est un assez bon argument pour passer quelques semaines à apprendre un certain assemblage à un moment donné dans votre carrière ...
L'utilisation d'un commutateur est probablement mieux à la fois pour la vitesse et le temps du programmeur. Vous faites moins de code redondant et il ne sera probablement pas besoin d'un nouveau cadre de pile.
Les commutateurs sont si efficaces qu'ils peuvent utiliser pour vraiment bizarre et déroutant magie noire .
mais l'efficacité est le nom du jeu ici.
itérer sur un tampon d'image afin de calculer de nouvelles valeurs de pixel ressemble à un problème embarrassant parallèle typique, en ce sens que vous voudrez peut-être envisager de pousser certains des travaux dans les threads de travail, cela devrait accélérer votre opération plus notamment que micro-optimisations telles que les préoccupations commutateur / cas.
En outre, au lieu de faire les instructions de branchement à chaque fois, vous pouvez appeler un pointeur de fonction à partir d'un tableau de pointeurs de fonction, où l'indice sert de identifiant de mode.
Alors que vous vous retrouvez avec des appels tels que:
computeWeight[mode](pixel);
Avec 5000x5000 pixels, les frais généraux d'appel de fonction pourrait également être réduite en appelant la fonction pour une gamme de pixels, plutôt que des pixels individuels.
Vous pouvez également utiliser la boucle de déroulement et passage de paramètres par référence / pointeur, afin d'optimiser davantage.
Beaucoup de bons points sont déjà donnés. La seule chose que je pouvais penser à ajouter à cela, est de déplacer les cas les plus fréquents dans le commutateur et le moins bas fréquents.
Donc, si le cas 4 arrive plus souvent que le cas 1, il devrait être au-dessus:
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
Dommage que vous n'utilisez pas c ++, car alors l'instruction switch pourrait être remplacé par le polymorphisme.
Vive!
Il y a beaucoup de suggestions créatives dans ce fil de façons de ne pas avoir à écrire 5 fonctions distinctes.
Sauf si vous lisez « mode » à partir d'un fichier ou d'entrée tapé la méthode de calcul peut être déterminée au moment de la compilation. En règle générale, vous ne voulez pas passer des calculs de temps de compilation pour l'exécution.
De toute façon le code serait plus facile à lire et personne ne serait confus quant à savoir si oui ou non vous vouliez mettre dans l'instruction break dans le premier cas ou non.
De même, lorsque vous obtenez des bugs dans le code environnant vous n'aurez pas à rechercher si le ENUM a été réglé sur une valeur incorrecte ou non.
En ce qui concerne les boucles internes ... 0-> var est mieux fait var-> 0 comme var-- déclenche le zéro drapeau (6502 jours). Cette approche signifie aussi « largeur » est chargé dans x et peut être oublié, même pour la « hauteur ». pixels également en mémoire sont généralement gauche> droite, top-> bas ont donc certainement x que votre boucle intérieure.
for (y = height; y--;) {
for (x = width; x--;) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Et aussi ... et très important est vos déclarations de commutation ont seulement 2 cas qui utilisent x ou y. Les autres sont des constantes.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
break;
//case 1:
// weight = (float)x/width;
// break;
//case 2:
// weight = (float)y/height;
// break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
Donc, fondamentalement, à moins que le mode 1 ou 2, le poids est calculé avant la boucle.
... Y loop code here
if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop
... X loop here
if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
calc_pixel_using_weight(weight);
J'ai trouvé des états de commutation très désobligeant si les données sont rares. Pour <4 éléments que j'irais pour if-then-else et assurez-vous les cas les plus courants sont le haut. Si la première condition attire 90% des cas, vous avez essentiellement frappé un home run. De même, si une autre condition est <1% a mis la dernière.
