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


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

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 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 vient avant. Aucun code ne vient après. Comme vous pouvez le voir, c'est juste l'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 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 n'en sais pas trop sur ce sujet, c'est pourquoi je demande ici.

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

Je sais déjà de 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.


690
2017-09-04 13:51


origine


Réponses:


La différence est provoquée par le même problème de super-alignement à partir 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;
    }
}

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 par colonne plutôt que par ligne.


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

Ceci élimine complètement tous les accès non-séquentiels, de sorte que vous n'obtenez plus de ralentissements aléatoires sur les grandes puissances-de-deux.


Core i7 920 à 3,5 GHz

Code original:

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

Outer-Loops interchangées:

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

872
2017-09-04 14:43



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é". La conclusion est donc que les optimisations des compilateurs prennent mieux soin de la micro-optimisation que les humains (enfin moi). Je laisse le reste de ma réponse pour référence.


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

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

Dans ce cas particulier, il vaut mieux calculer et mettre en cache horizontalement la somme des groupes de trois pixels car ils sont utilisés trois fois chacun.

J'ai fait quelques tests et je pense que ça vaut le partage. Chaque résultat est une moyenne de cinq tests.

Code secret par utilisateur1615209:

8193: 4392 ms
8192: 9570 ms

La version mystique:

8193: 2393 ms
8192: 2190 ms

Deux passes utilisant un tableau 1D: première passe pour les sommes horizontales, seconde pour la somme verticale et moyenne. 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 passes utilisant un tableau 1D et 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

Une passe en mémoire cache horizontale ne fait qu'une seule ligne avant de rester 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:

  • Pas d'avantages 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 préférable à leur calcul plusieurs fois.
  • Deux passes ne sont pas trois fois plus rapides, deux fois seulement.
  • Il est possible d'atteindre 3,6 fois plus vite en utilisant un seul passage et en mettant en cache un résultat intermédiaire

Je suis sûr que c'est possible de faire beaucoup mieux.

REMARQUE 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 du pseudo code. On m'a demandé de faire des tests dans les commentaires ... Voici une version complètement refactorisée avec des tests.


52
2017-10-11 12:08



L'ordre d'accès à l'élément pris en charge reste encore à portée de main. 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 consiste à savoir comment faire tomber la colonne la plus à gauche; lors de l'ajout d'une nouvelle colonne, rappelez-vous que c'est une valeur jusqu'à ce qu'elle sorte de la fenêtre d'échantillonnage.

Le coût avant: 9 lecture, 9 addition, 1 division Le coût après: 3 lectures, 3 addition, 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, donc il peut ê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 annulée et si la boucle déroulante (par le compilateur) fait déjà une compensation de latence.

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


-1