[C++/résolu] Pool

Pool [C++/résolu] - C++ - Programmation

Marsh Posté le 30-03-2006 à 17:41:52    

Salut les C++eurs! :)
 
Je cherche à faire un pool d'objets.
 
Cas particulier d'utilisation:

  • Au démarrage, allocation jusqu'à 100K objets de plusieurs classes dont certaines de tailles identiques et d'autres de tailles différentes.
  • Réutilisation de ces objets un nombre illimité de fois.

[:chatigret] Après recherches d'imlémentations & d'algos, j'ai concocté un code composé de deux classes template:

  • class Pool, contenant une pile chaînée dans un tableau. La pile est composée des éléments: soit libérés et chaînés, soit occupés et avec meta informations.
  • class Poolable, à faire hériter par d'autres classes pour être mises en pool.


Un peu de code:

Code :
  1. #include <stdio.h> // printf
  2. #include <stdlib.h> // malloc/free
  3. #include <sys/time.h> // gettimeofday
  5. // taille max d'un pool
  6. const unsigned int maxPoolElements=100000; // 100K
  8. // métadonnée sur l'allocation, kedal pour l'instant
  9. typedef void PoolAllocInfo;
  11. // une classe template de Pool, gérant la taille ``elementSize``
  12. template <size_t elementSize> class Pool
  13. {
  14.   // Le pool est constitué d'une pile chaînée, template statique
  15.   static class Pile
  16.   {
  17.     // la pile chaînée est elle-même composée d'éléments
  18.     struct PileElement
  19.     {
  20.       // l'objet est mis en premier pour faciliter free()
  21.       // rem: conséquences sur l'endianness?
  22.       char c[elementSize]; // réserver de l'espace pour l'objet
  23.       // métadonnées
  24.       union
  25.       {
  26.         // soit l'élément est libre et pointe sur le prochain libre...
  27.         PileElement* next;
  28.         PoolAllocInfo* info; // ...soit il est occupé
  29.       } meta;
  30.     };
  32.     PileElement* pile; // la pile (tableau avec alloc standard)
  33.     PileElement* first; // le premier élément libre
  34.     PileElement* last; // le dernier élément, pas encore utilisé
  36.     public:
  38.     Pile() // et hop! une nouvelle pile
  39.     {
  40.       // alloc standard
  41.       pile=first=(PileElement*)malloc(sizeof(PileElement)*maxPoolElements);
  42.       // boucle avec arithmétique pointeurs...
  43.       PileElement* m=first+maxPoolElements-1;
  44.       // ...où on initialise les métadonnées (meta.next)
  45.       for(PileElement* c=first;c<m;)
  46.       { PileElement* n=c+1; c->meta.next=n; c=n; }
  47.       // cas à part: initialiser last et sa méta
  48.       last=m;
  49.       m->meta.next=0;
  50.     }
  52.     inline ~Pile() // et hop! une pile en moins
  53.     { free(pile); }
  55.     inline void* allocate() // là on alloue
  56.     {
  57.       if(first) // s'il reste de la place
  58.       {
  59.         // on dépile de la liste libre
  60.         PileElement* e=first; // libre ne l'est plus...
  61.         first=e->meta.next; // ...et le pochain est libre
  62.         return e;
  63.       } // un petit message qui rappelle le Basic sur Z80
  64.       else { fprintf(stderr,"Missing memory\n" ); exit(1); }
  65.     }
  67.     inline void free(void* x) // Mémoire, par ordre de SM, je vous libère!
  68.     {
  69.       // on prie pour que ``x`` soit un pointeur retourné par allocate()
  70.       PileElement* e=(PileElement*)x;
  71.       // on empile dans la liste libre
  72.       e->meta.next=first;
  73.       first=e;
  74.     }
  76.     // les objets alloués sont fichés
  77.     inline static const PoolAllocInfo* info(void* x)
  78.     {
  79.       PileElement* e=(PileElement*)x; // abracadabra!
  80.       return e->meta.info;
  81.     }
  82.   } pile; // ça c'est la pile (static) pour la taille <elementSize>
  84.   public: // service public
  85.   inline static void* allocate() { return pile.allocate(); }
  86.   inline static void free(void* x) { return pile.free(x); }
  87.   inline static const PoolAllocInfo* info(void* x) { return pile.info(x); }
  88. };
  90. // dans la famille template <size_t elementSize>...
  91. template <size_t elementSize>
  92. // ...je veux la pile de Pool!
  93.   typename Pool<elementSize>::Pile Pool<elementSize>::pile;
  95. // classe à hériter pour être mis en pool
  96. template <class Element> class Poolable // nom à la c...
  97. {
  98.   public:
  100.   inline static void* operator new (size_t s) throw() // new Element
  101.   {
  102.     if(s!=sizeof(Element)) // le throw, c'est pour le chien
  103.     { fprintf(stderr,"Memory allocation size mismatch\n" ); exit(1); }
  104.     return Pool<sizeof(Element)>::allocate();
  105.   }
  107.   inline static void operator delete (void* p) // delete Element
  108.   { Pool<sizeof(Element)>::free(p); }
  110.   inline const PoolAllocInfo* allocInfo() // info Element
  111.   { Pool<sizeof(Element)>::info(this); }
  112. };
  114. // petit test, facile à utiliser finalement ce poolable,
  115. // mais pas très beau le doublon dans le template
  116. class Test1: public Poolable<Test1>
  117. { public: char a[256]; };
  119. // la même, pas poolable
  120. class Test2
  121. { public: char a[256]; };
  123. // pour comparer les deux tests
  124. typedef Test2 Test;
  126. // test...
  127. int main()
  128. {
  129.   const int n=maxPoolElements;
  130.   Test* t[n]={0};
  131.   struct timeval tv0; gettimeofday(&tv0,0);
  133.   // 20M de tests
  134.   for(unsigned int i=0;i<20000000/n;i++)
  135.   {
  136.     for(unsigned int j=0;j<n;j++)
  137.     if(t[j])
  138.     { delete t[j]; t[j]=0; }
  139.     else
  140.       t[j]=new Test();
  141.   }
  143.   // temps de test
  144.   struct timeval tv; gettimeofday(&tv,0);
  145.   int usecs=tv.tv_usec-tv0.tv_usec;
  146.   long secs=tv.tv_sec-tv0.tv_sec;
  147.   if(usecs<0) { usecs+=1000000; secs--; }
  148.   printf("%d.%06d\n",secs,usecs);
  150.   // libérer
  151.   for(unsigned int i=0;i<n;i++)
  152.     if(t[i]) delete t[i];
  154.   return 0;
  155. }

