Pourquoi le bouclage sur un tableau de 8192 éléments ralentit-il soudainement mon programme ?

Pourquoi le programme ralentit lors d'une boucle sur 8192 éléments

Considérez l'extrait de code suivant :

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; // result of mean filter

int main() {
    // Initialization
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            img[j][i] = (2 * j + i) % 8196;
        }
    }

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

Ce code présente variabilité des performances en fonction de la valeur de SIZE, comme le montre son exécution fois :

• TAILLE = 8191 : 3,44 secondes
• TAILLE = 8192 : 7,20 secondes
• TAILLE = 8193 : 3,18 secondes

Comprendre le Problème

La différence dans les temps d'exécution peut être attribuée à un problème connu appelé super-alignement :

• Lorsque SIZE est un multiple de 2048 (c'est-à-dire 8192 dans ce cas), l'accès aux éléments dans des modèles spécifiques déclenche une mémoire moins efficace disposition.

Gestion de la mémoire

Malloc/free n'est pas directement responsable de la différence de performances.

Ordre de boucle externe

Un autre problème clé dans ce code est l'ordre des boucles extérieures. Le code d'origine parcourt la matrice par colonne, tandis que l'itération par ligne est plus efficace pour l'accès à la mémoire.

Solution

Pour atténuer le problème de performances, les boucles externes doit être interchangé :

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

Performance Amélioration

Après avoir interchangé les boucles extérieures, les performances s'améliorent considérablement :

• TAILLE = 8191 : 0,376 seconde
• TAILLE = 8192 : 0,357 seconde
• TAILLE = 8193 : 0,351 secondes

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!