delete, vector et destructeur

Version imprimable

Bonjour,

Y a-t-il une fuite de mémoire dans le code suivant ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 std::vector<void*> components; struct Component { unsigned index; Component() : index(components.size()) {}; ~Component() { std::swap(components[index],components.back()); components.pop_back(); } }; struct Position : Component {}; struct Name : Component {}; int main() { components.push_back(new Position); components.push_back(new Name); components.push_back(new Name); components.push_back(new Position); components.push_back(new Name); Name* e = static_cast<Name*>(components[2]); delete e; return 0; }
Normalement, on fait d'abord delete, puis ensuite on enlève l'élément dans le vector, mais dans mon cas, je ne sais pas trop comment ça va se passer étant donné que delete appelle le destructeur, où justement je supprime l'élément du vector :aie:

:)

18/03/2015, 21h55
user019

Est-ce que ce code fuit? Il me semble que non.

Est-ce que ce code est donc bien fichu? Oh que non.

Une classe qui fait référence en dur à une variable globale qui contiendra toutes ses futures instances? Mmh. Pas sûr que ce pattern connaisse un grand succès.

Si tu expliques quel est le but de ton code, on peut t'orienter vers une solution plus standard.
18/03/2015, 22h40
MrPchoun

Bah, faut dire aussi, c'est un code minimal, en pratique y aura pas de variable globale, par contre elle contiendra effectivement toutes mes instances, pour épargner ma mémoire cache.

Le but du code ? En gros.

J'ai ce vector de components, et un autre vector (system) que je n'ai pas fait figurer ici, qui contiendra des pointeurs sur ces components. Je veux pouvoir supprimer facilement ces components depuis system sans avoir à tenir un registre où j'enregistre à quelle position j'ai enregistré tel component.
18/03/2015, 23h54
jblecanard
Un vector de void* :weird: c'est pas sérieux ça

Citation:

Envoyé par MrPchoun

par contre elle contiendra effectivement toutes mes instances, pour épargner ma mémoire cache.

Cette opitmisation me paraît bien prématurée. Early optimization is the root of all evil. Avant d'optimiser, on fait du profiling. Pour l'instant, tu es en au design, pas encore au profiling. En plus, elle ne fonctionne pas : si tu stockes des pointeurs, les components ne seront pas contigus et ton optimisation de cache ne sert à rien ! Après je suppose que Component est polymoprhique, dans lequel cas tu n'as pas le choix, tu ne pourras pas les stocker de manière contigue facilement.

Citation:

Envoyé par MrPchoun

Je veux pouvoir supprimer facilement ces components depuis system sans avoir à tenir un registre où j'enregistre à quelle position

Et pourtant, tu le fais : chaque component enregistre son indice. En plus, ça ne fonctionne pas : si tu supprimes un élément au milieu du vecteur, ça va te côuter cher car tous les éléments suivants seront déplacés, et en plus leur indices ne seront plus bon, et les références stockées dans ton system ne le seront plus non plus.

Pour faire le bon choix de la collection, il faut évaluer ton besoin:
- Si tu veux pouvoir supprimer un élément de manière peu coûteuse sans invalider les autres références et que tu ne fais pas ou peu de parcours de la liste : std::list
- SI tu veux faire des parcours de liste efficace : std::vector
- Si tu veux faire les deux : tu es niqué, mais il est probable que std::vector soit meilleur.
Ensuite, c'est une assez mauvaise idée d'utiliser des pointeurs nus, car non seulement c'est risqué, mais en plus tu ne définis pas clairement la politique de propriété de tes composants. Qui est propriétaire de l'objet ?
- Si c'est une propriété partagée entre les systèmes, considère l'usage de std::shared_ptr
- Si la collection "globale" est propriétaire (c'est à dire que le supprimer de la liste est équivalent à le supprimer complètement), utilise std::unique_ptr
Et enfin, las but not least, est-ce que tu ne gagnerais pas du temps à utiliser du code existant ?
19/03/2015, 10h20
Bousk

tu mets 5 éléments via new, tu les mets en void*, t'en delete 1 seul, sans destructeur virtuel
et tu te demandes si ça fuit ? :weird:
19/03/2015, 11h28
ternel

Et ne parlons même pas du fait que tu ne l'a pas enlevé du vector.

Ton idée a un nom: le pattern flyweight.
19/03/2015, 17h51
MrPchoun

@jblecanard :

Citation:

Et pourtant, tu le fais : chaque component enregistre son indice. En plus, ça ne fonctionne pas : si tu supprimes un élément au milieu du vecteur, ça va te côuter cher car tous les éléments suivants seront déplacés, et en plus leur indices ne seront plus bon, et les références stockées dans ton system ne le seront plus non plus.

Ben pas vraiment, c'est justement pour ça que j'utilise la méthode swap + pop_back :
- ça coute pas cher en temps
- ça déplace juste ce qu'il faut

Les vector me paraissent mieux, justement parce que je fais beaucoup d'itérations.

La solution shared_pointer, bien que très élégante, ne m'impressionne pas beaucoup au niveau des performances (x10 environ en temps), il me faut donc une autre solution.

Citation:

Et enfin, las but not least, est-ce que tu ne gagnerais pas du temps à utiliser du code existant ?

Moi, je code surtout pour me faire plaisir. Ça change tout mon rapport au temps ;-)

@bousk :

Ben écoute, merci d'apporter de la profondeur au débat. N'hésite surtout pas.

@leternel :

Merci, je vais aller creuser de ce côté là.
20/03/2015, 15h34
koala01

Salut,

Citation:

Envoyé par MrPchoun

@jblecanard :

Ben pas vraiment, c'est justement pour ça que j'utilise la méthode swap + pop_back :
- ça coute pas cher en temps
- ça déplace juste ce qu'il faut

Les vector me paraissent mieux, justement parce que je fais beaucoup d'itérations.

La solution shared_pointer, bien que très élégante, ne m'impressionne pas beaucoup au niveau des performances (x10 environ en temps), il me faut donc une autre solution.

Heuu... tu as fais des mesures concrètes et surtout correcte pour citer ce chiffre?

Es-tu sur que la différence de temps soit si importante ?

Es-tu sur que la différence ne vient pas de la nécessité d'augmenter la taille de ton tableau lors de l'ajout d'élément :question:

Car, il faut bien avouer que std::shared_ptr est, effectivement, une solution qui occasionne forcément une perte de performances, à cause du "comptage de références" qu'il implique afin de s'assurer que le dernier co-responsable d'un pointeur en vie s'occupe de le détruire.

Mais de là à dire que ce comptage de référence occasionne une telle perte, il y a de la marge : le comptage de référence est une opération à priori atomique, ce qui implique qu'il devrait s'effectuer en un temps minimum ;)

Ceci dit, les std::unique_ptr ne présentent pas cet inconvénient et représente, à mon sens, le type de pointeurs intelligent à utiliser "par défaut", dans le sens où on devrait commencer par utiliser std::unique_ptr et ne passer à un std::shared_ptr que si le besoin s'en fait sentir ;)

std::unique_ptr ne présente aucun overhead au niveau des performances, vu qu'il ne fait qu'une seule et unique chose : appeler delete sur le pointeur sous-jascent lorsqu'il est détruit (chose que tu devrais de toutes manières faire avant de perdre définitivement l'adresse à laquelle se trouve l'objet alloué dynamiquement ;)

Citation:

Moi, je code surtout pour me faire plaisir. Ça change tout mon rapport au temps ;-)

Bref, tu te tapes sur la tête avec un marteau en disant "mais ca fait tellement de bien quand ca s'arrête" :marteau:

Citation:

@bousk :

Ben écoute, merci d'apporter de la profondeur au débat. N'hésite surtout pas.

Et pourtant, il n'a pas tord...

