comment supprimer un ajout qui est à l'intérieur des crochets dans une instruction for

Question

J'ai ce code dans C:

for (i = 0; i < N_TIMES; i++) { 

    // --------------------------------------------------------------- 
    // Do not alter anything above this line 

    for (j=0; j < ARRAY_SIZE-7; j=j+8) { 
     sum += array[j]+array[j+1]+array[j+2]+array[j+3]+array[j+4]+array[j+5]+array[j+6]+array[j+7]; 
    } 
    for(;j<ARRAY_SIZE;j++) 
      sum+= array[j]; 

    // Do not alter anything below this line. 
    // --------------------------------------------------------------- 

    if (sum != checksum) { 
     printf("Checksum error!\n"); 
    } 
    sum = 0; 

} 

Où ARRAY_SIZE = 9973 et N_TIMES = 200000

Ce excersice est pour l'optimisation. Comment puis-je supprimer cet ajout qui est à l'intérieur des crochets dans la boucle interne (par exemple, tableau [j + 4])? Aidez-moi, s'il vous plaît.

Answer 1

utiliser une boucle intérieure:

for (j=0; j < ARRAY_SIZE-7; j=j+8) { 
    for (int k = j; k < (k + 8); ++k) { 
     sum += array[k]; 
    } 
} 

Answer 2

utiliser une boucle interne. Cela n'ajoutera pas de complexité à l'algorithme, puisque la boucle interne sera toujours comprise entre 0 et 7. Si c'est vraiment C, vous ne pouvez pas créer une autre variable. Ainsi, vous pouvez faire ceci:

for (j=0; j < ARRAY_SIZE-7; j=j+8) { 
    sum += array[j]; 
    for (array[j] = 0; array[j] < 8; array[j]++) { 
     sum += array[array[j]]; 
    } 
} 

Je suppose que cela va fonctionner, puisque vous ne aurez pas besoin array[j] plus.

Answer 3

EDIT2: Cette réponse est non valable aujourd'hui comme plus tôt, il a été étiqueté comme

C++ Essayez std::accumulate pour

C++ Voici un exemple

#include <numeric> 

int main(){ 
    int buf[10] = {7, 8, 1, 9, 5, 0, 2, 3, 6, 4}; 

    int sum = std::accumulate (buf, buf+7, 0); 
} 

Answer 4

Voici les résultats de certains tests, je l'ai fait. J'ai essayé 3 versions de votre code, une sans le dérouler, une avec votre déroulant et une avec les extensions sse. Puisque vous n'avez pas indiqué le type de votre tableau, j'ai utilisé des entiers, dans la séquence 1..ARRAY_SIZE.

Tout d'abord, la configuration, emmintrin.h est l'en-tête pour les intrinsèques sse.

#include <stdio.h> 
#include <stdlib.h> 
#include <emmintrin.h> // SSE2 
#include <time.h> 

int main(){ 
    const size_t ARRAY_SIZE = 9973; 
    const size_t N_TIMES = 200000; 
    int * array = malloc(ARRAY_SIZE*sizeof(*array)); 
    for (size_t i=0;i<ARRAY_SIZE;++i) array[i] = i; 
    clock_t start, stop; 

Ensuite, une simple boucle. Si l'optimiseur doit être aussi rapide que n'importe quoi d'autre, le compilateur sait que vous ajoutez des éléments de tableau adjacents et que vous pouvez dérouler, utiliser sse etc.

// Using normal loop 
    start = clock(); 
    int sum = 0; 
    for (size_t i=0;i<N_TIMES;++i){ 
     for (size_t j=0;j<ARRAY_SIZE;++j){ 
      sum += array[j]; 
     } 
    } 
    stop = clock(); 
    printf("normal %d\t%e\n",sum,difftime(stop,start)); 

suivant pour la comparaison de votre boucle

// Using unwrapped loop 
    start = clock(); 
    sum = 0; 
    for (size_t i=0;i<N_TIMES;++i){ 
     size_t j=0; 
     for (;j<ARRAY_SIZE-7;j+=8){ 
      sum += array[j+0] + array[j+1] + array[j+2] + 
       array[j+3] + array[j+4] + array[j+5] + 
       array[j+6] + array[j+7]; 
     } 
     for (;j<ARRAY_SIZE;++j){ 
      sum += array[j]; 
     } 
    } 
    stop = clock(); 
    printf("unrolled %d\t%e\n",sum,difftime(stop,start)); 

Et enfin une boucle en utilisant sse. Le type __m128i désigne un tableau d'entiers de 128 bits, qui doit être exploité en utilisant les intrinsèques _mm. Ce code charge le tableau 4 entiers à la fois dans un registre, l'ajoute à un registre de sommation, puis décompresse le registre de sommation à la fin.

// Using sse 
    start = clock(); 
    sum = 0; 
    __m128i sse_sum = _mm_setzero_si128(); 
    for (size_t i=0;i<N_TIMES;++i){ 
     size_t j=0; 
     for (;j<ARRAY_SIZE-3;j+=4){ 
      __m128i slice = _mm_load_si128((__m128i*)(array+j)); 
      sse_sum = _mm_add_epi32(sse_sum,slice); 
     } 
     for (;j<ARRAY_SIZE;++j){ 
      sum += array[j]; 
     } 
    } 
    int sse_result[4]; 
    _mm_store_si128((__m128i*)sse_result,sse_sum); 
    for (int i=0;i<4;++i) 
     sum += sse_result[i]; 
    stop = clock(); 
    printf("sse %d\t%e\n",sum,difftime(stop,start)); 
} 

Voici les résultats pour un compilateurs couple dont je disposais, toutes les attaques visant 64 bits Mac OS X 10.6. La première colonne est la version en boucle, la somme, le temps pris:

$ gcc --version 
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664) 
$ gcc loop.c -o loop -msse2 -O3 -std=c99 -ftree-vectorize && ./loop 
normal -2068657536 7.525430e+05 
unrolled -2068657536 9.638840e+05 
sse  -2068657536 4.929820e+05 

$ gcc-4.5 --version 
gcc-4.5 (GCC) 4.5.0 
$ gcc-4.5 loop.c -o loop -msse2 -O3 -std=c99 -ftree-vectorize && ./loop 
normal -2068657536 9.721320e+05 
unrolled -2068657536 9.610700e+05 
sse  -2068657536 1.196051e+06 

$ clang --version 
clang version 2.0 (trunk 103456) 
$ clang loop.c -o loop -msse2 -O3 -std=c99 -ftree-vectorize && ./loop 
normal -2068657536 1.155552e+06 
unrolled -2068657536 9.613550e+05 
sse  -2068657536 1.195248e+06 

Comme vous pouvez voir les résultats varient énormément entre les compilateurs. Dans gcc, il semble que la boucle normale soit bien optimisée, mieux performante que la boucle déroulée et presque aussi bonne que sse dans le compilateur Apple, alors que pour la version de base, la version sse est relativement lente (probablement parce qu'Apple a mis en place un meilleur default optimisations pour leur compilateur). Clang n'optimise pas si bien, même si ma version est un peu ancienne, et la boucle déroulée est la meilleure pour ce cas.À mon avis, la meilleure façon de procéder serait d'utiliser la boucle de base, à condition que votre compilateur fasse une vectorisation automatique (c'est ce que fait le -ftree-vectorize), car c'est le plus facile à comprendre. Vous allez tirer le meilleur parti du bidouillage avec les niveaux d'optimisation du compilateur plutôt que de dérouler manuellement les boucles.

Answer 5

Cela ressemble à une tentative de déroulement de la boucle. Essayez ceci à la place.

for (j=0; j < ARRAY_SIZE-7;) { 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
    sum += array[j++]; 
} 
for(;j<ARRAY_SIZE;j++) 
     sum+= array[j];