Acces memoire lent? - Page 1

Salut,

voila je viends de commencer à programmer sur la GP2X en utilisant la minimal lib, et je m'apercois que les acces mémoire sont relativement lent!! avez vous deja ete confronté a ce phenomene.

Mon programme n'est pourant pas tres gourmant en ressources c un rotozoom avec 4 additions par ligne et 2 additions par points plus quelque décalages.

Y a t 'il des solutions ou des contournements à cette lenteur? ou meme une explication..


voici le code+bin http://systemez1.free.fr/roto16bits.rar

d'avance merci

/ukko

-

Ben au niveau des angles les cos et sin sont préca donc ca devrait pas poser de probleme, car ca devient une simple lecture en mémoire

la dessu je ne pourrait repondre car je n'y connais pas en ASM ARM ou en performance materiel de la GP2x le seul lieu ou tu pourras avoir des reponses precises je penses serait le forum GP32x section Development [ GP2X ] et sous section I need help (dev stuff only) ou Developers' Corner [GP2X]

Salut,

Il y a en gros trois façon de faire ramer une architecture ARM :

- cache trashing (mauvaise utilisation du cache)
- utilisation abusive de divisions (attention, les modulos sont des divisions cachées)
- utilisation des floats dans la boucle du jeu (hors init donc)

Pour comprendre le cache trashing il faut savoir comment fonctionne le cache, petite explication :

Lors d'un acces memoire en lecture, la MMU (Memory Management Unit) verifie si l'adresse de la case memoire se trouve dans une zone "cacheable", si oui elle verifie si la case en question est déja dans le cache, si oui l'acces est quasi immediat (1 ou 2 cycles machine)

Si la zone est "cacheable" et que la case n'est pas deja chargée dans le cache, la MMU arrondis l'adresse en mettant les 5 bits de poid faible à zero et charge une ligne de cache entiere (32 octets) de la RAM vers le cache.

Suivant la frequence et la taille du bus (16 ou 32 bits suivant le type de RAM) la vitesse peut changer, mais on comprend bien que c'est BEAUCOUP plus lent qu'un acces direct dans le cache.

En general on considère qu'un acces hors du cache (cache miss) coute 10x plus cher en temps CPU qu'un acces dans le cache.

Pour un programme identique, au plus la taille du cache est importante, au moins le risque de cache miss est elevé, hélas sur GP2x la taille du cache est relativement faible (16Ko).

Dans le cas d'une ecriture, si la case se trouve déja dans le cache, seul le cache est mis à jour, si la case se trouve hors du cache, un acces en ecriture est effectué directement dans la RAM (lent donc) mais la MMU ne charge pas la ligne de cache entiere.

On comprend dès lors que le programmeur a tout interet à faire en sorte que son programme soit capable de "preloader" certains blocs memoire avant de travailler dessus, cela est surtout vrai pour les blitters bas niveaux qui sont generalement limités par la bande passante memoire.

La plupart des optimisations sur ARM consistent donc souvent a reduire la memoire occupée par les differentes ressources, et a faire en sorte de "sequentialiser" les acces, cad eviter au maximum de faire des lecture "aleatoires" qui multiplient les cache miss et ralentissent *considerablement* le CPU.

Il se trouve helas que GPH montre le mauvais exemple avec la GP2X, ils ont commis au moins deux erreurs logicielles :

- Le memcpy fourni par la lib C std integrée dans la distrib est non optimal (ma version perso tourne environ 2.5 fois plus vite)

- Le buffer video est configuré dans l'OS pour être "non cacheable", cad qu'AUCUN des acces dans la memoire video ne beneficie du cache.

Ils ont fait ça en sachant que le buffer video ne tient pas en entier dans le cache (16K vs 157K), donc pour eviter que le cache ne soit entierement renouvellé (plusieurs fois même) à chaque rafraichissement d'ecran, ben la zone est non cacheable, le cache peut donc être utilisé pour les autres acces memoire (variables globales, acces aux tableaux internes, mixer son..)

