allocation dynamique par blocs

Version imprimable

18/08/2010, 13h42
tachaout

allocation dynamique par blocs

Bonjour,

je dois créer un arbre d'objets à partir d'une liste. Le principe est le suivant:
Pour chaque objet O de la liste

si O existe déjà dans l'arbre (sa valeur) alors

on passe à l'objet suivant de la liste
sinon
créer un nouvel objet O' (avec new) qui est copie de O
Insérer O' dans l'arbre
Passer à l'objet suivant de la liste
FinSi
FinPour

Mon problème est que les multiples appels à "new" retardent énormément l'exécution. Je crois savoir qu'on pouvait s'allouer des blocs entiers de mémoire
et aller piocher dedans quand on a besoin de faire un "new" pour un nouvel objet.

Quelqu'un aurait-il l'amabilité de nous expliquer comment ça marche.
18/08/2010, 14h22
Invité

Bonjour,
Ca m'étonnerait assez que vous réussissiez à faire un algorithme d'allocation d'espace mémoire plus rapide que celui qui existe déjà.
Par contre, si vous faites beaucoup de "new + delete", là ça vaut le coup de réserver un tableau à l'avance.
Je pense que le mieux serait que vous montiez votre code.
18/08/2010, 14h36
Joel F

Alloue un bloc d'octet nu une bonne fois pour toute et utilise le new de placement pour construire tes objets dans la mémoire préallouée.

boost::pool résout déjà ce genre de problème.

Merci pour ces premières réponses.
Je mets une partie du code permettant de préciser le problème. Il s'agit
de construire un arbre préfixe à partir d'une liste de mots. J'ai pensé
m'allouer un vecteur de taille n d'objets et aller piocher dedans. Quand le vecteur est épuisé, on augmente sa taille ex: on y ajoute n cases. Comme ça, si au total j'ai besoin de faire m appels à "new", avec le vecteur, j'en ferai seulement m/n fois.

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
 
list<String> lesMots; //exemple: les mots du dictionaire
 
class noeud
{
public:
	char lettre;
	list<noeud *> les_fils; // la liste des fils
};
 
list<noeud *> arbreP;
 
void inserer_dans_arbre(unsigned int i, String &v, list<noeud *> &racine,  unsigned int &k){
	// i est la position dans le mot
	// v est le mot
	// racine est la racine du sous-ararbre dans lequel on insère
	// k est la taille du mot
	list<noeud *>::iterator it=racine.begin();
	while(it!=racine.end() && (*it)->lettre!=v[i]){
		it++;
	}
	if(it!=racine.end()){//il y est, donc juste passer à la lettre suivante
		if(i+1<k){//on n'a pas épuisé le mot
			inserer_dans_arbre(i+1, v, (*it)->les_fils, k);
		}
	}
	else{//il n'y est pas
		//////////////////////////////////////////////////////////////////////
		noeud * p=new(noeud); //c'est la partie couteuse
		/////////////////////////////////////////////////////////////////////
		p->lettre=v[i];
		racine.push_back(p);
		if(i+1<k){//on n'a pas épuisé le mot
			inserer_dans_arbre(i+1, v, p->les_fils, k);
		}
	}
}
int main(){
	//On récupère la liste des mots. Ensuite on crée l'arbre comme suit
	for(list<String>::iterator it=LesMots.begin(); it!=LesMots.end(); ++it){
		size_t k=(*it).size();
		inserer_dans_arbre(0, (*it), arbreP, k);
	}
	return 0;
}

18/08/2010, 15h17
Flob90

Si ce sont des petits objet, loki::SmallObject peut t'aider.

