Réinitialiser le tableau C int à zéro: le moyen le plus rapide?

En supposant que nous ayons un T myarray[100] avec T = int, unsigned int, long long int ou unsigned long long int, quel est le moyen le plus rapide pour réinitialiser tout son contenu à zéro (non seulement pour l’initialisation fois dans mon programme)? Peut-être avec memset?

Même question pour un tableau dynamic comme T *myarray = new T[100] .

memset (à partir de ) est probablement la méthode standard la plus rapide, car c’est généralement une routine écrite directement dans l’assemblage et optimisée à la main.

 memset(myarray, 0, sizeof(myarray)); // for automatically-allocated arrays memset(myarray, 0, N*sizeof(*myarray)); // for heap-allocated arrays, where N is the number of elements 

En passant, en C ++, le moyen idiomatique serait d’utiliser std::fill (à partir de ):

 std::fill(myarray, myarray+N, 0); 

qui peut être optimisé automatiquement dans un memset ; Je suis tout à fait sûr que cela fonctionnera aussi vite que memset pour int s, alors qu’il pourrait être légèrement pire pour les plus petits si l’optimiseur n’est pas assez intelligent. Toujours, en cas de doute, profil.

De memset() :

 memset(myarray, 0, sizeof(myarray)); 

Vous pouvez utiliser sizeof(myarray) si la taille de myarray est connue à la compilation. Sinon, si vous utilisez un tableau de taille dynamic, tel que obtenu via malloc ou new , vous devrez suivre la longueur.

Cette question, bien que relativement ancienne, nécessite quelques repères, car elle ne demande pas la manière la plus idiomatique, ni la manière d’écrire le moins de lignes possible, mais le plus rapidement possible. Et il est idiot de répondre à cette question sans quelques tests réels. J’ai donc comparé quatre solutions, memset vs std :: fill vs ZERO de la réponse d’AnT vs une solution que j’ai faite en utilisant des insortingnsèques AVX.

Notez que cette solution n’est pas générique, elle ne fonctionne que sur des données de 32 ou 64 bits. S’il vous plaît commenter si ce code fait quelque chose de incorrect.

 #include #define insortingn_ZERO(a,n){\ size_t x = 0;\ const size_t inc = 32 / sizeof(*(a));/*size of 256 bit register over size of variable*/\ for (;x < n-inc;x+=inc)\ _mm256_storeu_ps((float *)((a)+x),_mm256_setzero_ps());\ if(4 == sizeof(*(a))){\ switch(nx){\ case 3:\ (a)[x] = 0;x++;\ case 2:\ _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\ case 1:\ (a)[x] = 0;\ break;\ case 0:\ break;\ };\ }\ else if(8 == sizeof(*(a))){\ switch(nx){\ case 7:\ (a)[x] = 0;x++;\ case 6:\ (a)[x] = 0;x++;\ case 5:\ (a)[x] = 0;x++;\ case 4:\ _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\ case 3:\ (a)[x] = 0;x++;\ case 2:\ ((long long *)(a))[x] = 0;break;\ case 1:\ (a)[x] = 0;\ break;\ case 0:\ break;\ };\ }\ } 

Je ne prétends pas que c'est la méthode la plus rapide, car je ne suis pas un expert en optimisation de bas niveau. Il s'agit plutôt d'un exemple d'implémentation dépendant de l'architecture correcte, plus rapide que memset.

Maintenant, sur les résultats. J'ai calculé les performances pour les baies de taille 100 int et longue, allouées statiquement et dynamicment, mais à l'exception de msvc, qui éliminait le code mort sur les baies statiques, les résultats étaient extrêmement comparables. Les marquages ​​temporels sont des ms pour 1 million d'itérations, en utilisant la fonction d'horloge de faible précision de time.h.