void * est d'usage très régulier en C, mais est une véritable catastrophe en C++ qui propose un tas d'alternatives élégantes et bien plus sécurisantes (héritage public, paradigme générique, j'en passe et de meilleures)

La manière dont il s'est exprimé n'est sans doute pas celle te permet le plus facilement de trouver la solution à ton problème, mais elle a l'avantage de pointer exactement ton problème du doigt ;)

Citation:

Heuu... tu as fais des mesures concrètes et surtout correcte pour citer ce chiffre?

J'avais fait des mesures, oui. Après, le chiffre de 10 était peut être un peu gros, mais je me souviens de quelque chose d'assez énorme, qui m'a rebuté direct, pour ça que j'ai mis de côté la méthode smart pointer.

Je vais ré-exposer mon problème, parce que les solutions proposées ne me permettent vraiment pas d'y répondre.

Le problème avec toutes les implémentations d'Entity Component System que j'ai pu trouver (y compris anax), ce que toutes procédaient à peu près de la même manière :
Pour chaque entity
--Pour chaque system
----Si l'entity a les components que le system requiert
------get ces components
------update ces components

J'aimerais faire quelque chose qui demanderait moins d'itérations inutiles, du coup j'ai eu l'idée de stocker dans chaque système un vector de pointeurs vers les components des entity. Je développe :

L'entité A a les components Santé, Position et Name
L'entité B a les components Position et Name
L'entité C a juste le component Position

On pourrait stocker les entités de la manière suivante :

Code:

map<int,map<std::type_index,Component*>> entities.

Exemple : entities[3][typeid(Position)] = new Position; // On ajoute le component Position à l'entité 3

Le system S traite les entités qui possèdent les components Position et Name, il traitera donc les entités A et B
Eh bien dans S, il y aura un vector de pointeurs vers components (vector<void*> ou vector<Component*>, peu importe)
en [0], il pointera vers le component Position de l'entité A
en [1], il pointera vers le component Name de l'entité A
en [2], il pointera vers le component Position de l'entité B
en [3], il pointera vers le component Name de l'entité B

La fonction d'update gère toute seule tout ça.

Du coup, niveau algo, ça donne quelque chose du style
Pour chaque system
--get les components qui vont bien ([0] et [1] par exemple)
--update ces components

C'est quand même plus rapide niveau mise à jour.

J'ai déjà implémenté quelque chose de ce style là, mais j'aimerais l'optimiser. J'ai donc fait quelques tests :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 // super lent std::unordered_map<int,int> map = {{0,1},{1,8},{2,4},{3,6},{4,2},{5,8},{6,5},{7,4},{8,0},{9,1},{10,6},{11,3},{12,8},{13,4},{14,6}}; std::vector<int*> vector2; for (int i=0; i<15; i++) vector2.push_back(&map[i]); sf::Clock c; for (int i=0; i<1000; i++) for (int j=0; j<15; j++) (*vector2[j])++; std::cout<<c.getElapsedTime().asMicroseconds(); // rapide std::vector<int> vector1 = {1,8,4,6,2,8,5,4,0,1,6,3,8,4,6}; std::vector<int*> vector2; for (int i=0; i<15; i++) vector2.push_back(&vector1[i]); sf::Clock c; for (int i=0; i<1000; i++) for (int j=0; j<15; j++) (*vector2[j])++; std::cout<<c.getElapsedTime().asMicroseconds();
J'en ai donc déduit qu'il serait plus intéressant de stocker tous les components dans un seul vector, et de faire pointer les components des entités sur les éléments de ce vector. Ça donnerait :
Code:

1 2 3 vector<Component*> components; // tous les components, vraiment tous, c'est ici qu'on fait les new map<int,map<std::type_index,Component*>> entities. // les entités, on ne fait plus les new ici, on fait pointer sur components[x] vector<Component*> system; // pareil, ici, on fait aussi pointer sur components[x]
Mon problème, c'est que ça commence à devenir un véritable bordel si on veut supprimer un component d'une entity, et j'aurais voulu rendre ça beaucoup plus simple en stockant directement dans chaque component sa position dans les systems (c'est l'exemple de mon premier post) et aussi dans entities. Mon exemple n'était peut être pas super clean, mais l'idée était là.

Même en utilisant les shared_ptr, ça ne résoudrait pas mon problème, à savoir supprimer les éléments des containers.
Code:

1 2 3 vector<shared_ptr<Component>> components; // on peut éventuellement s'en passer map<int,map<std::type_index,shared_ptr<Component>> entities; vector<shared_ptr<Component>> system;

22/03/2015, 00h27
jblecanard

Citation:

Envoyé par koala01

Mais de là à dire que ce comptage de référence occasionne une telle perte, il y a de la marge : le comptage de référence est une opération à priori atomique, ce qui implique qu'il devrait s'effectuer en un temps minimum ;)

