Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1711 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  [C++/résolu] Pool

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[C++/résolu] Pool

n°1335717
nargy
Posté le 30-03-2006 à 17:41:52  profilanswer
 

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

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
mood
Publicité
Posté le 30-03-2006 à 17:41:52  profilanswer
 

n°1335723
_darkalt3_
Proctopathe
Posté le 30-03-2006 à 17:48:36  profilanswer
 

La STL ne te convient ?

n°1335725
nargy
Posté le 30-03-2006 à 17:50:54  profilanswer
 

> 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...

n°1335729
nargy
Posté le 30-03-2006 à 17:59:35  profilanswer
 

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
n°1335738
_darkalt3_
Proctopathe
Posté le 30-03-2006 à 18:05:12  profilanswer
 

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

n°1335745
nargy
Posté le 30-03-2006 à 18:11:41  profilanswer
 

ok je potasse ça..

n°1335785
nargy
Posté le 30-03-2006 à 19:04:25  profilanswer
 

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

Code :
  1. using namespace std;
  2. class Test3a
  3. {
  4.   public:
  5.   char a[256];
  6. };
  7. typedef vector<Test3a> Test3b;
  8. class Test3
  9. {
  10.   public:
  11.   Test3b d;
  12.   Test3(): d(1) {}
  13. };
  14. 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...

n°1335803
nargy
Posté le 30-03-2006 à 19:43:14  profilanswer
 

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.

n°1335987
nargy
Posté le 31-03-2006 à 00:25:05  profilanswer
 

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
n°1336072
_darkalt3_
Proctopathe
Posté le 31-03-2006 à 09:58:14  profilanswer
 

:jap:

mood
Publicité
Posté le 31-03-2006 à 09:58:14  profilanswer
 

n°1336348
nargy
Posté le 31-03-2006 à 14:40:24  profilanswer
 

Yesssss une frame par seconde de plus!


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  [C++/résolu] Pool

 

Sujets relatifs
[RESOLU] cherche script pour defilement de photos[Résolu] Un compteur de mots dans Word
Problème id dans création de tableau dynamique [résolu][resolu]Fonction sqrt non reconnue...
Bouton abandonner en javascript [RESOLU][RESOLU] Comment dessiner une fenêtre?
[Résolu] Vider le cacheBloc Serveur comme nukeClan sur un site HTML [résolu]
[résolu][VBA]Afficher mon document Word[RESOLU] Petit script VBS
Plus de sujets relatifs à : [C++/résolu] Pool


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR