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

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

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

Ensuite, vous créez une matrice res[][], et chaque champ ici est fait pour être la moyenne des 9 champs qui l'entourent 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 tout ce qu'il y a au programme. Par souci d'exhaustivité, voici ce qui précède. Aucun code ne vient après. Comme vous pouvez le voir, ce n'est qu'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 SIZE est un multiple de 2048, par exemple 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 trop sur ce sujet, c'est pourquoi je pose la question ici.

De plus, comment résoudre ce problème 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.

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

• Pourquoi la transposition d'une matrice de 512x512 est-elle beaucoup plus lente que la transposition d'une matrice de 513x513?
• Multiplication de matrice: petite différence de taille de matrice, grande différence de synchronisation

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

En partant 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;
    }
}

Cela laisse donc 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 affecte-t-il les performances lors de l'itération sur un tableau 2D?

Vous itérez la matrice en colonnes plutôt qu'en lignes.

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 complètement tous les accès non séquentiels afin que vous n'obteniez plus de ralentissements aléatoires sur de grandes puissances de deux.

Core i7 920 à 3,5 GHz

Code d'origine:

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

Boucles externes échangées:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds

Les tests suivants ont été effectués avec le compilateur Visual C ++ car il est utilisé par l'installation par défaut de Qt Creator (je suppose sans indicateur d'optimisation). Lors de l'utilisation de 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 du compilateur prennent mieux soin de la micro-optimisation 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 des tableaux à une dimension. Le traitement de tous les pixels se fait en une seule boucle. L'accès aléatoire aux points pourrait se faire 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 cela 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 de Mystical:

8193: 2393 ms
8192: 2190 ms

Deux passes en utilisant un tableau 1D: première passe pour les sommes horizontales, seconde pour la somme verticale et moyenne. Adressage en deux passes avec trois pointeurs et uniquement des incréments comme celui-ci:

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 en utilisant un tableau 1D et un adressage comme celui-ci:

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

8193: 932 ms
8192: 925 ms

Une passe de mise en cache des sommes horizontales juste une ligne en avant pour qu'elles restent en 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)
• Il est préférable de mettre en cache des sommes horizontales que de 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.

REMARQUE Veuillez noter que j'ai écrit cette réponse pour cibler les problèmes de performances 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 un pseudo-code. On m'a demandé de faire des tests dans les commentaires ... Voici une version complètement refactorisée avec des tests.