Attention là il y a un piège. Une opération sur un entier atomique (si l'architecture en dispose et on peut le vérifier avec atomic_is_lock_free) ne s'effectue pas "en un temp minimum". Les atomiques c'est bien mais ça a un coût : ça implique de synchroniser les caches entre les différents coeurs du processeur, ce n'est pas anodin du tout. C'est beaucoup plus cher que la même opération sur un entier non-atomique. Mal utilisé, ça peut carrément pourrir des perfos, même si ça les pourrira moins qu'un mutex qui réalise la même opération.

Encore une fois, ce sont les mesures qui doivent le déterminer. Mais il ne faut pas partir du principe que parce c'est atomique, l'impact est faible. Ca dépend.

Citation:

Envoyé par MrPchoun

Mon problème, c'est que ça commence à devenir un véritable bordel si on veut supprimer un component d'une entity, et j'aurais voulu rendre ça beaucoup plus simple en stockant directement dans chaque component sa position dans les systems (c'est l'exemple de mon premier post) et aussi dans entities. Mon exemple n'était peut être pas super clean, mais l'idée était là.

Même en utilisant les shared_ptr, ça ne résoudrait pas mon problème, à savoir supprimer les éléments des containers.

Hélas en effet ! J'ai eu exactement le même problème, et je l'ai réglé d'une manière assez peu catholique. L'idée, en gros est d'avoir des weak_ptr vers les components, et de ne stocker qu'un seul shared_ptr dans le propriétaire. C'est dommage car concrètement on n'a pas besoin de propriété partagée, mais on a besoin de pouvoir savoir si l'objet est encore en vie ou pas, et en standard seul weak_ptr sait faire cela. Au moment de faire ta passe d'update, tu en profites pour noter les références qui pointent vers des objets détruits et nettoyer le vector à la fin. Ca marche bien parce que tu sais que tu vas souvent faire des update, et donc que ce sera régulièrement nettoyé. Dans la pratique, je n'ai pas utilisé la lib standard et j'ai implémenté moi même une version de weak_ptr non thread safe, parce que j'avais qu'un seul thread et que je voulais pas payer l'atomicité, du coup c'est assez efficace. A toi de voir dans ton cas comment tu pourrais exploiter ça, tout dépend si tes suppressions sont fréquentes ou pas, comment tu multi-thread, etc.

En tout cas, ce n'est pas évident, et ça reste une affaire de compromis, nettoyer chaque collection qui a une référence vers ton composant aura un coût. Tu peux le payer à la suppression du composant, ou le payer plus tard lors d'une autre opération, mais la facture tombera. A mon avis, tu peux exploiter le fait que chaque système ne référence qu'un type de composant donné, je connais pas assez bien ton projet pour savoir ;).

Citation:

Envoyé par MrPchoun

J'avais fait des mesures, oui. Après, le chiffre de 10 était peut être un peu gros, mais je me souviens de quelque chose d'assez énorme, qui m'a rebuté direct, pour ça que j'ai mis de côté la méthode smart pointer.

Je viens de faire un petit exemple pour comparer les résultats. C'est vrai que les shared_ptr sont un peu plus coûteux que les pointeurs nus mais ce n'est une différence énorme non plus. J'ai lancer le code suivant quelques fois pour faire ces comparaisons:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <chrono>
#include <vector>
#include <memory>
#include <stdint.h>
 
void rawPointers(size_t nbElements)
{
    std::vector<uint32_t*> vect;
    vect.resize(nbElements);
    for (size_t i = 0; i < nbElements; ++i)
    {
        vect.push_back(new uint32_t(i));
    }
 
    for (size_t i = 0; i < nbElements; ++i)
    {
        delete vect[i];
    }
}
 
void sharedPointers(size_t nbElements)
{
    std::vector<std::shared_ptr<uint32_t>> vect;
    vect.resize(nbElements);
    for (size_t i = 0; i < nbElements; ++i)
    {
        vect.push_back(std::make_shared<uint32_t>(uint32_t(i)));
    }
}
 
int main()
{
   std::chrono::system_clock::time_point start;
   std::chrono::system_clock::time_point end;
 
   size_t nbElements = 1000000;
 
   start = std::chrono::system_clock::now();
   sharedPointers(nbElements);
   end = std::chrono::system_clock::now();
 
   std::cout << "Shared pointers - Elapsed Time: " <<  
             std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl;
 
 
   start = std::chrono::system_clock::now();
   rawPointers(nbElements);
   end = std::chrono::system_clock::now();
 
   std::cout << "Raw pointers - Elapsed Time: " <<  
             std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl;
 
 
   return 0;
}

J'obtiens les résultats suivant:

Code:

1
2
3
4
5
6
7
8
9
10
Shared Pointer Time (us)	 Raw Pointer Time (us)
190078	139325
196413	145892
207095	152433
183025	148365
193554	137738
177309	127623
 
191245.6667	141896
134.78%	100.00%

Sinon pour ton problème principal, je ne pense pas que le problème vienne des pointeurs nus ou des pointeurs intelligents mais de l'utilisation de std::map à l'intérieur d'une std::map. L'accès aux éléments d'une map est en log(N) si je ne me trompe pas, c'est à dire que c'est relativement lent pour chaque accès.

Je ne sais pas combien tu as de sortes de Component mais si ils sont peux nombreux et que tu dois activer désactiver régulièrement ceux-ci au niveau d'une entité, ne serait-il pas judicieux d'avoir pour chaque entité un tableau fixe de composant dont chaque case du tableau correspond à un composant particulier. Le problème de cette solution, c'est que tu dois faire un test à chaque fois pour savoir si le composant est utilisé ou non.
Voici un petit exemple:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Component
{
public:
   //tous les constructeurs etc
 
   virtual void update() = 0;
};
 
class ScoreComponent : public Component
{
public:
  static unsigned int id() const
  {
     return 0;
  }
  virtual void update()
  {
    //Quelque chose
  }
};
 
 
class InventoryComponent : public Component
{
public:
  static unsigned int id() const
  {
      return 1;
  }
 
  virtual void update()
  {
    //Quelque chose
  }
};
 
class Entity
{
private:
  std::vector<Component*> m_components;
 
public:
  Entity()
  {
     m_components.resize(2); //Le nombre de composants (tu peux faire un truc moins static en enregistrant les composants dans une factory par exemple) 
  }
 
  void attach(unsigned int id, Component * component)
  {
     m_components[id] = component;
  }
 
  void detach(unsigned int id)
  {
     m_components[id] = 0;
  }
 
  void update()
  {
     for (Components * comp : m_components)
     {
         if (comp)
         {
             comp->update();
         }
     }
  }
};
 
int main()
{
   ScoreComponent * score = new ScoreComponent();
   InventoryComponent * inventory = new InventoryComponent();
 
   Entity e;
   e.attach(ScoreComponent::id(), score);
   e.attach(InventoryComponent::id(), inventory); 
 
   e.detach(ScoreComponent::id());
   e.detach(InventoryComponent::id());
 
   delete score;
   delete inventory;
 
   return 0;
}

22/03/2015, 22h11
MrPchoun

@jblecanard

Pas bête, la méthode shared_ptr + weak_ptr, j'avais pas pensé à ça, ça peut toujours me délester des delete. Je vais approfondir ça :) Par contre, clean les vector à chaque boucle, ça me branche vraiment pas.. Le but c'est vraiment de gagner le max de temps dans le systems, quitte à en perdre un peu dans les ajouts/suppressions de Component, parce que les ajouts/suppressions ne se font pas à chaque boucle. Par contre les sytems, eux, tournent à chaque boucle :)