Seulement ils n'ont pas compris (j'en ai discuté directement avec eux) que les acces graphique constituent au bas mot 90% du temps CPU pour un jeu sur une console mobile, et que desactiver le cache dans la memoire video revient simplement a tuer les perfs.

La solution : reserver un back buffer perso (qui normalement est cacheable) et dessiner son ecran dedans, puis, ensuite copier tout cet ecran (avec un memcpy optimisé) vers le buffer video réel.

On perd du coup le page flipping hardware et l'acces au blitter 2D du chip graphique, mais pour ma part je n'utilise pas ce blitter que je trouve trop limité (pas d'alpha, pas de rotations, scaling etc...)

En arrivant a convaincre GPH de configurer la MMU differement on pourrait avoir tous les avantages, il existe aussi probablement une ruse pour le forcer depuis le programme, mais je n'ai pas trouvé comment....

Voila, en esperant que ces infos servent à quelques uns, je suis juste un peu etonné que personne ne semble s'en être rendu compte.

Sinon je viens de regarder ton code, il y a une petite optimisation a faire pour eviter deux additions dans la inner loop (l'angle peut etre inclu dans le couple u/v bien plus tôt).

Mais surtout il faut optimiser les acces memoire!

Ici on a une texture 256*256 en 16bits = 128Ko donc ne tient pas dans le cache.

Quand l'angle est proche de 0 les lectures de deux pixels consecutifs à l'ecran le sont aussi dans la texture, donc on ne fait en gros qu'un chargement de ligne de cache tous les 16 pixels (un ligne de cache = 32 octets donc 16 pixels).

Dans le cas ou l'angle est proche de 90° on tombe dans le cas inverse, les pixels consecutifs à l'ecran ne le sont jamais dans la texture, donc chaque acces donne lieu au chargement d'une ligne de cache depuis la RAM.

Il existe deux solutions :

La premiere consiste à developper ta boucle autrement, au lieu de balayer l'ecran par scanlines de 1 pixels de haut sur 320 de large, il faut le faire en petites boites, par exemple de 16 pixels par 16 pixels, je te laisse reflechir sur l'interet de cette methode.

Sinon tu peux transformer ta texture pour qu'elle occupe moins de memoire, par exemple en utilisant une palette (elle doit probablement passer en 16 couleurs avec un bon optimiseur de palette) et eventuellement en transformant la texture en "tiles".

Si bcp de parties de la texture sont identiques ou quasi identiques alors certains tiles seront repetés souvent, ce qui pourrait aider a fortement reduire le cache trashing.

cas ideal : faire en sorte que la texture prenne moins de 16Ko en RAM.

Pour t'en convaincre essaie donc avec une texture bcp plus petite, ou même en damier XOR codé en dur (sans acces RAM).

Tout d'abord merci pour ces reponses(ou explications)

J'ai bien notée cette histoire de cache qui faut imperativement prendre en consideration des l'ecriture du code, ce qui conditionne fortement les techniques(algo) utilisées.

Si j'ai bien compris tu préconise de passer par un backbufer géré "a la main" directement dans la mémoire, et ainsi permetre sont cache, mais ne pert on pas de temps par la suite en s'afranchissant du blitter et du page flip? quel sont les reels gains?

En ce qui concerene le code, je te l'accorde il est encore optimisable surtout maintenant apres ces diférentes explications, mais bon but n'etait pas la ,ce code n'est q'un pretexe comme un autre car je pensais naivement que ces quelques additions et acces mémoire ne poseraient pas de problemes et je souhaitait avoir une explication claire (comme tu vients de le faire dans ta premiere partie) à ces symptomes.

Encore merci d'avoir pris le temps d'ecrire une réponse si précise.

UKKO :
Si j'ai bien compris tu préconise de passer par un backbufer géré "a la main" directement dans la mémoire, et ainsi permetre sont cache, mais ne pert on pas de temps par la suite en s'afranchissant du blitter et du page flip? quel sont les reels gains?

C'est exactement ça, les gains sont tres importants, cela dit je ne les ai pas mesuré precisement, je dirais que c'est entre X2 et X3.

UKKO
En ce qui concerene le code, je te l'accorde il est encore optimisable surtout maintenant apres ces diférentes explications, mais bon but n'etait pas la ,ce code n'est q'un pretexe comme un autre car je pensais naivement que ces quelques additions et acces mémoire ne poseraient pas de problemes

La moindre operation dans la inner loop est couteuse, le mieux est de regarder le code assembleur generé et de voir comment reduire le nombre d'instructions utilisées pour ecrire chaque pixel, c'est tout l'art de l'optimisation bas niveau...

StephC_int13 :
La moindre operation dans la inner loop est couteuse...

qu'entends tu par la?


Au sujet du blitter d'apres ce que j'ai cru comprendre il ne permet que les copies de la memoire vers le buffer video et pas memoire vers memoire? est ce bien ca?

UKKO
:

StephC_int13 :
La moindre operation dans la inner loop est couteuse...

qu'entends tu par la?

Eh bien simplement qu'une simple instruction en trop dans la inner loop, si elle est appellée chaque fois qu'un pixel est dessiné, ça fait 240 * 320 * 60 = 4608000 cycles CPU de perdu par seconde. (pour un framerate à 60FPS)

Ces cyles correspondent en gros à 40 000 divisions par seconde, pour donner un ordre de grandeur, ça n'est jamais negligeable, donc les inner loop il faut y apporter une attention extreme, c'est pratiquement là que tout se joue (une fois que les pb de cache sont resolus)

Au sujet du blitter d'apres ce que j'ai cru comprendre il ne permet que les copies de la memoire vers le buffer video et pas memoire vers memoire? est ce bien ca?

Je ne sais pas, je n'ai pas tellement etudié les operations du chip graphique, en fait il serait peut être possible de lui faire faire le blit final, je n'en suis pas sûr.

C'est pas le bon plan de programmer un traitement graphiques en masse entièrement en C, forcement, ca va être lent, très lent !

Je te conseil de te diriger vers l'assembleur plutot que de chercher d'optimiser ton code C#, ca va t'ouvrir d'autre horizon et crois moi, l'asm c'est pas que du bleuf, ca booster fameusement ton code.

La solution idéal, c'est d'utiliser un backbuffering perso, ca te permet d'utiliser plus confortablement tes routines asm et ca te permet comme le souligne StephC, d'avoir plus de posibilité technique ( rotation, zoom, effet de lumière transparence, etc...)

sinon, il y a un petit truc en plus que tu peux optimiser sur ton code.

etant donné que dans ton code, l'orde n'est pas important, remplace :

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )
for(X=0;X<320;X++) par for(X=319; X--; )

ca booster legerement ton code lors de la compilation. c'est mieux que rien mais on vois un peu la différence, il y a quand même 76800 traitement par image, faut pas l'oublier.

-

c'est sur

Dans tous les cas il faut commencer par reflechir à l'algo tout en tenant compte des contraintes specifiques à la machine (ici processeur ARM, petit cache), coder en C, ameliorer tant que c'est possible, puis analyser le code produit par le compilateur, et decider si il est interessant de passer à une réimplementation en asm.

Dans certains cas on peut y gagner enormement, parfois presque rien, et souvent pas assez (par rapport à du code C correct) pour justifier le temps passé.

Le problème de l'assembleur est qu'il est plus long à tester (il faut le faire sur machine cible) et donc plus long a mettre au point, et helas assez peu de gens le maitrisent suffisament pour pouvoir ecrire plus efficacement qu'un compilo moderne.

Les fonctions qui s'y prettent le mieux sont les blitters, et les operations T&L en 3D, en gros les trucs que savent faire les puces 3D.

CoderMan :

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )
for(X=0;X<320;X++) par for(X=319; X--; )

