1. Introduction

2. Les invariants de boucle

for (int x=0; x<WIDTH; x++)
{
    for (int y=0; y<HEIGHT; y++)
    {
        DWORD offset = (WIDTH*y + x)*4;
        if (*(pScreen + offset) != 0x00FF00FF)
        {
            *(pScreen + offset) = MAKE_COLOR( f1(x,y), f2(x, y), f3(x, y) );
        }
    }
}

Cet exemple très simple rempli l'écran de couleurs issues de fonctions f1, f2 et f3 définies ailleurs. par exemple : f1(x, y) = 3*cos(x) + 6*sin(x+y)*cos(y)

Nous avons 2 multiplications pour calculer l'offset à chaque itération. Développons :
    offset = 4*WIDTH*y + 4*x
La première partie peut donc être sortie de la boucle intérieure.

for (int y=0; y<HEIGHT; y++)
{
    DWORD offset = WIDTH*y*4;
    for (int x=0; x<WIDTH; x++)
    {
        if (*(pScreen + offset + x*4) != 0x00FF00FF)
        {
            *(pScreen + offset + x*4) = MAKE_COLOR( f1(x,y), f2(x, y), f3(x, y) );
        }
    }
}

Voilà déja un multiplication sortie de la boucle intérieure. Continuons : y est incremente a chaque itération. Donc offset grandi de 4*WIDTH à chaque itération. et pourquoi multiplier x par 4 à chaque fois ? Donc nous utiliserons des additions :

DWORD offset = 0;
for (int y=0; y<HEIGHT; y++)
{
    for (int x=0; x<4*WIDTH; x+=4)
    {
        if (*(pScreen + offset + x) != 0x00FF00FF)
        {
            *(pScreen + offset + x) = MAKE_COLOR( f1(x,y), f2(x, y), f3(x, y) );
        }
    }
    offset += 4*WIDTH;
}

Nous pouvons maintenant supprimer l'addition superflue : offset+x.

DWORD offset = 0;
for (int y=0; y<HEIGHT; y++)
{
    for (int x=0; x<4*WIDTH; x+=4)
    {
        if (*(pScreen + offset) != 0x00FF00FF)
        {
            *(pScreen + offset) = MAKE_COLOR( f1(x,y), f2(x, y), f3(x, y) );
        }
        offset += 4;
    }
}

Et voilà, notre boucle ne contient plus qu'une addition au lieu d'une addition et de deux multiplications pour le calcul d'offset. Maintenant, vous pouvez regarder si vos fonctions f1, f2, f3 ne peuvent pas se modifier de la même facon que pour le calcul d'offset (pour sortir de la boucle le maximum de calculs).

Nous pouvons poursuivre en évitant d'effectuer à chaque fois certaines opérations ... comme le calcul de l'adresse mémoire de destination par exemple...

DWORD _pScreen = pScreen;

for (int y=0;y<HEIGHT; y++)
{
    for (int x=0; x<WIDTH; x++)
    {
        if (*_pScreen != 0x00FF00FF)
        {
            *_pScreen = MAKE_COLOR( f1(x,y), f2(x,y), f3(x,y) );
        }
        _pScreen++;
    }
}
 

3. Derouler les boucles

Pourquoi gagne-t-on ? Et bien on gagne "n" fois l'opération de calculer une expression et "n" fois un branchement.

Petit exemple :

ptr_dst_end=ptr_dst+max_x;
while (ptr_dst<ptr_dst_end)
{
    *ptr_dst++=*ptr_src++;
}

si on est sur que "max_x" est une valeur paire :

ptr_dst_end=ptr_dst+max_x;
while (ptr_dst<ptr_dst_end)
{
    *ptr_dst++=*ptr_src++;
    *ptr_dst++=*ptr_src++;
}

Si votre processeur n'a pas de fonctions de "post incrémentation", il peut être plus efficace de faire :

ptr_dst_end=ptr_dst+max_x;
while (ptr_dst<ptr_dst_end)
{
    ptr_dst[0]=ptr_src[0];
    ptr_dst[1]=ptr_src[1];
    ptr_dst+=2;
    ptr_src+=2;
}