@darkman19320

Citation:

je ne pense pas que le problème vienne des pointeurs nus ou des pointeurs intelligents mais de l'utilisation de std::map à l'intérieur d'une std::map

À vrai dire dans l'implémentation de mon ECS j'utilise des std::unordered_map, mais ça change pas grand chose en fait, puisque comme mes systems stockent des pointeurs sur Component, j'ai pas le temps d'accès à me farcir à chaque boucle. Je comprends ton exemple (par contre, où sont les systems ? Jamais d'update dans les Components, c'est mal :aie: ) mais pourquoi faire un vector à taille fixe et pas déclarer directement un Component*[2] ? L'accès en [x] est constant, alors qu'il ne l'est pas sur un vector..

Ça pourrait être pas mal comme idée, mais je sais pas comment ça va se passer au niveau des perfs en fait. Parce que je serai quand même obligé de stocker mes Entity dans une unordered_map, pour avoir un accès constant à une Entity. Au delà de ça, quand je mets tous mes Components dans un seul vector, j'ai l'impression que ça soulage un peu le systems. Si je fais un truc style unordered_map<vector<Component*>> ça risque de plomber le cache, même si mon vector de Component stockaient des new, ce qui fait que c'était pas aligné en mémoire, j'ai l'impressions que les perfs étaient pas trop dégeux.

En plus, stocker des Component vides dans un tableau, ça m'embête un peu, ça gave la RAM pour rien, imagine que j'ai une vingtaine de Component (Position, Santé, Sprite, Mouvement, ça va vite..) :aie:

Bref, éternel choix cornélien entre programme rapide/programme lourd !

Je vais adapter un peu ton code à ma sauce, je verrai bien !

Merci de vos réponses :oops:
22/03/2015, 22h48
darkman19320

Citation:

Envoyé par MrPchoun

L'accès en [x] est constant, alors qu'il ne l'est pas sur un vector..

Si si l'accès aux éléments à un vector est constant.

Sinon c'est vrai que je n'ai pas ajouté les System, je ne connais pas trop ce pattern du coup, j'ai fait au plus simple ^^

Citation:

Envoyé par MrPchoun

En plus, stocker des Component vides dans un tableau, ça m'embête un peu, ça gave la RAM pour rien, imagine que j'ai une vingtaine de Component (Position, Santé, Sprite, Mouvement, ça va vite..).

Tu ne stockes pas les Component mais des pointeurs sur des Components. Donc dans le pire des cas, dans ton tableaux tu auras une vingtaine de pointeurs donc de taille fixe. Mais je comprends ton point de vue.

Citation:

Envoyé par MrPchoun

Bref, éternel choix cornélien entre programme rapide/programme lourd!

Exactement, toujours le même problème. Bon courage!