Langue C
  1. Langue C
  3. Meilleur assemblage ou compilation pour un minimum de trois valeurs
Intereting Posts
Modèle de bits inversé en C Méta Programmation Macro dormir sur un événement c char * question Comment passer un tableau en référence à une fonction? Existe-t-il une alternative à l’utilisation du temps pour générer une génération de nombres aléatoires? Promotions de type de données lors d’opérations arithmétiques: -1 <(unsinged int) 1 == false Comstackr un programme C avec libpng sur Mac OS X Pourquoi TH32CS_SNAPMODULE32 ne fonctionne-t-il pas seul? Comment convertiriez-vous les caractères alpha en chaîne n en majuscule en C? Stocker une chaîne dans un tableau en c Quel est le type équivalent en C pour REAL (KIND = real_normal) en Fortran? L’exécution du programme commence-t-elle toujours à partir de main en C? Existe-t-il une version standard de strumPy? Quel est le codage par défaut pour les chaînes C?

Meilleur assemblage ou compilation pour un minimum de trois valeurs

Je regarde le code généré par GCC-4.8 pour x86_64 et je me demande s’il existe une meilleure (plus rapide) méthode pour calculer le minimum de trois valeurs.

Voici un extrait du module collections de Python qui calcule le minimum de m , rightindex+1 et leftindex : 

  ssize_t m = n; if (m > rightindex + 1) m = rightindex + 1; if (m > leftindex) m = leftindex;

GCC génère un code dépendant des séries avec les CMOV: 

 leaq 1(%rbp), %rdx cmpq %rsi, %rdx cmovg %rsi, %rdx cmpq %rbx, %rdx cmovg %rbx, %rdx

Existe-t-il un code plus rapide pouvant tirer parti d’une exécution parallèle dans le désordre du processeur en supprimant les dépendances de données? Je me demande s’il existe des astuces connues pour calculer le minimum de valeurs multiples sans utiliser de conditionnelles ou d’instructions prédites. Je me demande également s’il existe des propriétés insortingnsèques arithmétiques saturantes qui pourraient aider dans cette situation.

EDITS:

  • Comme indiqué, le code utilise une arithmétique signée, mais une réponse arithmétique non signée serait également utile.
  • J’ai posé des questions sur un minimum de trois, mais je suis également intéressé par un minimum de n où n est petit.
  • Les avertissements de Linus sur CMOV: http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

Minimum de deux numéros non signés a solution classique: 

 ; eax = min(eax, ebx), ecx - scratch register. .min2: sub ebx, eax sbb ecx, ecx and ecx, ebx add eax, ecx

Cette approche est probablement plus rapide que la solution avec cmov, mais pour une vitesse supérieure, les instructions doivent être séparées par d’autres instructions pour une exécution en parallèle.

L’implémentation de cette méthode pour trois nombres est possible: 

 ; eax = min(eax, ebx, edx), ecx - scratch register. .min3: sub ebx, eax sbb ecx, ecx and ecx, ebx add eax, ecx sub edx, eax sbb ecx, ecx and ecx, edx add eax, ecx

Une autre tentative consiste à tester la variante avec des sauts conditionnels. Pour les processeurs modernes, cela pourrait être encore plus rapide, surtout si les sauts sont très prévisibles: 

 .min3: cmp eax, ebx jle @f mov eax, ebx @@: cmp eax, edx jle @f mov eax, edx @@:

Voici les résultats de référence pour les méthodes suggérées. Le processeur est Intel Core-i7 2600K cadencé à 4 GHz. Les unités sont en nanosecondes par boucle (plus petit est mieux). Les mesures comprennent la génération de données de test pseudo-aléatoire et le temps système supplémentaire d’appel de fonction, en plus du code min3 réel à tester. 

  gcc cmov conditional classical sequence twigs branchless pseudo-random data 2.24 6.31 2.39 fixed data 2.24 2.99 2.39

Code source de référence

functions.s: les 3 solutions évaluées: 

 //---------------------------------------------------------------------------- .text .intel_syntax noprefix //----------------------------------------------------------------------------- // uint64_t min3_a (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_a min3_a: mov rax, rcx cmp rax, rdx cmovg rax, rdx cmp rax, r8 cmovg rax, r8 retq //----------------------------------------------------------------------------- // uint64_t min3_b (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_b min3_b: mov rax, rcx cmp rax, rdx jle skip1 mov rax, rdx skip1: cmp rax, r8 jle skip2 mov rax, r8 skip2: retq //----------------------------------------------------------------------------- // uint64_t min3_c (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_c min3_c: sub rdx, rcx sbb rax, rax and rax, rdx add rcx, rax sub r8, rcx sbb rax, rax and rax, r8 add rax, rcx retq //-----------------------------------------------------------------------------

