J'aurais besoin de vos conseils sur les conteneurs.
 
En C/C++ , j'ai besoin d'avoir des données stockées selon 5 paramètres indépendants.
 
Logiquement de base j'ai tenté un tableau a 5 dimensions en C, alloué en mémoire avec 5 boucles de malloc.
 
Le problème c'est qu'en acces c'est extremement lent. Seulement je ne vois pas comment faire autrement.

C/C++ n'est pas un langage !
 
Une base de données ?

pardon ?
 
 
 
est ce que cela te conviendrait ?
http://boost.org/libs/multi_index/doc/index.html
 
une base de donnée serait effectivement une bonne solution.

+1 sur le post de Darkalt, tu devrais préciser exactement ton langage.
 
Faudrait voir comment tu fais, parce que récupérer un élément dans un tableau type C pour un index donné, c'est instantané. En C++, le vector devrait correspondre à ce que tu cherches.
Si par contre ton code rame pour trouver un élément, c'est un tout autre sujet.
 
Edit: C est un langage. C++ est un langage.
Mais il faudrait savoir de quoi on parle. C/C++ ça veut rien dire...

Ben oui, on a le C et le C++, mais pas C/C++.

oki ^^

Arf non BDD c'est pas trop possible. C'est pour faire de la compression vidéo.
 
Je vous mets un bout de code sur ma fçon de malloc mon tableau , de le remplir , et la maniere dont j'y accede.
 

Parce que c/c++ n'est pas un langage.
Je ne suis pas assez clair ?

vector! Et si tu récupères une valeur hors champ, ton appli part dans les choux là
Et mis à part cette considération C++, tu es sûr que c'est la récupération d'une valeur qui prend du temps? Le lookup est quasi instatané si on vire les adressages qui sont de toutes façon difficilement compressible.
Si c'est ça qui pose souci, t'es bon pour faire un tableau 1D qui sera un tantinet plus rapide, mais faut vraiment que tu sois sûr que c'est cette partie qui rame... ce dont je doute légérement.

si si c'est bien cette partie, moi non plus je m'y attendais pas.
 
Le pire c'est que si je ne fais pas appel aux données calculées, mais si je calcule les formules des cosinus dans mon result = bla bla bal, j'obtiens un temps d'execution inférieur...
 
Pour ce qui est par contre de taper en dehors des indices des tableaux, ca y'a pas de risques  

vous me conseillez d'imbriquer des vectors  en fait ?

J'ai peur de pas comprendre: tu dis bien qu'avec ton code, le calcul d'un cos est plus rapide qu'une indexation? Tu as mesuré comment? Sur combien d'éléments?
 
Fais des tests avec un vector 1D puis un tableau 1D aussi tant qu'à faire.
 
(par contre, je suis pas le mieux placé pour t'aider à ce niveau je pense, mais ça m'intrigue un tantiner )

oui c bien ce que je disais irmat, mais c super bizarre. Meme carrément illogique.
 
La je susi en train de refaire deux versions épurées pr comparer.L'une avec un tableau de double à 5 dim , et l'une avec 5 vectors imbriques

deja passe à un conteneur mono dimensionnel avec dim1*dim2*dim3*dim4*dim5 éléments,
ça t'evitera de te tapper 5 niveaux d'indirections T_T et des milliards de cache misses.

Finalement avec 5 vectors c'est pas jouable du tout , c'est 3-4 fois plus lent qu'en tableaux.
 
Sinon j'ai trouvé d'ou venaient mes pb de lenteur : J'étais resté en mode Debug sous Studio. En release, ca va 3-4 fois plus vite.
 
Par contre Joel je vois pas comment je pourrais faire en une seule dim.
 
Imagine j'ai x = 1 et y = 2 et aussi x = 2 et y = 1
 
tab[1 *2] ca sera pas la meme chose que tab[2 * 1], a moins qu'il y ait une subtilité que j'ai pas captée

exemple simple : un tableau 2D de 5 lignes par 6 colonnes,
tu stockes les lignes les unes derriéres les autres dans un  
tableau de 5*6 = 30 éléments. L'accés à la ie ligne/je colonne se fait via tableau[j + i*6]. En gros tu remplaces les indirections par un caclul d'index.
 
Pour N dimensions, tu extrapoles la formule

Et tu crois qu'en faisant 5 multiplications (et 5 additions) j'irais plus vite qu'en ayant 5 dimensions ? Hum ... A tester remarque.

Oui, c'est certain.

 
5 flops + 1 indirection << 5 indirections
 
c'est deja testé crois moi

concretement une indirection ca se traduit par quoi ? plusieurs flops ?

La taille de ta matrice est importante ?
 
Je me souviens avoir fait une appli ou je créé une matrice 4D de int, d'une taille trop grande (1000x1000 je crois), en fait c'est bien évidement la taille en mémoire de cette matrice qui faisait ramer toute mon appli, c'était plus que ma quantité de ram
 
Mais bon, si ta matrice ne grandit pas dans tes proportions énorme, ça ne sera pas ça le problème.

la taille ouais si qd , ca fait 255 * 8 * 8 * 8 * 8 * taille d'un double

 
Ah bon ?!? Je pensais que quand on accède à un tableau multi-dimensionnel le compilo fait exactement ce que l'on ferait en codant la "technique" tableau 1D. Sauf que, dans mon esprit, le compilo ne pouvait que générer un code plus rapide.
 
