Discussion :

[LittleWhite]

Bonjour,

Je cherche à faire une pool mémoire permettant d'éviter toutes allocations de mémoire durant l'exécution du programme (enfin, plus précisément, durant la boucle de jeu).
Ma première idée est de reposer sur std::vector et de jouer avec le reserve(), que j'appelle à la construction de ma pool. Ok, c'est bien, mais lorsque je veux mettre un élément dans la pool, cet élément va être créé puis placé dans la pool (surement à travers une copie).

Heureusement, j'utilise emplace_back() permettant d'éviter la copie, si je ne dis pas de bêtises. Malheureusement, il y a toujours allocation de mémoire, notamment à la création de mon nouvel élément à mettre dans la pool.
En théorie, pour que ma pool soit parfaite, il ne faudrait pas que les éléments soient créés lors de la boucle de jeu, mais simplement à la création de la pool.

Pour ce faire, je devrais construire ma pool (mon std::vector) avec un resize(). Ainsi, les éléments seraient déjà prêt et je n'aurais qu'à les utiliser. Dans la boucle de jeu, je vais créer des objets qui seront dans la pool. En théorie, on les construiraient (avec des arguments), mais là, ce n'est pas exactement ce que je veux faire. Et là, je ne vois pas exactement comment faire, pour injecter de nouveaux éléments (ou du moins, des données pour construire les éléments) dans la pool, sans jamais faire d'allocation mémoire pour ces éléments.

Du coup, ma question est : comment bien faire. Je pensais que la sémantique de déplacement pourrait faire ce type "d'injection".

Voici mon implémentation de pool actuelle : https://github.com/LittleWhite-tb/Pa...ObjectPool.hpp

Est-ce que la meilleure solution est bien d'allouer la mémoire avec resize() (pour que tous les éléments soient créé), puis, lorsque j'ai besoin de faire un get() pour récupérer l'élément. Mais dans ce cas là, comment je construis l'élément (comme une réinitialisation, ou autre ?). Normalement, j'utiliserai un constructeur, mais dans un tel cas, cela n'irait pas, je crois, notamment car on ne peux pas appeler le constructeur à la main.

[Bousk]

Salut,

j'en ai jamais vraiment créé, mais utilisé, et je suis surpris que tu n'aies pas de méthodes Get et Release ?
Tel que je le vois, tous tes éléments sont créés au début, et l'utilisation de la pool par après est juste du Get/Release. Aucune construction d'objet, donc aucun constructeur appelé, on réutilise l'existant. Pas plus de destructeur.
Du coup il faudrait non pas un vector<T> mais un vector<struct {T m; bool used;}>.

A moins que tu ne parles que de réserver un espace mémoire pour tes allocations, donc ce serait plus l'utilisation d'un buffer qu'il te faudrait ? http://www.codeproject.com/Articles/...o-implement-it

[mintho carmo]

Je ne sais pas si tu connais le livre "game programming pattern". Si ce n'est pas le cas, tu as un chapitre sur les object pool dedans, cela devrait t'aider : http://gameprogrammingpatterns.com/object-pool.html

[LittleWhite]

Je ne sais pas si tu connais le livre "game programming pattern". Si ce n'est pas le cas, tu as un chapitre sur les object pool dedans, cela devrait t'aider : http://gameprogrammingpatterns.com/object-pool.html

