Vector et vitesse

Bonjour,

Pour la création d'un shoot them up, j'ai besoin de stocker beaucoup de "bullets" ( au moins 100 ) sachant que j'en détruis et crée très souvent et que je dois également les parcourir en entier à chaque frame.

Le tutoriel à cette adresse ( http://www.shmup-dev.com/forum/index.php?topic=1639.0 ) indique que le container le plus rapide à parcourir est un std::vector. Dans le cas d'un disque dur je comprends qu'un placement contigü évite des allers et retours à la tête de lecture mais dans le cas de la RAM est-ce vrai ?

voici ce qui est écrit dans le tutorial du lien précédent:

Citation:

---

The biggest factor is that we are going to want to iterate through the entire data set several times each frame for our various things we want to do with our bullets. Iteration through a list is significantly slower than through a vector due to a level of indirection caused by having to go through the next pointer. Since the actual processing on each bullet will be fairly minimal this performance hit can become a significant percentage of the total performance. Also no matter how we implement our bullets and lists we cant avoid the problem that whilst traversing the list we would be jumping around in memory all over the place which would thrash the cache, where as a vector will be stepping through memory contiguously which gives us the most efficient cache usage.

---

Il se trouve que j'utilise du polymorphisme pour gérer les différentes entités ( joueur,ennemis,bullets ). Dans mon vecteur je stocke alors des pointeurs IEntity*. Ces pointeurs sont contigüs mais comme il s'agit de pointeurs et non plus des valeurs, est-ce que je perds tout ou partie de l'avantage de contiguité offert par le vector ?

A chaque frame je dois donc parcourir près de 150 entités pour les mettre à jour,gérer les collisions,supprimer,créer tout en respectant leur ordre de création.
Je me demande donc quel est le container à priori le plus favorable pour cela ?

Merci

Le std::vector est (je pense) pas très approprié pour ton cas. Cela vient de la suppression et de l'insertion. Dans un vecteur, supprimer un élément au milieu prend beaucoup de temps. De plus, avec l'insertion, tu vas avoir un nombre considérable de copie, parce que le vecteur réalloue complètement toute la mémoire nécessaire.

Je pense qu'une std::list serait bien plus adaptée.

Tu l'as parcours grâce aux itérateurs, et pour la suppression, stocke un iterateur sur l'objet et comme ça c'est très rapide.

Voilà, en espérant avoir été utile.

Hydrolyre

L'idée dans le tutorial est de ne pas supprimer les entites mais de les "désactiver" ( avec un booleen "activé" par exemple ) comme cela ca t'évite des new / delete couteux. Quand l'entité meurt, tu sauvegardes son emplacement mémoire mais tu mets le booléen à faux.
Quand tu veux créer une nouvelle entité, au lieu de faire un new, tu regardes s'il n'y a pas un empalcement avec "active" à "false".

Ceci dit ca serait pour moi plus facile d'utiliser des lists, mais parcourir une suite de pointeurs est-il vraiment plus lent avec une suite sous forme de std::list que sous forme de std::vector ? Est-ce négligeable avec les PC actuels ?

Dans ce cas pourquoi avoir un tableau dynamique?

Code:

---

1 2 3 4 5 6 7 8

const static std::size_t Max_Size = 50;   boost::Array< IEntity*, Max_Size > Tab;   //ou   IEntity* Tab[ Max_Size ];

---

Ce code ne suffirait-il pas?

Hélas je ne connais pas la taille maximum :s
Je peux envisager une limite max mais la marge de sécurité sera telle que point de vue mémoire je ne sais pas si ce sera intéressant.

Je vais essayer de trafiquer avec des listes et si c'est trop lent et bien je me débrouillerai autrement en enregistrant des valeurs dans les vector ( ca supprime le coté pratique du polymorphisme mais bon... ).

Si l'ordre n'a pas d'importance, remplacer l'élément à retirer par le dernier et réduire de un la taille du vecteur sera bien plus efficace qu'une liste en parcours, en ajout et en retrait.

Réfléchis à comment une liste chainée est implémentée et tu verras alors l'indirection qui la rend moins efficace qu'un vecteur. Ce n'est pas juste une question de contiguïté.

PS: en général on tend à considérer que quand il y a peu d'éléments (peu =~ quelques centaines), un vecteur est plus efficace que ses alternatives. 100, ce n'est rien du tout.

Citation:

---

Envoyé par teto

Dans le cas d'un disque dur je comprends qu'un placement contigü évite des allers et retours à la tête de lecture mais dans le cas de la RAM est-ce vrai ?

---

Oui. Car si la mémoire est contiguë, la cache est utilisé efficacement. Sinon, il est peu utile. Et il y a un ordre de grandeur d'écart entre accès au cache et accès à la mémoire générale.

@Luc Hermitte >
sauf que l'ordre compte. Mais le tutorial prévoit justement une astuce pour respecter l'ordre avec les vector donc je crois que je vais suivre le tutorial :)

quelqu'un connaitrait une présentation du cache ( j'imagine qu'il doit y avoir ca sur developpez.com ) pour que j'approfondisse un peu le truc :D ?

Je ne sais pas pour le cache, mais une autre possible solution avec vector ou pas serait de faire une sorte de tableau avec une taille limite ( avec le std::vector prévoir juste un resize pour qu'il ne soit pas fait en plein milieu du programme ).

Dans ce tableau vous aurez les éléments actifs, les éléments inactifs et les cases libres.
L'idée, c'est d'avoir deux pointeurs ( compteurs ) qui permettent de connaitre la prochaine case libre, et la dernière case libre.

La prochaine case libre ( au début j'entends ) permet de rajouter des éléments.
La dernière case libre, permet de mettre l'élément à supprimer là bas ( à la fin du tableau ).

Pour le parcours vous pourrez faire une boucle for de 0 au pointeurs de la première case libre.
Pour la création, vérifié si la case libre, et la case libre de fin n'est pas la même ( et elle ne se serait pas inversé ( donc création dans les trucs inactifs ).
Inactivation d'un objet ( il est envoyé à la fin ).

Voilà, je crois que c'est une des meilleurs solution

Salut,

Ou sinon tu fais le plus simple/souple dans un premier temps puis si ça rame tu analyses d'où vient le problème et tu optimises.
Si c'est encapsulé un peu correctement le code à modifier ne devrait pas être trop conséquent...

MAT.

Citation:

---

Envoyé par teto

quelqu'un connaitrait une présentation du cache

---

Il y a des tutos système qui abordent le cache.
Sinon, pour une centaine d'éléments je serais de l'avis de Mat007 : code au plus simple et ensuite si c'est vraiment ça qui manque de perf affine. En premier abord, j'ai tendance à penser que pour 100 éléments, les différents conteneurs n'auront que des impacts mineurs sur les perfs par rapport à d'autres aspects. Ca peut même avoir l'effet inverse : mettre en œuvre une usine à gaz pour un conteneur optimal et perdre avec ces mécanismes tout les bénéfices de la simplicité d'un conteneur moins optimal.
100 éléments, ce n'est rien en fait.

Ok merci pour tous ces conseils comme j'ai le temps je vais tester les différentes solutions proposées.