Quand l'assemblage est-il plus rapide que le C ?

Question

L'une des raisons invoquées pour connaître l'assembleur est que, à l'occasion, il peut être utilisé pour écrire du code qui sera plus performant que si l'on écrivait ce code dans un langage de plus haut niveau, le C en particulier. Cependant, j'ai aussi entendu dire à plusieurs reprises que bien que ce ne soit pas entièrement faux, les cas où l'assembleur peut en fait pour générer un code plus performant sont à la fois extrêmement rares et nécessitent une connaissance et une expérience expertes de l'assemblage.

Cette question ne prend même pas en compte le fait que les instructions de l'assembleur seront spécifiques à la machine et non portables, ou tout autre aspect de l'assembleur. Il y a beaucoup de bonnes raisons de connaître l'assembleur en plus de celle-ci, bien sûr, mais c'est censé être une question spécifique sollicitant des exemples et des données, pas un discours étendu sur l'assembleur contre les langages de plus haut niveau.

Quelqu'un peut-il fournir exemples spécifiques de cas où l'assemblage sera plus rapide qu'un code C bien écrit utilisant un compilateur moderne, et pouvez-vous soutenir cette affirmation avec des preuves de profilage ? Je suis assez sûr que ces cas existent, mais je veux vraiment savoir à quel point ces cas sont ésotériques, puisque cela semble être un point de discorde.

Answer 1

Voici un exemple concret : Les multiplications en virgule fixe sur les vieux compilateurs.

Ils ne sont pas seulement pratiques sur les appareils sans virgule flottante, ils brillent lorsqu'il s'agit de précision, car ils vous donnent 32 bits de précision avec une erreur prévisible (la virgule flottante n'a que 23 bits et il est plus difficile de prévoir la perte de précision). absolu précision sur toute la plage, au lieu d'une précision quasi uniforme. relatif précision ( float ).

---

Les compilateurs modernes optimisent bien cet exemple en virgule fixe. Pour des exemples plus modernes qui nécessitent encore du code spécifique au compilateur, voir

• Obtenir la partie haute de la multiplication des entiers 64 bits : Une version portable utilisant uint64_t pour les multiplications 32x32 => 64-bit n'est pas optimisé sur un CPU 64-bit, vous avez donc besoin d'intrinsèques ou de __int128 pour un code efficace sur les systèmes 64 bits.
• _umul128 sur Windows 32 bits : MSVC ne fait pas toujours un bon travail lors de la multiplication d'entiers 32 bits castés en 64, donc les intrinsèques ont beaucoup aidé.

---

Le C ne possède pas d'opérateur de multiplication complète (résultat de 2N bits à partir d'entrées de N bits). La façon habituelle de l'exprimer en C est de mettre les entrées dans le type le plus large et d'espérer que le compilateur reconnaisse que les bits supérieurs des entrées ne sont pas intéressants :

// on a 32-bit machine, int can hold 32-bit fixed-point integers.
int inline FixedPointMul (int a, int b)
{
  long long a_long = a; // cast to 64 bit.

  long long product = a_long * b; // perform multiplication

  return (int) (product >> 16);  // shift by the fixed point bias
}

Le problème avec ce code est que nous faisons quelque chose qui ne peut pas être directement exprimé dans le langage C. Nous voulons multiplier deux nombres de 32 bits et obtenir un résultat de 64 bits dont nous retournons le 32 bits du milieu. Cependant, en C, cette multiplication n'existe pas. Tout ce que vous pouvez faire est de promouvoir les entiers en 64 bits et de faire une multiplication 64*64 = 64.

x86 (et ARM, MIPS et autres) peut cependant effectuer la multiplication en une seule instruction. Certains compilateurs avaient l'habitude d'ignorer ce fait et de générer du code qui appelle une fonction de la bibliothèque d'exécution pour effectuer la multiplication. Le décalage par 16 est également souvent effectué par une routine de bibliothèque (le x86 peut également effectuer de tels décalages).

