J'ai vu un tweet récemment qui m'a confondu (ceci a été posté par un codeur Xna, dans le contexte de la rédaction d'un jeu XNA):
Post de Shawn Hargreaves disant beaucoup la même chose . Je me demandais combien de vérité il y avait dans cela, car il y a beaucoup de calculs dans mon jeu.
Je me suis demandé, dans l'espoir d'un échantillon, mais l'affiche originale n'était pas incapable d'en donner une. Il a cependant dit que ceci:
Alors, je suis curieux ...
Quelqu'un peut-il donner un exemple de code où vous pouvez modifier une division en multiplication et obtenir un gain de performance, où le compilateur C # n'a pas pu faire la même chose elle-même.
5 Réponses :
donner des chiffres, sur ce PDF
Je ne demande pas la différence de vitesse des opérations réelles sur la CPU, mais plutôt la différence d'écriture C # et pourquoi le compilateur ne serait pas en mesure d'optimiser cela.
@Dantup vous voulez dire qu'il devrait multiplier x 0,5 au lieu de diviser par 2? Ou (encore mieux) qu'il devrait changer de 1 si c'est un entier?
@Xanatos Je demande dans quelles circonstances le compilateur pas est capable d'optimiser quelque chose que je pouvais facilement optimiser. Devrais-je changer tout mon "/ 2" à "* 0.5"? Si j'ai VARA * VARB Devrais-je le changer en division? etc.
@Dantup Si vous considérez les effets secondaires, alors il ne peut probablement pas. Par exemple, avec des points flottants, je ne suis pas sûr / 5 et * 0.2 sont la même chose. 0.2 ne peut pas être représenté par des points flottants (c'est périodique dans la base 2), vous avez donc déplacé l'erreur de "avant votre opération" à "après votre opération". Est-ce que 100000000000000/5 est identique à 10000000000 * 0,2 (où 0,2 est vraiment 1,999999999999999999 ...)?
@Xanatos C'est exactement l'une des choses que je pensais. Si le changement pourrait entraîner différentes valeurs, le compilateur ne sera bien sûr pas capable de le changer. Cela expliquerait une optimisation que vous pourriez faire «à la main», mais le tweet original semblait vous suggérer que vous pouvez apporter des modifications sans effets secondaires, mais un coup de pouce en performance. Y a-t-il une possibilité de cela?
Tandis que / 5 et * 0,2 peut être différent, du point de vue du programmeur, dans de nombreuses situations du monde réel, soit suffisante. Dans ma candidature, je serais heureux que le compilateur fasse cela, mais je peux voir des scénarios où il ne serait pas bon de permettre.
J'ai mis à jour ma question pour être un peu moins vague sur ce que j'étais après: Quelqu'un peut-il donner un exemple de code où vous pouvez modifier une division en multiplication et obtenir un gain de performance, où le compilateur C # n'a pas pu faire le même chose elle-même.
Il convient de souligner que la ressource que vous avez liée est de 1993 . Ces jours-ci, les différences ne sont même pas à distance que "grand" que votre réponse implique.
Ils sont numéro pour le "Pentium", probablement "original Pentium" :-)
Multipliez toujours de manière significative moins de cycles d'horloge (beaucoup plus rapides) que de diviser sur des processeurs modernes tels que Sandybridge, Ivybridge, etc. voir: Stackoverflow.com/questions/4125033/... et Stackoverflow.com/Questtions/12333638/... et autres liens plus actuels .
La plupart des compilateurs peuvent faire un travail raisonnable d'optimisation lorsque vous leur donnez une chance. Par exemple, si vous divisez par une constante , il est probable que le compilateur peut / optimisera que cela a donc fait aussi rapidement que tout ce que vous pouvez en substituer raisonnablement. Quand Cependant, vous avez deux valeurs qui ne sont pas connues à l'avance et vous devez diviser l'un à l'autre pour obtenir la réponse, s'il y avait beaucoup de place pour le compilateur de faire beaucoup avec ça, et pour Peu importe, s'il y avait beaucoup de place pour le compilateur pour l'optimiser beaucoup, le processeur le ferait pour que le compilateur ne soit pas obligé. Edit: votre meilleur choix pour quelque chose comme ça (c'est raisonnablement réaliste ) serait probablement quelque chose comme: Ceci est relativement facile à convertir à quelque chose comme: je peux ' t garantissent vraiment beaucoup d'une manière ou d'une autre sur un compilateur particulier qui le faisait. Il s'agit essentiellement d'une combinaison de réduction de la force et de levage de boucle. Il existe certainement des optimiseurs qui savent comment faire les deux, mais ce que j'ai vu du compilateur C # suggère que ce n'est peut-être pas (mais je n'ai jamais rien testé exactement comme celui-ci, et les tests que j'ai fait étaient quelques versions ...)
@Dantup - Danny Tuppeny: réorganiser un algorithme entier au travail inversé est au-delà des compilateurs les plus sophistiqués.
@ Jerry qui a du sens, bien que je ne pense pas que l'intention du tweet était de le faire (j'appellerais cela optimisant l'algorithme plus que «changeant des divisions en multiplications»). J'ai mis à jour ma question pour être un peu moins vague sur ce que j'étais après: Quelqu'un peut-il donner un exemple de code où vous pouvez modifier une division en multiplication et obtenir un gain de performance, où le compilateur C # n'a pas pu faire le même chose elle-même.
@Jerry: cette transformation produirait-elle le même résultat? J'ai un sentiment de point flottant arithmétique le fassera quelque part ... Bien sûr, la petite différence ne comportera probablement pas la plupart du temps, mais je ne pense pas que cela va bien pour un compilateur de faire cela.
@Martinho Fernandes: Je n'ai pas lu cette partie de la spécification C # assez récemment pour pouvoir dire à coup sûr. Je l'ai suggéré spécifiquement parce que je ne m'attendrais pas vraiment à ce que la plupart des compilateurs le fassent, mais dans de nombreux cas (par exemple, des graphiques), le résultat irait bien et la transformation est facile.
@Jerry L'échantillon semble assez simple, mais je peux voir quelques raisons pour lesquelles le compilateur ne pourrait pas le changer. Je ne l'ai pas testé (non pas compris comment obtenir CS courir sur mon iPad ...) Mais je suppose que c'est le long des mêmes lignes que le tweeter original allait :-)
Bien que le compilateur puisse optimiser des divisions et des multiplications par des pouvoirs de 2, d'autres numéros peuvent être difficiles ou impossibles à optimiser. Essayez d'optimiser une division 17 et vous verrez pourquoi. Ceci est bien sûr supposant que le compilateur ne sait pas que vous divisez 17 à l'avance (il s'agit d'une variable de temps d'exécution, pas une constante).
+1 pour le simple "difficile ou impossible optimiser ... pas une constante". Il peut en fait optimiser une division bonne mais plus (entière) que celle-là. Voir Stackoverflow.com/questions/171301/... - pas que ce soit nécessairement.
peu tard mais peu importe.
La réponse à votre question est oui.
Regardez mon article ici, http://www.codeproject.com/ KB / CS / UNIQUESTRINGINGLIST2.ASPX , qui utilise des informations basées sur l'article mentionné dans le premier commentaire à votre question.
J'ai une structure QuickDivideInfo qui stocke le nombre magique et le décalage d'un diviseur donné permettant ainsi de calculer la division et le modulo à utiliser une multiplication plus rapide. J'ai pré-calculé (et testé!) QuickDivideinfos pour une liste de nombres premiers d'or. Pour X64 au moins, la méthode .Divide sur QuickDivideInfo est inline et est 3 fois plus rapide que l'utilisation de l'opérateur de division (sur un I5); Cela fonctionne pour tous les numérateurs sauf ind.minvalue et ne peut pas déborder car la multiplication est stockée dans 64 bits avant de changer. (Je n'ai pas essayé sur x86, mais si cela n'a pas été conforme à certaines raisons, la méthode de la méthode de la division serait perdue et vous auriez à l'affiner manuellement).
de sorte que ce qui précède fonctionnera dans tous les scénarios (sauf int.minvalue) si vous pouvez précalculer. Si vous faites confiance au code qui génère le nombre / décalage magique, vous pouvez traiter n'importe quel diviseur à l'exécution.
D'autres petits diviseurs bien connus avec une gamme très limité de numérateurs pourraient être écrits en ligne et pourraient bien être plus rapides s'ils n'ont pas besoin d'un long intermédiaire.
division par multiple de deux: je m'attendrais à ce que le compilateur traite de cet exemple (comme dans votre largeur / 2), car il est constant. Si cela ne change pas alors en largeur >> 1 devrait être bien
while(start<=end)
{
int mid=(start+end)/2;
if(mid==A/mid)
return mid;
if(mid<A/mid)
{
start=mid+1;
ans=mid;
}
else
end=mid-1;
}
Qu'entendez-vous par «Le résultat est la limite de temps dépassée»? Voulez-vous dire une boucle infinie ou voulez-vous dire que c'est trop lent que prévu?
Il prend plus de temps pour calculer que le cas décrit par l'utilisation de la division @taégyung
Connexes: Optimiser les divisions entier avec Multiply Shift dans C # trouvé dans CED-Est < un href = "http://stackoverflow.com/questions/171301/whats-the-fastest-way-a-divide-an-integer-by-3"> Quel est le moyen le plus rapide de diviser un entier par 3? ) - montre comment les divisions peuvent être réduites, par exemple comme optimisation du compilateur. Utilise le fait de constantes qui concerne le meilleur Le compilateur peut faire tout en garantissant la sémantique des programmeurs. Dès que la division n'est pas une constante sur le meilleur compilateur (s) peut faire, c'est juste "l'exécuter comme c'est".
@pst truc intéressant - merci!