J'ai récemment écrit du code pour un projet de recherche sur lequel je travaille, où l'efficacité est très importante. J'ai envisagé de gratter certaines des méthodes régulières que je fais des choses dans et utilise plutôt des xors bitwise. Ce que je me demande, c'est si cela ferait si une différence (si j'effectue cette opération indique plusieurs millions de fois) ou si c'est la même chose après que j'utilise 03 dans g ++.
Les deux exemples qui se viennent à l'esprit: P>
J'ai eu une instance où (je travaille avec des INT purement positifs), je devais changer N à N-1 si N était impair ou n pour ( n + 1) si n était même. J'ai pensé que j'avais quelques options: p> ou p> finalement: p> Toutes les méthodes font clairement la même chose, mais mon sentiment était que le troisième serait le plus efficace. P> L'exemple suivant est sur une note plus générale. Disons que je comparais deux entiers positifs, l'un d'entre eux sera-t-il meilleur que les autres. Ou la différence ne sera-t-elle vraiment pas vraiment perceptible, même si j'effectue cette opération plusieurs millions de fois: P> if(n_1==n_2)
if(! (n_1 ^ n_2) )
if( n_1 ^ n_2) else \do work here
8 Réponses :
Je devais changer n à n-1 si n était même ou n à (n + 1) si n était impair.
Dans ce cas, quelle que soit l'efficacité,
n = n ^ 1 est mauvais .pour votre deuxième cas,
== sera tout aussi efficace (sinon plus) que l'un des autres.
En général, lorsqu'il s'agit d'optimisation, vous devriez Benchmark vous-même . Si une optimisation potentielle ne mérite pas d'analgéserie, cela ne vaut pas vraiment la peine de faire.
J'ai écrit ça tort, ma faute (corrigée). Aussi, pourquoi sera ==, soit tout autant si ce n'est plus si efficace? Cela fera-t-il simplement les mêmes opérations que j'écris et économisez des frais généraux?
CMP est une instruction Single Assembly . Si vous pensez que quelque chose impliquant de nombreuses manipulations dans les bits serait plus rapide que cette instruction unique, vous ne devriez vraiment pas essayer de faire des optimisations de bas niveau.
Un bon compilateur optimisera n% 2 mais vous pouvez toujours vérifier l'assemblage produit pour voir. Si vous voyez des divisions, commencez à l'optimiser vous-même parce que la division est à peu près aussi lente que possible.
Vous devez faire confiance à votre compilateur. GCC / ++ est le produit des années de développement et il est capable de faire des optimisations que vous envisagez probablement de faire. Et, il est probable que si vous commencez à jouer, vous altérerez ses efforts pour optimiser votre code.
Il est assez facile de vérifier, allumez simplement votre désassembleur. Jetez un coup d'œil:
FC: P>
$ cc -O3 -c f.c $ otool -tV f.o f.o: (__TEXT,__text) section _f1: 00 pushq %rbp 01 movq %rsp,%rbp 04 xorl $0x01,%edi 07 movl %edi,%eax 09 leave 0a ret 0b nopl _f1(%rax,%rax) _f2: 10 pushq %rbp 11 movq %rsp,%rbp 14 leal 0xff(%rdi),%eax 17 leal 0x01(%rdi),%edx 1a andl $0x01,%edi 1d cmovel %edx,%eax 20 leave 21 ret
F2 semble être "Soustraire 1, Ajout de 2".
Ce n'est pas seulement que le chemin d'instruction de XOR est plus court. Sur La plupart des instructions sur les bits de matériel sont plus rapides que les arithmétiques entier, de nombreux compilateurs ajouteront du code pour traiter des débordements entier, etc. lors de l'ajout ou de la soustraction.
Quel matériel a des instructions binaire plus rapides que les arithmétiques entier? Au bras, au moins, ils sont tous identiques.
La grande victoire du code plus court est typique qu'elle s'intégrera mieux au cache.
À propos de la seule façon de savoir, c'est sûr de tester. Je devrais accepter que cela prendrait un compilateur assez intelligent à produire aussi efficace de la sortie pour: comme cela pourrait pour Quant à votre deuxième question, je doute que cela fait une différence - une comparaison sur l'égalité va se retrouver rapidement pour l'un de ces méthodes. Si vous voulez une vitesse, la principale chose à faire est d'éviter d'avoir une branche impliquée du tout - par exemple. Quelque chose comme: peut être écrit comme: Edit: au moins les compilateurs que j'ai à portée de main (GCC & MSVC), ne génèrent pas de Edit2: Etant donné que Potatoswatter a soulevé une autre possibilité à l'aide de bit-sage et au lieu de multiplication, j'ai décidé de tester cela avec les autres. Voici le code avec celui ajouté: maintenant la partie vraiment intéressante: les résultats de la troisième version sont assez intéressants. Pour MS VC ++, nous obtenons à peu près ce que la plupart d'entre nous attendraient probablement: à l'aide du Dans ce cas, le code à l'aide de Le mauvais résultat avec la troisième version du code compilé avec GCC nous ramène à ce que j'ai dit commencement avec [et finit cette modification]: Comme je l'ai dit de commencer, "le seul moyen de savoir à coup sûr est de tester" - mais du moins dans ce test limité, la multiplication bat toujours le [RÉRENTION DE EDIT2:] Le résultat avec GCC en utilisant n ^ = 1; , Mais je n'ai rien vérifié assez récemment pour dire avec une certitude. c + = d * (a == b); . En regardant la langue d'assemblage, la seconde se ressemblait souvent un peu désordonnée (avec la laid de croft pour obtenir le résultat de la comparaison des drapeaux dans un registre normal) mais toujours mieux performer en évitant les branches. cmov pour le si , mais ils génèrent un sete Pour le * (A == b) . J'ai élargi le code à quelque chose de testable. et au lieu du * , donne une amélioration définie - presque autant d'une amélioration que * donne sur si . Avec GCC, le résultat est tout à fait différent de: si est beaucoup plus proche de la vitesse du code Utilisation de * , mais le code à l'aide de & est plus lent que l'un des lot plus lent! Au cas où quelqu'un se soucie, j'ai trouvé cela suffisamment surprenant que je compilisais à plusieurs reprises avec des drapeaux différents, reproduisez quelques fois à chacun, et ainsi de suite et que le résultat était tout à fait cohérent - le code utilisant & était toujours considérablement plus lent. si . Il peut y avoir certains combinaison de compilateur, drapeaux de compilateur, processeur, modèle de données, comptage d'itération, etc., qui favorise le si sur la multiplication - il n'y a aucune doute que le La différence est suffisamment petite qu'un test qui passe dans l'autre direction est entièrement crédible. Néanmoins, je crois que c'est une technique qui mérite de savoir; Pour les compilateurs et les processeurs traditionnels, il semble raisonnablement efficace (bien que ce soit certainement plus utile avec MSVC qu'avec GCC). & démontre le degré auquel 1) des micro-optimisations peuvent être / sont spécifiques au compilateur, et 2) combien de résultats de la vie réelle différentes peuvent provenir d'attentes.
CMOV est idéal pour le compilateur d'optimiser ce genre de choses. L'assemblage généré serait probablement en ajoutant C et D, suivi d'un mouvement conditionnel en C si la condition est vraie. Peut-être même plus vite sur les processeurs modernes (s'ils peuvent par élargir l'ajout et la comparaison) que la version multipliée à base de drapeau (qui est strictement série et utilise mul ).
Outre CMOV , des branches prévisibles sont plus rapides que la multiplication. Multiplier par un booléen est le genre de chose à tester sur des données du monde réel après la fin de tout le reste et vous n'avez absolument rien de mieux à faire.
Oh, aussi, en fonction de la latence de MULT, C + = D & - (A == B); pourrait être plus rapide.
@Potatoswatter: C'est probablement le plus rapide, aussi longtemps que vous pouvez vivre avec un code légèrement non portable (principalement théorique - cela ne fonctionnera tout simplement pas sur le complément 1S ou le matériel de signer / de magnitude, qui sont tous deux assez rares, au moins pour les entiers).
C + = D & -Signé (A == b); Mais je suis en train de rester avec "la branche est probablement prévisible et donc libre".
@Potatoswatter: Vous pouvez vous en tenir à cela si vous le souhaitez, mais si vous regardez le code de test ci-dessus, vous verrez la preuve que c'est faux. Avec la distribution non signée, le code doit fonctionner même sur un complément ou un matériel de signer / de magnitude, mais peut ne pas donner un véritable avantage (mais comme je l'ai dit auparavant, un tel matériel est assez rare que peu de personnes ont une raison de prendre en charge).
Votre code ne prouve rien sur le code de l'OP. Comme je l'ai dit, "des branches prévisibles sont plus rapides que la multiplication" et "test sur les données du monde réel", car c'est le seul moyen de savoir si les branches sont prédites bien ou non. Lorsque je suis présenté avec une branche problématique, j'essaie d'améliorer la prévisibilité plutôt que de trouver une substitution algébrique. Les succursales correctement prédits sont gratuites, comme dans les cycles zéro sur la plupart des machines.
@Potatoswatter: faire une longue histoire courte, vous n'êtes tout simplement pas mal. Voir (par exemple) Intel.com/assets/pdf/manual/248966.pdf , §3.4.1.1 et AMD.com/ US-EN / ACTIFS / CONTENU_TYPE / WHITE_PAPERS_AND_TECH_DOCS / ... , §6.3. Oh, mais attendez: ceux-ci ne sont écrits que par Intel et AMD. Évidemment Vous En savoir plus sur la façon dont les processeurs fonctionnent que jamais!
HMM, "3.4.1.1 Élimination des succursales L'élimination des succursales améliore les performances car: • Il réduit la possibilité de maltraites. • Il réduit le nombre d'entrées de tampon cible de la branche requises (BTB). Des branches conditionnelles, qui ne sont jamais prises, ne consomment jamais des ressources BTB. . " "6.3 Les branches dépendent de l'optimisation des données aléatoires Évitez les branches conditionnelles qui dépendent de données aléatoires, car ces branches sont difficiles à prédire." Qu'est-ce que j'ai dit de la prédiction? Vous êtes sur un rouleau, mec. Réfuté par la première phrase des deux références que vous avez données.
@Potatoswatter: Vous avez prétendu: "... Les succursales correctement prédits sont gratuites comme libre ..." Intel dit: "... Chaque branche compte. Même des branches prédit correctement ont un effet négatif ..." Vous discutez avec moi régulièrement, Et vous perdez à chaque fois. Laissez votre intelligence gagner sur votre tête de pigée et apprendre de cela.
Pas cher que libre ne signifie pas absolument gratuit, c'est une expression. Vous avez coupé la phrase: «Même les branches prédites correctement ont un effet négatif sur la quantité de code utile livré au processeur." Tant que les instructions de branche ne sont pas suffisamment nombreuses pour affamer le processeur d'autres instructions, elles sont assez bon marché et contrairement à une multiplication, n'introduisez pas une dépendance. Ce n'est pas une connaissance obscure.
Premier argument: vous avez dit que les couts numériques produisent un comportement non défini et sont dangereux pendant que j'ai dit que le comportement n'est défini pas par C ++ mais par la spécification matérielle. Vous ne pouvez pas fournir un exemple de soutien à votre demande. Je dirais que tu avais tort sur celui-là. Deuxième argument: vous avez fait une affirmation vide que "mon code était faux" et votre méthode très spécialisée de comparaison de la FP est "droite", mais n'a encore pas fourni d'exemple ni d'une revendication de fond. Encore une fois je pense que tu as l'air stupide. Maintenant, vous prétendez qu'une chaîne de trois opérations entière comprises incl est un multim n'est moins cher qu'une branche prédite + ajouter.
@Potatoswatter: Donc, la première ligne est que vous n'admettez pas que vous n'aurez pas tort, même lorsque la norme le dit, vous n'admettez pas que vous n'êtes pas tort, même lorsque vous le prouver et que vous le prouve, et, en gros, autant que vous vous souciez, le Un simple fait que vous détenez une opinion rend "juste" peu importe les faits le prouvent autrement. Vous avez également oublié de mentionner votre prétention complètement idiote qu'une recherche binaire est vraiment un arbre binaire.
Eh bien, je suppose que quelqu'un de lire nos arguments pourrait venir à l'une des deux conclusions. Je pense que vous avez des moyens curieux d'interpréter des choses et des habitudes particulières des "erreurs de coller-coller" et de vous déclarer le Victor plutôt que de présenter un argument. De plus, je viens de courir votre test ci-dessus sur ma machine (Core2, GCC 4.2 -O3, OS X) et Additif1 est sorti de l'avant 549107 à 685495, ou 20% plus rapide. (I a fait Ajoutez un appel à Srand .) La vraie leçon ici est d'éviter une optimisation prématurée et d'essayer d'être scientifique.
est Si c'est vraiment critique pour la fonctionnalité de votre programme, il pourrait également être considéré comme un problème de portabilité: si vous testez votre compilateur et que vous êtes rapide, vous seriez probablement une surprise lorsque vous essayez sur un autre compilateur. Généralement ce n'est pas un problème pour les optimisations algébriques.
est n ^ = 1 plus rapide que si (n% 2) --n; sinon ++ n; ? Oui. Je ne m'attendrais pas à ce qu'un compilateur optimise cela. Étant donné que l'opération bitwise est tellement plus succincte, il peut être utile de vous familiariser avec Xor et peut-être ajouter un commentaire sur cette ligne de code.
x ^ y plus rapide que x == y ? Non. Faire des choses au rond-point, les voies ne sont généralement pas bonnes.
Pourquoi vérifierait-il que l'égalité soit plus rapide que x ^ y? Afin de vérifier l'égalité, vous devez faire une X0R. Il n'y a absolument aucun moyen de se déplacer. Dans le code de la machine ne serait pas le moyen de le faire, être de faire une X0R, puis de vérifier si le drapeau zéro a été lancé? Contrairement à juste faire le X0R et en plaçant le résultat dans un registre, au lieu de la jeter.
@LiberalCid: En pratique, tout plus simple que la multiplication est efficacement la même vitesse, car le temps est mesuré en cycles. Le processeur passe très peu d'énergie sur l'exécution d'opérations simples par rapport à la comptabilité d'exécution d'instructions parallèles. Je n'ai jamais dit soit plus vite. Tous les ISA n'ont pas une opération XOR qui définit des drapeaux. Sur une architecture de registre affamée comme x86, le maintien d'un résultat inutile pourrait causer une autre chose à être poussée sur la pile - très mal. Aussi xor (court pour exclusif ou) est orthographié avec un OH, pas un zéro.
n ^ = 1 et n1 == n2 est probablement le meilleur que vous puissiez faire, mais vraiment, si vous êtes après une efficacité maximale, NE PAS EYELLOW BELLER LE CODE à la recherche de petites choses comme ça.
Je suis un peu en désaccord avec la plupart des réponses ici, c'est pourquoi je me vois toujours de répondre à une question de 2010: -)
XOR est pratiquement parlant l'opération la plus rapide qu'une CPU peut éventuellement faire, et la bonne partie est que tous les CPU le soutiennent. La raison en est assez facile: une porte XOR peut être créée avec seulement 4 portes NAND ou 5 ni portes - ce qui signifie qu'il est facile de créer en utilisant le tissu de votre silicium. Sans surprise, tous les CPU que je connaisse peut exécuter votre opération XOR en une tique d'une horloge (ou même moins).
Si vous devez faire une XOR sur plusieurs articles dans un tableau, les CPU X64 modernes prennent également en charge XOR sur plusieurs articles à une fois comme F.Ex. les instructions de la SIMD sur Intel.
La solution alternative que vous optez utilise le si, alors-ele. Certes, la plupart des compilateurs sont capables de comprendre cette chose facile ... mais pourquoi prendre des chances et quelle est la conséquence?
La conséquence de votre compilateur ne pas comprendre les erreurs de prévision de la branche. Une seule échec de prédiction de la branche prend facilement 17 ticks d'horloge. Si vous prenez un coup d'œil aux vitesses d'exécution des instructions du processeur, vous constaterez que les succursales sont assez mauvaises pour votre performance, en particulier lorsque vous traitez de données aléatoires.
Notez que cela signifie également que si vous construisez votre test de manière incorrecte, les données gâcheront vos mesures de performance.
Pour conclure: Pensez d'abord, puis programme, puis profil - pas l'inverse. Et utilisez XOR.
Si pour une raison quelconque, vous pensez que vous écrivez un code illisible, commencez-le! Les optimisations comme celle-ci peuvent être bien expliquées dans quelques lignes.
Bien sûr, si j'écris quelque chose comme ça, je le commente. Je suis juste curieux s'il y a un point dessus.
Avez-vous déjà exécuté votre code via un profileur? Il y a probablement des optimisations d'ordre supérieur que vous pouvez faire qui vous donnera une meilleure chance pour votre argent.
Ah - Je pense que cela dépend vraiment de la plate-forme cible. Par exemple, certains systèmes intégrés aspirent vraiment à% (un FPGA I fois écrit pour l'avoir fait). Donc, dans certains cas, vous verrez une grosse victoire avec elle, mais j'imagine que vous ne verrez pas une énorme différence sur les systèmes d'extrémité supérieure.
Vos sentiments quant à ce qui fonctionnera plus vite sont extrêmement peu fiables, en particulier si vous pensez
si (! (N_1 ^ n_2)) etsi (n_1 ^ n_1) sinon sont susceptibles de sois différent. Jouez avec des choses comme vous le souhaitez, mais testez la performance. En outre, les micro-optimisations ne sont que des micro-optimisations lorsque vous avez profilées et avez constatées que le code en question exécute souvent suffisamment pour se soucier.