Nous nous retrouvons donc avec un ou deux appels à la bibliothèque, juste pour une multiplication. Cela a de graves conséquences. Non seulement le décalage est plus lent, mais les registres doivent être préservés à travers les appels de fonction et cela ne facilite pas non plus l'inlining et le code-unrolling.

Si vous réécrivez le même code en assembleur (en ligne), vous pouvez obtenir un gain de vitesse significatif.

En outre, l'utilisation de l'ASM n'est pas la meilleure façon de résoudre le problème. La plupart des compilateurs vous permettent d'utiliser certaines instructions assembleur sous forme intrinsèque si vous ne pouvez pas les exprimer en C. Le compilateur VS.NET2008 par exemple expose le mul 32*32=64 bit comme __emul et le shift 64 bit comme __ll_rshift.

En utilisant les intrinsèques, vous pouvez réécrire la fonction de manière à ce que le compilateur C ait une chance de comprendre ce qui se passe. Cela permet d'inliner le code, d'allouer des registres, d'éliminer les sous-expressions communes et de procéder à la propagation des constantes. Vous obtiendrez un énorme l'amélioration des performances par rapport au code assembleur écrit à la main de cette façon.

Pour référence : Le résultat final pour le mul à virgule fixe pour le compilateur VS.NET est :

int inline FixedPointMul (int a, int b)
{
    return (int) __ll_rshift(__emul(a,b),16);
}

La différence de performance des divisions en virgule fixe est encore plus importante. J'ai obtenu des améliorations allant jusqu'à un facteur 10 pour du code de division en virgule fixe en écrivant quelques lignes d'asm.

---

L'utilisation de Visual C++ 2013 donne le même code d'assemblage pour les deux façons.

gcc4.1 de 2007 optimise également la version C pure de manière satisfaisante. (L'explorateur de compilateur Godbolt n'a pas de versions antérieures de gcc installées, mais on peut supposer que même les versions plus anciennes de gcc pourraient faire cela sans intrinsèques).

Voir source + asm pour x86 (32-bit) et ARM sur l'explorateur compilateur Godbolt%3B%0A%7D%0A%23endif%0A%0A%0A/+Intrinsics+are+more+useful+for+extended+precision%0A++when+there+isn!'t+a+wide-enough+type.%0A++e.g.+128-bit+integer+on+compilers+without+__int128%0A+/%0A'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:32.75251522372254,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:g412,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'1',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-m32++-fomit-frame-pointer',source:1),l:'5',n:'0',o:'x86-64+gcc+4.1.2+(Editor+%231,+Compiler+%231)+C%2B%2B',t:'0')),k:34.10775747948107,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:arm710,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-mthumb+-mcpu%3Dcortex-m4',source:1),l:'5',n:'0',o:'ARM+gcc+7.2.1+(none)+(Editor+%231,+Compiler+%232)+C%2B%2B',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:33.91415144294414,l:'3',n:'0',o:'',t:'0'),(g:!((g:!((h:compiler,i:(compiler:clang30,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-xc+-O3+-m32',source:1),l:'5',n:'0',o:'x86-64+clang+3.0.0+(Editor+%231,+Compiler+%233)+C%2B%2B',t:'0')),k:33.33333333333333,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cl19_2015_u3_32,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:c%2B%2B,libs:!(),options:'-Ox',source:1),l:'5',n:'0',o:'x86+MSVC+19+2015+U3+(Editor+%231,+Compiler+%234)+C%2B%2B',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:33.33333333333333,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4) . (Malheureusement, il n'y a pas de compilateurs assez vieux pour produire du mauvais code à partir de la simple version C pure).

---

Les processeurs modernes peuvent faire des choses pour lesquelles le C n'a pas d'opérateurs. du tout comme popcnt ou le balayage des bits pour trouver le premier ou le dernier bit activé. . (POSIX a un ffs() mais sa sémantique ne correspond pas à la fonction x86 bsf / bsr . Voir https://en.wikipedia.org/wiki/Find_first_set ).

Certains compilateurs peuvent parfois reconnaître une boucle qui compte le nombre de bits activés dans un entier et la compiler en un fichier popcnt (si elle est activée au moment de la compilation), mais il est beaucoup plus fiable d'utiliser l'instruction __builtin_popcnt en GNU C, ou sur x86 si vous ne visez que du matériel avec SSE4.2 : _mm_popcnt_u32 de <immintrin.h> .

Ou en C++, assigner à un std::bitset<32> et utiliser .count() . (Il s'agit d'un cas où le langage a trouvé un moyen d'exposer de manière portative une implémentation optimisée de popcount par le biais de la bibliothèque standard, d'une manière qui compilera toujours quelque chose de correct, et qui pourra tirer parti de tout ce que la cible supporte). Voir aussi https://en.wikipedia.org/wiki/Hamming_weight#Language_support .

De même, ntohl peut être compilé en bswap (x86 32-bit byte swap for endian conversion) sur certaines implémentations de C qui l'ont.

---

Un autre domaine important pour les intrinsèques ou l'asm écrite à la main est la vectorisation manuelle avec les instructions SIMD. Les compilateurs ne sont pas mauvais avec des boucles simples comme dst[i] += src[i] * 10.0; mais se comportent souvent mal ou ne s'auto-vectorisent pas du tout lorsque les choses deviennent plus compliquées. Par exemple, il est peu probable que vous obteniez quelque chose comme Comment implémenter atoi en utilisant SIMD ? généré automatiquement par le compilateur à partir du code scalaire.

Answer 2

Il y a plusieurs années, j'apprenais à quelqu'un à programmer en C. L'exercice consistait à faire pivoter un graphique de 90 degrés. Il est revenu avec une solution qui lui a pris plusieurs minutes, principalement parce qu'il utilisait des multiplications et des divisions, etc.

Je lui ai montré comment reformuler le problème en utilisant des décalages de bits, et le temps de traitement est descendu à environ 30 secondes avec le compilateur non optimisé dont il disposait.

Je venais d'obtenir un compilateur optimisant et le même code faisait tourner le graphique en moins de 5 secondes. J'ai regardé le code assembleur que le compilateur générait, et à partir de ce que j'ai vu, j'ai décidé que mes jours d'écriture en assembleur étaient terminés.

Answer 3

À peu près chaque fois que le compilateur voit du code en virgule flottante, une version écrite à la main sera plus rapide si vous utilisez un vieux mauvais compilateur. ( Mise à jour de 2019 : Ce n'est pas vrai en général pour les compilateurs modernes. En particulier lors de la compilation pour toute autre chose que x87 ; les compilateurs ont plus de facilité avec SSE2 ou AVX pour les mathématiques scalaires, ou tout autre non-x86 avec un jeu de registres FP plat, contrairement à la pile de registres de x87).

La raison principale est que le compilateur ne peut pas effectuer d'optimisations robustes. Voir cet article de MSDN pour une discussion sur le sujet. Voici un exemple où la version assembleur est deux fois plus rapide que la version C (compilée avec VS2K5) :

#include "stdafx.h"
#include <windows.h>

float KahanSum(const float *data, int n)
{
   float sum = 0.0f, C = 0.0f, Y, T;

   for (int i = 0 ; i < n ; ++i) {
      Y = *data++ - C;
      T = sum + Y;
      C = T - sum - Y;
      sum = T;
   }

   return sum;
}

float AsmSum(const float *data, int n)
{
  float result = 0.0f;

  _asm
  {
    mov esi,data
    mov ecx,n
    fldz
    fldz
l1:
    fsubr [esi]
    add esi,4
    fld st(0)
    fadd st(0),st(2)
    fld st(0)
    fsub st(0),st(3)
    fsub st(0),st(2)
    fstp st(2)
    fstp st(2)
    loop l1
    fstp result
    fstp result
  }

  return result;
}

int main (int, char **)
{
  int count = 1000000;

  float *source = new float [count];

  for (int i = 0 ; i < count ; ++i) {
    source [i] = static_cast <float> (rand ()) / static_cast <float> (RAND_MAX);
  }

  LARGE_INTEGER start, mid, end;

  float sum1 = 0.0f, sum2 = 0.0f;

  QueryPerformanceCounter (&start);

  sum1 = KahanSum (source, count);

  QueryPerformanceCounter (&mid);

  sum2 = AsmSum (source, count);

  QueryPerformanceCounter (&end);

  cout << "  C code: " << sum1 << " in " << (mid.QuadPart - start.QuadPart) << endl;
  cout << "asm code: " << sum2 << " in " << (end.QuadPart - mid.QuadPart) << endl;

  return 0;
}

Et quelques chiffres obtenus sur mon PC avec la version par défaut de l'application. * :

  C code: 500137 in 103884668
asm code: 500137 in 52129147

Par curiosité, j'ai remplacé la boucle par un dec/jnz et cela n'a fait aucune différence dans les temps - parfois plus rapide, parfois plus lent. Je suppose que l'aspect mémoire limitée éclipse les autres optimisations. (Note de l'éditeur : il est plus probable que le goulot d'étranglement de la latence de la FP soit suffisant pour masquer le coût supplémentaire de l'optimisation de la mémoire. loop . En effectuant deux sommations de Kahan en parallèle pour les éléments pairs et impairs, et en les ajoutant à la fin, on pourrait peut-être accélérer cette opération d'un facteur 2).

Oups, j'exécutais une version légèrement différente du code et il a sorti les chiffres dans le mauvais sens (c'est-à-dire que le C était plus rapide !). Corrigé et mis à jour les résultats.

Answer 4

Sans donner d'exemple spécifique ou de preuve de profilage, vous pouvez écrire un meilleur assembleur que le compilateur lorsque vous en savez plus que le compilateur.

Dans le cas général, un compilateur C moderne en sait beaucoup plus sur la manière d'optimiser le code en question : il sait comment fonctionne le pipeline du processeur, il peut essayer de réorganiser les instructions plus rapidement qu'un humain, etc. C'est en gros la même chose qu'un ordinateur qui est aussi bon ou meilleur que le meilleur joueur humain pour les jeux de société, etc. simplement parce qu'il peut effectuer des recherches dans l'espace du problème plus rapidement que la plupart des humains. Bien que vous puissiez théoriquement être aussi performant que l'ordinateur dans un cas spécifique, vous ne pouvez certainement pas le faire à la même vitesse, ce qui le rend infaisable pour plus de quelques cas (c'est-à-dire que le compilateur vous surpassera très certainement si vous essayez d'écrire plus de quelques routines en assembleur).

D'autre part, il existe des cas où le compilateur ne dispose pas d'autant d'informations - je dirais principalement lorsqu'il travaille avec différentes formes de matériel externe, dont le compilateur n'a aucune connaissance. L'exemple principal étant probablement les pilotes de périphériques, où l'assembleur combiné à la connaissance intime du matériel en question par un humain peut donner de meilleurs résultats qu'un compilateur C ne pourrait le faire.

D'autres ont mentionné les instructions à usage spécial, ce dont je parle dans le paragraphe ci-dessus - des instructions dont le compilateur peut avoir une connaissance limitée ou nulle, ce qui permet à un humain d'écrire un code plus rapide.

Answer 5

Seulement lors de l'utilisation de certains jeux d'instructions spéciales que le compilateur ne supporte pas.

Pour maximiser la puissance de calcul d'un processeur moderne doté de plusieurs pipelines et d'un branchement prédictif, vous devez structurer le programme d'assemblage d'une manière qui le rend a) presque impossible à écrire pour un humain b) encore plus impossible à maintenir.

De même, de meilleurs algorithmes, structures de données et gestion de la mémoire vous permettront d'obtenir des performances supérieures d'au moins un ordre de grandeur à celles des micro-optimisations que vous pouvez réaliser en assembleur.