fonction itoa optimisée

Je réfléchis à la façon de mettre en œuvre la conversion d’un entier (4 octets, non signé) en chaîne avec des instructions SSE. La routine habituelle consiste à diviser le nombre et à le stocker dans une variable locale, puis à inverser la chaîne (la routine d’inversion manque dans cet exemple):

char *convert(unsigned int num, int base) { static char buff[33]; char *ptr; ptr = &buff[sizeof(buff) - 1]; *ptr = '\0'; do { *--ptr="0123456789abcdef"[num%base]; num /= base; } while(num != 0); return ptr; } 

Mais l’inversion prendra du temps supplémentaire. Existe-t-il un autre algorithme que l’on peut utiliser de préférence avec l’instruction SSE pour paralléliser la fonction?

La première étape pour optimiser votre code consiste à supprimer le support de base arbitraire. En effet, diviser par une constante est presque sûrement une multiplication, mais la division par base est une division, et parce que '0'+n est plus rapide que "0123456789abcdef"[n] (aucune mémoire impliquée dans la première).

Si vous avez besoin d’aller plus loin, vous pouvez créer des tables de recherche pour chaque octet de la base qui vous tient à coeur (par exemple, 10), puis append les résultats (par exemple, en décimal) pour chaque octet. Un péché:

 00 02 00 80 (input) 0000000000 (place3[0x00]) +0000131072 (place2[0x02]) +0000000000 (place1[0x00]) +0000000128 (place0[0x80]) ========== 0000131200 (result) 

Terje Mathisen a inventé un itoa () très rapide qui ne nécessite pas de tables de recherche. Si l’explication de son fonctionnement ne vous intéresse pas, passez à Performance ou Implémentation.

