Discussion :

[tachaout]

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.

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

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

[tachaout]

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 :

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
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;
}

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

[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 :

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

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.

[tachaout]

j'ai essayé de remplacer

Code :

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

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 )

Merci pour les bons tuyaux

[Arzar]

Bonjour,

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 :

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

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 :

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

typedef std::list<noeud *> NoeudList;

par :

Code :

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

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

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

[tachaout]

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.

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

VS 10 Express en release et /O2
EDIT :

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

Code :

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

typedef std::list<noeud *> NoeudList;

par :

Code :

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

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

et pouf, le temps de construction et de remplissage de l'arbre a été divisé par 2 !
(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

[Arzar]

Je me cite :

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 :

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
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 !
Le profileur avait raison...

EDIT :

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

[tachaout]

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 :

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

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é ==========

[Arzar]

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

[tachaout]

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