Bobby Sixkilla
19/09/2006, 00h10
Optimisation du modulo
Auteur : Brunni
Voici une petite explication sur comment faire un modulo et une division à la main. Prenons le cas où on veut faire x%y. En gros, on voit qu'on peut faire ça très facilement, comme ceci:
while(x>=y)
x-=y;
Bien sûr ça devient très lent si x est grand. Alors le principe n'est pas compliqué, c'est d'abord de vérifier si x n'est pas supérieur à 4*y, ou 16*y, de manière à éliminer rapidement les plus grosses valeurs...
while(x>=4*y)
x-=4*y;
while(x>=y)
x-=y;
Ce qui donne par optimisation (décalages binaires):
while (x >= y<<2)
x-=y<<2;
while (x >= y)
x-=y;
Et on peut continuer en insérant également au début:
while (x >= y<<4)
x-=y<<4;
Afin d'accélérer le tout. Finalement, cela devient très simple: en partant de la valeur maximale souhaitée, on peut faire une vérification par échelons (puissances de 2). Cela donnerait, en reprenant le code plus haut, et en partant de 30, car on a 32 bits moins les deux premiers:
//Par étapes de 2
for (i=30;i>=0;i-=2) {
while (x >= y<<i)
x -= y<<i;
}
Je le fais par étapes de deux, mais je pourrais y aller par trois, par un, ou même plus. Ici, puisqu'on extrait 2 bits à la fois, le nombre d'itérations maximum pour chaque test est de 3 (11) et comme 16 groupes de bits sont vérifiés (de 30 à 0 par étapes de 2), ça fait au maximum 64 opérations, et 16 au minimum. Si je prends un seul bit à la fois, ça donne une seule itération maximum, mais 32 tests à effectuer (64 opérations au max, 32 au min), finalement plus lent dans presque tous les cas. Et si je prends trois bits à la fois, ça donne 7 itérations maximum par test, et 10 tests à effectuer (soit 80 opérations au max, 10 au min). On voit donc que la solution de prendre 2 bits à la fois est le meilleur compromis.
Voilà donc la routine que j'ai écrite, mais elle n'est pas réellement plus rapide que la routine originale. J'ai bien la version boucle déroulée en ASM quelque part mais elle prend beaucoup trop de place, je préfère cette routine, plus lente mais qu'on peut mettre en IWRAM pour gagner déjà pas mal par rapport à la routine intégrée:
unsigned int IN_IWRAM modulo(s32 i, u32 x, u32 y) {
//x%y
u32 j;
while((y<<i)==0)
i-=2;
for (;i>=0;i-=2) {
j=y<<i;
while(x>=j) {
x-=j;
}
}
return x;
}
//Modulo 32 bits ou 16 bits
#define mod32(x,y) modulo(30,x,y)
#define mod16(x,y) modulo(14,x,y)
Il faut appeler mod32 ou mod16 suivant que les nombres seront maximum sur 16 ou 32 bits.
Après je me suis demandé comment faire une division, et finalement c'est exactement identique (ce qui explique pourquoi les routines de division ou de modulo font presque toujours les deux en même temps). Il suffit d'ajouter à une variable le nombre de fois qu'on a enlevé y à x. Par exemple si on fait x-=y<<2, soit x-=y*4, ça veut dire que x contenait 4 fois y, soit 1<<2 (=4) en fait. J'ajoute cela à z qui est le résultat de la division:
unsigned int IN_IWRAM division(s32 i, u32 x, u32 y) {
//x%y
u32 j,z=0;
while((y<<i)==0)
i-=2;
for (;i>=0;i-=2) {
j=y<<i;
while(x>=j) {
x-=j;
z+=1<<i;
}
}
return z;
}
#define div32(x,y) division(30,x,y)
#define div16(x,y) division(14,x,y)
D'ailleurs même s'il n'est pas retourné, x contient x%y à la fin de cette fonction, et z=x/y.
Ce qu'on se rend compte après ça, c'est que la lenteur de la division et du modulo est variable, et dépend de la grandeur de x par rapport à y. Faire 12874834%5 sera très lent, mais 12874834%4894563 ou 27%5 déjà beaucoup moins. C'est un problème parce que si vos objets se déplacent selon un timer, le jeu aura tendance à ralentir au fur et à mesure que le temps passe (puisque la valeur du timer augmentera constamment).
Auteur : Brunni
Voici une petite explication sur comment faire un modulo et une division à la main. Prenons le cas où on veut faire x%y. En gros, on voit qu'on peut faire ça très facilement, comme ceci:
while(x>=y)
x-=y;
Bien sûr ça devient très lent si x est grand. Alors le principe n'est pas compliqué, c'est d'abord de vérifier si x n'est pas supérieur à 4*y, ou 16*y, de manière à éliminer rapidement les plus grosses valeurs...
while(x>=4*y)
x-=4*y;
while(x>=y)
x-=y;
Ce qui donne par optimisation (décalages binaires):
while (x >= y<<2)
x-=y<<2;
while (x >= y)
x-=y;
Et on peut continuer en insérant également au début:
while (x >= y<<4)
x-=y<<4;
Afin d'accélérer le tout. Finalement, cela devient très simple: en partant de la valeur maximale souhaitée, on peut faire une vérification par échelons (puissances de 2). Cela donnerait, en reprenant le code plus haut, et en partant de 30, car on a 32 bits moins les deux premiers:
//Par étapes de 2
for (i=30;i>=0;i-=2) {
while (x >= y<<i)
x -= y<<i;
}
Je le fais par étapes de deux, mais je pourrais y aller par trois, par un, ou même plus. Ici, puisqu'on extrait 2 bits à la fois, le nombre d'itérations maximum pour chaque test est de 3 (11) et comme 16 groupes de bits sont vérifiés (de 30 à 0 par étapes de 2), ça fait au maximum 64 opérations, et 16 au minimum. Si je prends un seul bit à la fois, ça donne une seule itération maximum, mais 32 tests à effectuer (64 opérations au max, 32 au min), finalement plus lent dans presque tous les cas. Et si je prends trois bits à la fois, ça donne 7 itérations maximum par test, et 10 tests à effectuer (soit 80 opérations au max, 10 au min). On voit donc que la solution de prendre 2 bits à la fois est le meilleur compromis.
Voilà donc la routine que j'ai écrite, mais elle n'est pas réellement plus rapide que la routine originale. J'ai bien la version boucle déroulée en ASM quelque part mais elle prend beaucoup trop de place, je préfère cette routine, plus lente mais qu'on peut mettre en IWRAM pour gagner déjà pas mal par rapport à la routine intégrée:
unsigned int IN_IWRAM modulo(s32 i, u32 x, u32 y) {
//x%y
u32 j;
while((y<<i)==0)
i-=2;
for (;i>=0;i-=2) {
j=y<<i;
while(x>=j) {
x-=j;
}
}
return x;
}
//Modulo 32 bits ou 16 bits
#define mod32(x,y) modulo(30,x,y)
#define mod16(x,y) modulo(14,x,y)
Il faut appeler mod32 ou mod16 suivant que les nombres seront maximum sur 16 ou 32 bits.
Après je me suis demandé comment faire une division, et finalement c'est exactement identique (ce qui explique pourquoi les routines de division ou de modulo font presque toujours les deux en même temps). Il suffit d'ajouter à une variable le nombre de fois qu'on a enlevé y à x. Par exemple si on fait x-=y<<2, soit x-=y*4, ça veut dire que x contenait 4 fois y, soit 1<<2 (=4) en fait. J'ajoute cela à z qui est le résultat de la division:
unsigned int IN_IWRAM division(s32 i, u32 x, u32 y) {
//x%y
u32 j,z=0;
while((y<<i)==0)
i-=2;
for (;i>=0;i-=2) {
j=y<<i;
while(x>=j) {
x-=j;
z+=1<<i;
}
}
return z;
}
#define div32(x,y) division(30,x,y)
#define div16(x,y) division(14,x,y)
D'ailleurs même s'il n'est pas retourné, x contient x%y à la fin de cette fonction, et z=x/y.
Ce qu'on se rend compte après ça, c'est que la lenteur de la division et du modulo est variable, et dépend de la grandeur de x par rapport à y. Faire 12874834%5 sera très lent, mais 12874834%4894563 ou 27%5 déjà beaucoup moins. C'est un problème parce que si vos objets se déplacent selon un timer, le jeu aura tendance à ralentir au fur et à mesure que le temps passe (puisque la valeur du timer augmentera constamment).