Discussion :

[kochfet]

Salut,

Dans un problème d'optimisation, quelle est la solution la plus meilleure pour coder une matrice d'objets? utiliser un vector<vector<Objet>> ou un vector<vector Objet*>? Autrement, quelle est la solution la plus optimisée: utiliser des objets ou des pointeurs sur objets

[koala01]

Salut,

Salut,

Dans un problème d'optimisation, quelle est la solution la plus meilleure pour coder une matrice d'objets? utiliser un vector<vector<Objet>> ou un vector<vector Objet*>?

Tout dépend de si ta matrice est creuse ou non.

Si elle n'est pas creuse (comprends : s'il existe un élement pour chaque colonne dans chaque ligne), le mieux est sans doute de "simplement" considérer ta matrice comme étant un tableau composé de (nombre de ligne * nombre de colonnes) éléments.

Pour accéder à l'élément se trouvant à la ligne L et à la colonne C, on utilise alors la formule index recherché = L * nombre de colonnes + C.

Cette approche ne sera, en tout état de cause, jamais plus mauvaise que n'importe quelle autre approche possible, mais peut en revanche s'avérer intéressante du fait que tous les éléments seront effectivement contigus en mémoire.

Autrement, quelle est la solution la plus optimisée: utiliser des objets ou des pointeurs sur objets

Il n'y a, pour ainsi dire, aucune différence entre utiliser un pointeur sur un objet ou utiliser l'objet lui-même (je dis "pour ainsi dire" car il reste encore à prouver qu'il y ait la moindre différence )

Plus sérieusement, il y a de fortes chances pour que tout accès à un objet se transforme en l'accès à l'adresse mémoire à laquelle il commence + le décalage permettant d'accéder au membre impliqué.

Et comme un pointeur n'est jamais qu'une valeur représentant une adresse mémoire... où pourrait se nicher la moindre différence

Ceci dit, en C++, les cas où tu as réellement besoin de travailler avec des pointeurs sont particulièrement rares et la plupart ont trait, d'une manière ou d'une autre, à l'héritage et au polymorphisme.

Le principe à suivre, c'est donc de travailler sur des objets ou sur des références (éventuellement constantes) chaque fois que possible, et de n'utiliser les pointeurs que lorsque tu n'as pas d'autre choix.

Tu n'auras pas le choix si:

1. Tu veux placer un objet ayant sémantique d'entité (en gros, un objet de n'importe type intervenant dans une hiérarchie de classe) dans une collection
2. Tu veux créer un objet ayant sémantique d'entité en le considérant comme étant du type de base, mais en créant un objet du type dérivé
3. Tu veux pouvoir représenter la "non existence" de l'objet
4. Tu dois créer une relation particulière dans laquelle un membre de ton objet doit faire référence à quelque chose du même type que ton objet

Enfin, il faut savoir que l'utilisation de pointeurs nu ne va pas sans occasionner certains soucis, en terme de durée de vie.

Autant que faire se peut, il est utile de préférer l'utilisation de pointeurs intelligents, comme std::unique_ptr, std::shared_ptr ou autres ( attention : C++11 only )voir les shared pointers de boost

[imperio]

Si tu as un réel besoin d'optimisation pour une matrice, je te conseille de directement faire un tableau de Objet* (new Objet*[]). J'ai créé un programme ayant besoin de matrice (moteur de raytracing) et j'ai remarqué que les vector étaient beaucoup trop lents pour ce que je faisais (on parle d'une différence de plusieurs secondes à l'exécution sur une durée totale de moins de 30 secondes). Après mon utilisation des vector n'était peut-être pas parfaite, toujours étant que ça a été un gain de temps non-négligeable. Cependant, si tu n'as pas spécialement besoin de vitesse, je te recommande plutôt les vector qui sont beaucoup plus agréables à utiliser.

[kochfet]

Merci pour vos réponses.

Autre information que je veux citer :

En fait, je suis entrain de coder un problème ou je dois optimiser un temps de réponse d'une requête donc le facteur temps est très important pour moi. Aussi, les différentes cases de ma matrice sont des objets appartenant à une hiérarchie d'héritage. Tous ces objets sont des classes filles de la même classe mère.

[Ehonn]

Si tu as un réel besoin d'optimisation pour une matrice, je te conseille de directement faire un tableau de Objet* (new Objet*[]). J'ai créé un programme ayant besoin de matrice (moteur de raytracing) et j'ai remarqué que les vector étaient beaucoup trop lents pour ce que je faisais (on parle d'une différence de plusieurs secondes à l'exécution sur une durée totale de moins de 30 secondes). Après mon utilisation des vector n'était peut-être pas parfaite, toujours étant que ça a été un gain de temps non-négligeable. Cependant, si tu n'as pas spécialement besoin de vitesse, je te recommande plutôt les vector qui sont beaucoup plus agréables à utiliser.