Il y a plus de 15 ans, Terje Mathisen a mis au point un itoa () parallélisé pour la base 10. L’idée est de prendre une valeur 32 bits et de la diviser en deux morceaux de 5 chiffres. (Une recherche rapide sur Google pour “Terje Mathisen itoa” a donné cet article: http://computer-programming-forum.com/46-asm/7aa4b50bce8dd985.htm )

On commence comme ça:

 void itoa(char *buf, uint32_t val) { lo = val % 100000; hi = val / 100000; itoa_half(&buf[0], hi); itoa_half(&buf[5], lo); } 

Nous pouvons maintenant avoir simplement besoin d’un algorithme capable de convertir n’importe quel entier du domaine [0, 99999] en chaîne. Une façon naïve de faire cela pourrait être:

 // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { // Move all but the first digit to the right of the decimal point. float tmp = val / 10000.0; for(size_t i = 0; i < 5; i++) { // Extract the next digit. int digit = (int) tmp; // Convert to a character. buf[i] = '0' + (char) digit; // Remove the lead digit and shift left 1 decimal place. tmp = (tmp - digit) * 10.0; } } 

Plutôt que d'utiliser une virgule flottante, nous utiliserons une mathématique en virgule fixe de 4,28 car elle est nettement plus rapide dans notre cas. C'est-à-dire que nous fixons le point binary à la 28ème position du bit, de sorte que 1.0 soit représenté par 2 ^ 28. Pour convertir en point fixe, il suffit de multiplier par 2 ^ 28. Nous pouvons facilement arrondir au nombre entier le plus proche en masquant avec 0xf0000000 et nous pouvons extraire la partie fractionnaire en masquant avec 0x0fffffff.

(Remarque: l'algorithme de Terje diffère légèrement dans le choix du format à virgule fixe.)

Alors maintenant nous avons:

 typedef uint32_t fix4_28; // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { // Convert `val` to fixed-point and divide by 10000 in a single step. // NB we would overflow a uint32_t if not for the parentheses. fix4_28 tmp = val * ((1 << 28) / 10000); for(size_t i = 0; i < 5; i++) { int digit = (int)(tmp >> 28); buf[i] = '0' + (char) digit; tmp = (tmp & 0x0fffffff) * 10; } } 

Le seul problème avec ce code est que 2 ^ 28/10000 = 26843.5456, ce qui est tronqué à 26843. Cela provoque des inexactitudes pour certaines valeurs. Par exemple, itoa_half (buf, 83492) produit la chaîne "83490". Si nous appliquons une petite correction dans notre conversion en 4.28 points fixes, alors l'algorithme fonctionne pour tous les nombres du domaine [0, 99999]:

 // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { fix4_28 const f1_10000 = (1 << 28) / 10000; // 2^28 / 10000 is 26843.5456, but 26843.75 is sufficiently close. fix4_28 tmp = val * ((f1_10000 + 1) - (val / 4); for(size_t i = 0; i < 5; i++) { int digit = (int)(tmp >> 28); buf[i] = '0' + (char) digit; tmp = (tmp & 0x0fffffff) * 10; } } 

Terje entrelace la partie itoa_half pour les moitiés basse et haute:

 void itoa(char *buf, uint32_t val) { fix4_28 const f1_10000 = (1 << 28) / 10000; fix4_28 tmplo, tmphi; lo = val % 100000; hi = val / 100000; tmplo = lo * (f1_10000 + 1) - (lo / 4); tmphi = hi * (f1_10000 + 1) - (hi / 4); for(size_t i = 0; i < 5; i++) { buf[i + 0] = '0' + (char)(tmphi >> 28); buf[i + 5] = '0' + (char)(tmplo >> 28); tmphi = (tmphi & 0x0fffffff) * 10; tmplo = (tmplo & 0x0fffffff) * 10; } } 

Il existe une astuce supplémentaire qui accélère légèrement le code si la boucle est entièrement déroulée. La multiplication par 10 est implémentée en tant que séquence LEA + SHL ou LEA + ADD. Nous pouvons enregistrer 1 instruction en la multipliant par 5, ce qui ne nécessite qu'un seul LEA. Cela a le même effet que de décaler tmphi et tmplo de 1 position à chaque passage dans la boucle, mais nous pouvons compenser en ajustant nos comptes et masques de décalage comme ceci:

 uint32_t mask = 0x0fffffff; uint32_t shift = 28; for(size_t i = 0; i < 5; i++) { buf[i + 0] = '0' + (char)(tmphi >> shift); buf[i + 5] = '0' + (char)(tmplo >> shift); tmphi = (tmphi & mask) * 5; tmplo = (tmplo & mask) * 5; mask >>= 1; shift--; } 

Cela ne sert que si la boucle est complètement déroulée, car vous pouvez précalculer la valeur de décalage et masque pour chaque itération.

Enfin, cette routine produit des résultats zéro-padded. Vous pouvez supprimer le remplissage en renvoyant un pointeur sur le premier caractère différent de 0 ou sur le dernier caractère si val == 0:

 char *itoa_unpadded(char *buf, uint32_t val) { char *p; itoa(buf, val); p = buf; // Note: will break on GCC, but you can work around it by using memcpy() to dereference p. if (*((uint64_t *) p) == 0x3030303030303030) p += 8; if (*((uint32_t *) p) == 0x30303030) p += 4; if (*((uint16_t *) p) == 0x3030) p += 2; if (*((uint8_t *) p) == 0x30) p += 1; return min(p, &buf[15]); } 

Il existe une astuce supplémentaire applicable au code 64 bits (c’est-à-dire AMD64). Les registres supplémentaires, plus larges, permettent d’accumuler chaque groupe de 5 chiffres dans un registre; Une fois que le dernier chiffre a été calculé, vous pouvez les écraser avec SHRD, OU avec 0x3030303030303030 et les stocker dans la mémoire. Cela améliore les performances pour moi d'environ 12,3%.

Vectorisation

Nous pourrions exécuter l'algorithme ci-dessus tel quel sur les unités SSE, mais les performances ne sont pratiquement pas améliorées. Toutefois, si nous scindons la valeur en morceaux plus petits, nous pouvons tirer parti des instructions de multiplication SSE4.1 32 bits. J'ai essayé trois scissions différentes:

  1. 2 groupes de 5 chiffres
  2. 3 groupes de 4 chiffres
  3. 4 groupes de 3 chiffres

La variante la plus rapide consistait en 4 groupes de 3 chiffres. Voir ci-dessous pour les résultats.

Performance

J'ai testé de nombreuses variantes de l'algorithme de Terje en plus des algorithmes proposés par Vitaut et Inge Henriksen. J'ai vérifié par des tests exhaustifs des entrées que la sortie de chaque algorithme correspond à itoa ().

Mes chiffres proviennent d'un Westmere E5640 sous Windows 7 64 bits. Je compare les performances à la priorité temps réel et suis verrouillé sur le cœur 0. J'exécute chaque algorithme 4 fois pour tout forcer dans le cache. Je passe 2 ^ 24 appels à l’aide de RDTSCP pour supprimer l’effet de tout changement dynamic de vitesse d’horloge.

J'ai chronométré 5 modèles d'entrées différents:

  1. itoa (0 .. 9) - presque meilleure performance
  2. itoa (1000 .. 1999) - sortie plus longue, pas de prédiction erronée de twig
  3. itoa (100000000 .. 999999999) - sortie la plus longue, aucune erreur de twig
  4. itoa (256 valeurs aléatoires) - longueur de sortie variable
  5. itoa (65536 valeurs aléatoires) - variation de la longueur de sortie et suppression des caches L1 / L2

Les données:

  ALG TINY MEDIUM LARGE RND256 RND64K NOTES
 NULL 7 clk 7 clk 7 clk 7 clk 7 clk Base de référence aérienne
 TERJE_C 63 clk 62 clk 63 clk 57 clk 56 clk Meilleure implémentation C de l'algorithme de Terje
 TERJE_ASM 48 clk 48 clk 50 clk 45 clk 44 clk Version naïve, AMD64 écrite à la main de l'algorithme de Terje
 TERJE_SSE 41 clk 42 clk 41 clk 34 clk 35 clk Version insortingnsèque SSE de l'algorithme de Terje avec regroupement de chiffres 1/3/3/3
 INGE_0 12 clk 31 clk 71 clk 72 clk 72 clk Premier algorithme d'Inge
 INGE_1 20 clk 23 clk 45 clk 69 clk 96 clk Le deuxième algorithme d'Inge
 INGE_2 18 clk 19 clk 32 clk 29 clk 36 clk Version améliorée du deuxième algorithme d'Inge
 VITAUT_0 9 clk 16 clk 32 clk 35 clk 35 clk l'algorithme de vitaut
 VITAUT_1 11 clk 15 clk 33 clk 31 clk 30 clk Version améliorée de l'algorithme de vitaut
 LIBC 46 clk 128 clk 329 clk 339 clk 340 clk MSVCRT12 implémentation

Mon compilateur (VS 2013 Update 4) a produit un code étonnamment mauvais; la version assemblage de l'algorithme de Terje est juste une traduction naïve, et elle est 21% plus rapide. J'ai également été surpris par les performances de la mise en œuvre SSE, que je m'attendais à ralentir. La grande surprise a été la rapidité avec laquelle INGE_2, VITAUT_0 et VITAUT_1 ont été. Bravo à vitaut pour avoir imaginé une solution portable qui optimise même mes meilleurs efforts au niveau de l'assemblage.

Remarque: INGE_1 est une version modifiée du deuxième algorithme d'Inge Henriksen car l'original comporte un bogue.

INGE_2 est basé sur le deuxième algorithme donné par Inge Henriksen. Plutôt que de stocker des pointeurs sur les chaînes précalculées dans un tableau char * [], il stocke les chaînes elles-mêmes dans un tableau char [] [5]. L'autre grande amélioration concerne la manière dont il stocke les caractères dans le tampon de sortie. Il stocke plus de caractères que nécessaire et utilise l'arithmétique de pointeur pour renvoyer un pointeur sur le premier caractère différent de zéro. Le résultat est nettement plus rapide - même avec la version optimisée pour SSE de l'algorithme de Terje. Il convient de noter que le microréglement privilégie un peu cet algorithme car, dans les applications du monde réel, le jeu de données de 600K fera sauter en permanence les caches.

VITAUT_1 est basé sur l'algorithme de vitaut avec deux petites modifications. La première modification consiste à copier les paires de caractères dans la boucle principale, ce qui réduit le nombre d'instructions de stockage. Semblable à INGE_2, VITAUT_1 copie les deux caractères finaux et utilise l'arithmétique de pointeur pour renvoyer un pointeur sur la chaîne.

la mise en oeuvre

Ici, je donne le code pour les 3 algorithmes les plus intéressants.

TERJE_ASM:

 ; char *itoa_terje_asm(char *buf, uint32_t val) ; ; *** NOTE *** ; buf *must* be 8-byte aligned or this code will break! itoa_terje_asm: MOV EAX, 0xA7C5AC47 ADD RDX, 1 IMUL RAX, RDX SHR RAX, 48 ; EAX = val / 100000 IMUL R11D, EAX, 100000 ADD EAX, 1 SUB EDX, R11D ; EDX = (val % 100000) + 1 IMUL RAX, 214748 ; RAX = (val / 100000) * 2^31 / 10000 IMUL RDX, 214748 ; RDX = (val % 100000) * 2^31 / 10000 ; Extract buf[0] & buf[5] MOV R8, RAX MOV R9, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R8, 31 ; R8 = buf[0] SHR R9, 31 ; R9 = buf[5] ; Extract buf[1] & buf[6] MOV R10, RAX MOV R11, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R10, 31 - 8 SHR R11, 31 - 8 AND R10D, 0x0000FF00 ; R10 = buf[1] << 8 AND R11D, 0x0000FF00 ; R11 = buf[6] << 8 OR R10D, R8D ; R10 = buf[0] | (buf[1] << 8) OR R11D, R9D ; R11 = buf[5] | (buf[6] << 8) ; Extract buf[2] & buf[7] MOV R8, RAX MOV R9, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R8, 31 - 16 SHR R9, 31 - 16 AND R8D, 0x00FF0000 ; R8 = buf[2] << 16 AND R9D, 0x00FF0000 ; R9 = buf[7] << 16 OR R8D, R10D ; R8 = buf[0] | (buf[1] << 8) | (buf[2] << 16) OR R9D, R11D ; R9 = buf[5] | (buf[6] << 8) | (buf[7] << 16) ; Extract buf[3], buf[4], buf[8], & buf[9] MOV R10, RAX MOV R11, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R10, 31 - 24 SHR R11, 31 - 24 AND R10D, 0xFF000000 ; R10 = buf[3] << 24 AND R11D, 0xFF000000 ; R11 = buf[7] << 24 AND RAX, 0x80000000 ; RAX = buf[4] << 31 AND RDX, 0x80000000 ; RDX = buf[9] << 31 OR R10D, R8D ; R10 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) OR R11D, R9D ; R11 = buf[5] | (buf[6] << 8) | (buf[7] << 16) | (buf[8] << 24) LEA RAX, [R10+RAX*2] ; RAX = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) | (buf[4] << 32) LEA RDX, [R11+RDX*2] ; RDX = buf[5] | (buf[6] << 8) | (buf[7] << 16) | (buf[8] << 24) | (buf[9] << 32) ; Compact the character strings SHL RAX, 24 ; RAX = (buf[0] << 24) | (buf[1] << 32) | (buf[2] << 40) | (buf[3] << 48) | (buf[4] << 56) MOV R8, 0x3030303030303030 SHRD RAX, RDX, 24 ; RAX = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) | (buf[4] << 32) | (buf[5] << 40) | (buf[6] << 48) | (buf[7] << 56) SHR RDX, 24 ; RDX = buf[8] | (buf[9] << 8) ; Store 12 characters. The last 2 will be null bytes. OR R8, RAX LEA R9, [RDX+0x3030] MOV [RCX], R8 MOV [RCX+8], R9D ; Convert RCX into a bit pointer. SHL RCX, 3 ; Scan the first 8 bytes for a non-zero character. OR EDX, 0x00000100 TEST RAX, RAX LEA R10, [RCX+64] CMOVZ RAX, RDX CMOVZ RCX, R10 ; Scan the next 4 bytes for a non-zero character. TEST EAX, EAX LEA R10, [RCX+32] CMOVZ RCX, R10 SHR RAX, CL ; NB RAX >>= (RCX % 64); this works because buf is 8-byte aligned. ; Scan the next 2 bytes for a non-zero character. TEST AX, AX LEA R10, [RCX+16] CMOVZ RCX, R10 SHR EAX, CL ; NB RAX >>= (RCX % 32) ; Convert back to byte pointer. NB this works because the AMD64 virtual address space is 48-bit. SAR RCX, 3 ; Scan the last byte for a non-zero character. TEST AL, AL MOV RAX, RCX LEA R10, [RCX+1] CMOVZ RAX, R10 RETN 

