Le context

J’ai récemment eu à traiter un problème de performance sur un algorithme assez simple de traitement d’image (détection de teinte dominante), et comme une des principales sources de problème était liée à l’accès à la mémoire (un problème que j’ai rencontré de manière assez récurrente dans ma vie de développeur), j’ai décidé d’en faire un poste.

Globalement, un algorithme de détection de teinte dominante demande de parcourir plusieurs fois chaque pixel de l’image pour établir la couleur “moyenne” de l’image, puis en sélectionnant la couleur d’un pixel de l’image la plus proche de cette moyenne.

Ce type d’opération est assez fréquent dans le monde du développement (des opérations assez simples sur une liste de données assez longue), et pour garantir de bonnes performances, il est essentiel de comprendre comment le processeur accède à la mémoire vive, afin d’organiser nos données en mémoire et les parcourir efficacement.

La démo

Pour illustrer cela, nous allons partir d’un exemple synthétique très simple : une fonction permettant de calculer la somme des racines carrées d’un tableau de “double” à 2 dimensions :

static double SumOfSqrtSquareMatrix(double[,] matrix, int edgeSize)
{
    double result = 0;
    for (int i = 0; i < edgeSize; i++)
    {
        for (int j = 0; j < edgeSize; j++)
        {
            result += Math.Sqrt(matrix[j, i]);
        }
    }
    return result;
}

Ce code est très simple : on parcours notre tableau, on effectue un calcul, et on agrège les résultats. En terme purement algorithmique, nous ne voyons pas vraiment d’opportunité d’optimisation.

Et pourtant, un développeur averti sur l’optimisation des accès à la mémoire trouvera très rapidement une optimisation redoutablement efficace pour des grandes valeurs de “edgeSize” :

static double SumOfSqrtSquareMatrixFixed(double[,] matrix, int edgeSize)
{
    double result = 0;
    for (int i = 0; i < edgeSize; i++)
    {
        for (int j = 0; j < edgeSize; j++)
        {
            result += Math.Sqrt(matrix[i, j]);
        }
    }
    return result;
}

La seule différence concerne la ligne 8 : matrix[j, i] est devenu matrix[i, j].

Avant d’expliquer pourquoi cela a de l’importance, voyons les performances obtenues (sur ma machine de dev), avec un edgeSize de 10000 :

Test ancienne version
00:00:01.7850279
00:00:01.7423263
00:00:01.7223322
00:00:01.7287703
00:00:01.7277380
00:00:01.7109888
00:00:01.6921702
00:00:01.7110170
00:00:01.6940506
00:00:01.6723361
Test nouvelle version
00:00:00.5146454
00:00:00.5054358
00:00:00.5009777
00:00:00.5038211
00:00:00.5036235
00:00:00.5057318
00:00:00.5100192
00:00:00.5081637
00:00:00.5034978
00:00:00.5039220
Press any key to continue . . .

On voit que la 2e version met à peu près 3.35 fois moins de temps (c’est plutôt pas mal vu le peu de modifications apportées).

C’est exactement le genre de chose que j’ai fait pour l’optimisation de code pour la détection de teinte dominante, et c’est à peu de chose prêt le même gain que j’ai pu observer.

Le pourquoi

Pour pouvoir travailler sur des données, le CPU doit les charger dans ses registres (petits espaces mémoires accessible directement aux unités de calcul etc.). A l’échelle du processeur, charger des données depuis la mémoire vive est une opération très longue, et depuis de nombreuses années, les fabricants de processeurs font donc appel à de la mémoire “cache” beaucoup plus rapide. La plupart du temps, on a même plusieurs étages de cache avec un cache L1 très petit mais très rapide, un L2 un peu plus grand et moins rapide, un L3 encore plus grand et moins rapide etc.

Quand le processeur doit atteindre une donnée, il regarde si elle est dans son cache de niveau 1. Si elle n’y est pas, il va chercher dans le niveau 2 etc. jusqu’au pire des cas, où il va chercher dans la mémoire vive. Quand la donnée est trouvée, avant d’être placée dans un registre du processeur, elle est aussi placée dans les caches de niveau plus bas que celui dans lequel elle a été trouvée. Mais pour éviter trop d’allers-retours entre les différents niveau de cache et la mémoire vive, elle n’est pas remontée seule, mais par bloc (dans les processeurs x86/x86-64bits modernes, ces blocs font en général 64 octets) : quand j’accède à matrix[i,j], un bloc de mémoire contenant matrix[i,j] ainsi que les 64 octets de données stockées à côté est chargée en cache et les données proches de matrix[i,j] dans le tableau sont donc accessibles très rapidement par le processeur (car elles ont été montées en cache).

La première version de l’algorithme (accédant à matrix[j, i]) accédait de manière non linéaire à la mémoire, et du coup, le nombre de “cache miss” était beaucoup plus important que dans la version corrigée (car matrix[j+1, i] est beaucoup plus loin de matrix[j,i] que matrix[j, i+1]). La deuxième version accède quand à elle de manière totalement linéaire à la mémoire (on parcourt le tableau dans l’ordre dans lequel il est stocké en mémoire vive) et on a donc beaucoup moins besoin d’aller charger des données depuis la mémoire vive ou depuis les caches de haut niveau (plus lents que le cache L1).

Conclusion

On a pu voir dans cet exemple que l’ordre dans lequel on parcours des objets en mémoire a un impact énorme sur les performance d’un algorithme. Voici les règles générales qu’on peut en déduire:

• Globalement, essayer de favoriser les accès mémoire linéaires
• Pour ceci, parcourir les tableaux (ou List<T> C#, vector<T> c++…) dans leur ordre naturel
• En .Net, préférer les listes de structures que de classes comme source de données pour nos algorithmes (car un tableau de structure garantie que les différents éléments soient placés de manière contigüe en mémoire)
• De la même manière, en C++, préférer des tableaux d’objets que des tableaux de pointeur vers des objets comme source de données pour nos algorithmes