Après compilation gcc/linux, j'obtiens les temps suivants:

* pool    : 6.397160 sec.
* new/del : 10.888527 sec.

Mais certains points ne me satifont pas:

  • doublon du nom de la classe de base avec la classe poolable
  • gestion des erreurs... médiocre
  • métadonnées et structures... je ne mesure pas l'impact des compilateurs sur l'alignement/endianness/sizeofs de ma structure d'élément de pile
  • gain de temps presque négligeable avec des objets à initialiser
  • piles de taille statiques, à rendre plus dynamique(?)
  • métadonnées inexploitées...


Si vous avez des remarques ou des suggestions sur mon code, elles sont les bienvenues :)
 
Merci par avance :jap: !


Message édité par nargy le 31-03-2006 à 00:26:04
Reply

Marsh Posté le 30-03-2006 à 17:41:52   

Reply

Marsh Posté le 30-03-2006 à 17:48:36    

La STL ne te convient ?

Reply

Marsh Posté le 30-03-2006 à 17:50:54    

> La STL ne te convient ?
aucune idée, j'ai pas essayé... quand j'ai vu __pool_allocator avec ``__`` j'ai pris peur!
mais je ne suis peut être pas tombé sur la bonne doc...

Reply

Marsh Posté le 30-03-2006 à 17:59:35    

Dans la doc de boost:: object_pool, j'ai les temps suivants:
t.malloc() -> Amortized O(1),
t.free(p) -> O(N).
 
Je sais pas comment ils font leurs pools, mais l'algo que j'utilise est en O(1) (strict).
 
Même avec un pool dynamique, ça ne devrait pas dépasser O(lg(N))...


Message édité par nargy le 30-03-2006 à 17:59:49
Reply

Marsh Posté le 30-03-2006 à 18:05:12    

boost et STL sont optimisées pour ce genre de containers
 
http://www.sgi.com/tech/stl/

Reply

Marsh Posté le 30-03-2006 à 18:11:41    

ok je potasse ça..

Reply

Marsh Posté le 30-03-2006 à 19:04:25    

Tu est toujours là _darkalt3_?
 
jai essayé le test ci-dessus avec:
 

Code :
  1. using namespace std;
  3. class Test3a
  4. {
  5.   public:
  6.   char a[256];
  7. };
  9. typedef vector<Test3a> Test3b;
  11. class Test3
  12. {
  13.   public:
  14.   Test3b d;
  15.   Test3(): d(1) {}
  16. };
  18. typedef Test3 Test;


Mais c est horriblement lent:

* pool    : 6.397160 sec.
* new/del : 10.888527 sec.
* stl     : 15.035032 sec.


je my prends peut-être pas de la bonne façon...

Reply

Marsh Posté le 30-03-2006 à 19:43:14    

ha ouais, c est pas ça, d'après le source std_allo.h c'est un algo en O(N) aussi.
ok, bon tant pis.

Reply

Marsh Posté le 31-03-2006 à 00:25:05    

Bon, en ce qui concerne STL, l allocateur standard dont sont dérivés les autres possède les caractéristiques suivantes:
- algorithme en O(N/20),
- alloue 16 piles de 8 à 128 bytes
 
En ce qui concerne le premier point, ça rend l allocateur moins performant qu un new/delete.
 
En ce qui concerne le deuxième point, je doit gérer entre autre deux classes dont le sizeof est plus proche de 256 que de 128, ça ne me convient pas non plus.
 
Par contre jai trouvé la manière d utiliser les métadonnées de mon implémentation pour rendre le pool dynamique: allouer une pile deux fois plus grande à chaque fois, garder la pile en métadonnée. Comme les allocations atteignent un maximum je peut n être jamais obligé de désallouer ces piles.
 
L algo résultant est en O(lg(N)), et utilise 2 fois plus de mémoire temporaire, ce qui me convient. A vue de nez elle reste plus rapide que new/delete.
 
Merci pour ta participation _darkalt3_ :)


Message édité par nargy le 31-03-2006 à 11:39:05
Reply

Marsh Posté le 31-03-2006 à 09:58:14    

:jap:

Reply

Marsh Posté le 31-03-2006 à 09:58:14   

Reply

Marsh Posté le 31-03-2006 à 14:40:24    

Yesssss une frame par seconde de plus!

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed