Pourquoi mon programme est lent lorsqu'une boucle plus exactement 8192 éléments?

Voici l'extrait du programme en question. La matrice img[][] a la taille Taille×Taille, et est initialisée à:

img[j][i] = 2 * j + i

ensuite, vous faites une matrice res[][] , et chaque champ ici est fait pour être la moyenne des 9 champs autour de lui dans la matrice img. La bordure est laissée à 0 pour plus de simplicité.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

C'est au programme. À des fins d'exhaustivité, voici ce qui vient avant. Aucun code ne vient après. Comme vous pouvez le voir, c'est juste une initialisation.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

fondamentalement, ce programme est lent lorsque la taille est un multiple de 2048, p.ex. les temps d'exécution:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

le compilateur est GCC. D'après ce que je sais, c'est à cause de la gestion de la mémoire, mais je ne sais pas grand chose sur ce sujet, c'est pourquoi je demande ici.

Aussi comment corriger ce serait bien, mais si quelqu'un pouvait expliquer ces temps d'exécution, je serais déjà assez heureux.

je connais déjà malloc / free, mais le problème n'est pas la quantité de mémoire utilisée, c'est simplement le temps d'exécution, donc je ne sais pas comment cela pourrait aider.

695
demandé sur casperOne 2012-09-04 17:51:31
la source

3 ответов

la différence est causée par le même problème de super-alignement des questions connexes suivantes:

Mais c'est seulement parce qu'il y a un autre problème avec le code.

à partir de la boucle d'origine:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

remarquez D'abord que les deux boucles internes sont triviales. Ils peuvent être déroulés comme suit:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

donc il reste les deux boucles externes qui nous intéressent.

Maintenant, nous pouvons voir que le problème est le même dans cette question: Pourquoi l'ordre des boucles d'affecter les performances lors de l'itération sur un tableau 2D?

vous itérez la matrice colonne-sage au lieu de ligne-Sage.


pour résoudre ce problème, vous devez échanger les deux boucles.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

cela élimine tous les accès non séquentiels complètement de sorte que vous n'obtenez plus de ralentissements aléatoires sur les grands pouvoirs-de-deux.


Core i7 920 @ 3.5 GHz

Code Original:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Interchangeables Extérieure De La Boucle:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
882
répondu Mysticial 2017-05-23 13:31:30
la source

les tests suivants ont été effectués avec Visual C++ compiler car il est utilisé par l'installation par défaut de Qt Creator (je suppose sans drapeau d'optimisation). En utilisant GCC, il n'y a pas de grande différence entre la version de Mystical et mon code "optimisé". La conclusion est donc que les optimisations des compilateurs prennent mieux soin de la micro-optimisation que les humains (moi enfin). Je laisse le reste de ma réponse pour la référence.


il n'est pas efficace de traiter les images de cette façon. Il est préférable d'utiliser des matrices en une seule dimension. Le traitement de tous les pixels se fait en une boucle. L'accès aléatoire aux points pourrait être fait en utilisant:

pointer + (x + y*width)*(sizeOfOnePixel)

dans ce cas particulier, il est préférable de calculer et de mettre en cache la somme de trois groupes de pixels horizontalement parce qu'ils sont utilisés trois fois chacun.

j'ai fait quelques tests et je pense que cela vaut la peine de partager. Chaque résultat est une moyenne de cinq tests.

code Original par user1615209:

8193: 4392 ms
8192: 9570 ms

version mystique:

8193: 2393 ms
8192: 2190 ms

deux passes utilisant un tableau 1D: première passe pour les sommes horizontales, deuxième pour la somme verticale et moyenne. Deux passes d'adressage avec trois pointeurs et seulement des incréments comme ceci:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

deux passes utilisant un tableau 1D et s'adressant comme ceci:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

cache en une seule passe horizontal totalise juste une ligne d'avance pour qu'ils restent dans le cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Conclusion:

  • aucun avantage à utiliser plusieurs pointeurs et incréments (je pensais que cela aurait été plus rapide)
  • cache des sommes horizontales est mieux que de les calculer plusieurs fois.
  • deux passes n'est pas trois fois plus rapide, deux fois seulement.
  • il est possible d'atteindre 3,6 fois plus vite en utilisant à la fois un passage simple et la mise en cache d'un résultat intermédiaire

je suis sûr qu'il est possible de faire beaucoup mieux.

NOTE S'il vous plaît, notez que j'ai écrit cette réponse pour cibler les problèmes de performance générale plutôt que le problème de cache expliqué dans L'excellente réponse de Mystical. Au début, c'était juste un pseudo code. On m'a demandé de faire des tests dans les commentaires... Voici une version entièrement remaniée avec des tests.

52
répondu bokan 2015-02-20 10:08:42
la source

L'accès à l'élément de commande pris en charge il y a encore quelques branches basses de fruits à gauche. L'accumulation peut être faite de telle sorte que lors de l'itération vers la droite seulement 3 nouvelles valeurs doivent être récupérées de la mémoire et accumulées. L'astuce est de savoir comment faire tomber la colonne la plus à gauche; en ajoutant une nouvelle colonne se rappeler sa valeur jusqu'à ce qu'il sort de la fenêtre d'échantillonnage.

Le coût avant: 9 lire, 9 plus, 1 division Le coût après: 3 Lire, 3 Ajouter, 1 division

pensez à la fenêtre d'échantillonnage comme la boîte de 3x3 où vous gardez la trace de chaque colonne (1x3) séparément. Accumuler une nouvelle colonne et baisse la plus ancienne.

la division est une instruction de latence élevée de sorte qu'il pourrait être avantageux de cacher la latence, mais avant d'y aller, la sortie du compilateur devrait être inspectée si la division par constante est supprimée et si la boucle déroulante (par le compilateur) fait déjà une compensation de latence.

mais après l'optimisation la plus dramatique de l'utilisation correcte du cache ce sont vraiment des choses mineures.

-1
répondu t0rakka 2017-10-11 15:08:18
la source

Autres questions sur c++ performance memory-management gcc