J'ai besoin de la manière la plus efficace (dans les cycles du processeur) pour déterminer si deux chiffres ont le même signe / différent. Mais la capture est si l'un des chiffres est nul, j'ai besoin de pouvoir le distinguer des nombres avec des signes identiques / différents (c'est-à-dire zéro est traité comme un "troisième" signe fort>). Le code suivant est similaire à ce dont j'ai besoin, mais les valeurs de retour peuvent être n'importe quoi tant qu'il n'y a que trois valeurs de retour distinctes. return y? (((x^y) >= 0)? 1 : -1) : 0;
8 Réponses :
Votre exemple ne fonctionne pas car vous n'avez pas mis par la parenthèse autour (x ^ y)
Ceci fonctionne: P>
return y ? ((x^y) | 1) : 0;
Les parenthèses de votre code ne sont pas assorties. En outre, le code ne semble pas renvoyer le résultat correct pour x == 0.
OP a dit que X n'était pas égal à 0, et mes parenthèses sont assorties
Avec la seconde, vous obtenez une valeur négative si le panneau est différent et une valeur positive si elle est identique, mais la valeur elle-même peut changer; J'ai proposé cela depuis que je ne sais pas vraiment connaître l'utilisation
Je n'ai pas nécessairement besoin de valeurs de retour de -1,0,1 tout cela est bien tant qu'il n'y a que trois valeurs de retour distinctes.
"Un ensemble d'opérations de bits qui retourneraient 11111111, 0 ou 1 serait compliqué et certainement plus lent que le code ci-dessus." C'est tellement pas vrai. Voir la solution de Thelnonward. Un saut mal prédit est plus cher qu'une charge de bateau de bits, donc je prendrai la version sans succursale tous les jours. (En supposant que nous parlons d'optimisation du cycle)
Mon intuition me dirait que la solution de dessinée est plus lente que la mienne (et Jukka Suomela's One a l'air plus rapide), mais je conviens que la meilleure chose à faire est d'essayer toutes les réponses de cette question et de les profiler
Son a 8 opérations triviales (aucune division ou quoi que ce soit de tel), vous avez deux opérations et une succursale qui étallera le pipeline en cas de mauvaise émission qui, en dépendra des données, se produira plus ou moins souvent. Quoi qu'il en soit, votre fonction prend comme 2-20 cycles, ses prises 8. Donc, si plus d'un des appels sur trois provoque une mauvaise représentation, ses victoires.
Cela dépend fortement des données, si vous utilisez une distribution uniforme, la succursale n'échouera que 1 sur 13; Mais je dois reconnaître que j'avais sérieusement tort avec "Je pense que tu ne peux pas faire beaucoup plus vite"
Eh bien, ça va aller "l'autre sens" 1 en 13 fois, aucun mot sur lequel est la branche prévue. Il se peut que ce soit réellement correct 1 en 13 fois ... :) En outre, la solution de Jukka Suomela ci-dessous n'a que 6 opérations et aucune branche.
La prédiction des succursales est dynamique. Après la première branche (qui est 50/50), le processeur stocke la succursale du cache et l'utilise comme prédiction pour la prochaine fois. Deux fausses prédictions d'affilée (0,6% de chances avec une distribution uniforme) sont nécessaires pour modifier la prédiction, mais si elle se produit, les performances vont chuter pour 4 branches
Les processeurs modernes ont des prédicteurs des succursales assez sophistiqués et n'utilisent pas nécessairement le dernier résultat. Les CPU plus anciennes, ou des processeurs moins chers, pas tellement. Certaines architectures ont la prédiction initiale là-bas dans le code de l'OP (je connais le PPC), et certains utilisent toujours cela (sparcs précoces par exemple) selon Wikipedia. De toute façon, comme vous le dites, c'est dynamique, et si vous voulez des performances, la dynamique est rarement ce que vous voulez.
Que diriez-vous:
__Z3fooii: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax movl 12(%ebp), %edx popl %ebp sall $4, %eax addl %edx, %eax movl _ZZ3fooiiE4sign+544(,%eax,4), %eax ret
Il est possible que le calcul de la valeur soit plus rapide que d'utiliser la table en raison de son rechargement fréquent au cache de processeur. Dépend de la manière dont le code d'appel est organisé
@Assk: Cela peut être vrai, mais certainement quelque chose qu'il faudrait être mesuré pour être confirmé. Mais vous devez également vous remettre au fait que s'il y a un type de conditionnel (deux dans la question de l'OP), un stand de processeur va se produire et ce n'est pas rapide non plus (mais plus rapide que d'aller chercher de la mémoire principale à la mémoire cache).
J'y ai pensé, mais je crains que l'instruction de charge de l'indice de table soit encore plus coûteuse que la multiplication.
@Justin: Vous pouvez implémenter les deux et les heures (ou mieux les profiler). De mon expérience, la détection «intuitive» des goulots d'étranglement n'est pas trop fiable.
@Justine: La multiplication par les constantes est généralement compilée pour déplacer et ajouter et donc très vite. De plus, vous pouvez redéclaré le tableau de signalisation en tant que signe [13] [16], ce qui signifie que seul << 4 est nécessaire pour calculer l'index.
Vous pouvez faire quelque chose comme ça (seulement avec des noms de variables appropriés et fait beaucoup moins laid!) Notez que cette ne fonctionne que avec des numéros de compliment 2s et si vos valeurs sont limitées à -6 à 6 comme dans vos questions. I>
Profilez-le pour vous assurer que c'est plus rapide que la façon de faire et seulement Écrivez un code comme celui-ci une fois que vous avez déterminé que vous ne pouvez pas répondre à vos exigences en utilisant une approche beaucoup plus évidente. Avec prédiction de branche, etc., les branches ne sont pas toujours ralentissées sur X86 par exemple. Je n'écrirais jamais de code peu insodérable comme celui-ci à moins que je n'ai eu aucun choix à satisfaire aux exigences de performance. P>
extraire essentiellement les bits de signe et exclusifs pour obtenir le résultat que vous souhaitez. P>
test ecx, ecx
je SHORT $LN1@foo
test edx, edx
je SHORT $LN1@foo
; Line 12
xor ecx, edx
mov eax, 1
sar ecx, 4
and ecx, 1
add ecx, ecx
sub eax, ecx
; Line 13
ret 0
$LN1@foo:
; Line 5
xor eax, eax
; Line 13
ret 0
OP a dit x ne peut pas être 0, vous pouvez donc laisser tomber ce chèque.
Bien son premier paragraphe et l'exemple semblaient contredire que. Si ce n'est pas possible, alors oui
EDIT:
-((x&y)<0) // -1 or 0 ((-x&-y)<0) // 1 or 0 -((x&y)<0) | ((-x&-y)<0)
Excellent bit-filedling, +1. Le milieu est mon préféré, bien que je sois le sentiment qu'il devrait être possible de raser une autre opération de celle-ci .. Je ne peux tout simplement pas mettre mon doigt dessus.
Voici une autre version (avec des tours de manipulation de bits laids non portables): Certaines explications: suppose le complément de deux de deux arithmétiques et suppose que >> se déplace avec une extension de signe.
(x ^ y) >> 4) est -1 si l'un des x et y est négatif, sinon il est 0.
(x ^ (- y)) >> 4) est -1 si exactement l'un des x et -y est négatif, sinon il est 0.
+1, très élégant. est >> 4 moins cher que >> 31 dans n'importe quelle situation, ou pourquoi >> 4? (Sauf que nous pouvons l'utiliser, étant donné les gammes de valeur)
Comment est-il non portable au fait? Sauf pour nécessiter des changements signés et des deux twos compléter l'arithmétique?
Je mets >> 4 sur le mien parce que c'était tout ce qui était nécessaire à la question et n'avait besoin d'aucune hypothèse sur la taille de l'INT sur cette plate-forme.
@roe: le changement de bit par n'importe quel montant prend le même nombre de cycles d'horloge sur X86; J'imagine que c'est la même chose sur la plupart des autres transformateurs populaires aussi
@Martin - Pour chaque compilateur C ou C ++ que j'ai jamais utilisé, le changement de zéro à droite-zéro si vous changez de type non signé , mais remplit le signe d'un signé Type. Je ne suis pas sûr à 100% qui est mandaté par les normes, mais je serais surpris si ce n'est pas le cas. C'est-à-dire que les déplacements C sont des changements arithmétiques, mais un décalage arithmétique sur un type non signé (où il n'y a pas de piqué de signalisation à copier) équivaut à un décalage logique. Java inventé >>> Parce que Java n'a pas de types d'entiers non signés. Mauvaise solution imo - Je ne me souviens jamais qui est censé être le décalage logique plutôt que arithmétique.
@Blueraja - C'est certainement vrai pour les copeaux de bureau actuels, mais des serveurs de barils nécessitant une ou plusieurs horloges par bits sont moins chers en silicium. Ils ont été utilisés beaucoup dans Ye Olden Days, et je ne serais pas surpris de les trouver sur Vraiment Minimal processeurs intégrés, etc., etc. MAINTENANT.
@Steve, @martin: la norme C ++ laisse la mise en œuvre du comportement définie si la valeur est signée et négative, mais nécessite des zéros pour des valeurs non négatives signées. Donc, en C ++ au moins, l'extension du signe est toujours une possibilité.
Pour exprimer le signe du numéro x code> sous forme d'entier "normalisé" (IE -1, 0, +1) Utilisez inline int compare_sign(int x, int y) {
return sign(x) * sign(y);
}
Ne pouvons-nous pas dériver le signe de deux entiers avec (x> y) - (x
Un mélange de solutions par Andreyt et Loki Astari: sans succursale, compact, efficace (deux recherches de tableau 1D, une multiplie): Alternativement, une approche moins compacte plus efficace (une multiplie , une figure 1D Array): p> static int S[73]= {
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
0,
+1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1,
+1, +1, +1, +1, +1, +1 }, * Sign= &S[36];
return Sign[x * y];
Si la contrainte [-6 .. + 6] ne contient pas (ni x! = 0), une solution sans succursale est donnée par (5 ops): et une solution Cela fonctionne pour la gamme complète d'entier est (9 ops):
N'est-ce pas l'un des exemples qui sont utilisés pour "Supercompilation"? IIRC, c'est très différent sur différents processeurs, et la raison pour laquelle c'est un exemple courant est que le code résultant de I86 est assez surprenant.