En realité le compilateur arrive souvent à optimiser lui même ceci.

Mais c'est pas une mauvaise idée de le faire, en effet, enfin seulement dans la inner loop, pour le reste c'est negligeable.

StephC_int13
:

CoderMan :

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )
for(X=0;X<320;X++) par for(X=319; X--; )

En realité le compilateur arrive souvent à optimiser lui même ceci.

Mais c'est pas une mauvaise idée de le faire, en effet, enfin seulement dans la inner loop, pour le reste c'est negligeable.

Justement non, le compilateur ne sais pas interpréter si le code dans le for peut être utilisé à l'envers, c'est a dire en diminuant la variable X ou Y alors que celle ci est à la base incrémenté.

CoderMan
:

StephC_int13
:

CoderMan :

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )
for(X=0;X<320;X++) par for(X=319; X--; )

En realité le compilateur arrive souvent à optimiser lui même ceci.

Mais c'est pas une mauvaise idée de le faire, en effet, enfin seulement dans la inner loop, pour le reste c'est negligeable.

Justement non, le compilateur ne sais pas interpréter si le code dans le for peut être utilisé à l'envers, c'est a dire en diminuant la variable X ou Y alors que celle ci est à la base incrémenté.

Sisi, si les compteur de boucle ne sont pas utilisés dans la boucle, "le compilo" sait compter à l'envers.