Notons qu'aujourd'hui, dérouler les boucles n'amène plus ou très peu d'amélioration des performances sur les processeurs munis de cache (plus de code, plus d'utilisation de cache) et les branchements conditionnels sont prédits par les processeurs x86 depuis le Pentium, puis améliorés sur Pentium Pro. (Les processeurs Pentium II proposent même des instructions d'affectation conditionnelle évitant les branchements, mais ceci sort du cadre de l'article)
 
 

4. Les accès mémoire, première tournée : VRAM vs RAM

for (int x=0; x<WIDTH; x++)
{
    if (*pScreen != 0x00FF00FF)
    {
        *pScreen = MAKE_COLOR( f1(x,y), f2(x, y), f3(x, y) );
    }
    pScreen++;
}

Une autre optimisation consisterait à s'interroger sur le type de mémoire accédé par _pScreen : RAM ou VRAM ?

Dans le cas de la RAM, celle-ci est "cachée" (et de manière très spécifique à chaque modèle de processeur : l'écriture ne fait pas rentrer l'adresse de destination dans le cache, la lecture si sur processeurs Pentium, mais l'écriture fait rentrer l'adresse destination dans le cache depuis le Pentium MMX.)

La VRAM, elle, n'est pas cachée. L'écriture dans la VRAM est très lente (de quelques à quelques dizaines de cycles) et elle est bufferisée par le bus pour des écritures consécutives en fonction de l'alignement (2, 4 ou 8 octets.) Par "écriture bufferisée" je veux dire que le fait d'écrire dans la VRAM est non bloquant : le processeur exécute les instructions suivantes sans ralentir, sauf s'il écrit à nouveau dans la VRAM alors que l'écriture précédente n'est pas encore terminée. Par contre, la lecture, elle est super lente et bloquante.

Ainsi, la lecture à l'adresse _pScreen peut donc être très pénalisant en VRAM par rapport à la RAM. Dans l'état actuel, _pScreen a donc intérêt à pointer en RAM. Par contre, si on avait évité cette lecture, il aurait été plus intéressant de pointer directement en VRAM, les écritures y étant parallélisées avec le calcul du pixel suivant dans la macro MAKE_COLOR() (enfin, ceci dit, si on fait des sinus et cosinus dedans, la différence de vitesse n'est plus du tout justifiée, mais alors les autres optimisations non plus.)

5. Les accès mémoire, deuxième tournée : la mémoire cache

Ensuite il y a des spécificité différentes selon les processeurs, par exemple sur pentium, tans que toute la ligne de cache n'est pas chargée le processeur est bloqué, par contre sur pentium2 et processeurs suivants, dès que la valeur requise est dispo dans le cache du processeur il la lit, se debloque, et le reste de la ligne de cache se charge en parallèle avec l'execution par le processeur des instructions suivantes.

Cas interessant, si les blocs ont une largeur multiple de la taille d'une ligne de cache, et que leur adresse de depart soit alignée sur la taille d'une ligne de cache, et que la taille d'un bloc soit inférieure ou egale à la taille du cache de ton processeur ... et bien la vitesse de lecture sera indépendante de l'ordre de lecture des valeurs dans le bloc.

Nous pouvons donc voir cela :
Si vous avez "n" boucles, vérifiez qu'elles sont dans un sens optimal. Typiquement, les routines graphiques sont de ce type:

for (y=0;y<max_y;y++)
{
    for (x=0;x<max_x;x++)
    {
        DoSomething(x,y);
    }
}

Mais j'ai déja vu ca:

for (x=0;x<max_x;x++)
{
    for (y=0;y<max_y;y++)
    {
        DoSomething(x,y);
    }
}

Et ca, c'est mal. Ca veut dire qu'on accede a la mémoire de facon désalignée (sauf si vous avez stocké votre image en YX au lieu de XY, mais c'est rare :), et donc le cache passe son temps a lire et a flusher a chaque pixel au lieu de ne le recharger qu'une fois tous les "n" pixels.

Cependant, comme le dit Tuo :
"Ca (l'inversion des boucles) peut etre interessant pour du texturing soft par exemple... un peu comme le (très) célèbre rotozoom ecrit par pascal / cubic team qui cartonnait (on n'a pas fait mieux depuis sur PC je pense). A ce moment, le tiling peut etre TRES interessant, car la lecture dans la texture n'etant pas lineaire, puisque dependant de l'angle que l'on applique dans son rotozoom, il est parfois plus interessant de changer de sens de remplissage (vertical au lieu de horizontal par exemple), en faisant un tile : en effet, du coup dans chaque tile l'ecart en mémoire entre les données lues diminue considérablement par rapport au fait de le faire lineairement, et donc le cache fonctionne un (bon) peu mieux. Ce qui explique d'ailleurs pourquoi le rotozoom de Cubic Team ne ralentissait quasiment pas quand il tournait, contrairement a une implementation plus basique :)"
 
 

6. Conditions de sortie

for (x=0;x<320;x++)    {}

C'est moins efficace que:

x=320;
while (x--)    {}

Parce que TOUS les processeurs (ok, au moins les x86, les 68k, les SHx, les Rx00, le 6502, etc...) savent comparer avec la valeur "0" en un test, alors que pour compare avec "320", il y a un chargement de valeur immédiate suivit d'une soustracation. Alors il vaut mieux charger 320 une fois et vérifier si on arrive a zéro.

7. Conclusion

Je laisse la conclusion a Kwa : "Remarquons que ces optimisations doivent être vues à titre d'éducation ou de sensibilisation et non comme un exemple jusqu'au boutiste à appliquer systématiquement rendant certains morceaux de code difficiles à suivre. Si je doute qu'aucun compilateur ne fasse d'optimisations poussées sur le cache (comme une réorganisation de boucles x et y), les optimisations à base de déplacement des constantes en dehors de la boucle est fait par les compilateurs C/C++ depuis de très nombreuses années."
 

Document "Optimisation des boucles", daté du 21-03-2001

Auteur :
    Vincent Prat "Gore" (http://vprat.ifrance.com/) (vprat@ifrance.com)

Collaborations précieuses :
    Fabien Allaine "Arthur" (http://www.arthie.net/)
    David Alloza "Oxythan" (e-mail)
    Jean-Michel Hervé "Tuo" (http://tuo.planet-d.net/)
    Matin Korolczuk "Kwa" (http://programland.planet-d.net/)
    Mickael Pointier "DBug" (http://www.defence-force.org/computing/oric/dbug/index.htm)
 

Merci de ne pas modifier cet article sans l'accord de son auteur. (c) Vincent PRAT 2001