performance d’entiers non signés vs signés

Y at-il un gain / perte de performance en utilisant des entiers non signés sur des entiers signés?

Si oui, cela va-t-il pour le court et le long aussi?

Division par puissances de 2 est plus rapide avec unsigned int , car il peut être optimisé en une seule instruction de décalage. Avec l’ signed int , cela nécessite généralement plus d’instructions de la machine, car la division s’achève vers zéro , mais se décale vers la droite. Exemple:

 int foo(int x, unsigned y) { x /= 8; y /= 8; return x + y; } 

Voici la partie x pertinente (division signée):

 movl 8(%ebp), %eax leal 7(%eax), %edx testl %eax, %eax cmovs %edx, %eax sarl $3, %eax 

Et voici la partie y pertinente (division non signée):

 movl 12(%ebp), %edx shrl $3, %edx 

En C ++ (et C), le dépassement d’entier signé est indéfini, tandis que le dépassement d’entier non signé est défini pour envelopper. Notez que, par exemple, dans gcc, vous pouvez utiliser le drapeau -fwrapv pour définir le dépassement signé (pour envelopper).

Un dépassement d’entier signé non défini permet au compilateur de supposer que les dépassements ne se produisent pas, ce qui peut créer des opportunités d’optimisation. Voir par exemple cet article de blog pour discussion.

Cela dépendra de la mise en œuvre exacte. Dans la plupart des cas, il n’y aura pas de différence. Si vous y tenez vraiment, vous devez essayer toutes les variantes que vous considérez et mesurer les performances.

unsigned conduit à une performance identique ou supérieure à celle signed . Quelques exemples:

  • Division par une constante qui est une puissance de 2 (voir aussi la réponse de FredOverflow )
  • Division par un nombre constant (par exemple, mon compilateur implémente la division par 13 en utilisant 2 instructions asm pour les non signés et 6 instructions pour les signés)
  • Vérifier si un nombre est pair (je ne sais pas pourquoi mon compilateur MS Visual Studio l’implémente avec 4 instructions pour les numéros signed ; gcc le fait avec 1 instruction, comme dans le cas unsigned )

short conduit généralement à une performance identique ou inférieure à celle de int (en supposant que sizeof(short) < sizeof(int) ). La dégradation des performances se produit lorsque vous affectez un résultat d'une opération arithmétique (qui est généralement int , jamais short ) à une variable de type short , qui est stockée dans le registre du processeur (qui est également de type int ). Toutes les conversions de short en int prennent du temps et sont agaçantes.

Remarque: certains DSP ont des instructions de multiplication rapides pour le type signed short ; dans ce cas précis, le short est plus rapide que l' int .

En ce qui concerne la différence entre int et long , je ne peux que deviner (je ne suis pas familier avec les architectures 64 bits). Bien sûr, si int et long ont la même taille (sur les plates-formes 32 bits), leurs performances sont également les mêmes.


Un ajout très important, signalé par plusieurs personnes:

Ce qui compte vraiment pour la plupart des applications, c’est l’empreinte mémoire et la bande passante utilisée. Vous devez utiliser les plus petits entiers nécessaires ( short , peut-être même signed/unsigned char ) pour les grands tableaux.

Cela donnera de meilleures performances, mais le gain est non linéaire (c'est-à-dire non pas d'un facteur 2 ou 4) et quelque peu imprévisible - cela dépend de la taille du cache et de la relation entre les calculs et les transferts de mémoire dans votre application.

Cela dépend à peu près du processeur spécifique.

Sur la plupart des processeurs, il existe des instructions pour l’arithmétique signée et non signée. La différence entre l’utilisation d’entiers signés et non signés se limite à celle utilisée par le compilateur.

Si l’un des deux est plus rapide, il est complètement spécifique au processeur, et la différence est probablement minime, si elle existe.

La différence de performance entre les entiers signés et non signés est en réalité plus générale que ne le suggère la réponse d’acceptation. La division d’un entier non signé par une constante quelconque peut être plus rapide que la division d’un entier signé par une constante, que la constante soit une puissance de deux ou non. Voir http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

À la fin de son poste, il inclut la section suivante:

Une question naturelle est de savoir si la même optimisation pourrait améliorer la division signée. Malheureusement, il semble que ce ne soit pas le cas pour deux raisons:

L’incrément du dividende doit devenir une augmentation de la magnitude, c’est-à-dire l’incrémentation si n> 0, la décrémentation si n <0. Cela introduit une dépense supplémentaire.

La pénalité pour un diviseur non coopératif est environ deux fois moins importante en division signée, laissant une fenêtre plus réduite pour les améliorations.

Ainsi, il semble que l’algorithme d’arrondi puisse fonctionner en division signée, mais sous-performe l’algorithme d’arrondi standard.

Bref, ne vous en faites pas avant. Mais dérange-toi après.

Si vous voulez avoir des performances, vous devez utiliser les optimisations de performances d’un compilateur qui peuvent fonctionner contre le bon sens. Une chose à retenir est que différents compilateurs peuvent comstackr le code différemment et qu’ils ont eux-mêmes différentes sortes d’optimisations. Si nous parlons d’un compilateur g++ et que nous parlons de maximiser son niveau d’optimisation en utilisant -Ofast , ou au moins un indicateur -O3 , dans mon expérience, il peut comstackr un long type en code avec des performances encore meilleures, ou même juste int .

C’est de ma propre expérience et je vous recommande d’écrire tout d’abord votre programme complet et de ne plus vous soucier de ces choses que lorsque vous aurez le code sur vos mains et que vous pourrez le comstackr avec des optimisations pour essayer les types meilleur. C’est également une bonne suggestion très générale concernant l’optimisation du code pour les performances, écrivez d’abord rapidement, essayez de comstackr avec des optimisations, ajustez les choses pour voir ce qui fonctionne le mieux. Et vous devriez également essayer d’utiliser différents compilateurs pour comstackr votre programme et choisir celui qui génère le code machine le plus performant.