Les std::vector sont aussi performants que les tableaux dynamiques. Pour des tableaux 2D, il faut en effet éviter des std::vector<std::vector<T>> et préférer un std::vector linéarisé (encapsulé dans une classe). Il serait intéressant que tu puisses nous donner un exemple qui reproduit ceci
Autre petite différence, de base std::vector initialise tous ces éléments contrairement à new.
Une fois ces éléments connus, il suffit de faire attention à bien réserver la place (ne pas faire des push_back dans tous les sens) et aux copies pour avoir les mêmes performances.

@kochfet> Questions performances, il faut mieux supprimer l'héritage (polymorphisme d'inclusion) au profit des templates (polymorphisme paramétrique).
Ça dépend ce que tu fais avec ton objet une fois que tu l'as recupèré de ta matrice mais si peu d'opérations sont faites le coût d'accès au bon type sera élévé (en pourcentage).
http://cpp.developpez.com/faq/cpp/?p...e_parametrique

[koala01]

Merci pour vos réponses.

Autre information que je veux citer :

En fait, je suis entrain de coder un problème ou je dois optimiser un temps de réponse d'une requête donc le facteur temps est très important pour moi. Aussi, les différentes cases de ma matrice sont des objets appartenant à une hiérarchie d'héritage. Tous ces objets sont des classes filles de la même classe mère.

Bah, j'ai envie de dire que, dés le moment où tu parles d'héritage, tu n'as de toutes façons pas beaucoup le choix quant à la méthode pour placer tes objets dans une collection : tu devras, de toutes façons les placer dans tes collections sous la forme de pointeurs .

Je m'explique:

Dés que l'on commence à parler d'héritage, on rentre dans une logique dans laquelle les différents types que l'on envisage ont sémantique d'entité, c'est à dire que tous les types intervenant dans la hiérarchie sont (ou du moins devraient être):

1. identifiables de manière unique et non ambigüe, quitte à ce que ce soit sur base de l'adresse mémoire à laquelle ils se trouvent
2. non copiables, pour respecter le premier point
3. non assignable, pour respecter le premier point
4. non immuables (tu dispose de certaines fonctions permettant de modifier les valeurs qui n'interviennent pas dans le premier point)
5. non comparables en globalité (tu ne peux envisager de comparer que les valeurs de certaines de leurs caractéristiques équivalentes)

Comme les éléments intervenant dans une hiérarchie d'objet sont, par nature, non copiables (point (2) de la liste ), et qu'il est impossible de créer une collection de références sur des objets (de toutes manières, si l'on regarde au niveau du code binaire, une référence et un pointeur sont strictement pareil ), le seul moyen pour maintenir tes objets dans une collection qu'il te reste est... le recours à des pointeurs

De plus, pour profiter du polymorphisme d'héritage (en fait du polymorphisme ad-hoc ), tu n'auras pas le choix : tu devras de toutes manières utiliser des pointeurs ou des références sur tes objets, sous peine d'assister à un phénomène de "slicing" (la perte des données qui n'appartient pas à la seule classe de base de ton objet)

De ce fait, si ton problème est l'optimisation, tu devras envisager d'autres solutions car tu sera obligé de passer par des pointeurs

La solution qui consiste à considérer une matrice (non creuse) comme étant un tableau contenant <nombre de lignes> * <nombre de colonnes> que j'ai présentée dans ma première intervention présente sans doute la seule solution d'optimisation (réelle ou imaginaire) que tu pourrais envisager en terme de stockage de tes informations.

Bien sur, cette solution apportera de la facilité d'utilisation (ce qui n'est jamais négligeable), mais le gain en terme de performances que tu en tireras mériterait clairement d'être évalué (ceci étant dit pour expliquer le "réel ou imaginaire" )

Maintenant, il est bon de se rappeler que

premature optimisation is root of evil

