En C, pourquoi “signed int” est-il plus rapide que “unsigned int”?

En C, pourquoi ” signed int plus rapide que ” unsigned int ? Certes, je sais que cela a été demandé et répondu à plusieurs resockets sur ce site (liens ci-dessous). Cependant, la plupart des gens ont dit qu’il n’y avait pas de différence. J’ai écrit du code et trouvé accidentellement une différence de performances significative.

Pourquoi la version “non signée” de mon code serait-elle plus lente que la version “signée” (même en testant le même nombre)? (J’ai un processeur Intel x86-64).

Liens similaires

  • Comparaison plus rapide entre ints signés et non signés
  • performance des entiers non signés vs signés

Commande de compilation: gcc -Wall -Wextra -pedantic -O3 -Wl,-O3 -g0 -ggdb0 -s -fwhole-program -funroll-loops -pthread -pipe -ffunction-sections -fdata-sections -std=c11 -o ./test ./test.c && ssortingp --ssortingp-all --ssortingp-unneeded --remove-section=.note --remove-section=.comment ./test


version signed int

NOTE: Il n’y a pas de différence si je déclare explicitement signed int sur tous les nombres.

 int isprime(int num) { // Test if a signed int is prime int i; if (num % 2 == 0 || num % 3 == 0) return 0; else if (num % 5 == 0 || num % 7 == 0) return 0; else { for (i = 11; i < num; i += 2) { if (num % i == 0) { if (i != num) return 0; else return 1; } } } return 1; } 

version unsigned int

 int isunsignedprime(unsigned int num) { // Test if an unsigned int is prime unsigned int i; if (num % (unsigned int)2 == (unsigned int)0 || num % (unsigned int)3 == (unsigned int)0) return 0; else if (num % (unsigned int)5 == (unsigned int)0 || num % (unsigned int)7 == (unsigned int)0) return 0; else { for (i = (unsigned int)11; i < num; i += (unsigned int)2) { if (num % i == (unsigned int)0) { if (i != num) return 0; else return 1; } } } return 1; } 

Testez ceci dans un fichier avec le code ci-dessous:

 int main(void) { printf("%d\n", isprime(294967291)); printf("%d\n", isprime(294367293)); printf("%d\n", isprime(294967293)); printf("%d\n", isprime(294967241)); // slow printf("%d\n", isprime(294967251)); printf("%d\n", isprime(294965291)); printf("%d\n", isprime(294966291)); printf("%d\n", isprime(294963293)); printf("%d\n", isprime(294927293)); printf("%d\n", isprime(294961293)); printf("%d\n", isprime(294917293)); printf("%d\n", isprime(294167293)); printf("%d\n", isprime(294267293)); printf("%d\n", isprime(294367293)); // slow printf("%d\n", isprime(294467293)); return 0; } 

Résultats ( time ./test ):

 Signed - real 0m0.949s Unsigned - real 0m1.174s 

    Votre question est véritablement insortingguante, car la version non signée génère un code toujours plus lent de 10 à 20%. Pourtant, le code pose plusieurs problèmes:

    • Les deux fonctions renvoient 0 pour 2 , 3 , 5 et 7 , ce qui est incorrect.
    • Le test if (i != num) return 0; else return 1; if (i != num) return 0; else return 1; est complètement inutile car le corps de la boucle n’est exécuté que pour i < num . Un tel test serait utile pour les petits tests principaux, mais leur boîtier spécial n’est pas vraiment utile.
    • les versions dans la version non signée sont redondantes.
    • Le code d’parsing comparative qui produit une sortie textuelle sur le terminal n’est pas fiable, vous devez utiliser la fonction clock() pour chronométrer les fonctions gourmandes en ressources CPU sans aucune entrée / sortie.
    • l'algorithme de test principal est totalement inefficace car la boucle exécute num / 2 fois au lieu de sqrt(num) .

    Simplifions le code et exécutons des tests de performance précis:

     #include  #include  int isprime_slow(int num) { if (num % 2 == 0) return num == 2; for (int i = 3; i < num; i += 2) { if (num % i == 0) return 0; } return 1; } int unsigned_isprime_slow(unsigned int num) { if (num % 2 == 0) return num == 2; for (unsigned int i = 3; i < num; i += 2) { if (num % i == 0) return 0; } return 1; } int isprime_fast(int num) { if (num % 2 == 0) return num == 2; for (int i = 3; i * i <= num; i += 2) { if (num % i == 0) return 0; } return 1; } int unsigned_isprime_fast(unsigned int num) { if (num % 2 == 0) return num == 2; for (unsigned int i = 3; i * i <= num; i += 2) { if (num % i == 0) return 0; } return 1; } int main(void) { int a[] = { 294967291, 0, 294367293, 0, 294967293, 0, 294967241, 1, 294967251, 0, 294965291, 0, 294966291, 0, 294963293, 0, 294927293, 1, 294961293, 0, 294917293, 0, 294167293, 0, 294267293, 0, 294367293, 0, 294467293, 0, }; struct testcase { int (*fun)(); const char *name; int t; } test[] = { { isprime_slow, "isprime_slow", 0 }, { unsigned_isprime_slow, "unsigned_isprime_slow", 0 }, { isprime_fast, "isprime_fast", 0 }, { unsigned_isprime_fast, "unsigned_isprime_fast", 0 }, }; for (int n = 0; n < 4; n++) { clock_t t = clock(); for (int i = 0; i < 30; i += 2) { if (test[n].fun(a[i]) != a[i + 1]) { printf("%s(%d) != %d\n", test[n].name, a[i], a[i + 1]); } } test[n].t = clock() - t; } for (int n = 0; n < 4; n++) { printf("%21s: %4d.%03dms\n", test[n].name, test[n].t / 1000), test[n].t % 1000); } return 0; } 

    Le code compilé avec clang -O2 sous OS / X produit cette sortie:

      isprime_slow: 788.004ms unsigned_isprime_slow: 965.381ms isprime_fast: 0.065ms unsigned_isprime_fast: 0.089ms 

    Ces synchronisations sont cohérentes avec le comportement observé du PO sur un système différent, mais montrent l'amélioration spectaculaire provoquée par le test d'itération plus efficace: 10000 fois plus rapide!

    Concernant la question Pourquoi la fonction est-elle plus lente avec unsigned? , regardons le code généré ( gcc 7.2 -O2 ):

     isprime_slow(int): ... .L5: movl %edi, %eax cltd idivl %ecx testl %edx, %edx je .L1 .L4: addl $2, %ecx cmpl %esi, %ecx jne .L5 .L6: movl $1, %edx .L1: movl %edx, %eax ret unsigned_isprime_slow(unsigned int): ... .L19: xorl %edx, %edx movl %edi, %eax divl %ecx testl %edx, %edx je .L22 .L18: addl $2, %ecx cmpl %esi, %ecx jne .L19 .L20: movl $1, %eax ret ... .L22: xorl %eax, %eax ret 

    Les boucles internes sont très similaires, le même nombre d'instructions, les mêmes instructions. Voici cependant quelques explications potentielles:

    • cltd étend le signe du registre eax dans le registre edx , ce qui peut entraîner un délai d'instruction car eax est modifié par l'instruction movl %edi, %eax immédiatement précédente. Cela rendrait cependant la version signée plus lente que la version non signée, pas plus rapide.
    • les instructions initiales des boucles peuvent être mal alignées pour la version non signée, mais il est peu probable que le fait de changer l'ordre dans le code source n'ait aucun effet sur les timings.
    • Bien que le contenu du registre soit identique pour les codes d'opération de division signés et non signés, il est possible que l'instruction idivl prenne moins de cycles que l'instruction divl . En effet, la division signée opère avec moins de précision que la division non signée, mais la différence semble assez grande pour ce petit changement.
    • Je soupçonne que plus d’ idivl ont été consacrés à la mise en œuvre d’ idivl sur idivl car les divisions signées sont plus courantes que les divisions non signées (comme le montre le nombre d’années de statistiques de codage chez Intel).
    • comme l'a commenté rcgldr, en examinant les tableaux d'instructions pour les processus Intel, pour Ivy Bridge, DIV 32 bits prend 10 opérations micro, 19 à 27 cycles, IDIV 9 opérations micro, 19 à 26 cycles. Les temps de référence correspondent à ces horaires. La micro-opération supplémentaire peut être due aux opérandes plus longs de DIV (64/32 bits) par opposition à IDIV (63/31 bits).

    Ce résultat surprenant devrait nous apprendre quelques leçons:

    • l'optimisation est un art difficile, soyez humble et procrastinez.
    • l'exactitude est souvent brisée par les optimisations.
    • choisir un meilleur algorithme bat l'optimisation de loin.
    • toujours le code de référence, ne faites pas confiance à votre instinct.

    Étant donné que le dépassement d’entier signé n’est pas défini, le compilateur peut faire beaucoup d’hypothèses et d’optimisations sur du code impliquant des entiers signés. Le débordement d’entier non signé est défini comme un bouclage, afin que le compilateur ne puisse pas optimiser autant. Voir aussi http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html#signed_overflow et http://www.airs.com/blog/archives/120 .

    D’après la spécification d’instruction sur AMD / Intel, nous avons (pour K7):

     Instruction Ops Latency Throughput DIV r32/m32 32 24 23 IDIV r32 81 41 41 IDIV m32 89 41 41 

    Pour i7, la latence et le débit sont les mêmes pour IDIVL et DIVL , une légère différence existe pour les µops.

    Cela peut expliquer la différence, car les codes d’assemblage -O3 ne diffèrent que par la signature (DIVL vs IDIVL) sur ma machine.

    Test candidat alternatif wiki qui peut / peut ne pas montrer une différence de temps significative.

     #include  #include  #define J 10 #define I 5 int main(void) { clock_t c1,c2,c3; for (int j=0; j 

    Échantillon de sortie

     2761 2746 -15 2777 2777 0 2761 2745 -16 2793 2808 15 2792 2730 -62 2746 2730 -16 2746 2730 -16 2776 2793 17 2823 2808 -15 2793 2823 30