Je vous crois, hein, mais j'aimerais bien comprendre. Sur 'std::vector< std::vector<...>> ' OK, avec un template de template ce serait vraiment une optimisation de derrière les fagots de transformer en tableau 1D. Mais sur x[][] qu'est-ce qui empêche le compilateur de transformer en tableau 1D, ou en ce qu'il veut et qu'il considère comme le + rapide ?
 
J'utilise tableau N dimensions --> tableau 1 dimension + petite routine d'accès uniquement quand N n'est pas connu à la compilation.
 
Sinon, y'a eu un p'tit thread vaguement lié ici : http://forum.hardware.fr/hfr/Progr [...] 3390_1.htm
 
Chsais pas si ça peut aider ou pas, mais c'est un peu sur le même thème.

Hmm c'est pas bête ce que tu dis boulgakov.
 
Mais je crois que le mieux c'est de tester

 
 
parce dans son code il fait des allocations explicites. (après si tu fais un vrai tableau tab[][].... là oui c'est déplié en tableau contigu)
 
c'est pas un bloc mémoire de doubles, c'est un bloc mémoire de pointeur de pointeur de pointeur, etc.... donc cache trashing, page fault & tout le bordel. (y'a ptet autant de conso mémoire en pointeurs qu'en double au bout d'un moment)
 
guynemer >> tu peux éliminer des multiplications en regardant la cohérence spaciale que tu peux obtenir dans l'utilisation ultérieure.  
ie dans le cas d'une image 2D, si tu traites pixel par pixel, bin tu fais qu'incrémenter un indice/pointeur, si tu traites des pixels aléatoires mais ligne par ligne, tu peux maintenir un pointeur sur chaque début de ligne (que tu avance de la taille d'une ligne) et que tu indexes en fonction du pixel aléatoire que tu veux traiter.
 
idem réorganiser pour que:
[grandeur variant le moins][un peu plus][encore un peu plus][le plus]
 
ie tab[45][5][8][4] et tab[45][5][8][6] risquent d'être distant de quelques octets, et seront peut-être dans la même ligne de cache  
 
alors que tab[4][8][5][45] et tab[6][8][5][45] ne seront certainement pas dans la même ligne, et distant de plusieurs Mo (cache-trashing, TLB miss, page-faults...)

 
Ce n'est vrai que pour les TABLEAUX pas les zones mémoires allouées dynamiquement et utilisés comme telles.
La sémantique de
 
float tab[N][M];
 
est fondamentalement différente de celle de :
 
float** tab;

toutes ces ********* dès le matin, ça fout la gerbe. Boost !

boost c'est bien

 
Ouaip' (j'y ai pensé quelques minutes après avoir posté, mais j'ai eu la flemme d'éditer mon texte).
 

c'est quoi boost ? On m'a glissé ce nom vite fait pas je n'en sais pas plus.
 
En plus visiblement on m'a conseillé de m'arranger pr calculer uniquement sur des INT plutot que des double ou float, et que ca acccélerarait de bcp le temps d'execution.

float deja oui ca me parait mieux.
 
boost : http://www.boost.org

j'ai commencé à regarder la doc merci. Maintenant je me demande si ca va me permettre de gagner du temps face à un "basique" gros tableau d'int si je pars sur une dim. Hum

 
multi_array mais faut voir. Deja essaye effectivment ton gros tableau 1D

C'est un grand classique dans le traitement d'images...

Clairement

 
Tant qu'on est dans le sujet, est-ce que vous pensez qu'il peut y avoir un gain significatif à découper l'image en bandes verticales de X pixels de large (bon ça nécessite un effort préalable pour faire ce découpage) et de traiter séparément chaque bande afin d'éviter lors de la lecture de pixels alentours d'aller tapper 4km plus loin dans la mémoire parcequ'on lit des lignes un peu plus haut et qu'avec la largeur des lignes ça fait super loin en mémoire ?
( Pour info c'est pour faire des convolutions un peu grosses )

ça dépend....si tu as des traitements à faire dans le sens horizontal qui te font passer d'une bande à l'autre, ça risque de pas être génial...d'autant que ça fait perdre de l'accélération dans le calcul des indices des pixels contigus, a priori.

'fin je pense pas que le gain de base soit super terrible, en fait...à moins d'avoir vraiment une image monstrueusement énorme en largeur...

Je pensais justement me débrouiller pour ne pas avoir de changement de bande, comme ça au niveau des indices y'a pas de calcul plus complexe que le truc habituel.
Par contre, pas de changement de bande ça veut dire qu'on doit utiliser plus de mémoire en mettant des marges droites et gauches pour la convolution ....

Y'a t'il des options de compilation utilisables sous VS 2005 pour optimiser le temps de calcul ? des flags à rajouter à la ligne de commande ? Eventuellement des flags pour pouvoir utiliser les instructions spécifiques des procs genre SSE, MMX , etc. ?

sse mmx ca s'utilisent pas comme ça, à moins d'utiliser icc qui fait un boulot pas trop dégeu d'auto-vectorisation. sinon, cf ma sig