(l'optimisation prématurée la route des enfers )

Avant donc de t'inquiéter des problèmes de performances d'accès via un pointeur, une référence ou un objet, je te conseillerais fortement de t'inquiéter:

1. de l'opportunité des héritages que tu envisages (et de veiller à respecter LSP)
2. d'optimiser tes algorithmes
3. de vérifier (par benchmark) les parties de tes algorithmes qui sont particulièrement lentes
4. d'optimiser ces parties
5. de recommencer en (2)

[Bousk]

Les std::vector sont aussi performants que les tableaux dynamiques.

Tu dois pouvoir trouver des benchmark qui montreront le contraire, il y a toujours une indirection supplémentaire, parfois non négligeable au bout d'un moment et/ou mal inliné.

Pour des tableaux 2D, il faut en effet éviter des std::vector<std::vector<T>> et préférer un std::vector linéarisé (encapsulé dans une classe).

Le vector de vector (et tout tableau 2D ou presque) est à proscrire.
Mais la linéarisation d'un tableau 2D est complètement orthogonale à l'encapsulation dans une classe. Donc non, l'encapsulation n'est pas obligatoire, si elle n'apporte rien on s'en passe.

[koala01]

Mais la linéarisation d'un tableau 2D est complètement orthogonale à l'encapsulation dans une classe. Donc non, l'encapsulation n'est pas obligatoire, si elle n'apporte rien on s'en passe.

L'encapsulation est effectivement orthogonale, mais, dans le cas particulier d'un tableau 2D, je crois personnellement qu'elle apportera toujours assez pour ne jamais s'en passer.

Ne serait-ce que du fait que l'on obtiendra une stabilité de l'interface (principalement la fonction itemAt(ligne, colonne), ou similaire ) indépendamment du fait que l"on peut décider "à tout moment" de stocker les lignes ou les colonnes en premier

En effet, lorsque le besoin de performances se fait sentir, on peut s'éviter bien des problèmes de cache en fonction de l'ordre des accès successifs "simplement" en décidant de créer X colonnes de Y lignes ou X lignes de Y colonnes:

Si la plupart des accès se font colonnes par colonne, au lieu de se faire ligne par ligne, le simple passage d'une solution à l'autre peut faire gagner énormément, sans que cela ne soit forcément à placer dans l'optimisation prématurée

[Ehonn]

Tu dois pouvoir trouver des benchmark qui montreront le contraire, il y a toujours une indirection supplémentaire, parfois non négligeable au bout d'un moment et/ou mal inliné.
Le vector de vector (et tout tableau 2D ou presque) est à proscrire.
Mais la linéarisation d'un tableau 2D est complètement orthogonale à l'encapsulation dans une classe. Donc non, l'encapsulation n'est pas obligatoire, si elle n'apporte rien on s'en passe.

Une rapide recherche donne par exemple ceci
http://stackoverflow.com/questions/1...s-or-stdvector
std::vector est aussi rapide que le tableau dynamique.
L'indirection supplémentaire doit être supprimé lorsque le compilateur optimise, s'il ne le fait pas, on change de compilateur ^^

Le std::vector de std::vector a des propriétés sympatiques que n'a pas un T **, facilité d'utilisation, for range loop par exemple.
Lorsqu'on encapsule un std::vector linéarisé, on peut en faire un foncteur pour pouvoir écrire (i, j) (ou même [i][j] en passant par un proxy) au lieu de [i * N + j]. On peut aussi ajouter les méthodes nb_row et nb_col. L'encapsulation a de forte chance d'apporter quelque chose et un foncteur peut être entièrement inliné

[koala01]

Allez, les enfants, on arrête de se chamailler

Fixons, si vous voulez bien, un tout petit peu les choses:

Commençons, si vous le voulez bien, par diviser le problème en deux catégories:

1. les performances d'accès à un élément
2. les performances d'augmentation (ou de diminution) de la taille

Pour ce qui est de la rapidité d'accès, il faut savoir que std::vector offre la garantie que les éléments seront contigus en mémoire tout comme c'est le cas pour un tableau C style.

Comme l'opérateur [] de std::vector est inliné et ne fait rien d'autre (à part pour VS, en mode debug, qui rajoute un assert, me semble-t-il(*) ) qu'utiliser l'opérateur [] du tableau C style utilisé en interne, il ne devrait pas y avoir de différence (*)

(*) Comprenons nous : on peut observer des différences de performances en mode débug et ce pour différentes raisons, mais un test de perf ne devrait jamais se faire qu'en mode release, avec toutes les optimisations envisagées activées, autrement le test n'a purement et simplement pas de sens

Pour ce qui est de l'utilisation d'itérateurs, il est cohérent de penser qu'il y aura des différences de performances, du fait de la nécessité de créer l'itérateur (et encore, un benchmark serait utile pour s'en assurer ), mais, dans l'optique qui nous intéresse à la base de cette conversation, je présume que vous serez d'accord avec moi pour estimer que c'est sans objet étant donné qu'il est rare de vouloir manipuler un tableau 2D avec des itérateurs

Au final, ce qui aura le plus de chance de "plomber" les performances, ce sera le phénomène de "cache miss", c'est à dire le fait que l'élément auquel on essaye d'accéder ne se trouve pas dans la page mémoire qui est accessible.

Mais ce phénomène apparaitra aussi bien sur un tableau C style que sur un std::vector et dépendra essentiellement:

1. de la taille des éléments du tableau
2. de la proximité de l'élément recherché par rapport au dernier élément auquel on a accédé (pour simplifier: la différence entre l'index de l'élément recherché et celui du dernier élément auquel on a accédé)
3. de ce que l'on aura fait entre deux accès successifs à différents éléments du tableau

Autant dire que le seul point sur lequel nous aurons un tant soit peu le contrôle, c'est ce qui est fait entre deux accès successifs, et ca, ca nous ramène aux problèmes d'algorithmie

Pour ce qui est des modifications de taille du tableau, maintenant.

Il est un fait que les comportements qui tentent à modifier la taille d'un std::vector sont, globalement, plus lent que la gestion dynamique de la mémoire pour les tableaux C style. Mais...

Il faut, encore une fois, remettre ce problème en perspective par rapport au problème posé dans cette discussion, à savoir: l'utilisation de tableaux 2D.

Tout omme on part du principe (c'est la précondition au fait d'utiliser des tableaux linéarisés ) que ce tableau représente une matrice non creuse, on peut estimer que l'on a de fortes chances de connaitre le nombre de lignes et de colonnes qui doivent le composer avant même de vouloir remplir ce tableau.

La fonction reserve de std::vector et / ou le constructeur qui permet de prévoir une taille prédéfinie pour std::vector devrai(en)t donc nous permettre de limiter le nombre de modifications de la taille du tableau à... une seule et unique fois au moment de créer la matrice.

De ce fait, le problème de la modification de la taille du tableau n'en est finalement plus un, dans le sens où, soyons honnêtes, même si reserve (ou tout autre comportement similaire) venait à durer dix fois plus longtemps que la gestion manuelle de la mémoire, il y aurait largement de quoi faire avant que les 30 millisecondes nécessaire à ce comportement pour un std::vector ne changent quoi que ce soit par rapport aux 3 millisecondes pour un new, vous ne croyez pas

[imperio]

Les std::vector sont aussi performants que les tableaux dynamiques. Pour des tableaux 2D, il faut en effet éviter des std::vector<std::vector<T>> et préférer un std::vector linéarisé (encapsulé dans une classe). Il serait intéressant que tu puisses nous donner un exemple qui reproduit ceci
Autre petite différence, de base std::vector initialise tous ces éléments contrairement à new.
Une fois ces éléments connus, il suffit de faire attention à bien réserver la place (ne pas faire des push_back dans tous les sens) et aux copies pour avoir les mêmes performances.

@kochfet> Questions performances, il faut mieux supprimer l'héritage (polymorphisme d'inclusion) au profit des templates (polymorphisme paramétrique).
Ça dépend ce que tu fais avec ton objet une fois que tu l'as recupèré de ta matrice mais si peu d'opérations sont faites le coût d'accès au bon type sera élévé (en pourcentage).
http://cpp.developpez.com/faq/cpp/?p...e_parametrique

Pour ce que j'en ai vu, les vector sont plus lents que les tableaux C like. La perte de performance était sur la méthode operator[]. Cependant comme l'a dit koala01 :

(*) Comprenons nous : on peut observer des différences de performances en mode débug et ce pour différentes raisons, mais un test de perf ne devrait jamais se faire qu'en mode release, avec toutes les optimisations envisagées activées, autrement le test n'a purement et simplement pas de sens

Mon moteur de raytracing étant toujours en développement, je ne l'ai jamais compilé en mode release. Peut-être qu'à ce moment là ça changera quelque chose, mais 30 secondes d'écart sur une exécution de moins de 2 minutes me paraît quand même énorme pour que ce soit seulement amputable au mode debug (je compile avec -g2) !

[koala01]

Mon moteur de raytracing étant toujours en développement, je ne l'ai jamais compilé en mode release. Peut-être qu'à ce moment là ça changera quelque chose, mais 30 secondes d'écart sur une exécution de moins de 2 minutes me paraît quand même énorme pour que ce soit seulement amputable au mode debug (je compile avec -g2) !

Pas forcément...

Cela dépend déjà du compilateur utilisé car il n'est pas impossible qu'il n'inline déjà purement et simplement pas les fonctions en mode debug.

Pour rester dans le domaine de ce qui est propre au mode debug du compilateur, il faut savoir qu'il rajoute un tas d'informations qui sont, justement, prévue pour te permettre le débuggage et que cela fait forcément des instructions supplémentaires à l'exécution.

Sans compter les éventuels assert et autres joyeusetés du genre qu'il peut ajouter sur un simple tab[]

Tout cela mis ensemble va donc, très clairement, donner un avantage au tableaux C style vu qu'il n'y a, purement et simplement aucun controle à ce niveau là

A mon avis, tu es peut etre parti un peu trop vite en besogne en décidant de passer à l'utilisation de tableaux C style avant d'avoir des tests en mode release

Et je présume qu'il sera sans doute difficile de reprendre tout ton code pour repasser à une version utilisant les std::vector histoire de comparer

[Bousk]

Pour ce que j'en ai vu, les vector sont plus lents que les tableaux C like. La perte de performance était sur la méthode operator[].

Oui vector peut être plus lent, mais il ne sera en tous cas jamais plus rapide. L'ajout de l'indirection n'est pas étrangère et vide de conséquence.
Mais oui cette indirection est souvent diminuée, jusqu'à supprimée, grâce à l'inlining, surtout en release. En debug, il y a aussi des conséquences mais est-ce grave ? Les benchmarks se font sur un mode Release.

En debug, tu as en plus certaines opérations d'initialisation qui peuvent être faîtes par l'IDE qui entrent en compte et "ralentissent" certaines opérations. Ou des ASSERT tout simplement.

Et ne parlons pas de la méthode at qui fait du bound checking et retourne une exception out_of_range en cas de problème. Qui est de loin le pire choix en terme de temps d'exécution.

Et tu peux passer très simplement à du C-Array à partir d'un vector.
- vector::data en C++11
- tout simplement &(vec[0]); &(vec.front());

[imperio]

A mon avis, tu es peut etre parti un peu trop vite en besogne en décidant de passer à l'utilisation de tableaux C style avant d'avoir des tests en mode release

Et je présume qu'il sera sans doute difficile de reprendre tout ton code pour repasser à une version utilisant les std::vector histoire de comparer

Pas vraiment, j'avais encapsulé cette gestion dans une classe donc ça ne change à vrai dire pas grand chose au niveau du code si ce n'est un new et un delete en plus. Cependant ça vaut le coup de tester, je m'y remettrai quand j'aurai du temps en recompilant en mode release.

[kochfet]

Voilà ma classe graphe que j'arrive à la coder :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
class graphe
{
vector<Noeud*> vecNoeuds ; // Noeud est une classe
Lien ** matLiens ;// Lien est classe et matLiens c'est une matrice des liens
};

Est ce c'est le bon choix?

[kochfet]

puisque je veux utiliser la notion d'héritage et la notion de polymorphisme alors là je vais utiliser vector< vector <Lien*>>.
Est ce que je suis dans le bon chemin ?????????

[Médinoc]

Ça dépend du nombre de dimensions que tu veux.
Et si tu préfères n'avoir qu'un seul vector, qui est quand même plus performant (auquel cas on peut l'encapsuler dans une classe du genre:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
template< class T >
class Matrice
{
	std::vector<T> vec;
	size_t width;
	size_t height;
public:
	Matrice(size_t width, size_t height)
		: vec(width*height), width(width), height(height)
	{ }
	T const &at(size_t x, size_t y) const { return vec.at(x + y*width); }
	T       &at(size_t x, size_t y)       { return vec.at(x + y*width); }
};

Avec ça tu as un vecteur 2D sans avoir à gérer un vecteur de vecteurs.

[kochfet]

Merci Médinoc pour la réponse mais :

Dans mon problème, la taille de la matrice est égale à la taille de vecNoeuds le vecteur qui contient les différents noeuds à ajouter dans le graphe. Bien sur dans mon cas cette taille est inconnu à l'avant. donc la taille de la matrice peut changer en ajoutant des nouveaux noeuds. Elle n'est pas fixe.

[Médinoc]

Dans ce cas on ajoute les méthodes pour redimensionner:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Matrice::swap(Matrice &obj)
{
	vec.swap(obj.vec);
	std::swap(width, obj.width);
	std::swap(height, obj.height);
}
 
void Matrice::Resize(size_t newWidth, size_t newHeight)
{
	Matrice newMat(newWidth, newHeight);
	for(int y=0 ; y<min(height, newHeight) ; ++y)
	{
		for(int x=0 ; x<min(width, newWidth) ; ++x)
			newMat.at(x, y) = at(x, y);
	}
	newMat.swap(*this);
}