@Pierre Dolez: Le système d'allocation n'est pas parfait surtout pour les petits objets, pour ca qu'il existe plétore d'allocateur pour eux (j'ai cité Loki mais il y en a peut-etre dans boost).
18/08/2010, 17h51
Invité
Oui, ça ressemble tout à fait à une structure de liste chainée.
Ce qui me gène un peu dans l'organisation, la classe Noeud comporte 2 informations la lettre (1 octet) et un pointeur sur la liste des noeuds fils 4 octets. C'est à dire que l'espace utilisé, sauf la lettre, ne sert qu'à décrire l'arbre.
Pour un essai de rapidité, essayez de remplacer
Code:

1 2 3 noeud * p=new(noeud); //c'est la partie couteuse // par noeud *p=(noeud*)malloc(sizeof(noeud));
D'autre part, vous passez des paramètres à la fonction par référence, c'est à dire que leur valeur sera modifiée au retour, est-ce souhaité? ne vaudrait-il pas mieux mettre const ?
Avez-vous un fichier d'essai?
Je suppose que le but est d'utiliser l'arbre, une fois réalisé, ça ne me semble pas trop grave si sa création demande un peu de temps, pourvu que l'utilisation est rapide.
18/08/2010, 18h59
tachaout
j'ai essayé de remplacer
Code:

1 2 3 noeud * p=new(noeud); par noeud *p=(noeud*)malloc(sizeof(noeud));
il semble qu'il y a un problème avec l'appel de p->les_fils;
ça fait une erreur d'exécution. On dirait qu'il ne la crée pas cette liste.
j'ai par exemple testé :
cout<<p->les_fils.size()<<endl;
l'exécution s'arrête

Sinon, je suis en train de me documenter sur les allocateurs, j'avoue que
je ne connaissais pas <memory> (débutant :oops:)

Merci pour les bons tuyaux
18/08/2010, 19h57
Invité

Bonsoir,
Ca ne m'étonne qu'à moitié.
En effet les deux lignes sont équivalentes. Il y aurait pu avoir une petite différence de temps d'exécution : information intéressante, mais c'est plus grave, vous adressez probablement des régions mémoire interdites.
J'ai presque terminé de le réécrire à ma sauce, à demain.
18/08/2010, 20h06
Davidbrcz

Citation:

En effet les deux lignes sont équivalentes

Absolument pas !!!! new appelle le constructeur de l'objet, malloc ne fait que réserver de la mémoire. Les comportements NE SONT PAS DU TOUT équivalents, ce qui explique le plantage décrit (la mémoire pour le noeud est réservée mais aucun n'objet n'est construit, en particulier les_fils).

Sinon, tout a déjà été dit par Joel Et Flob90 (allocateur spécialisé dans loki ou boost, placement new si on veut faire les choses à la main)
18/08/2010, 20h40
Goten

boost::pool est plus que controversé aux dernières nouvelles...
18/08/2010, 20h54
Flob90

@Goten: Tu aurais un document/une discussion sur le sujet ? :)
18/08/2010, 21h34
Goten

Non, je l'ai juste croisé sur la ML plusieurs fois. (certaine personne parlait de le deprecated il me semble) car free() (enfin, l'équivalent sémantique, je me rappelle plus le nom exact) est vraiment lent IIRC!.
19/08/2010, 08h55
Joel F

Oui je m'en rappelles. Y a un bug dans la desallcoation d'une variante de pool.
Llib en elle meme n'a pas été rafraichie depuis un bout de temps.

Patches welcome.
19/08/2010, 11h07
Invité

@Davidbrcz

Citation:

Citation:
En effet les deux lignes sont équivalentes
(réponse)
Absolument pas !!!! new appelle le constructeur de l'objet, malloc ne fait que réserver de la mémoire. Les comportements NE SONT PAS DU TOUT équivalents, ce qui explique le plantage décrit (la mémoire pour le noeud est réservée mais aucun n'objet n'est construit, en particulier les_fils).

New appelle le constructeur de l'objet, mais justement il n'y en pas.
Les_fils est déclaré, son type, mais ni initialisé, encore moins construit.
Tel que je vois partir ce sujet, ce sera un joli débat entre spécialistes.
tachaout est débutant, si vous préférez que je me retire tout de suite, dites-le, et proposez-lui des verrues à C++ (standard ou périmé ou historique, on ne sait plus)
19/08/2010, 11h30
Davidbrcz

Citation:

New appelle le constructeur de l'objet, mais justement il n'y en pas.

