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

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

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

memset(from <string.h>) est probablement le moyen standard le plus rapide, car il s'agit généralement d'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

À propos, en C ++, la manière idiomatique serait d'utiliser std::fill(from <algorithm>):

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

qui peut être optimisé automatiquement en un memset; Je suis tout à fait sûr que cela fonctionnera aussi vite que memsetpour ints, alors qu'il peut fonctionner légèrement moins bien pour les types plus petits si l'optimiseur n'est pas assez intelligent. Pourtant, en cas de doute, profil.

Cette question, bien qu'assez ancienne, a besoin de quelques repères, car elle ne demande pas la manière la plus idiomatique, ou la manière qui peut être écrite avec le moins de lignes, mais la manière la plus rapide . Et il est ridicule de répondre à cette question sans des 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 créée en utilisant les intrinsè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. Veuillez commenter si ce code fait quelque chose d'incorrect.

#include<immintrin.h>
#define intrin_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(n-x){\
    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(n-x){\
    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étendrai 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épendante de l'architecture correcte qui est plus rapide que memset.

Maintenant, sur les résultats. J'ai calculé les performances pour les tableaux de taille 100 int et longs, à la fois alloués statiquement et dynamiquement, mais à l'exception de msvc, qui a éliminé le code mort sur les tableaux statiques, les résultats étaient extrêmement comparables, donc je ne montrerai que les performances des tableaux dynamiques. Les marquages ​​de temps sont en ms pour 1 million d'itérations, en utilisant la fonction d'horloge de faible précision de time.h.

clang 3.8 (En utilisant le frontend clang-cl, les indicateurs d'optimisation = / OX / arch: AVX / Oi / Ot)

int:
memset:      99
fill:        97
ZERO:        98
intrin_ZERO: 90

long long:
memset:      285
fill:        286
ZERO:        285
intrin_ZERO: 188

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

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

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

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

Il se passe beaucoup de choses intéressantes ici: llvm tuant gcc, les optimisations irrégulières typiques de MSVC (il effectue une élimination impressionnante du code mort sur les tableaux statiques et a ensuite des performances terribles pour le remplissage). Bien que mon implémentation soit beaucoup plus rapide, cela peut être uniquement dû au fait qu'elle reconnaît que la compensation de bits a beaucoup moins de frais généraux que toute autre opération de réglage.

La mise en œuvre de Clang mérite plus d'être examinée, car elle est beaucoup plus rapide. Quelques 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 (~ 220 ms) et sont comparables à ceux de gcc. Cependant, le memsetting différent de zéro avec un tableau de 800 octets ne fait aucune différence de vitesse, ce qui explique probablement pourquoi dans ce cas, leur memset a des performances pires que mon implémentation - la spécialisation est uniquement pour les petits tableaux et la coupure est juste autour de 800 octets. Notez également que gcc 'fill' et 'ZERO' ne sont pas optimisés pour memset (en regardant le code généré), gcc génère simplement du code avec des caractéristiques de performances identiques.

Conclusion: memset n'est pas vraiment optimisé pour cette tâche et les gens le prétendraient (sinon le memset de gcc et msvc et llvm aurait les mêmes performances). Si les performances comptent, memset ne devrait pas être une solution finale, en particulier pour ces tableaux de taille moyenne maladroits, car il n'est pas spécialisé pour l'effacement de bits et il n'est pas optimisé à la main, pas mieux que le compilateur ne peut le faire seul.

De memset():

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

Vous pouvez utiliser sizeof(myarray)si la taille de myarrayest connue au moment de la compilation. Sinon, si vous utilisez un tableau de taille dynamique, comme obtenu via mallocou new, vous devrez garder une trace de la longueur.

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 d'implémenter 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 une fonctionnalité de type C ++ qui vous permettra de "réinitialiser à zéro" un tableau d'objets de tout type sans avoir à recourir à des hacks comme memset. Fondamentalement, il s'agit d'un analogue C du modèle de fonction C ++, sauf que vous devez spécifier l'argument de type explicitement.

En plus de cela, vous pouvez créer un «modèle» pour les tableaux non dégradé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 objets 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 pouvez utiliser:

T myarray[100] = {0};

Pour la déclaration dynamique, je suggère la même manière: memset

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

Ajoutez simplement ceci à un en-tête:

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

Voici la fonction que j'utilise:

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

template<typename T, size_t N>
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, il y a plus de C ++ 11 que d'utiliser memset. Vous obtenez également une erreur de compilation si vous utilisez un tableau dynamique avec la spécification de la taille.