Optimisation des compilateurs/Les optimisations liées à la hiérarchie mémoire

À l'heure actuelle, la majorité des instructions d'un programme sont des accès mémoire, et non des instructions de calculs ou des branchements. Et cela a une conséquence assez fâcheuse : obtenir de bonnes performances demande de faire bon usage de la hiérarchie mémoire, que ce soit au niveau du compilateur ou du programmeur. C'est pour cela que les compilateurs disposent d'optimisations assez intéressantes, qui permettent d'exploiter correctement les structures de données choisies par le programmeur. Ce chapitre va aborder ces optimisations, et vous expliquer en quoi elles consistent.

La re-matérialisation

Il arrive souvent que l'on n'ait pas assez de registres pour stocker des variables temporaires. Dans ce cas, le contenu de certains registres est alors sauvegardé sur la pile pour une utilisation ultérieure : on parle de spilling. À ce petit jeu, les programmeurs assembleurs disposent d'une optimisation dont aucun compilateur actuel n'est capable : ils peuvent sauvegarder les registres, non pas sur la pile, mais dans les registres MMX ou SSE. Mais si cette optimisation n'est pas possible automatiquement, il vaut mieux recalculer certaines variables temporaires que de les mémoriser temporairement dans un registre : on parle de rematérialisation. Cette optimisation est en quelque sorte l'inverse de celle qui supprime les expressions redondantes.

Les optimisations des parcours de tableaux

Dans la plupart des cas, les compilateurs ne peuvent pas changer les structures de données en d'autres, plus adaptées aux hiérarchies mémoires actuelles. À la place, les compilateurs optimisent les parcours de tableaux : ils changent l'ordre de parcours des tableaux, ou le sens de traversée. Pour cela, ils modifient les boucles qui permettent de faire ces parcours. C'est pour cela que les optimisations que nous allons voir vont toutes impliquer des boucles, au point qu'elles auraient parfaitement eu leur place dans le chapitre précédent. Cette optimisation permet de gagner assez facilement en performances, parfois d'un facteur 10, parfois plus.

Le changement de l’ordre des boucles

L'optimisation consiste à changer l’ordre des boucles entrelacées, histoire de parcourir les tableaux ligne par ligne, au lieu de les traverser colonne par colonne. Pour comprendre ce que fait cette optimisation, il faut savoir que les langages de programmation usuels stockent les tableaux de tableaux ligne par ligne : des données d'une ligne sont consécutives en mémoire, et les lignes sont placées les unes à la suite des autres en mémoire. Dans ces conditions, il vaut mieux parcourir les tableaux ligne par ligne, histoire de profiter de la mémoire cache du processeur et de diverses techniques de préchargement (prefetching). D'autres langages fonctionnent colonne par colonne.

L'optimisation d'échange de boucle demande juste d'échanger une boucle externe avec une interne, afin de respecter le principe de localité : cela permet d’éviter à la mémoire cache de chercher des lignes de données d’une itération à une autre. Considérons l’exemple d’un tableau à deux dimensions et qu’on dispose du code suivant pour le remplir :

   For i from 0 to 10 
   For j from 0 to 20
     A [i,j]= i + j

Ce code peut être optimisé de la sorte avec ce type d’optimisation :

   For j from 0 to 20
   For i from 0 to 10
     A [i,j]= i + j

Un défaut de cette optimisation est qu'elle dépend de la technique du cache utilisée et de la disposition du tableau dans la mémoire utilisée par le compilateur. Elle ne s'applique pas de la même manière selon que le langage stocke les tableaux de tableaux ligne par ligne ou colonne par colonne, par exemple. De plus, elle ne fonctionne que quand le compilateur peut prouver que la modification n'a pas d'effet de bord, ce qui n'est pas toujours possible. Par exemple, le compilateur n'a pas le droit de le faire dans un cas pareil :

for (int i = 0; i < nbLignes; ++i)
{
    for (int j = 0; j < nbColonnes; ++j)
    {
         tab[i][j] = fonction(i,j);
    }
}

La fusion de boucles

Elle fusionne plusieurs boucles en une seule. Exemple en C :

int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
  a[i] = 1;                     
}
for (i = 0; i < 100; i++)
{
  b[i] = 2;
}

L’exécution de ces deux boucles séparées est équivalent au code suivant :

int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
  a[i] = 1; 
  b[i] = 2;
}

Cette technique optimise le temps d’exécution du programme. En outre, il y a une technique similaire appelée fission de boucle qui consiste à exécuter une seule boucle en deux boucles et qui optimise l’utilisation de mémoire et donc qui applique mieux le principe de localité.

La division de boucles (« Loop splitting » ou « loop peeling »)

C’est la division d’une boucle en plusieurs autres boucles ou bien la suppression de dépendance. Cette technique consiste à faire l'inverse de la fusion de boucle : des boucles qui itèrent sur des tableaux différents sont scindées en deux. Ainsi, chaque boucle travaillera indépendamment sur chaque tableau d'un bloc (on parcourt un tableau puis l'autre). Cette technique améliore la localité et la gestion du cache comparé à une seule boucle qui piocherait les données dans un tableau puis dans l'autre. Suivant la situation, cette optimisation sera plus ou moins efficace par rapport à la fusion de boucle : le compilateur dispose d'heuristiques pour déterminer quand utiliser telle ou telle optimisation suivant la situation.

Un cas simple et spécial de cette technique consiste à supprimer une première itération complexe de la boucle et de la mettre à l’extérieur de cette dernière.

Voici un exemple de « loop peeling ». On suppose que le code original est :

For j from 1 to 20
  A [j] = A [1] + B [j]

Comme cette affectation du tableau A dépend du tableau A lui même, le compilateur ne peut pas utiliser le parallélisme en toute sécurité. Pour cela, il supprime l’affectation problématique de A[1] de l’intérieur de la boucle et la met à l’extérieur.

On obtient donc après ce type d’optimisation :

A [1] = A [1] + B [1]
For j from 2 to 20
  A [j] = A [1] + B [j]

La valeur de A[1] issu du premier calcul peut ensuite être stockée en registre pour l'utiliser à chaque itération de la boucle.

Cette technique d’optimisation est introduite dans le compilateur gcc dans la version 3.4.