min3test.c, programme principal (mingw64 / windows): 

 #define __USE_MINGW_ANSI_STDIO 1 #include  #include  #include  uint64_t min3_a (uint64_t rcx, uint64_t rdx, uint64_t r8); uint64_t min3_b (uint64_t rcx, uint64_t rdx, uint64_t r8); uint64_t min3_c (uint64_t rcx, uint64_t rdx, uint64_t r8); //----------------------------------------------------------------------------- // // queryPerformanceCounter - similar to QueryPerformanceCounter, but returns // count directly. uint64_t queryPerformanceCounter (void) { LARGE_INTEGER int64; QueryPerformanceCounter (&int64); return int64.QuadPart; } //----------------------------------------------------------------------------- // // queryPerformanceFrequency - same as QueryPerformanceFrequency, but returns count direcly. uint64_t queryPerformanceFrequency (void) { LARGE_INTEGER int64; QueryPerformanceFrequency (&int64); return int64.QuadPart; } //---------------------------------------------------------------------------- // // lfsr64gpr - left shift galois type lfsr for 64-bit data, general purpose register implementation // static uint64_t lfsr64gpr (uint64_t data, uint64_t mask) { uint64_t carryOut = data >> 63; uint64_t maskOrZ = -carryOut; return (data << 1) ^ (maskOrZ & mask); } //--------------------------------------------------------------------------- uint64_t min3 (uint64_t a, uint64_t b, uint64_t c) { uint64_t smallest; smallest = a; if (smallest > b) smallest = b; if (smallest > c) smallest = c; return smallest; } //--------------------------------------------------------------------------- static void runtests (uint64_t pattern, uint64_t mask) { uint64_t startCount, elapsed, index, loops = 800000000; double ns; startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_a (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_b (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_c (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); } //--------------------------------------------------------------------------- int main (void) { uint64_t index, pattern, mask; uint64_t count_a = 0, count_b = 0, count_c = 0; mask = 0xBEFFFFFFFFFFFFFF; pattern = 1; // sanity check the asm functions for (index = 0; index < 1000000; index++) { uint64_t expected, result_a, result_b, result_c; uint64_t pattern1 = (pattern >> 0) & 0xFFFFF; uint64_t pattern2 = (pattern >> 20) & 0xFFFFF; uint64_t pattern3 = (pattern >> 40) & 0xFFFFF; pattern = lfsr64gpr (pattern, mask); expected = min3 (pattern1, pattern2, pattern3); result_a = min3_a (pattern1, pattern2, pattern3); result_b = min3_b (pattern1, pattern2, pattern3); result_c = min3_c (pattern1, pattern2, pattern3); if (result_a != expected) printf ("min3_a fail, %llu %llu %llu %llu %llu\n", expected, result_a, pattern1, pattern2, pattern3); if (result_b != expected) printf ("min3_b fail, %llu %llu %llu %llu %llu\n", expected, result_b, pattern1, pattern2, pattern3); if (result_c != expected) printf ("min3_c fail, %llu %llu %llu %llu %llu\n", expected, result_c, pattern1, pattern2, pattern3); if (expected == pattern1) count_a++; if (result_b == pattern2) count_b++; if (result_c == pattern3) count_c++; } printf ("pseudo-random dissortingbution: %llu, %llu, %llu\n", count_a, count_b, count_c); // raise our priority to increase measurement accuracy SetPriorityClass (GetCurrentProcess (), REALTIME_PRIORITY_CLASS); printf ("using pseudo-random data\n"); runtests (1, mask); printf ("using fixed data\n"); runtests (0, mask); return 0; } //---------------------------------------------------------------------------

construire la ligne de commande: 

 gcc -Wall -Wextra -O3 -omin3test.exe min3test.c functions.s

La fonction min(x,y,z) est continue, mais sa dérivée ne l’est pas. Ce dérivé a la norme 1 partout où il est défini. Il n’y a simplement aucun moyen d’exprimer cela en tant que fonction arithmétique.

L’arithmétique de saturation a ses propres discontinuités, le raisonnement précédent ne peut donc pas être utilisé dans ce cas. Cependant, le sharepoint saturation est indépendant de l’entrée. Cela implique donc que vous deviez redimensionner les entrées. À ce stade, je suis convaincu que le code résultant ne sera pas plus rapide.

Ce n’est bien sûr pas une preuve complète de la non-existence d’un code plus rapide, mais vous auriez probablement besoin d’une recherche exhaustive pour cela.