Je l'ai verifié en analysant du code generé, il sait d'ailleurs faire des tas de trucs tordus mais manque souvent de bon sens, helas.

Cela dit, quand on dit "le compilo" c'est oublier de tenir compte qu'il en existe pas mal, et que les params de compilation peuvent changer le resultat.

Donc, certains compilos, dans certaines conditions, savent faire ce genre d'optimisation, donc le faire à la main c'est s'assurer que ce sera fait tout le temps.

De manière generale, il ne faut jamais faire une confiance aveugle a un compilateur, il faut aller verifier soit même le resultat.

-

StephC_int13
:

CoderMan
:

StephC_int13
:

CoderMan :

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )
for(X=0;X<320;X++) par for(X=319; X--; )

En realité le compilateur arrive souvent à optimiser lui même ceci.

Mais c'est pas une mauvaise idée de le faire, en effet, enfin seulement dans la inner loop, pour le reste c'est negligeable.

Justement non, le compilateur ne sais pas interpréter si le code dans le for peut être utilisé à l'envers, c'est a dire en diminuant la variable X ou Y alors que celle ci est à la base incrémenté.

Sisi, si les compteur de boucle ne sont pas utilisés dans la boucle, "le compilo" sait compter à l'envers.

Je l'ai verifié en analysant du code generé, il sait d'ailleurs faire des tas de trucs tordus mais manque souvent de bon sens, helas.

for(Y=0;Y<240;Y++) par for(Y=239; Y--; )

Je suis d'accord pour dire que certain compilateur optimise très bien mais dans ce cas là, c'est impossible, je penses pas que certains compilateurs soit capable d'interpreter le contenue d'une boucle de ce type.

// exemple ( qui ne rime a rien certe mais tout programme mérite son code, le compilateur ne décide pas si le programme est inutile ou pas )

for (x=0;x<63999;x++)
{
Video[x]=x;
Video[x+1]=1;
}

le résultat dans video sera { 0,1,2,3,4,5,6,7,8,..... };