Si. Il est juste synthétisé par le compilateur quand le le programmeur n'en fournit pas (tout comme l'est le constructeur de copie, operator= et le destructeur). C'est le gang des "Big Four". Cf la norme pour les détails.

Citation:

Les_fils est déclaré, son type, mais ni initialisé, encore moins construit.

Si, si, il l'est (cf au dessus).

Citation:

tachaout est débutant,

débutant n'est pas synonyme d'incompétent ! Et au vu de son utilisation de la STL, je pense qu'il est sur la bonne voie pour apprendre.

Citation:

et proposez-lui des verrues à C++ (standard ou périmé ou historique, on ne sait plus)

Loki ou boost des verrues du C++ ? Soit j'ai très mal compris, soit c'est vraiment une preuve que vous n'avez jamais regardé en détail aucune de ces deux bibliothèques.
19/08/2010, 12h03
Invité

Effectivement, je n'ai jamais regardé ces bibliothèques.
Donc, le me sens incompétent pour continuer à le renseigner. :cry:
PS et je ne les regarderai jamais.
19/08/2010, 12h41
Davidbrcz

Citation:

Envoyé par Pierre Dolez

Effectivement, je n'ai jamais regardé ces bibliothèques.
Donc, le me sens incompétent pour continuer à le renseigner. :cry:
PS et je ne les regarderai jamais.

Et pourquoi donc ne pas regarder ce qu'elles offrent ? Ce sont des très bons outils écrits par des gens extrêmement compétents , qui offrent des fonctionnalités fortes intéressantes et surtout très utiles dans un grand nombre de cas.
19/08/2010, 12h45
Invité

Et pourquoi regarder?
J'ai tout ce qu'il me faut.
19/08/2010, 12h52
tachaout

Citation:

Envoyé par Pierre Dolez

Donc, le me sens incompétent pour continuer à le renseigner. :cry:

ça serait dommage de priver un "débutant" de tes conseils à cause de discussions entre "mentors" sachant qu'il y a certainement des visiteurs du forum encore plus "débutants"

Bon, alors je répond. Voici le code
J'utilise la bibliothèque Borland (VCL)
Certaines lignes de l'entête sont peut-être inutiles.
J'utilise 2 classes de Borland
AnsiString, très voisin de string, mais il faut vérifier si le 1er caractère est de rang 0 ou de rang 1.
TList, c'est une liste de pointeurs.
La structure NOEUD définit le lattre concernée et un pointeur sur la liste éventuelle des fils. Ce pointeur existe toujours, mais la liste peut être vide.
Cette structure est traitée pas le compilateur comme une classe.
Elle comporte un constructeur qui crée la liste, et un destructeur.
J'ai fait quelque changements, par exemple la longueur du mot n'est pas passée en paramètre.
Pour être tout à fait franc, je n'ai pas compris le but de ce calcul, donc je ne peux pas vraiment vérifier qu'il est bon.

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
87
88
89
90
91
92
93
94
95
96
#include <vcl.h>
 
#include <vcl\Classes.hpp>
#include <vcl\SysUtils.hpp>
#include <vcl\Windows.hpp>
#include <vcl\System.hpp>
#include <conio.h>
#include <stdio.h>
 
typedef struct NOEUD
{
	char lettre;
	TList *les_fils; // la liste des fils
        NOEUD(char L)
        {
          lettre = L;
          les_fils = new TList();
        }
        ~NOEUD(){/* à faire*/}
}TabNOEUD;
typedef TabNOEUD* ptrNoeud;
 
int inserer_dans_arbre(unsigned int rang,
                       const AnsiString &v,
                       TList *racine)
{
        int i=rang;
	// i est la position dans le mot  (rang)
	// v est le mot
	// racine est la racine du sous-ararbre dans lequel on insère
	unsigned int k=v.Length();// k est la taille du mot
        char Lettre=v[i];
        int ir;
        ptrNoeud it=NULL;
        for ( ir=0; ir< racine->Count; ir++)
        {
          it=(ptrNoeud)racine->Items[ir];
          if (it->lettre == Lettre) break;
        }
        if (ir < racine->Count)
        {
          if (++i < k && it != NULL)
            inserer_dans_arbre(i, v, it->les_fils);
        }
	else
        {//il n'y est pas
		//////////////////////////////////////////////////////////////////////
	  ptrNoeud p=new NOEUD(Lettre); //c'est la partie couteuse
		/////////////////////////////////////////////////////////////////////
          racine->Add(p);
          if (++i < k )
            inserer_dans_arbre(i, v, p->les_fils);
	}
        return 0;
}
 
