Y a-t-il un moyen d'optimiser la ligne de code C suivante (pour éviter la ramification)?
if (i < -threshold || i > threshold) {
counter++;
}
10 Réponses :
Que diriez-vous des éléments suivants:
push %rbp mov %rsp,%rbp movw $0xa,-6(%rbp) movw $0x14,-4(%rbp) movw $0x0,-2(%rbp) movswl -4(%rbp),%edx movswl -6(%rbp),%eax neg %eax cmp %eax,%edx setl %dl movzwl -4(%rbp),%eax cmp -6(%rbp),%ax setg %al or %edx,%eax movzbw %al,%dx movzwl -2(%rbp),%eax lea (%rdx,%rax,1),%eax mov %ax,-2(%rbp) mov $0x0,%eax leaveq retq
ne comprend pas comment cela empêche la ramification. Pouvez-vous coller le code de montage généré ici?
Cela ajouterait 2 à compter si le seuil <0, i> seuil, et je <-HRehold. Il peut être sûr de supposer que le seuil> = 0, mais si l'OP devrait modifier pour ajouter cette hypothèse.
@ Au X86, les évaluations des conditions que les entiers peuvent être effectuées avec des instructions SETL et setg , un peu coûteux car peu fréquenté mais toujours moins cher qu'une branche maltraitée.
C'est une mauvaise pratique de programmation en général, mais si cela était nécessaire sur Cuda, j'utiliserais la méthode d'Oli dans un battement de coeur.
Avez-vous testé la différence entre le bitwise ou | et le logique ou || ?
Pourquoi ne pas le faire comme ça? Stackoverflow.com/Questtions/17095324/...
Comparer l'absolu des deux
Le changement de droite d'un nombre négatif est dans. La question posée "portable".
Agréable. C99 a char_bit dans limites.h au lieu de 8 pour le faire fonctionner sur des architectures inhabituelles (mais toujours en complément). En outre, vous voulez utiliser «absolu> seuil», probablement.
@Oli Charlesworth non, c'est défini sur la mise en œuvre. 6.5.7.5.
Selon la distribution des valeurs de 'i', votre processeur peut bien mettre en cache la prédiction de la branche pour vous mieux que tout changement de code que vous pourriez faire. Voir http://igoro.com / Archives / Fast-and-Slow-and-Slow-Stat-Stat-Staintes-prédictions-in-modern-processeurs / pour une excursion intéressante. Discussion Reddit: http://www.reddit.com/r/programming/ Commentaires / C7UES / FAST_AND_SLOW_IFSTATIFS_BRANCH_PREDICTION_IN /
Vous pouvez utiliser le truc suivant qui réduit les branches à une seule branche: ou, pour le pédaltique: p> if (((unsigned) i + (unsigned) threshold) > ((unsigned) threshold << 1))
{
counter++;
}
L'ajout (et le quart de vitesse) pourrait déborder. De plus, il ne devrait y avoir qu'une branche dans le code d'origine (bien, dépend de l'ensemble de l'instruction, je suppose).
@Oli: Il ne peut pas trop déborder si l'original n'a pas débordé. Si le décalage de gauche a débordé, alors le test d'origine (i <-Hreshold) || (i> seuil) n'aurait aucun sens. Cela marche. Je l'ai beaucoup utilisé. C'est un Tweak non évident.
@Skizz: Je conviens que cela fonctionne dans la pratique dans l'arithmétique de deux compléments. Mais techniquement, le comportement sur le débordement entier est indéfini. Et cela peut arriver dans votre code si par exemple. Seuil = int_max .
@Oli: Cela dépend de la taille de l'int car << favoriserait la valeur LHS à un INT. Vous pouvez explicitement le jeter, vous voulez être vraiment sûr.
@Skizz: Si vous deviez jeter toutes les entrées de non signé, je me sentirais plus heureux à propos de cet extrait de code!
Skizz est correct, mais seulement sur une technicité. En supposant que int est supérieur à 16 bits, car i et seuil a été spécifié par OP pour être 16 bits, la somme ne peut pas déborder. Mais en général, il faut se lancer vers non signé avant l'addition plutôt que après.
@R: C'est un bon point. Je n'avais pas pris en charge le fait que Skizz travaille en 32 bits (en supposant X86) alors que la question était basée sur 16 bits. Dans ce cas, tant que nous pouvons garantir que Tailleof (non signé)> Tailleof (I) , je conviens que l'approche de Skizzy fonctionne (à part quand seuil <0 <0 ) .
Ceci est basé sur Bit Twiddling Hacks , (hautement recommandé)
#define CHAR_BIT 8
int main()
{
int i=-3; // example input
int treshold=2; // example treshold
int count=0;
// step 1: find the absolute value of i
unsigned int r; // the result goes here
int const mask = i >> (sizeof(int) * CHAR_BIT - 1);
r = (i + mask) ^ mask;
// step 2: compute the sign of the difference
// sign becomes 0 (if r<=treshold)
// sign becomes 1 otherwise
int sign = 1 ^ ((unsigned int)(r-treshold-1) >> (sizeof(int) * CHAR_BIT - 1));
count+=sign;
return count;
}
Les numéros négatifs de changement de droite sont définis par la mise en œuvre.
Du bit Twiddling Hacks Site Web: Le 7 mars 2003, Angus Duggan a souligné que la spécification de l'ANSI C de 1989 laisse le résultat de la mise en œuvre de la mise en œuvre de droite signée, donc sur certains systèmes, ce hack pourrait ne pas fonctionner. J'ai lu que l'ANSI C n'exige pas que les valeurs soient représentées comme complémentaire de deux deux, il peut donc ne pas fonctionner pour cette raison (sur un nombre de vieilles anciennes dimintionnellement qui utilise encore son complément). Cela dépend donc de la manière de répondre à la question portable de la question.
@Oli, vous avez raison pour que les nombres négatifs qui changent de droite sont définis. Si vous trouvez un compilateur qui ne met pas en œuvre cela comme réplication de bits sigificants (par exemple ce que tout le monde attend) je vous enverrai une bootle de vin .. (Non, les compilateurs écrits par vous-même ne s'appliquent pas)
@Nils: Non, je ne peux pas penser à un! Mais je sais que certains processeurs n'ont pas d'instruction de décalage arithmétique, je pouvais donc imaginer qu'un compilateur pour une telle plate-forme peut ne pas vous embarquer avec l'extension de signe manuel (qui doit prendre au moins quelques cycles supplémentaires).
Oli Charlesworth, je pense, a la bonne idée. Cependant, je soupçonne qu'il peut être encore optimisé (au détriment de la lisibilité).
Le seuil peut être normalisé à zéro pour supprimer une comparaison.
c'est-à-dire, ...
L'un ou l'autre de ces ajouts pourrait déborder.
Oli a raison mais il est facilement réparé. Cast to Unsigné Avant l'ajout, puis c'est bien. Étant donné que les valeurs d'origine correspondent à signée INT , cela fonctionnera bien.
@R: sur les systèmes utilisant des arithmétiques de deux compléments, la coulée d'un INT négatif à un non signé ajoutera (uint_max + 1) à celui-ci, mais je pense que la norme permet explicitement les systèmes d'utiliser le format de magnitude +, auquel cas la distribution soustraite la valeur de ((uint_max + 1) / 2). Malheureusement, je ne connais pas d'une manière portable garantie d'ajouter une valeur éventuellement négative à une valeur non signée lorsque la somme peut mentir entre INT_MAX et UINT_MAX.
@supercat méfiez-vous, r .. semble vraiment résolu sur le sujet de la coulée négative signée INTS à non signé. Mais il a raison. Il est défini par la norme: il ajoute uint_max + 1 jusqu'à ce que le numéro soit dans la plage correcte. C'est la distribution de non signée à signé qui est définie par la mise en œuvre.
Il existe un idiome standard pour la vérification de la plage avec une seule instruction de comparaison. Cela va comme suit: comme exemple commun (cette version si Si votre type d'origine est plus grand que Pour que cette méthode fonctionne, vous devez naturellement avoir comme pour la façon dont cette "astuce" fonctionne, il est purement déterminé, après la réduction modulo < code> uint_max + 1 , si Dans votre cas, je pense que ce qui suit devrait Travailler juste bien: si Parler d'optimisations, un bon compilateur doit optimiser votre test de plage d'origine pour utiliser l'arithmétique non signé où elle sait que les contraintes sont remplies. Je soupçonne beaucoup le faire avec isdigit est garanti pour être correct par la norme): int (par exemple long long ), vous devrez utiliser des types non signés plus grands (par exemple, non signé long long ). Si a et B sont des constantes ou ont déjà un type non signé, ou si vous savez BA ne déborde pas, vous pouvez omettre le casting de B . a <= b et les types / valeurs doivent être tels que l'expression originale ( Ie A <= x && x <= B ou similaire) se comporte de manière mathématique correctement correctement. Par exemple, si x a été signé et b non signé, x <= b pourrait évaluer à false quand x = -1 et b = uint_max-1 . Tant que vos types d'origine sont tous signés ou plus petits que le type non signé que vous lancez, ce n'est pas un problème. xa se situe dans la plage 0 à BA . Seuil ne change pas entre les itérations de la boucle, le compilateur peut probablement conserver les deux le seuil et 2U * Seuil Dans Registres. A et B constant, mais peut-être pas avec des expressions plus complexes. Même si le compilateur peut l'optimiser, le (non signé) XA x est évalué exactement une fois.
Quel est le problème avec le code d'origine? A-t-il vraiment besoin d'optimiser la main?
Un compilateur décent devrait pouvoir l'optimiser très bien. Toute optimisation des mains ne conduirait probablement qu'à l'obfuscation.
Ce code n'a pas de branche de manière extrêmement portable (toutefois, la mise en œuvre d'ABS peut en avoir une).
counter -= ((threshold - abs(i)) >> 15);
Vous dites "les deux" mais il y a trois variables.
N'oubliez pas que cela fonctionne si cela fonctionne à coup sûr, mais essayez
si (((((non signé) i> seuil)@ZDAV Il ne fonctionne certainement pas pour la plupart des compilateurs. De telles moulages sont au moins définis par la mise en œuvre et obtenez généralement le complément de 2 2.
@Pascal: mauvais . La conversion en non signé est définie exactement par la spécification de la langue. Cependant, il est défini différemment de ce que ZDAV pense (ce n'est pas une valeur absolue).
@R .. Hé, détendez-vous, d'autres ne ressentent pas la nécessité d'utiliser audacieux et des capitales lorsque vous soulignez des erreurs.