{

Si certain compilateur compile automatiquement comme tu le prétend ca donne ceci

//
for (x=63999;x--)
{
Video[x]=x;
Video[x+1]=1;
}

le résultat dans video sera { 0,1,1,1,1,1,1,1,1,..... };

C'est pourquoi tu te trompe lorsque tu affirmes que certain compilateur optimise automatiquement ce genre d'optimisation.
Certain compilateur sont malin mais pas encore pour analyser entièrement le programme et ce que cela va donner.

Si tu fait de l'asm, tu sais que décrementer un registre pour créer un "for" et beaucoup plus rapide et personnellement, je préfère que le compilateur fait son travail d'optimisation avec un minimum d'optimisation c# vers ASM en aident en quelque sorte le compilateur a faire le bon choix.

CoderMan :


Si certain compilateur compile automatiquement comme tu le prétend ca donne ceci

//
for (x=63999;x--)
{
Video[x]=x;
Video[x+1]=1;
}


C'est pourquoi tu te trompe lorsque tu affirmes que certain compilateur optimise automatiquement ce genre d'optimisation.
Certain compilateur sont malin mais pas encore pour analyser entièrement le programme et ce que cela va donner.

Arf... Avant de contredire tu devrais peut être verifier au lieu de te baser sur des suppositions....

Tu devrais aussi faire attention à ce qui est ecrit, j'ai bien precisé que les variables compteurs ne doivent pas être utilisés dans la boucle (pour autre chose que compter le nombre de cycles)

Si tu fait de l'asm, tu sais que décrementer un registre pour créer un "for" et beaucoup plus rapide

Euh, petite precision, on parle de C ici et non de C#, on est d'accord ?

Sinon, pour être encore plus precis, la decrementation d'un registre dont le resultat est zero va armer un des flags d'etat du CPU, (le flag Z comme Zero) qui permet d'economiser un test donc un cycle machine dans la boucle.

Si la boucle contient 30 instructions, cette optimisation fera gagner 3.3%, difficile de dire que c'est "beaucoup plus rapide"

et personnellement, je préfère que le compilateur fait son travail d'optimisation avec un minimum d'optimisation c# vers ASM en aident en quelque sorte le compilateur a faire le bon choix.

Euh, je ne suis pas sûr de suivre, tu veux dire quoi exactement ?

Il n'existe à ma connaissance qu'une seule methode fiable pour aider le compilateur à optimiser : regarder le resultat et changer le source pour l'ameliorer....

Et rien de pire que de se baser sur des croyances ou suppositions plus ou moins bien fondées...

Heu stephC c'est toi même qui avance la supposition ./15

"En realité le compilateur arrive souvent à optimiser lui même ceci."

Je te démontre que ce que tu dis est faux avec un exemple.

pour le reste pas besoin de déballer un cours entier de prouver que cela ne sert a rien surtout quand je dis plus haut qu'il faut obligatoirement faire ces propres routines en ASM pour que cela soit rapide.

Et tu sais 3,3% par ci, 2% par là... au total ca crée quelques fps en plus...

et personnellement, je préfère que le compilateur fait son travail d'optimisation avec un minimum d'optimisation c# vers ASM en aident en quelque sorte le compilateur a faire le bon choix.

Euh, je ne suis pas sûr de suivre, tu veux dire quoi exactement ?

cherche de la documentation sur l'optimisation c, tu comprendras.

CoderMan :
Heu stephC c'est toi même qui avance la supposition ./15

"En realité le compilateur arrive souvent à optimiser lui même ceci."

Je te démontre que ce que tu dis est faux avec un exemple.

Non, ta demonstration est basée sur un exemple bidon, puisque il sort de ton imagination et pas du resultat d'une compilation réelle..

Et tu sais 3,3% par ci, 2% par là... au total ca crée quelques fps en plus...

Personne ne dit le contraire, mais il faut mesurer ses propos, a t'entendre on pourrait croire que c'est l'optimisation du siecle, le truc qui change tout, alors qu'il s'agit d'une economie de bout de chandelle, certes utile dans les inner loop tres courtes, mais tellement triviale que le compilo sait le faire lui même dans la plupart des cas.

Si tu ne sais pas verifier le code generé par un compilo je peux le faire pour toi et publier le resultat ici, si tu ne me crois pas sur parole.

cherche de la documentation sur l'optimisation c, tu comprendras.

Hahahaha

Enfin bon je vais pas argumenter ici indefiniment.....

Je rapelles a juste titre que c'est toi et toi seul qui a focalisé mon attention sur ce bout de code qui n'etait là que comme "bonus" au code d'EKKO.

Je pensais avoir affaire a quelque d'assez mature...je me trompe !

Tu affirmes quelques choses, je te prouve que non avec un "exemple débile". Apparemment, Monsieur aime critiquer mais n'aime pas être corriger.

Tout a était dit, je pense que les lecteurs de ce sujet auront compris, je trouve d'hommage de voir ce genre d'enfantillage lorsque l'on ne sait pas quoi répondre, le sujet est pour ma part clos.

je trouve dommage que vous vous emballiez pour si peu !
Arf un vrai exemple aurait été mieux voire carrément un "bench" au moins ca aurait été clair
Sinon coderman, juste pour info.. tu fais quoi dans la vie ?
t'as fais quoi comme étude ?

Car d'un coté on a un gars de int13 mais toi qui es tu ?

Sinon coderman, juste pour info.. tu fais quoi dans la vie ? t'as fais quoi comme étude ? Car d'un coté on a un gars de int13 mais toi qui es tu ?

Oula, j'ai fini les études d'info depuis bien longtemps !
Sinon ca veut dire quoi ?!? Que l'on doit obligatoirement coller unes étiquettes aux personnes pour pouvoir placer le niveau des propos ???

Je suis au courant que StephC13 vient de Int13, et alors ? est-ce une raison valable pour ne pas le corriger surtout si l'erreur en question est expliqué noir sur blanc ?

je trouve dommage que vous vous emballiez pour si peu ! Arf un vrai exemple aurait été mieux voire carrément un "bench" au moins ca aurait été clair

Un benchmark apparemment testé a été fait "Si la boucle contient 30 instructions, cette optimisation fera gagner 3.3%, difficile de dire que c'est "beaucoup plus rapide"

...

Voila ceci etait pour répondre à tes questions oeildefeu

ce n'est pas une attaque faut pas le prendre comme ca
Simplement vu qu'on ne connait pas tes compétences (celle de Steph son un peu prouvé par le fait qu'il travail chez int13) on ne peut connaitre le poids de tes propos..
Pis faisant parti d'autres forum défois on se retrouve a débattre contre un gars de 13 ans qui affirme des conneries.. au moins maintenant on sait que c'est pas ça !