INGE_2:

 uint8_t len100K[100000]; char str100K[100000][5]; void itoa_inge_2_init() { memset(str100K, '0', sizeof(str100K)); for(uint32_t i = 0; i < 100000; i++) { char buf[6]; itoa(i, buf, 10); len100K[i] = strlen(buf); memcpy(&str100K[i][5 - len100K[i]], buf, len100K[i]); } } char *itoa_inge_2(char *buf, uint32_t val) { char *p = &buf[10]; uint32_t prevlen; *p = '\0'; do { uint32_t const old = val; uint32_t mod; val /= 100000; mod = old - (val * 100000); prevlen = len100K[mod]; p -= 5; memcpy(p, str100K[mod], 5); } while(val != 0); return &p[5 - prevlen]; } 

VITAUT_1:

 static uint16_t const str100p[100] = { 0x3030, 0x3130, 0x3230, 0x3330, 0x3430, 0x3530, 0x3630, 0x3730, 0x3830, 0x3930, 0x3031, 0x3131, 0x3231, 0x3331, 0x3431, 0x3531, 0x3631, 0x3731, 0x3831, 0x3931, 0x3032, 0x3132, 0x3232, 0x3332, 0x3432, 0x3532, 0x3632, 0x3732, 0x3832, 0x3932, 0x3033, 0x3133, 0x3233, 0x3333, 0x3433, 0x3533, 0x3633, 0x3733, 0x3833, 0x3933, 0x3034, 0x3134, 0x3234, 0x3334, 0x3434, 0x3534, 0x3634, 0x3734, 0x3834, 0x3934, 0x3035, 0x3135, 0x3235, 0x3335, 0x3435, 0x3535, 0x3635, 0x3735, 0x3835, 0x3935, 0x3036, 0x3136, 0x3236, 0x3336, 0x3436, 0x3536, 0x3636, 0x3736, 0x3836, 0x3936, 0x3037, 0x3137, 0x3237, 0x3337, 0x3437, 0x3537, 0x3637, 0x3737, 0x3837, 0x3937, 0x3038, 0x3138, 0x3238, 0x3338, 0x3438, 0x3538, 0x3638, 0x3738, 0x3838, 0x3938, 0x3039, 0x3139, 0x3239, 0x3339, 0x3439, 0x3539, 0x3639, 0x3739, 0x3839, 0x3939, }; char *itoa_vitaut_1(char *buf, uint32_t val) { char *p = &buf[10]; *p = '\0'; while(val >= 100) { uint32_t const old = val; p -= 2; val /= 100; memcpy(p, &str100p[old - (val * 100)], sizeof(uint16_t)); } p -= 2; memcpy(p, &str100p[val], sizeof(uint16_t)); return &p[val < 10]; } 

