Mon dilemme concerne comment mieux gérer les longues boucles lourdes pouvant accepter des paramètres. Considérez la méthode suivante:
void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
if (secondaryModification)
{
for (int i = 0; i < 10000000; i++)
{
byte* b = startingAddress + i;
*b+= 1;
*b+= 2;
}
}
else
{
for (int i = 0; i < 10000000; i++)
{
byte* b = startingAddress + i;
*b+= 1;
}
}
}
5 Réponses :
Pourquoi pas comme ceci:
byte * b = startingAddress, * const end = startingAddress + 10000000;
while (b != end) { *(b++) += incr; }
Je pense que l'OP a déclaré "inutile de dire que le code n'est qu'un exemple et non le cas réel. Ne donnez pas de solutions relatives à * b + = 1 en soi." et votre solution appliquée uniquement à l'affaire donnée. Pour une solution plus compliquée, l'utilisation d'un pointeur à fonction fonctionnerait, mais pourrait ne pas vraiment améliorer les performances en raison de la surcharge de l'appel de la fonction (par rapport à la branche simple).
@Matthieum.: Je pense que c'est juste vraiment ce que veut. Vous pouvez sûrement remplacer l'initialisation de augmenter par une composition plus compliquée de conditions. Si l'ensemble du corps de la boucle doit être flexible, nous avons besoin de quelque chose d'autre (et il n'est pas clair que l'indirection via un pointeur de fonction est meilleure que le conditionnel), mais cela n'est pas clair de la question. -1 pour le OP pour cela.
Une technique pour ce type de problème qui fonctionne à la fois C et C ++ consiste à utiliser une fonction en ligne. Pour C ++, vous ne pouvez qu'utiliser simplement une fonction de modèle (efficacement la même solution, mais légèrement plus élégante).
Voici la solution inline pour C / C ++: P>
inline void HeavyLoop_inline(byte* startingAddress, bool secondaryModification)
{
for (int i = 0; i < 10000000; i++)
{
byte* b = startingAddress+ i;
*b+= 1;
if (secondaryModification) *b+= 2;
}
}
void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
if (secondaryModification)
{
HeavyLoop_inline(startingAddress, TRUE);
}
else
{
HeavyLoop_inline(startingAddress, FALSE);
}
}
Et comment cela améliorerait-il les performances? Il ajoute seulement un appel de méthode supplémentaire, mais conserve la condition IF à l'intérieur de la boucle ... ou chaque compilateur optimise l'état?
Il va en ligne le code avec le même problème. Le "si" est toujours là toujours. N'est-ce pas?
@Pubby: Pourquoi est-ce une "terrible solution"?
+1 Cela devrait avoir l'effet souhaité tant que la fonction est réellement inlinée; Le drapeau est une constante de la compilation. L'optimiseur doit donc pouvoir supprimer le code mort. J'utiliserais probablement un paramètre de modèle, pour être sûr que le compilateur le traite comme une constante de temps de compilation (comme je l'ai fait dans ma réponse, avant de lire celui-ci).
+ Le compilateur doit pouvoir dire que l'argument est connu, il peut donc inclure ou exclure le * b + = 2 au moment de la compilation.
+1, ceux qui ne comprennent pas cela devraient probablement compiler et démonter avec une optimisation appropriée. L'inlinisation permet à l'optimiseur de prédire statiquement la branche si (secondaire) , donc dans le faux cas, il sera complètement éliminé, et dans le cas vrai, le test de la condition sera éliminé et le * B + = 2 laissé dans. Et puis, espérons-le, combiné avec le * b + = 1 .
+1 pour votre réponse détaillée. Comme c'est C ++, je vais aller avec le modèle fonctionne car il semble plus élégant que vous l'avez dit.
EDIT: Compte tenu du nouveau texte de l'OP ", le problème traite des instructions qui ne peuvent pas être pré-calculées en dehors de la boucle."
Si l'instruction ne peut pas être pré-calculée à l'extérieur de la boucle, puis par Définition Il doit être calculé à l'intérieur la boucle, et autre chose que votre code d'origine avec le chèque à l'intérieur de la boucle obtichait simplement le code. Je suppose que puisque vous posez cette question, il y a encore un autre détail que vous ne nous montrez pas. Réponse originale: Premièrement, écrivez-le de manière évidente jusqu'à ce que le profilage vous montre que c'est trop lent. Mais dans ce cas, vous pouvez calculer le terme avant:
J'ai souligné la partie dans ma question qui explique que * b + = 1 et * b + = 2 sont des exemples et non perfectifs, désolé pour toute confusion.
Vous pouvez implémenter la boucle comme modèle; L'argument de modèle est une constante de temps de compilation. L'optimisation doit donc supprimer le code indésirable lorsqu'il est faux. Vous avez alors besoin d'une enveloppe pour permettre que la bonne spécialisation soit appelée sur la base d'une valeur d'exécution: pendant la compilation, les deux versions du modèle seront instanciées (une contenant * B + = 2; et un non plus, et non plus de test d'exécution sur l'argument); Ils doivent ensuite être inlinés dans la fonction wrapper pour générer exactement le même code que votre deuxième exemple - mais sans la nécessité de dupliquer un code source.
Cela semble intéressant, je suis inconnu avec des fonctions de modèle en C ++. Je ne suis pas sûr de ce que vous entendez par "L'argument de modèle est une constante de temps de compilation". Est-ce que le compilateur crée statiquement deux fonctions distinctes (une pour chaque valeur possible de secondaire ) ou est la fonction créée à l'exécution avant d'être appelée via heavyloop
@Rotem: Deux fonctions sont générées à l'heure de la compilation; En général, les spécialisations de modèles sont toujours générées lors de la compilation si elles sont nécessaires.
Oh je vois, alors n'avais-tu pas appelé HeavyLoop
@Rotem: C'est vrai. Une spécialisation de modèle n'est instanciée que si elle est nécessaire, ou si vous l'instanciez explicitement (c'est-à-dire un modèle VIDHOPHOOP
@MikeSeseymour Regardez maintenant ce que vous avez fait: Stackoverflow.com/Questtions/19221646/...
EDIT: strong> Pour mieux cibler ce que l'OP souhaitée et retirez toujours le CRUFT, ce message a été complètement édité. Bien sûr, je suppose que vous avez profilé ceci et cela a été montré Être un point chaud ... Droite? P> En fait, je parie que vous ne l'avez pas fait. Et que vous sous-estimez sérieusement votre compilateur. P> Par exemple, voici votre code compilé avec LLVM: P> .lr.ph: ; preds = %0
%2 = icmp eq i32 %sm, 0
br i1 %2, label %3, label %5
+1 Pour me montrer quelque chose de cool, je ne savais pas, bien que ma question soit de savoir comment traiter des valeurs qui ne peuvent pas être prédéterminées en dehors de la boucle. Je m'excuse si cela n'était pas clair de la question.
@Rotem: J'ai complètement changé la réponse pour mieux présenter le comportement que vous recherchez (en utilisant des déclarations pures afin que le compilateur ne voit pas par les différentes opérations). Voyez comment il a simplement dupliqué le code de boucle, spécialisé soit pour sm == true (étiquette 5) ou SM == false (étiquette 3) et hosté la comparaison de la boucle :)?
C'est extrêmement intéressant et valide la réclamation faite par d'autres dans cette question. Merci de prendre le temps.
Dommage que je ne puisse pas donner plus que +1 - la seule réponse raisonnable ici. Pourquoi obscurcir le code avec des modèles pour faire quelque chose à mi-chemin du compilateur décent fera de toute façon? (Et si cela n'a pas de problèmes de performances beaucoup plus gros que cela de toute façon), le mieux que vous puissiez faire avec l'optimisation manuelle est d'éviter une branche (au moins, je ne vois vraiment pas comment aucune des réponses données avec des modèles, etc. fait quelque chose de plus que de hisser l'invariant hors de la boucle)
@Matthieu: J'ai testé cette méthode (aucune optimisation manuelle) vs. La fonction de modèle Mike suggérée. La fonction de test prend 5 paramètres booléens. Lorsque tous les paramètres sont transmis comme true, ou en d'autres termes, lorsqu'aucune branche de code ne doit être jetée, il n'y a aucune différence de performance. Cependant, quand ils sont tous faux, je reçois une différence de 35% de performance. Il est absolument possible que je ne puisse tout simplement pas mettre en place du commutateur compilateur correctement en raison du manque d'expérience.
@Rotem: il est possible que s'il existe de nombreux commutateurs différents, le compilateur ne saura pas tous les invariants hors de la boucle. Dans ce cas, vous pouvez essayer d'utiliser la solution de modèle.
Je pense que vous devez trouver un exemple légèrement plus complexe, sinon des solutions simplistes comme Kerrek seront affichées.
Avez-vous prouvé que le compilateur ne fait pas cette optimisation elle-même? Les invariants de levage hors des boucles ont été une optimisation standard pendant une longue période et est facile à mettre en œuvre pour démarrer.
"Si c'était une langue comme Python, je pouvais simplement créer de manière dynamique une fonction pour gérer la boucle" - bien que la surcharge d'un appel via un pointeur de fonction soit presque certainement supérieure à la surcharge du
si si Je doute vivement que vous obtenez des performances de cette façon. Mais peut-être que je sous-estime CPPHON, est-il capable d'inliquer un appel de fonction après cette fonction a été définie localement avec une capture variable et l'optimise en fonction de la valeur de la variable?Assurez-vous également de ne pas optimiser que si la boucle en question est vraiment le goulot d'étranglement de la performance de votre application (voir optimisation prématurée, par exemple ici: C2.com/cgi/wiki?prematureOptimisation )
Dans vos cas réels, effectuez la modification Ajoutez principalement des énoncés supplémentaires sur le corps de la boucle ou déclenchent-ils des corps boutiques complètement alternatifs?
@delnan: Même sans hisser hors de la boucle, la prédiction de la branche dynamique de la CPU devrait faire assez bien avec cela. Donc, bien que j'accepte que c'est inutile de faire cette optimisation si le compilateur le fait, méfiez-vous qu'il pourrait bien être inutile de faire cette optimisation même si le compilateur ne le fait pas.
Si ce n'est pas votre cas réel, est-ce au moins représentatif du cas actuel? C'est-à-dire que la quantité d'incrément constante lors de chaque invocation de fonction ou avez-vous besoin d'un moyen de rechercher le montant de l'incrément au cours de chaque cycle de la boucle? Ne pas trop simplifier la question à laquelle il perd son point principal!
@Steve: CPPHON ne le fera pas, c'est un interprète de décharge. Pypy d'autre part a un compilateur JIT Tracing. Supprimer des sauts conditionnels et des appels d'inlinage est le moins les jits de traçage. Et la façon dont il est construit, cela ne se soucie pas du moindre bit si le code a été écrit à la main ou créé de manière dynamique. Il y a Motion de code invariant de boucle aussi, donc il devrait donc Hauteur tout
gardien qui pourrait rester hors de la boucle, quel que soit l'endroit où la variable vient.@ degetl0r - Je suis d'accord, aurait dû trouver un meilleur exemple. J'ai gras la partie de ma question à ce sujet.
@Delnan - non, je n'ai pas, je n'étais pas au courant que le compilateur puisse le faire, je vais le profiler.
@Steve - Je voulais créer de manière dynamique la fonction entière, y compris la boucle, pas seulement la partie à l'intérieur de la boucle.
@Frerich - Oui, ils ajoutent des déclarations supplémentaires.
@Kerreksb - Je voulais principalement savoir comment se débarrasser de
inutile si chèques dans des boucles longues, je pense que ce problème ne s'appuie pas fortement sur les déclarations réelles, n'est-ce pas?ROTEM: Voir le commentaire à ma réponse - il n'est tout simplement pas clair de votre question quelle est la situation la plus générale que vous devez aborder. S'il s'agit de travailler une valeur d'incrément à partir d'un ensemble de conditions, ma réponse devrait s'appliquer; Sinon, alors vous aurez besoin Quelques sorte d'expédition de ramification.
@Kerrek Si la valeur pourrait être déduite en dehors de la boucle, ce serait un non-question. Dans mon cas actuellement en cours, une option passe les valeurs via une table d'approvisionnement, une option multiplie le résultat par une matrice et une option zérose que certaines sur les valeurs, mais je ne comprends vraiment pas pourquoi cela compte si c'est une donnée si c'est un que la valeur ne peut pas être calculée en dehors de la boucle.
@Rotem: Donc, la question de savoir comment optimiser
pour (byte * b ...) {if (condition) {foo (* b); } else {bar (* b); } ?@Kerrek je suppose que cela pourrait être formulé de cette façon, bien que j'essayais d'éviter d'appeler d'autres fonctions de la boucle. Mais peut-être que cela aurait été plus facile à comprendre.
Utilisez votre deuxième option ci-dessus si la performance est un problème; Sinon, utilisez le premier. Il existe d'autres solutions qui sont plus "élégantes" et peut-être quelques lignes plus courtes, mais elles obscurcissent la logique du programme et la logique masquée est l'appât bogue.