voidl Afficher(ptrNoeud noeud)
{
  TList *Fils=noeud->les_fils;
  if (Fils != NULL)
  {
    printf("\n Lettre=%c %d fils",noeud->lettre, Fils->Count );
    for (int i=0; i<Fils->Count; i++)
    {
      ptrNoeud unFils =(ptrNoeud)Fils->Items[i];
      Afficher(unFils);
    }
  }
}
int main(){
	//On récupère la liste des mots. Ensuite on crée l'arbre comme suit
        ptrNoeud arbreP = new NOEUD(0); // le premier niveau de noeuds
        for (int i=0; i< 11; i++)
        {
          AnsiString v;
          switch(i)
          {
            case 0:  v="zero"; break;
            case 1:  v="un";  break;
            case 2:  v="deux";  break;
            case 3:  v="trois";  break;
            case 4:  v="lundi"; break;
            case 5:  v="mardi"; break;
            case 6:  v="mercredi"; break;
            case 7:  v="jeudi"; break;
            case 8:  v="ventredi"; break;
            case 9:  v="samedi"; break;
            case 10:  v="dimanche"; break;
          }
          inserer_dans_arbre(1, v, arbreP->les_fils);
          // le premier caractères est 1 et non 0 pour un AnsiString
        }
        Afficher(arbreP);
        while (!kbhit()); // ou system("pause");
	return 0;
}

La fonction kbhit() attend la frappe d'un caractère. On peut remplacer cette ligne pas "system("pause");

19/08/2010, 14h40
tachaout

Citation:

Envoyé par Pierre Dolez

J'ai fait quelque changements, par exemple la longueur du mot n'est pas passée en paramètre.

elle est en paramètre par souci d'optimisation: pas besoin de faire appel
à la fonction size (ou length) m*n fois si m est le nombre de mots à insérer
et n est la longueur moyenne de chaque mot. On l'appellera une fois pour chaque mot c'est à dire "seulement" m fois.

Citation:

Envoyé par Pierre Dolez

Pour être tout à fait franc, je n'ai pas compris le but de ce calcul, donc je ne peux pas vraiment vérifier qu'il est bon.

Un exemple d'application : trouver tous les plus longs mots qui commencent par "aba". Par exemple, on doit retourner "abattre" mais pas "abat" car ce dernier est contenu dans un plus long mot. Pour cela, il suffit de récupérer toutes les branches (de la racine jusqu'à une feuille) de l'arbre dont le prefixe est "aba".

Merci bien
19/08/2010, 16h44
Arzar

Bonjour,

Citation:

Envoyé par tachaout

Mon problème est que les multiples appels à "new" retardent énormément l'exécution.

Est-ce que tu peux détailler comment tu en es arrivé à cette conclusion ?

Car, pour ma part, avec le code donné dans ton premier post, si je remplis une liste définit comme ceci :

Code:

std::list<std::string> LesMots; //exemple: les mots du dictionaire

avec les mots du dico français trouvé ici (22740 mots), la construction et remplissage de l'arbre se font en moins de 50ms, donc je ne peux pas profiler le code. (pas assez d'échantillon). Il faut que je réitère environ 100 fois la construction de l'arbre pour que le profileur commence à donner des résultats probants, et il ne semble pas du tout pointer vers le new.

Quel est ta plate-forme et compilateur ? Tu es certain de bien compiler en release ?

EDIT :
Tiens, avant de rentrer dans les complications sur la gestion mémoire, le simple fait de remplacer dans mon code :

Code:

typedef std::list<noeud *> NoeudList;

par :

Code:

typedef llvm::SmallVector<noeud*, 5> NoeudList;

et pouf, le temps de construction et de remplissage de l'arbre a été divisé par 2 ! :D
(Il suffit d'inclure dans le projet SmallVector.h disponible ici, ainsi que type_traits.h dispo ici et SmallVector.cpp dispo ici)

Citation:
Envoyé par Pierre Dolez
Bon, alors je répond. Voici le code
J'utilise la bibliothèque Borland (VCL)
Certaines lignes de l'entête sont peut-être inutiles.
J'utilise 2 classes de Borland
AnsiString, très voisin de string, mais il faut vérifier si le 1er caractère est de rang 0 ou de rang 1.
TList, c'est une liste de pointeurs.
La structure NOEUD définit le lattre concernée et un pointeur sur la liste éventuelle des fils. Ce pointeur existe toujours, mais la liste peut être vide.
Cette structure est traitée pas le compilateur comme une classe.
Elle comporte un constructeur qui crée la liste, et un destructeur.
J'ai fait quelque changements, par exemple la longueur du mot n'est pas passée en paramètre.
Pour être tout à fait franc, je n'ai pas compris le but de ce calcul, donc je ne peux pas vraiment vérifier qu'il est bon.
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 87 88 89 90 91 92 93 94 95 96 #include <vcl.h> #include <vcl\Classes.hpp> #include <vcl\SysUtils.hpp> #include <vcl\Windows.hpp> #include <vcl\System.hpp> #include <conio.h> #include <stdio.h> typedef struct NOEUD { char lettre; TList *les_fils; // la liste des fils NOEUD(char L) { lettre = L; les_fils = new TList(); } ~NOEUD(){/* à faire*/} }TabNOEUD; typedef TabNOEUD* ptrNoeud; int inserer_dans_arbre(unsigned int rang, const AnsiString &v, TList *racine) { int i=rang; // i est la position dans le mot (rang) // v est le mot // racine est la racine du sous-ararbre dans lequel on insère unsigned int k=v.Length();// k est la taille du mot char Lettre=v[i]; int ir; ptrNoeud it=NULL; for ( ir=0; ir< racine->Count; ir++) { it=(ptrNoeud)racine->Items[ir]; if (it->lettre == Lettre) break; } if (ir < racine->Count) { if (++i < k && it != NULL) inserer_dans_arbre(i, v, it->les_fils); } else {//il n'y est pas ////////////////////////////////////////////////////////////////////// ptrNoeud p=new NOEUD(Lettre); //c'est la partie couteuse ///////////////////////////////////////////////////////////////////// racine->Add(p); if (++i < k ) inserer_dans_arbre(i, v, p->les_fils); } return 0; } voidl Afficher(ptrNoeud noeud) { TList *Fils=noeud->les_fils; if (Fils != NULL) { printf("\n Lettre=%c %d fils",noeud->lettre, Fils->Count ); for (int i=0; i<Fils->Count; i++) { ptrNoeud unFils =(ptrNoeud)Fils->Items[i]; Afficher(unFils); } } } int main(){ //On récupère la liste des mots. Ensuite on crée l'arbre comme suit ptrNoeud arbreP = new NOEUD(0); // le premier niveau de noeuds for (int i=0; i< 11; i++) { AnsiString v; switch(i) { case 0: v="zero"; break; case 1: v="un"; break; case 2: v="deux"; break; case 3: v="trois"; break; case 4: v="lundi"; break; case 5: v="mardi"; break; case 6: v="mercredi"; break; case 7: v="jeudi"; break; case 8: v="ventredi"; break; case 9: v="samedi"; break; case 10: v="dimanche"; break; } inserer_dans_arbre(1, v, arbreP->les_fils); // le premier caractères est 1 et non 0 pour un AnsiString } Afficher(arbreP); while (!kbhit()); // ou system("pause"); return 0; }
La fonction kbhit() attend la frappe d'un caractère. On peut remplacer cette ligne pas "system("pause");
Ce code est bourré de bugs et mauvaises pratiques. On a inventé le C++ depuis...
Pourquoi utiliser la VCL de borland alors que le standard propose ce qu'il faut ?
Pourquoi faire des typedef struct NOEUD ? N'importe quel cours de débutant C++ indique que cela n'a pas lieu d'être en C++
Tu gères un new dans le constructeur, j'imagine que le delete tu le laisses à la charge du posteur. Mais où sont les politiques de copie et les gestions d'exception ??? Il serait préférable de comprendre le RAII puis d'apprendre les outils qui vont avec : std::vector, pointeurs intelligents, etc.
Quel intérêt d'utiliser des chaînes de caractères non standard ???
Il existe des équivalents C++ pour les en-têtes standard (<cstdio> à la place de <stdio.h>). Ce sont ceux là qu'il faut utiliser.
conio.h : :cry:

Citation:

Envoyé par wikipedia

conio.h is a C header file used in old MS-DOS compilers to create text user interfaces. It is not described in The C Programming Language book, and it is not part of the C standard library, ISO C nor is it required by POSIX.

19/08/2010, 18h48
tachaout

Citation:

Envoyé par Arzar

Est-ce que tu peux détailler comment tu en es arrivé à cette conclusion ?

Je n'ai pas voulu embêter les gens avec des détails qui nous auraient sorti du sujet (c'est déjà le cas j'ai l'impression ;) ). En réalité, les données sont sous la forme de chaines d'entiers par exemple, ceci. C'est un fichier de 1,5 million de mots et il existe ~ 6 millions de caractères (entiers différents). Ce qui fait que les mots sont très longs.