oula!!! on s'écarte du sujet la

Bon voila un exemple rapide,


[code]
void clear1(PIXEL* dst)
{
Uint32 i, j;

for(j = 0; j < 240; j++)
for(i = 0; i < 320; i++)
{
*dst++ = 0;
}

}

clear1:

mov r2, #0
add r3, r0, #0x96, 22

clear1_loop:

strh r2, [r0], #2
cmp r0, r3
bne clear1_loop
mov pc, lr



void clear2(PIXEL* dst)
{
Uint32 i, j;

for(j = 239; j--; )
for(i = 310; i--; )
{
*dst++ = 0;
}

}


clear2:
mov r3, #0x95, 22
sub r3, r3, #0x5E
add r3, r0, r3
mov r2, #0

clear2_loop:

strh r2, [r0], #2
cmp r0, r3
bne clear2_loop|
mov pc, lr

[/code]

On voit que le compilo fait ce qu'il a de mieux a faire, fusionner les compteurs et utiliser un test sur le pointeur plutôt que sur un compteur de boucle, il est interessant de noter que le code C "optimisé" à la sauce CoderMan fait 2 instructions de plus sans pour autant être plus rapide....

Morale de l'histoire : verifier la sortie du compilo

Juste une petite question, c'est avec quel logiciel/desassembleur que tu vérifies la sortie en asm?

beersleep :
Juste une petite question, c'est avec quel logiciel/desassembleur que tu vérifies la sortie en asm?

Je demande simplement au compilo de sortir le listing assembleur.

La syntaxe differe suivant le compilateur, pour GCC il faut utiliser -S dans la ligne de commande pour lui dire de compiler sans assembler..

Faire un petit gcc --help pour voir tous les arguments dispo