http://sourceforge.net/projects/itoa/

Il utilise un grand tableau statique statique de tous les entiers à 4 chiffres et l’utilise pour la conversion en chaîne de 32 ou 64 bits.

Portable, pas besoin d’un jeu d’instructions spécifiques.

La seule version plus rapide que j’ai pu trouver était en code assembleur et limitée à 32 bits.

Cet article compare plusieurs méthodes de conversion de nombre entier en chaîne, également appelée itoa. La méthode la plus rapide indiquée est fmt::FormatInt de la bibliothèque fmt, environ 8 fois plus rapide que sprintf / std::ssortingngstream et 5 fois plus rapide que l’ ltoa naïve de ltoa / itoa (les nombres réels peuvent bien sûr varier en fonction de la plate-forme) .

Contrairement à la plupart des autres méthodes, fmt::FormatInt passe les chiffres. Il minimise également le nombre de divisions entières en utilisant l’idée tirée de l’exposé de Alexandrescu intitulé Trois conseils d’optimisation pour C ++ . L’implémentation est disponible ici .

Ceci est bien sûr si C ++ est une option et que vous n’êtes pas limité par l’API de itoa .

Disclaimer: Je suis l’auteur de cette méthode et de la bibliothèque fmt .

Problème intéressant. Si vous êtes intéressé par itoa() seulement 10 radix, alors j’ai créé un exemple 10 fois plus rapide et un exemple 3 fois plus rapide que l’ itoa() typique de itoa() .

Premier exemple (performance 3x)

La première, qui est 3 fois plus rapide que itoa() , utilise un modèle de conception logicielle à inversion unique et est basée sur l’ itoa() open source itoa() trouvée dans groff .

 // itoaSpeedTest.cpp : Defines the entry point for the console application. // #pragma comment(lib, "Winmm.lib") #include "stdafx.h" #include "Windows.h" #include  #include  using namespace std; #ifdef _WIN32 /** a signed 32-bit integer value type */ #define _INT32 __int32 #else /** a signed 32-bit integer value type */ #define _INT32 long int // Guess what a 32-bit integer is #endif /** minimum allowed value in a signed 32-bit integer value type */ #define _INT32_MIN -2147483647 /** maximum allowed value in a signed 32-bit integer value type */ #define _INT32_MAX 2147483647 /** maximum allowed number of characters in a signed 32-bit integer value type including a '-' */ #define _INT32_MAX_LENGTH 11 #ifdef _WIN32 /** Use to init the clock */ #define TIMER_INIT LARGE_INTEGER frequency;LARGE_INTEGER t1, t2;double elapsedTime;QueryPerformanceFrequency(&frequency); /** Use to start the performance timer */ #define TIMER_START QueryPerformanceCounter(&t1); /** Use to stop the performance timer and output the result to the standard stream */ #define TIMER_STOP QueryPerformanceCounter(&t2);elapsedTime=(t2.QuadPart-t1.QuadPart)*1000.0/frequency.QuadPart;wcout<, 1989-1992 \author Inge Eivind Henriksen, 2013 \note Function was originally a part of \a groff, and was refactored & optimized in 2013. \relates itoa() */ const char *Int32ToStr(_INT32 i) { // Make room for a 32-bit signed integers digits and the '\0' char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; *--p = '\0'; if (i >= 0) { do { *--p = numbersIn10Radix[i % 10]; i /= 10; } while (i); } else { // Negative integer do { *--p = reverseArrayEndPtr[i % 10]; i /= 10; } while (i); *--p = '-'; } return p; } int _tmain(int argc, _TCHAR* argv[]) { TIMER_INIT // Make sure we are playing fair here if (sizeof(int) != sizeof(_INT32)) { cerr << "Error: integer size mismatch; test would be invalid." << endl; return -1; } const int steps = 100; { char intBuffer[20]; cout << "itoa() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) itoa(i, intBuffer, 10); TIMER_STOP; } { cout << "Int32ToStr() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) Int32ToStr(i); TIMER_STOP; } cout << "Done" << endl; int wait; cin >> wait; return 0; } 