C'est exactement comme ça que je l'ai appris. Malheureusement, je trouve ce design très C/C++, mais pas C++11. Là, j'essaie de faire le code le plus simple possible (en utilisant au mieux l'existant), tout en ayant exactement ce que je veux (et qu'il soit facile à utiliser (et difficile de mal utiliser aussi)).

Par contre, une chose que cet exemple ne montre pas, c'est la technique du swap. En théorie, dans une pool, on a jamais besoin de garder un boolean pour chaque élément. Il suffit de swap chaque élément mort, à la fin de la liste (le swap se fait entre l'élément actuel et le dernier actif) et de diminuer le compteur d'élément vivant. Ainsi, les éléments vivant sont absolument toujours au début, ce qui permet de, balancer la liste des particules directement au GPU car le tampon est déjà prêt (le GPU s'en fout de ce qui est mort ou vivant, il veux juste un tampon contigu à afficher). Cela évite aussi le clearing (tout comme l'utilisation du boolean).
C'est d'ailleurs grâce à cette technique que je pouvais reposer complètement sur std::vector, lors de mon implémentation, montrée ci-dessus.

j'en ai jamais vraiment créé, mais utilisé, et je suis surpris que tu n'aies pas de méthodes Get et Release ?

Exactement. Cela est "étonnant" et d'ailleurs c'est une des fautes de mon design. Par contre le Release, chez moi, c'est le purge(), car je ne veux pas l'utilisateur de la pool garde les instances dans un coin de sa mémoire pour pouvoir dire : "ah, tiens, maintenant je release cela". Le purge() peut être vu comme moins optimisé, sachant que le parcours pour savoir ce qu'il faut virer ou non, est fait sur toute la liste.

Mon problème du Get() (ce que je n'aime pas pour le moment et je cherchais à faire mieux), c'est qu'il chaque classe que je vais mettre dans la pool() doit avoir une fonction init() (une fonction similaire à un constructeur, sans pour autant être un constructeur) afin de mettre les valeur d'initialisation de l'objet.

Pour ce que vous appelez buffer, je connais aussi et c'est ultra cool pour le débogage et les systèmes ultra limités en mémoire. Par contre, je ne veux pas tomber jusqu'à ce niveau (ça me casse les pieds de refaire des allocateurs et une gestion de la fragmentation et ainsi de suite ).

[jo_link_noir]

Ne pas utiliser vector serait beaucoup mieux en fait, justement car il fait appel au constructeur. Pour le faire à la main: placement new.
(note que emplace_back ou push_back revient au même dans ton code: les 2 appelleront le constructeur de mouvement).

Un petit exemple avec le placement new:

Code :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#include <new>
#include <utility>
#include <algorithm>
 
template<class T>
struct Buffer
{
  Buffer(std::size_t sz)
  : p(static_cast<T*>(::operator new(sz * sizeof(T))))
  , begin(p)
  , end(p + sz)
  {}
 
  ~Buffer()
  {
    std::for_each(begin, p, [](T & x) { x.~T(); });
    ::operator delete(begin);
  }
 
  template<class... Args>
  T & create(Args && ... args)
  {
    assert(p != end);
    new (p) T(std::forward<Args>(args)...);
    return *p++;
  }
 
private:
  T * p;
  T * begin;
  T * end;
};

Par contre, tu ne pourras pas faire la technique du swap car elle modifie les références. Parmi les solutions qui me viennent en tête
- Passer par un "buffer" (un peu comme le code au-dessus) + un tableau de T* sur le buffer. Le swap s'applique sur le tableau sans invalider les références.
- Garantir que le dernier élément créé soit le premier supprimé .

[mintho carmo]

Remarque pour le move : si ton type T est une structure qui ne contient pas des objets dynamiques (pointeurs, vector, string, etc), alors ton move fera une copie. Et comme en général, le but d'un pool object est d'éviter les allocations, c'est généralement le cas. Donc ta fonction add fera une copie.

Code :

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

1
2
3
struct Data { int i, j, k; };
Data d;
pool.add(d); // copie(

Quand a ta fonction create, tu crées un objet par défaut avant de l'utiliser (et donc potentiellement ne pas utiliser les valeurs par défaut que tu as utilisé.

Code :

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

1
2
auto& d = pool.create();
d.i = 1; // initialisation de i dans create est inutile

Pour le add, remplace par le placement new de jo_link_noir (qui est en fait un emplace_back). Tu peux aussi utiliser vector + emplace_back. Si tu ne veux pas utiliser un vector, tu peux, mais il faudrait quand même créer une capsule RAII plutôt que de faire comme jo_link_noir (cf l'article de Stroustrup sur l'exception safe de vector). Regarde aussi std::get_temporary_buffer plutôt que new[size]

[LittleWhite]

J'ai encore du mal à vous suivre.

Tu peux aussi utiliser vector + emplace_back.

Donc, en théorie, on peut y arriver, sans jouer avec les new/delete ?
Pourquoi dans ma version cela ne fonctionnait pas alors ? À cause de l'utilisation de la référence ? Il faut mieux que je std::forward tous les arguments permettant la construction d'une instance ?

[mintho carmo]

Donc, en théorie, on peut y arriver, sans jouer avec les new/delete ?
Pourquoi dans ma version cela ne fonctionnait pas alors ? À cause de l'utilisation de la référence ? Il faut mieux que je std::forward tous les arguments permettant la construction d'une instance ?

Oui pour new/delete
Oui pour la référence. Passer un objet par référence veut dire que ton objet existe dans ton code appelant, avec sa propre adresse mémoire. Lorsque tu fais le push ou l'emplace, tu crées un objet a une autre adresse mémoire. Il y a donc forcement une copie.
Pour éviter la copie, il faut soit créer l'objet dans ton pool et retourner une référence dans ton code appelant, soit créer directement ton objet dans le pool, avec les arguments passés en paramètres.
Par contre, pas besoin de passer chaque paramètre en forward, tu utilises un universal reference (varaidic template + rvalue ref), comme dans le code de jo_link_noir.

A mon sens, les personnes ne preferent pas utiliser vector, tout simplement parce qu'il en fait trop. Du coup, cela peut avoir un cout sur les performances. Et comme un pool object est un conteneur, autant le faire directement a partir de zero que de se baser sur un conteneur existant.
(il doit etre possible de concevoir le pool object comme un adaptater - comme std::stack ou std::queue - pour pouvoir l'utiliser avec d'autres conteneurs que vector, par exemple array ou dynarray)

[ternel]

Tu devrais pouvoir y arriver, dans le sens ou emplace_back ne crée pas de copie. Il crée un objet à la fin du bloc.
En gros, c'est un placement new.
Par contre, il y a une grosse subtilité: reserve permet d'allouer à l'avance un gros buffer.
Cela dit, je ne sais pas si retirer des éléments ne peut pas déclencher un vidage. (je n'ai pas souvenir du détail).

[mintho carmo]

Cela dit, je ne sais pas si retirer des éléments ne peut pas déclencher un vidage. (je n'ai pas souvenir du détail).

Non. Vector était conçu pour ne jamais diminuer sa mémoire, uniquement l’augmenter... ce qui posait parfois des problèmes. Il y avait un hack avec swap pour forcer la libération de la mémoire réservée.
Maintenant, il y a shrink_to_fit pour cela (C++11).

[LittleWhite]

Je vois et je crois que j'arrive à voir ce qu'il faut faire.

Par contre, il y a une grosse subtilité: reserve permet d'allouer à l'avance un gros buffer.

Sauf que les objets ne sont pas construit. L'espace est alloué, certes, mais les objets ne sont pas.
Du coup, avec reserve, y a pas moyen d'éviter une allocation d'un objet temporaire, pour l'injecter (copie) dans l'espace alloué (je ne suis pas sur de bien m'exprimer).

[mintho carmo]

(je ne suis pas sur de bien m'exprimer)

Pas sûr

[Médinoc]

Normalement, reserve() au début puis constructions avec emplace_back() devrait éviter tout objet temporaire (ou du moins, toute copie, si un move est possible).

[LittleWhite]

Et comment pourrais-je vérifier si c'est bien le cas ? Je me suis penché du coté de Valgrind et de Massif ... mais je n'ai pas eu de réponse très claire durant mes tests.
@Medinoc : si vous dites que cela marche, alors ma première implémentation (voir GitHub) était assez juste, sauf pour le coup de la référence. Dois-je utiliser une signature en '&&' pour la méthode add() ?

@mintho carmo : Oui, désolé, c'est parce que ce n'est pas clair dans ma tête

[Médinoc]

Mettre un && dans le Add(), ça ferait un move (il y aurait donc au moins l'objet temporaire construit, puis un move vers le vecteur).
emplace_back() fonctionne non pas avec les objets, mais avec les paramètres du constructeur. add() devrait donc être déclarée de la même façon qu'emplace_back(), c'est-à-dire probablement une fonction template variadique, et devrait forwarder ses arguments à emplace_back() comme emplace_back() les forwarde au constructeur.

[LittleWhite]

Voici ma nouvelle version : https://github.com/LittleWhite-tb/Pa...ObjectPool.hpp
(La fonction create(), disons qu'on peut l'ignorer, sachant qu'elle n'est jamais utilisée, c'est la fonction add(), qui m'intéressais.)

Comment testeriez vous, pour être certain qu'il n'y a pas d'éléments créer à la volée et que toute la mémoire est allouée au début. Je veux dire, côté test, pas côté code (genre, valgrind/massif, mais je n'arrive pas à en extraire l'information adéquate).

[jo_link_noir]

Une idée: un objet qui référence un int et l'incrémente à chaque copie. Vérifier ensuite que la valeur attendue est la même que le nombre de copie supposé.

[mintho carmo]

(HS : n'oublie pas de mettre noexcept dans le constructeur par mouvement de T - si possible - pour conserver la strong garantie exception de emplace_back)

(HS2 : et tu devrais prendre l'habitude d'utiliser using au lieu de typedef)

[Bousk]

En fait quand je parlais de Get et Release, c'est pour cette utilisation:

Code :

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

1
2
3
4
 
T* pObj = myPool.Get();
// do stuff...
myPoll.Release(pObj);

[Kaamui]

Bonjour,

Je cherche à faire une pool mémoire permettant d'éviter toutes allocations de mémoire durant l'exécution du programme (enfin, plus précisément, durant la boucle de jeu).
Ma première idée est de reposer sur std::vector et de jouer avec le reserve(), que j'appelle à la construction de ma pool. Ok, c'est bien, mais lorsque je veux mettre un élément dans la pool, cet élément va être créé puis placé dans la pool (surement à travers une copie).

Je trouve cette conversation intéressante mais je me pose quelques questions sur la finalité : tu parles de boucle de jeu, tu vas donc avoir un jeu où toutes les instances ont une durée de vie égale à la durée d'exécution du code séparant chaque instanciation de la boucle du jeu additionnée à la durée d'exécution de ta boucle de jeu. Pourquoi ne pas gérer cela sous forme d'un bête catalogue de ressources ? Tu cherches à éviter d'utiliser plus de mémoire ou plus d'objet ?

Je demandes cela car je trouve ton code un peu compliqué (mais je soupçonne de ne pas comprendre la finalité totalement, le code est peut-être juste complexe)