Pourquoi mon programme est-il lent lors de la boucle sur exactement 8192 éléments?

Les tests suivants ont été effectués avec le compilateur Visual C++ tel qu'il est utilisé par L'installation par défaut de Qt Creator (je suppose sans indicateur d'optimisation). Lorsque vous utilisez GCC, il n'y a pas de grande différence entre la version de Mystical et mon code "optimisé". Donc, la conclusion est que les optimisations du compilateur prennent soin de la micro-optimisation mieux que les humains (moi enfin). Je laisse le reste de ma réponse pour référence.

Il n'est pas efficace de traiter les images de cette façon. Il est préférable d'utiliser unique tableaux de dimension. Le traitement de tous les pixels est effectué en une seule 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 car ils sont utilisés trois fois chacun.

J'ai fait quelques tests et je pense que ça vaut la peine d'être partagé. 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 passer en utilisant un tableau 1D: premier passage pour les sommes horizontales, deuxième pour la somme verticale et moyenne. Adressage à deux passes 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 passent en utilisant un tableau 1D et en 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

Un passage de mise en cache horizontale somme juste une ligne avant afin 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 d'utiliser plusieurs pointeurs et juste des incréments (je pensais que cela aurait été plus rapide)
• la mise en cache des sommes horizontales est meilleure que les calculer plusieurs fois.
• deux passes ne sont pas trois fois plus rapides, deux fois seulement.
• Il est possible d'obtenir 3,6 fois plus rapidement en utilisant à la fois un seul passage et la mise en cache d'un résultat intermédiaire

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

NOTE Veuillez noter que j'ai écrit cette réponse pour cibler les problèmes de performance généraux plutôt que le problème de cache expliqué dans L'excellente réponse de Mystical. Au début, c'était juste du pseudo-code. On m'a demandé de faire des tests dans les commentaires... Voici une version complètement refactorisée avec des tests.

L'ordre d'accès aux éléments pris en charge il reste encore quelques fruits à faible pendaison. L'accumulation peut être faite de telle sorte que lors de l'itération vers la droite, seules les nouvelles valeurs 3 doivent être récupérées de la mémoire et accumulées. L'astuce consiste à savoir comment supprimer la colonne la plus à gauche; lorsque vous ajoutez une nouvelle colonne, souvenez-vous de sa valeur jusqu'à ce qu'elle sorte de la fenêtre d'échantillonnage.

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

Pensez à la fenêtre d'échantillonnage en tant que boîte 3x3 où vous gardez une trace de chaque colonne (1x3) séparément. Accumulez une nouvelle colonne et déposez la plus ancienne.

La division est une instruction à latence élevée, il peut donc être avantageux de masquer la latence mais avant d'y aller, la sortie du compilateur doit être inspectée si la division par constante est élidée et si le déroulement de la boucle (par le compilateur) fait déjà une compensation de latence.

Mais après l'optimisation la plus spectaculaire de l'utilisation du cache correctement ce sont vraiment des choses mineures.