Un programme de calcul d’algèbre linéaire multithread optimisé peut facilement avoir une différence de performance supérieure à 10 fois optimisée vs non optimisée. Donc, c’est important.

La sortie de l’optimiseur contredit la logique dans de nombreux cas. Par exemple, j’ai eu un cas où une différence entre a[x]+=b et a[x]=b changé le temps d’exécution du programme presque 2x. Et non, a[x]=b n’était pas le plus rapide.

Voici par exemple NVidia déclarant que pour programmer leurs GPU:

Remarque: Comme c’était déjà le cas, l’arithmétique signée devrait être préférée à l’arithmétique non signée chaque fois que possible pour un meilleur débit sur SMM. La norme du langage C impose plus de ressortingctions sur le comportement de débordement pour les mathématiques non signées, ce qui limite les possibilités d’optimisation du compilateur.

Non seulement la division par puissances de 2 est plus rapide avec le type non signé, la division par toute autre valeur est également plus rapide avec le type non signé. Si vous regardez les tables d’instructions d’Agner Fog, vous verrez que les divisions non signées ont des performances similaires ou supérieures à celles des versions signées.

Par exemple avec le AMD K7

 ╔═════════════╤══════════╤═════╤═════════╤═══════════════════════╗ ║ Instruction │ Operands │ Ops │ Latency │ Reciprocal throughput ║ ╠═════════════╪══════════╪═════╪═════════╪═══════════════════════╣ ║ DIV │ r8/m8 │ 32 │ 24 │ 23 ║ ║ DIV │ r16/m16 │ 47 │ 24 │ 23 ║ ║ DIV │ r32/m32 │ 79 │ 40 │ 40 ║ ║ IDIV │ r8 │ 41 │ 17 │ 17 ║ ║ IDIV │ r16 │ 56 │ 25 │ 25 ║ ║ IDIV │ r32 │ 88 │ 41 │ 41 ║ ║ IDIV │ m8 │ 42 │ 17 │ 17 ║ ║ IDIV │ m16 │ 57 │ 25 │ 25 ║ ║ IDIV │ m32 │ 89 │ 41 │ 41 ║ ╚═════════════╧══════════╧═════╧═════════╧═══════════════════════╝ 

La même chose s’applique à Intel Pentium

 ╔═════════════╤══════════╤══════════════╗ ║ Instruction │ Operands │ Clock cycles ║ ╠═════════════╪══════════╪══════════════╣ ║ DIV │ r8/m8 │ 17 ║ ║ DIV │ r16/m16 │ 25 ║ ║ DIV │ r32/m32 │ 41 ║ ║ IDIV │ r8/m8 │ 22 ║ ║ IDIV │ r16/m16 │ 30 ║ ║ IDIV │ r32/m32 │ 46 ║ ╚═════════════╧══════════╧══════════════╝ 

Bien sûr, ceux-ci sont assez anciens. Des architectures plus récentes avec plus de transistors pourraient combler le fossé, mais les choses de base s’appliquent: en général, vous avez besoin de plus de macro, de plus de logique, de plus de latence pour effectuer une division signée.

Traditionnellement, int est le format entier natif de la plate-forme matérielle cible. Tout autre type d’entier peut entraîner des pénalités de performance.

MODIFIER:

Les choses sont légèrement différentes sur les systèmes modernes:

  • int peut en effet être 32 bits sur les systèmes 64 bits pour des raisons de compatibilité. Je crois que cela se produit sur les systèmes Windows.

  • Les compilateurs modernes peuvent implicitement utiliser int lors des calculs pour des types plus courts dans certains cas.

IIRC, sur x86 signé / non signé ne devrait faire aucune différence. Le short / long, par contre, est une autre histoire, car la quantité de données devant être transférée vers / depuis la RAM est plus grande pour les longs (les autres raisons peuvent inclure des opérations de dissortingbution comme la prolongation ou la durée).

Entier non signé est avantageux dans la mesure où vous stockez et traitez les deux en tant que stream binary, je veux seulement dire une donnée, sans signe, donc la multiplication devient plus simple (plus rapide) avec les opérations de décalage binary

Les entiers signés et non signés fonctionneront toujours tous les deux comme des instructions à horloge unique et auront les mêmes performances en lecture-écriture, mais selon le Dr Andrei Alexandrescu, il est préférable de ne pas signer avec les signes signés. La raison en est que vous pouvez placer deux fois plus de nombres dans le même nombre de bits parce que vous ne gaspillez pas le bit de signe et que vous utiliserez moins d’instructions pour vérifier les nombres négatifs augmentant les performances de la ROM réduite. D’après mon expérience avec la machine virtuelle Kabuki , qui intègre une implémentation de scripts ultra-performante, il est rare que vous ayez réellement besoin d’un numéro signé lorsque vous travaillez avec de la mémoire. J’ai passé des années à faire de l’arithmétique de pointeur avec des numéros signés et non signés et je n’ai trouvé aucun avantage à signer quand aucun bit de signe n’est nécessaire.

On peut préférer signer quand on utilise le décalage des bits pour effectuer la multiplication et la division des puissances de 2, car vous pouvez effectuer des puissances négatives de 2 divisions avec des entiers du complément 2 signés. S’il vous plaît voir d’ autres vidéos YouTube de Andrei pour plus de techniques d’optimisation. Vous pouvez également trouver de bonnes informations dans mon article sur l’ algorithme de conversion Integer-to-Ssortingng le plus rapide au monde .