clang 3.8 (Utilisation du front de clang-cl, indicateurs d'optimisation = / OX / arch: AVX / Oi / Ot)

 int: memset: 99 fill: 97 ZERO: 98 insortingn_ZERO: 90 long long: memset: 285 fill: 286 ZERO: 285 insortingn_ZERO: 188 

gcc 5.1.0 (indicateurs d'optimisation: -O3 -march = native -mtune = native -mavx):

 int: memset: 268 fill: 268 ZERO: 268 insortingn_ZERO: 91 long long: memset: 402 fill: 399 ZERO: 400 insortingn_ZERO: 185 

msvc 2015 (indicateurs d'optimisation: / OX / arch: AVX / Oi / Ot):

 int memset: 196 fill: 613 ZERO: 221 insortingn_ZERO: 95 long long: memset: 273 fill: 559 ZERO: 376 insortingn_ZERO: 188 

Il y a beaucoup de choses intéressantes à faire ici: llvm kill gcc, les optimisations spotties typiques de MSVC (il fait une impressionnante élimination du code mort sur les tableaux statiques et a alors des performances terribles pour le remplissage). Bien que mon implémentation soit nettement plus rapide, cela peut être dû au fait qu'elle reconnaît que la compensation des bits a beaucoup moins de charge que toute autre opération de paramétrage.

La mise en œuvre de Clang mérite plus d'attention, car elle est nettement plus rapide. Certains tests supplémentaires montrent que son memset est en fait spécialisé pour zéro - les memsets non nuls pour un tableau de 400 octets sont beaucoup plus lents (~ 220ms) et sont comparables à ceux de gcc. Cependant, la configuration non nulle avec un tableau de 800 octets ne fait pas de différence de vitesse, ce qui explique probablement pourquoi leur memset a de moins bonnes performances que mon implémentation - la spécialisation ne concerne que les petites baies et l’arrêt juste autour de 800 octets. Notez également que gcc 'fill' et 'ZERO' n'optimisent pas pour memset (en regardant le code généré), gcc génère simplement du code avec des caractéristiques de performance identiques.

Conclusion: memset n'est pas vraiment optimisé pour cette tâche et les gens le prétendent (sinon, mccet de gcc et msvc et llvm aurait les mêmes performances). Si les performances sont importantes, memset ne devrait pas être une solution finale, en particulier pour ces baies de taille moyenne, car elle n'est pas spécialisée dans la compensation des bits, et elle n'est pas optimisée à la main par le compilateur.

Vous pouvez utiliser memset , mais uniquement parce que notre sélection de types est limitée aux types intégraux.

Dans le cas général en C, il est logique de mettre en œuvre une macro

 #define ZERO_ANY(T, a, n) do{\ T *a_ = (a);\ size_t n_ = (n);\ for (; n_ > 0; --n_, ++a_)\ *a_ = (T) { 0 };\ } while (0) 

Cela vous donnera des fonctionnalités de type C ++ qui vous permettront de “réinitialiser à zéro” un tableau d’objects de n’importe quel type sans avoir à recourir à des hacks comme memset . Fondamentalement, il s’agit d’un modèle de fonction analogique C de C ++, sauf que vous devez spécifier explicitement l’argument de type.

En plus de cela, vous pouvez créer un “modèle” pour les tableaux non décomposés

 #define ARRAY_SIZE(a) (sizeof (a) / sizeof *(a)) #define ZERO_ANY_A(T, a) ZERO_ANY(T, (a), ARRAY_SIZE(a)) 

Dans votre exemple, il serait appliqué comme

 int a[100]; ZERO_ANY(int, a, 100); // or ZERO_ANY_A(int, a); 

Il est également intéressant de noter que spécifiquement pour les objects de types scalaires, on peut implémenter une macro indépendante du type

 #define ZERO(a, n) do{\ size_t i_ = 0, n_ = (n);\ for (; i_ < n_; ++i_)\ (a)[i_] = 0;\ } while (0) 

et

 #define ZERO_A(a) ZERO((a), ARRAY_SIZE(a)) 

transformer l'exemple ci-dessus en

  int a[100]; ZERO(a, 100); // or ZERO_A(a); 

Pour la déclaration statique, je pense que vous pourriez utiliser:

 T myarray[100] = {0}; 

Pour une déclaration dynamic, je suggère la même chose: memset

zero(myarray); est tout ce dont vous avez besoin en C ++.

Ajoutez simplement ceci dans un autre fichier:

 template inline void zero(T(&arr)[SIZE]){ memset(arr, 0, SIZE*sizeof(T)); } 

Voici la fonction que j’utilise:

 template static void setValue(T arr[], size_t length, const T& val) { std::fill(arr, arr + length, val); } template static void setValue(T (&arr)[N], const T& val) { std::fill(arr, arr + N, val); } 

Vous pouvez l’appeler comme ceci:

 //fixed arrays int a[10]; setValue(a, 0); //dynamic arrays int *d = new int[length]; setValue(d, length, 0); 

Ci-dessus est plus C ++ 11 que d’utiliser memset. Vous obtenez également une erreur de compilation si vous utilisez un tableau dynamic en spécifiant la taille.