Salut à tous,
 
J'ai implémenté il y a peu un décodeur audio et je me suis trouvé face à un problème de performance. Mon patron m'a conseillé de remplacer mes adressages de matrices/tableaux (tab[x][y]) par un pointeur que j'incrémente (ptr+xx).
 
J'ai trouvé cela étonnant, mais comme on en apprend tous les jours...Bref, j'ai quand même décidé de tester cela avant de modifier 20.000 lignes de code.
Code de test :

Résultat des courses en optimisation -O3 :
T1 = 531
T2 = 532
 
Ai-je loupé quelque chose ou est-ce que les deux modes d'adressage se valent ?
 
Merci d'avance.
 
Cordialement,
Sébastien.

tu as raté quelque chose en effet, car c'est strictement la même chose. Ton patron voulais sans doute parler de l'allocation mémoire :
 
# #define SIZE 10000
#
# float tab[SIZE][SIZE];
# float tab2[SIZE][SIZE];
 
 
regarde du côté de malloc() et de free()

Au niveau de l'allocation des deux tableaux, il s'agit juste d'un exemple ici.

Mon patron me parlait bien de la vitesse d'adressage.

Pour en revenir à la question de base, il me semble que la seule chose que fasse le compilateur lorsqu'il tombe sur des [][] est de les remplacer par l'addition correspondante par rapport à l'adresse de base du tableau/matrice, c'est ça ?

Edit : En fait son argumentation tenait au fait que tab[x][y] implique une multiplication et deux additions à chaque passage de boucle (tab + (x * size + y)), alors que ptr++ n'implique d'une incrémentation.

Mon autre patron argumenta qu'avec les optimisations du compilateur, cela ne devrait pas entrer en ligne de compte.

Edit2 : Effectivement, en réalisant le test sans optimisation :
T1= 1031
T2= 797

Donc j'imagine qu'au final il est vrai que ptr++ est plus rapide que tab[][], mais qu'une fois les optimisations du compilateur activée, la différence est alors infime/nulle.

Encore des FUDs ... L'acces par pointeur lineaire est la pire des façons vu qu'elle va pas plus vite que celle en [][] et est plus chiante à utiliser.

cf ces sujets :
http://forum.hardware.fr/hfr/Progr [...] 9389_1.htm
http://forum.hardware.fr/hfr/Progr [...] 0227_1.htm

En gros, un tableau 2D ca s'alloue via un bloc contigue + 1 tableau de pointeur sur ligne. En terme de code résultant, y a pas plus de *+ qu'avec l'autre vu qu'elles sont précalculées.

cf aussi : http://codepad.org/nDy8z2iG

Autre chose, le "temps d'adressage" on s'en fout. C'est le respect des caches qui est important.Apres, regarde du coté du déroulage de boucle, fusion de boucle, jam & roll loop. Si ca suffit pas SSE2+ ou Altivec en fonction du Proc et oepnMP si tu as plus de 1 coeur

Pour les problèmes de performances, plutôt que de faire des tentatives hasardeuses pour tenter de débusquer le problème, je préconiserais plutôt l'utilisation d'un profiler (prof ou gprof pour les plus basiques, mais il y en a d'autres, par exemple analyzer/collect sous Sun).

Ça permet de faire des statistiques sur les appels, de voir très simplement où se situent les goulots d'étranglement, et de cibler les optimisations là où elles comptent vraiment.

PAPI aussi

Merci pour les infos.

J'ai jamais entendu parler d'aucun de ces termes/techniques, donc je vais essayer de jeter un oeil et voir ce que je peux en faire. Je suis ingénieur électronique débutant donc les optimisations avancées, ça me passe un peu haut dessus de la tête. xD

Oui j'ai déjà fait ça avec valgrind (callgrind), mais j'arrive à un point où je n'ai pas une fonction qui prend plus de 3-4% de la puissance de calcul...

Merci pour vos conseils en tout cas.

edit :

Cela est-il vraiment gênant de déclarer le tableau de pointeur sur une ligne, et d'allouer à chaque pointeur une zone mémoire indépendante ?

edit2 : Bon, évidemment, c'pas bon pour le cache.

Voila
 
Le cache c'ets le truc qui fait la difference entre un code et un code efficace, parfois avec un facteur 10.

J'aurais ptet du regarder plus attentivement le relevé des "cache miss" de Valgrind. Je jetterai un oeil demain matin.

N'ayant aucune idée des ordres de grandeur, à partir de combien de % de cache miss peut-on considérer qu'il y a un problème à ce niveau ?

ca depend. En gros, vire les cache misses des grosses boucles le reste tu t'en tapes mais cachegrind te file tout. Ensuite rebench et affine.
 

J'ai été occupé hier, donc j'ai reporté Valgrind à ce matin, résultats :

Je ne suis pas spécialiste mais j'imagine qu'avec moins de 1% de misses, ça ne doit pas influer beaucoup sur les perfs.

Merci pour les conseils en tout cas, au moins je n'aurais pas de regrets en me disant que j'aurais pu remplacer mes [][] par des pointeurs ou supprimer les cache misses.

Ca me parait pas mal.
Est-ce pour juste les boucles cirtiques ou toutes l'appli ?
 
Apres si t'as trjrs des pb de perfs y a plein d'astuce que je peut te donner mais faudrait que je voit la forme général de tes calculs.

Toute l'appli.
Et j'ai fait le tri par fonction, il n'y en a aucune avec un % de cache miss incroyablement haut par rapport aux autres.
 
Malheureusement pour les soucis de perfs, je suis en stage et il ne me reste que 3 semaines pour m'en occuper (d'autant plus qu'il me reste la moitié de l'appli à porter en fixed-point...). Mes patrons ont donc jugé que ce serait difficile d'obtenir une appli assez optimisée pour tourner sur un ARM et je vais donc passer le temps qu'il me reste à rédiger mon rapport.
 
Pour des raisons de copyrights, je ne peux pas te montrer mon code source, et vu que le standard AAC est payant, je vois mal comment t'indiquer la forme des calculs.
 
Merci pour ton aide.

Sinon vu que ta matrice elle est static, tu supprimes ta boucle de mise à 0 et c'est encore plus rapide :tirelangue

J'ai quand même du bol que sur 40.000 lignes de code, je n'ai que des boucles de mise à zéro.