multiplication rapide des valeurs dans un tableau

Question

Y at-il un moyen rapide pour multiplier les valeurs d'un ensemble de flotteur en C++, pour optimiser cette fonction (où count est un multiple de 4):

void multiply(float* values, float factor, int count) 
{ 
    for(int i=0; i < count; i++) 
    { 
     *value *= factor; 
     value++; 
    } 
} 

Une solution doit travailler sur Mac OS X et Windows, Intel et non-Intel. Pensez SSE, vectorisation, compilateur (gcc vs. MSVC).

Answer 1

Si vous voulez que votre code soit multiplate-forme, alors vous devrez écrire un code indépendant de la plateforme, ou vous devrez écrire une charge de #ifdef s.

Avez-vous essayé de dérouler manuellement la boucle et de voir si cela fait une différence?

Answer 2

Puisque vous connaissez le count est un multiple de 4, vous pouvez déroulez votre boucle ...

void multiply(float* values, float factor, int count) 
{ 
    count = count >> 2; // count/4 
    for(int i=0; i < count ; i++) 
    { 
     *value *= factor; 
     *(value+1) *= factor; 
     *(value+2) *= factor; 
     *(value+3) *= factor; 
     value += 4; 
    } 
} 

Answer 3

Avertissement: De toute évidence, cela ne fonctionnera pas sur iPhone, iPad, Android, ou leurs équivalents futurs .

#include <mmintrin.h> 
#include <xmmintrin.h> 

__m128 factor4 = _mm_set1_ps(factor); 
for (int i=0; i+3 < count; i += 4) 
{ 
    __m128 data = _mm_mul_ps(_mm_loadu_ps(values), factor4); 
    _mm_storeu_ps(values, data); 
    values += 4; 
} 
for (int i=(count/4)*4; i < count; i++) 
{ 
    *values *= factor; 
    value++; 
} 

Answer 4

Avez-vous pensé à OpenMP?

La plupart des ordinateurs modernes ont des processeurs multicœurs et presque tous les principaux compilateurs semblent avoir OpenMP intégré. Vous gagnez de la vitesse à tout prix.

Voir Wikipedia's article on OpenMP.

Answer 5

La meilleure solution est de rester simple, et laissez le compilateur l'optimiser pour vous. GCC connaît SSE, SSE2, altivec et quoi d'autre. Si votre code est trop complexe, votre compilateur ne pourra pas l'optimiser sur toutes les cibles possibles.

Answer 6

Comme vous l'avez mentionné, il existe de nombreuses architectures qui ont des extensions SIMD et SIMD est probablement votre meilleur pari en matière d'optimisation. Ils sont tous spécifiques aux plates-formes et les langages C et C++ ne sont pas compatibles SIMD.

La première chose à faire est cependant d'activer les indicateurs spécifiques SIMD pour votre build donné. Le compilateur peut reconnaître des modèles qui peuvent être optimisés avec SIMD. La prochaine chose est d'écrire du code SIMD spécifique à la plate-forme en utilisant l'intrinsèque ou l'assemblage du compilateur, le cas échéant. Vous devez cependant conserver une implémentation portable non-SIMD pour les plates-formes qui n'ont pas de version optimisée. #ifdef s activer SIMD sur les plates-formes qui le prennent en charge. Enfin, au moins sur ARM mais pas sur Intel, sachez que les plus petits types entiers et flottants permettent un plus grand nombre d'opérations parallèles par instruction SIMD unique.

Answer 7

Je pense qu'il n'y a pas grand-chose à faire qui fasse une grande différence. Peut-être que vous pouvez accélérer un peu avec OpenMP ou SSE. Mais les processeurs modernes sont déjà assez rapides. Dans certaines applications, la bande passante/latence de la mémoire est en fait le goulot d'étranglement et la situation empire. Nous avons déjà trois niveaux de cache et avons besoin d'algorithmes de prélecture intelligente pour éviter d'énormes retards. Il est donc logique de penser aussi aux modèles d'accès à la mémoire.Par exemple, si vous implémentez un tel multiply et un add et l'utiliser comme ceci:

void multiply(float vec[], float factor, int size) 
{ 
    for (int i=0; i<size; ++i) 
    vec[i] *= factor; 
} 

void add(float vec[], float summand, int size) 
{ 
    for (int i=0; i<size; ++i) 
    vec[i] += summand; 
} 

void foo(float vec[], int size) 
{ 
    multiply(vec,2.f,size); 
    add(vec,9.f,size); 
} 

vous passez essentiellement deux fois sur le bloc de mémoire. En fonction de la taille du vecteur, il peut ne pas rentrer dans le cache L1, auquel cas le passage à deux reprises ajoute du temps supplémentaire. C'est évidemment mauvais et vous devriez essayer de garder les accès mémoire "locaux". Dans ce cas, une seule boucle

void foo(float vec[], int size) 
{ 
    for (int i=0; i<size; ++i) { 
    vec[i] = vec[i]*2+9; 
    } 
} 

est susceptible d'être plus rapide. En règle générale: Essayez d'accéder à la mémoire de manière linéaire et essayez d'accéder à la mémoire "localement", ce qui veut dire, essayez de réutiliser les données qui sont déjà dans le cache L1. Juste une idée.