Sous Windows 64 bits, l’exécution de cet exemple a pour résultat:

 itoa() took: 2909.84 ms. Int32ToStr() took: 991.726 ms. Done 

Sous Windows 32 bits, l’exécution de cet exemple a pour résultat:

 itoa() took: 3119.6 ms. Int32ToStr() took: 1031.61 ms. Done 

Deuxième exemple (performance 10x)

Si cela ne vous dérange pas de passer du temps à initialiser certaines mémoires tampons, il est possible d’optimiser la fonction ci-dessus pour qu’elle soit 10 fois plus rapide que l’ itoa() typique de itoa() . Ce que vous devez faire est de créer des tampons de chaîne plutôt que des tampons de caractères, comme ceci:

 // itoaSpeedTest.cpp : Defines the entry point for the console application. // #pragma comment(lib, "Winmm.lib") #include "stdafx.h" #include "Windows.h" #include  #include  using namespace std; #ifdef _WIN32 /** a signed 32-bit integer value type */ #define _INT32 __int32 /** a signed 8-bit integer value type */ #define _INT8 __int8 /** an unsigned 8-bit integer value type */ #define _UINT8 unsigned _INT8 #else /** a signed 32-bit integer value type */ #define _INT32 long int // Guess what a 32-bit integer is /** a signed 8-bit integer value type */ #define _INT8 char /** an unsigned 8-bit integer value type */ #define _UINT8 unsigned _INT8 #endif /** minimum allowed value in a signed 32-bit integer value type */ #define _INT32_MIN -2147483647 /** maximum allowed value in a signed 32-bit integer value type */ #define _INT32_MAX 2147483647 /** maximum allowed number of characters in a signed 32-bit integer value type including a '-' */ #define _INT32_MAX_LENGTH 11 #ifdef _WIN32 /** Use to init the clock */ #define TIMER_INIT LARGE_INTEGER frequency;LARGE_INTEGER t1, t2;double elapsedTime;QueryPerformanceFrequency(&frequency); /** Use to start the performance timer */ #define TIMER_START QueryPerformanceCounter(&t1); /** Use to stop the performance timer and output the result to the standard stream. Less verbose than \c TIMER_STOP_VERBOSE */ #define TIMER_STOP QueryPerformanceCounter(&t2);elapsedTime=(t2.QuadPart-t1.QuadPart)*1000.0/frequency.QuadPart;wcout<= 1, setting it smaller will make the buffers smaller but the performance slower. If you want to set it larger than 100000 then you must add some more cases to the switch blocks. Try to make it smaller to see the difference in performance. It does however seem to become slower if larger than 100000 */ static const _INT32 numElem10Radix = 100000; /** Array used for fast lookup number character lookup */ const char *numbersIn10Radix[numElem10Radix] = {}; _UINT8 numbersIn10RadixLen[numElem10Radix] = {}; /** Array used for fast lookup number character lookup */ const char *reverseNumbersIn10Radix[numElem10Radix] = {}; _UINT8 reverseNumbersIn10RadixLen[numElem10Radix] = {}; void InitBuffers() { char intBuffer[20]; for (int i = 0; i < numElem10Radix; i++) { itoa(i, intBuffer, 10); size_t numLen = strlen(intBuffer); char *intStr = new char[numLen + 1]; strcpy(intStr, intBuffer); numbersIn10Radix[i] = intStr; numbersIn10RadixLen[i] = numLen; reverseNumbersIn10Radix[numElem10Radix - 1 - i] = intStr; reverseNumbersIn10RadixLen[numElem10Radix - 1 - i] = numLen; } } /*! \brief Converts a 32-bit signed integer to a string \param i [in] Integer \par Software design pattern Uses a single pass non-reversing algorithm with string buffers and is 10x as fast as \c itoa(). \returns Integer as a string \copyright GNU General Public License \copyright 1989-1992 Free Software Foundation, Inc. \date 1989-1992, 2013 \author James Clark, 1989-1992 \author Inge Eivind Henriksen, 2013 \note This file was originally a part of \a groff, and was refactored & optimized in 2013. \relates itoa() */ const char *Int32ToStr(_INT32 i) { /* Room for INT_DIGITS digits, - and '\0' */ char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; _INT32 modVal; *--p = '\0'; if (i >= 0) { do { modVal = i % numElem10Radix; switch(numbersIn10RadixLen[modVal]) { case 5: *--p = numbersIn10Radix[modVal][4]; case 4: *--p = numbersIn10Radix[modVal][3]; case 3: *--p = numbersIn10Radix[modVal][2]; case 2: *--p = numbersIn10Radix[modVal][1]; default: *--p = numbersIn10Radix[modVal][0]; } i /= numElem10Radix; } while (i); } else { // Negative integer const char **reverseArray = &reverseNumbersIn10Radix[numElem10Radix - 1]; const _UINT8 *reverseArrayLen = &reverseNumbersIn10RadixLen[numElem10Radix - 1]; do { modVal = i % numElem10Radix; switch(reverseArrayLen[modVal]) { case 5: *--p = reverseArray[modVal][4]; case 4: *--p = reverseArray[modVal][3]; case 3: *--p = reverseArray[modVal][2]; case 2: *--p = reverseArray[modVal][1]; default: *--p = reverseArray[modVal][0]; } i /= numElem10Radix; } while (i); *--p = '-'; } return p; } int _tmain(int argc, _TCHAR* argv[]) { InitBuffers(); TIMER_INIT // Make sure we are playing fair here if (sizeof(int) != sizeof(_INT32)) { cerr << "Error: integer size mismatch; test would be invalid." << endl; return -1; } const int steps = 100; { char intBuffer[20]; cout << "itoa() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) itoa(i, intBuffer, 10); TIMER_STOP; } { cout << "Int32ToStr() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) Int32ToStr(i); TIMER_STOP; } cout << "Done" << endl; int wait; cin >> wait; return 0; } 

Sous Windows 64 bits, l’exécution de cet exemple a pour résultat:

 itoa() took: 2914.12 ms. Int32ToStr() took: 306.637 ms. Done 

Sous Windows 32 bits, l’exécution de cet exemple a pour résultat:

 itoa() took: 3126.12 ms. Int32ToStr() took: 299.387 ms. Done 

Pourquoi utilisez-vous des tampons de recherche de chaîne inversée?

Il est possible de le faire sans les tampons de recherche de chaîne inversée (ce qui économise la moitié de la mémoire interne), mais cela le ralentit considérablement (environ 850 ms sur les systèmes 64 bits et 380 ms sur les systèmes 32 bits). Je ne comprends pas vraiment pourquoi c’est tellement plus lent – en particulier sur les systèmes 64 bits, pour tester cela vous-même, vous pouvez simplement changer le code suivant:

 #define _UINT32 unsigned _INT32 ... static const _UINT32 numElem10Radix = 100000; ... void InitBuffers() { char intBuffer[20]; for (int i = 0; i < numElem10Radix; i++) { _itoa(i, intBuffer, 10); size_t numLen = strlen(intBuffer); char *intStr = new char[numLen + 1]; strcpy(intStr, intBuffer); numbersIn10Radix[i] = intStr; numbersIn10RadixLen[i] = numLen; } } ... const char *Int32ToStr(_INT32 i) { char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; _UINT32 modVal; *--p = '\0'; _UINT32 j = i; do { modVal = j % numElem10Radix; switch(numbersIn10RadixLen[modVal]) { case 5: *--p = numbersIn10Radix[modVal][4]; case 4: *--p = numbersIn10Radix[modVal][3]; case 3: *--p = numbersIn10Radix[modVal][2]; case 2: *--p = numbersIn10Radix[modVal][1]; default: *--p = numbersIn10Radix[modVal][0]; } j /= numElem10Radix; } while (j); if (i < 0) *--p = '-'; return p; } 

Cela fait partie de mon code dans asm. Cela ne fonctionne que pour la gamme 255-0. Cela peut être plus rapide, mais ici vous pouvez trouver la direction et l’idée principale.

4 imuls 1 lecture en mémoire 1 écriture en mémoire

Vous pouvez essayer de réduire de 2 imules et utiliser des sauts avec le décalage. Cependant, vous ne trouvez rien de plus rapide en C / C ++ / Python;)

 void itoa_asm(unsigned char inVal, char *str) { __asm { // eax=100's -> (some_integer/100) = (some_integer*41) >> 12 movzx esi,inVal mov eax,esi mov ecx,41 imul eax,ecx shr eax,12 mov edx,eax imul edx,100 mov edi,edx // ebx=10's -> (some_integer/10) = (some_integer*205) >> 11 mov ebx,esi sub ebx,edx mov ecx,205 imul ebx,ecx shr ebx,11 mov edx,ebx imul edx,10 // ecx = 1 mov ecx,esi sub ecx,edx // -> sub 10's sub ecx,edi // -> sub 100's add al,'0' add bl,'0' add cl,'0' //shl eax, shl ebx,8 shl ecx,16 or eax,ebx or eax,ecx mov edi,str mov [edi],eax } } 

@Inge Henriksen

Je crois que votre code a un bug:

 IntToStr(2701987) == "2701987" //Correct IntToStr(27001987) == "2701987" //Incorrect 

Voici pourquoi votre code est faux:

 modVal = i % numElem10Radix; switch (reverseArrayLen[modVal]) { case 5: *--p = reverseArray[modVal][4]; case 4: *--p = reverseArray[modVal][3]; case 3: *--p = reverseArray[modVal][2]; case 2: *--p = reverseArray[modVal][1]; default: *--p = reverseArray[modVal][0]; } i /= numElem10Radix; 

Il devrait y avoir un premier 0 avant “1987”, qui est “01987”. Mais après la première itération, vous obtenez 4 chiffres au lieu de 5.

Alors,

IntToStr (27000000) = “2700” // incorrect