Citation:

Envoyé par Arzar

Quel est ta plate-forme et compilateur ? Tu es certain de bien compiler en release ?

VS 10 Express en release et /O2
EDIT :

Citation:

Envoyé par Arzar

Tiens, avant de rentrer dans les complications sur la gestion mémoire, le simple fait de remplacer dans mon code :

Code:

typedef std::list<noeud *> NoeudList;

par :

Code:

typedef llvm::SmallVector<noeud*, 5> NoeudList;

et pouf, le temps de construction et de remplissage de l'arbre a été divisé par 2 ! :D
(Il suffit d'inclure dans le projet SmallVector.h disponible ici, ainsi que type_traits.h dispo ici et SmallVector.cpp dispo ici)

llvm !!! on en apprend des choses

Merci
19/08/2010, 18h50
Invité

@3DArchi
Je vous prie d'accepter toutes mes excuses.
Mais je vais tout de même répondre à vos questions.
1- et c'est le plus important, il ne s'agissait en aucun cas pour moi de donner une solution. Mais pour voir, peut-être par curiosité, j'ai voulu l'écrire.
2- je n'ai pas vu d'autre réponses que "va donc chez boost", j'ai cherché à être plus constructif, mais à l'évidence c'était une erreur.
3- j'utilise la VCL parce que c'est ma bibliothèque. Le standars des voitures en France c'est Renault, me reprocherez-vous d'utiliser une Fiat ?
4- Je ne connais pas le cours de débutant qui indique que "typedef struct ..." n'a pas lieu d'être en C++, alors disons que je ne fais pas du C++, j'utilise un langage qui via mon compilateur est bien compris par ma machine. D'ailleurs, je n'ai jamais dit que je faisais du C++, je me contente de développer et d'utiliser un langage, dont j'ai oublié le nom, pour communiquer avec ma machine.
5- effectivement je laisse le delete "à faire", mais comme il ne s'agit pas de quelque-chose à utiliser, cela ne m'a pas paru très grave, mais je me rend compte qu'encore une fois, je me suis trompé.
6- Wijipédia ne constitue pas pour moi une référence en la matière.

Je me cite :

Citation:

Envoyé par Arzar

t que je réitère environ 100 fois la construction de l'arbre pour que le profileur commence à donner des résultats probants, et il ne semble pas du tout pointer vers le new.

Bon pour avoir le cœur net, vu que je n'avais pas confiance dans le profileur, j'ai quand même créer rapidos un allocator de type arène très très crade :
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 #include <vector> template <typename T> struct RingBufferAllocator { RingBufferAllocator(size_t nbOject) : buffer((noeud*)malloc(nbOject * sizeof(T))), bump_pt(buffer), counter(0), { } ~RingBufferAllocator() { free(buffer); } T* construct() { T* t = new (bump_ptr) T; bump_ptr++; counter++; return t; } T* buffer; T* bump_ptr; int counter; }; // dans le main RingBufferAllocator<noeud> g_allocator(100000); // en global ... //... // dans inserer_dans_arbre() //noeud * p = new(noeud); //c'est la partie couteuse noeud* p = g_allocator.construct();
Il n'y a donc plus aucune allocation mémoire durant la construction de l'arbre, le new étant remplacé par la fonction construct extrêmement cheap (une incrémentation de pointeur + un appel au constructeur de noeud)...

A peine 5% de gain dans les timings ! :cry:
Le profileur avait raison...

EDIT :

Citation:

Je n'ai pas voulu embêter les gens avec des détails qui nous auraient sorti du sujet (c'est déjà le cas j'ai l'impression ). En réalité, les données sont sous la forme de chaines d'entiers par exemple, ceci. C'est un fichier de 1,5 million de mots et il existe ~ 6 millions de caractères (entiers différents). Ce qui fait que les mots sont très longs.

Des détails !? :aie:
C'est sur qu'avec de telles volumes la donne est complètement changée... Vaut donc mieux ne pas trop tenir compte de ce que j'ai pu dire dans les posts précédent. :D

Citation:
Envoyé par Arzar
Je me cite :

Bon pour avoir le cœur net, vu que je n'avais pas confiance dans le profileur, j'ai quand même créer rapidos un allocator de type arène très très crade :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 template <typename T> struct RingBufferAllocator { RingBufferAllocator(size_t nbOject) : buffer((noeud*)malloc(nbOject * sizeof(T))), bump_pt(buffer), counter(0), { } ~RingBufferAllocator() ....
à la compilation, j'ai une erreur au niveau des deux accolades dont voici le message

1>mon_prog.cpp(53): error C2059: erreur de syntaxe*: '{'
1> mon_prog.cpp(49)*: lors de la compilation de la fonction membre 'RingBufferAllocator<T>::RingBufferAllocator(size_t)' de la classe modèle
1> with
1> [
1> T=noeud
1> ]
1> mon_prog.cpp(74)*: voir la référence à l'instanciation de la classe modèle 'RingBufferAllocator<T>' en cours de compilation
1> with
1> [
1> T=noeud
1> ]
========== Génération*: 0 a réussi, 1 a échoué, 0 mis à jour, 0 a été ignoré ==========

19/08/2010, 20h42
Arzar

Il y a une virgule en trop après "counter(0),"
19/08/2010, 22h17
tachaout

Citation:

Envoyé par Arzar

Il y a une virgule en trop après "counter(0),"

Merci à tous et spécialement à Arzar,

ta solution m'a permis de gagner 8 secondes pour la construction d'un arbre qui prenait auparavant 45 secondes. Mais ce qui est encore plus intéressant c'est que le traitement que je fais sur l'arbre prend maintenant 3mn au lieu de 4 auparavant.

Mon explication est que cela est dû à la proximité "spaciale" des noeuds qui rend l'utilisation du cache mémoire et le prefetch plus performant.

Question subsidiaire en abusant de votre patience: comment augmenter dynamiquement la taille allouée ?

thanx
21/08/2010, 11h33
koala01

Salut,

Il est préférable de ne pas le faire, parce que la logique se base sur bump_ptr qui avance dans l'espace mémoire alloué à la base, et qu'il est utilisé pour calculer l'adresse d'autres éléments.

Comme malloc renverrait sans doute une adresse différente pour le début du premier élément, toutes les relations seraient invalidées, et tu devrais donc reconstruire littéralement tout l'arbre existant à chaque élargissement de la zone allouée.

Je disais dans mon intervention précédente que je ne savais plus pourquoi c'était déconseillé, et je m'en suis rappelé juste après avoir posté une énorme bêtise :aie:... je l'ai donc supprimée aussi vite :D