Discussion :

[Babcool]

Bonjour

Je suis en train de travailler sur un algo de fouille de donnée et j'ai un problème avec l'allocation mémoire.

Je construit un arbre pour lequel je représente ma liste d'enfant par un tableau de pointeur. Or, après un certain nombre d'allocation (ca tourne autour de 65500), malloc refuse de m'allouer de la mémoire alors que j'ai encore de la ram dispo (il bloque en général à 800mo de mémoire utilisée). perror contient la description d'erreur suivante : Cannot allocate memory... (trop utile )

Mes allocations se font par bloc de 4*7000 octets environ. Est ce qu'une trop grosse allocation peut échouer si il n'y a pas de zone assez grande dans la ram (ce qui serait étonnant, car ca ne fait que 21 ou 22ko au maximum...).

J'ai aussi un swap assez grand pour qu'il soit utilisé, mais il ne monte jamais d'un poil...

Est ce que quelqu'un aurait une idée qui pourrait m'aider?

Merci d'avance

[TheDrev]

Je n'ai jamais été confronté à ce genre de problème, mais il s'agit peut être d'une limitation ou sécurité du système. Si c'est le cas il faudrait passer par un stockage dans un fichier comme mémoire temporaire.

[Invité]

Bonjour,
J'ai pas tout compris.
Vous dites que vous avez un arbre et un tableau de pointeurs.
Vous dites aussi que ça bloque autour de 65500. Est-ce que ce ne serait pas exactement à 65535 ? Si c'est le cas, ça ressemble fort à la limite de l'unsigned int.
Mais je ne comprend pas pourquoi vous avez un tableau de pointeurs, le solution habituelle pour ce genre de chose est une liste chainée.
Pour moi, les notions d'arbre et de tableau de pointeur sont contradictoires, on fait l'un ou l'autre, suivant les cas.

[Babcool]

Hum, en fait, je représente les enfants d'un noeud sous la forme d'un tableau de pointeur. La taille du tableau correspondant au maximum à la cardinalité de mon alphabet (en général inférieur, car je ne considère que les items plus grands que le contenu du noeud). Cela me permet de gagner en vitesse lors d'une recherche d'un chemin dans l'arbre.

Le 65000 est variable et j'ai déjà dépassé quelques fois le 65535 (65800 ou 900 au maximum, je ne sais plus exactement). Donc je dépasse sans trop de problème le short.

C'est peut etre effectivement un problème lié à une limite de sécurité du système, mais dans ce cas, je ne connais pas du tout ce point la. Toutes mes allocations se font en début de programme, elles sont donc réalisées dans un temps très court. Mais je ne pense pas que cela puisse avoir une influence...

[Obsidian]

Je construit un arbre pour lequel je représente ma liste d'enfant par un tableau de pointeur. Or, après un certain nombre d'allocation (ca tourne autour de 65500), […] Mes allocations se font par bloc de 4*7000 octets environ. Est ce qu'une trop grosse allocation peut échouer si il n'y a pas de zone assez grande dans la ram (ce qui serait étonnant, car ca ne fait que 21 ou 22ko au maximum...)

Je vais peut-être dire une ânerie mais 65500 × 4 × 7000, ça fait 1.834.000.000, soit pas loin de 2 Go de mémoire. À ce stade, l'architecture comme l'O.S. que tu utilises sont significatifs. Donc :

— Il se peut effectivement que ton système mette en place des quotas. Mais si c'est sur ta machine personnelle, c'est peu probable ;
— Quand tu alloues un bloc de mémoire, tu alloues également de la place pour un bloc descripteur qui contient les infos nécessaire pour libérer ce bloc avec free(). Cela augmente d'autant la quantité de mémoire que tu consommes ;
— Lorsque tu flirtes avec les 2 Go, tu commences à atteindre les limites du format « signed int » sur 32 bits ;
— Tous tes blocs, même s'ils ne sont pas forcément mappés simultanément, doivent avoir une position propre dans le plan mémoire pour pouvoir être exploités par le processus, celle-là même qui t'est renvoyé par malloc(). Et un segment de 2 Go octets de mémoire, ça commence à être dur à caser sur une machine 32 bits. Plus précisément, 32 bits te permettent de représenter exactement 4 Gio de mémoire. Là-dessus, il y en a un bon quart qui est occupé par le PCI. Le reste l'est par le BIOS, les vecteurs d'interruptions et autres, mais surtout par le kernel de ton système d'exploitation, le code de ton processus, toute sa pile (qui peut être conséquente), et par les bibliothèques partagées.

Donc, remplir le plan mémoire aux alentours de l'endroit où tu plantes est cohérent.

J'ajoute que procéder de cette manière, c'est un peu sauvage. D'une manière générale, on devrait toujours avoir une idée même subjective du coût en ressources d'une requête au système, et pas voir cela simplement comme un modèle mathématique…

[Sve@r]

Je construit un arbre pour lequel je représente ma liste d'enfant par un tableau de pointeur.

Ce serait intéressant de voir la structure que t'utilises histoire de voir si t'aurais pas foiré avec les définitions...

Mais je ne comprend pas pourquoi vous avez un tableau de pointeurs, le solution habituelle pour ce genre de chose est une liste chainée.
Pour moi, les notions d'arbre et de tableau de pointeur sont contradictoires, on fait l'un ou l'autre, suivant les cas.

Pas forcément. On n'est pas obligé de voir les arbres comme des arbres binaires.
On peut très bien imaginer un noeud de ce type

Code C :

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

1
2
3
4
typedef struct s_noeud {
    int elem;
    struct s_noeud **tabNoeud;    // Tableau de pointeurs
} t_noeud;

Ce genre de noeud sera utilisé par exemple dans un algorithme de jeu d'échecs. Le noeud stocke le coup possible et son tableau pointe sur l'ensemble des coups qui vont en découler...

[Babcool]

Je vais peut-être dire une ânerie mais 65500 × 4 × 7000, ça fait 1.834.000.000, soit pas loin de 2 Go de mémoire.

Il faut que j'ajoute une précision, cette quantité est environ à diviser par deux (au moins) car les noeud de l'arbre alloue un tableau dont la taille correspond à la liste des items plus grands que leur contenu, donc si on considère qu'on a une répartition homogène des noeuds sur la hauteur (ce qui est une minoration brutale ), on peut diviser par 2 la taille totale alloué, ce qui permet de tomber approximativement sur 900 mo de mémoire vive, ce qui était annoncé par le moniteur système.

À ce stade, l'architecture comme l'O.S. que tu utilises sont significatifs. Donc :

— Il se peut effectivement que ton système mette en place des quotas. Mais si c'est sur ta machine personnelle, c'est peu probable ;
— Quand tu alloues un bloc de mémoire, tu alloues également de la place pour un bloc descripteur qui contient les infos nécessaire pour libérer ce bloc avec free(). Cela augmente d'autant la quantité de mémoire que tu consommes ;
— Lorsque tu flirtes avec les 2 Go, tu commences à atteindre les limites du format « signed int » sur 32 bits ;
— Tous tes blocs, même s'ils ne sont pas forcément mappés simultanément, doivent avoir une position propre dans le plan mémoire pour pouvoir être exploités par le processus, celle-là même qui t'est renvoyé par malloc(). Et un segment de 2 Go octets de mémoire, ça commence à être dur à caser sur une machine 32 bits. Plus précisément, 32 bits te permettent de représenter exactement 4 Gio de mémoire. Là-dessus, il y en a un bon quart qui est occupé par le PCI. Le reste l'est par le BIOS, les vecteurs d'interruptions et autres, mais surtout par le kernel de ton système d'exploitation, le code de ton processus, toute sa pile (qui peut être conséquente), et par les bibliothèques partagées.

Donc, remplir le plan mémoire aux alentours de l'endroit où tu plantes est cohérent.

Pour le dernier point, j'avoue que je suis pas ultra calé en gestion mémoire, donc y'a bien moyen que le tout ne soit pas rempli complètement correctement. Est ce qu'il y a moyen de faire d'une autre manière afin de mieux remplir le tout?
J'ai encore 500 ou 600mo de mémoire vive dispo en général quand ça plante. Si le remplissage n'est pas optimal (pour des problèmes d'alignements ou autre), je ne devrais quand même rien avoir de plus nan?

J'ajoute que procéder de cette manière, c'est un peu sauvage. D'une manière générale, on devrait toujours avoir une idée même subjective du coût en ressources d'une requête au système, et pas voir cela simplement comme un modèle mathématique…

En fait, le cout en ressources dépend énormément des données que je met en entrée, de leur densité et de leur répartition. Comme pour l'instant, je n'ai quasiment aucune info sur ces points, je fais des tests pour voir comment ça réagit... Mais d'un jeu de donnée à l'autre, ça change du tout au tout, donc... xD

Pour la structure de donnée, Sve@r, tu n'étais vraiment pas loin :

Code :

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

1
2
3
4
5
6
7
8
 
typedef struct s_cell{
	int content;
	int support;
	struct s_cell* father;
	struct s_cell** children;
 
} cell;

et la fonction de création d'une cellule :

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
 
cell* create_new_cell(int content, int support)
{
	static int nb_alloue = 0;
	cell* result = (cell*)malloc(sizeof(cell));
	result->content = content;
	result->support = support;
	result->children = (cell**) malloc(sizeof(cell)*(ITEM_MAX - content));
	if (result->children == NULL && ITEM_MAX - content > 0)
	{
		printf("Erreur allocation mémoire dans create_new_cell\n");
perror("Erreur malloc : ");
		printf("content : %d et item_max : %d alloc realisee : %d\n",content,ITEM_MAX,nb_alloue);
 
		exit(EXIT_FAILURE);
	}
	int i;
		for (i = 0; i< ITEM_MAX - result->content; i++)
		{
			result->children[i] = NULL;
		}
 
	result->father = NULL;
	nb_alloue++;
return result;
}

Tout n'est pas encore optimisé (en particulier le fait de mettre à null toute els cases de mon tableau, un calloc serait ptet mieux, m'enfin, pour ces détails, je verrais plus tard...

En tout cas, merci bien pour votre aide jusqu'à maintenant ^^

[Sve@r]

Pour la structure de donnée, Sve@r, tu n'étais vraiment pas loin :

Code :

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

1
2
3
4
5
6
7
8
 
typedef struct s_cell{
	int content;
	int support;
	struct s_cell* father;
	struct s_cell** children;
 
} cell;

et la fonction de création d'une cellule :

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
 
cell* create_new_cell(int content, int support)
{
	static int nb_alloue = 0;
	cell* result = (cell*)malloc(sizeof(cell));
	result->content = content;
	result->support = support;
	result->children = (cell**) malloc(sizeof(cell)*(ITEM_MAX - content));
	if (result->children == NULL && ITEM_MAX - content > 0)
	{
		printf("Erreur allocation mémoire dans create_new_cell\n");
perror("Erreur malloc : ");
		printf("content : %d et item_max : %d alloc realisee : %d\n",content,ITEM_MAX,nb_alloue);
 
		exit(EXIT_FAILURE);
	}
	int i;
		for (i = 0; i< ITEM_MAX - result->content; i++)
		{
			result->children[i] = NULL;
		}
 
	result->father = NULL;
	nb_alloue++;
return result;
}

Ok, quelques petites malfaçons qu'on peut corriger assez vite
1) interdit de quitter une fonction par exit. La bonne approche est de renvoyer NULL et c'est l'appelant qui décide du choix à faire
3) utiliser une statique pour compter le nb d'éléments => danger. C'est pas forcément mauvais mais imaginons que tu veuilles gérer 2 arbres distincts en parallèle, ta statique cumulera le nb total d'éléments (et non le nb d'élémnts de chaque arbre). Or il y a des solutions plus élégantes
3) tu vas remplir result->content sans avoir vérifié que result a bien été alloué
4) le cast du malloc. Bon, il y a une petite gueguerre à ce propos que je ne veux pas redéclencher donc ça je le laisse de coté.

Tout n'est pas encore optimisé (en particulier le fait de mettre à null toute els cases de mon tableau, un calloc serait ptet mieux, m'enfin, pour ces détails, je verrais plus tard...

Ok, je vais te donner une idée de ce qu'il est possible de faire
Tout d'abord, il faut absolument, quand on traite des arbres, définir une structure pour gérer l'arbre lui-même. Ca peut paraitre tout con car on se dit "ben un arbre c'est juste le premier élément" mais si on se force un peu, on en retire plein d'avantages. En effet, une fois que la structure est créée, même si elle n'a qu'un élément (le premier noeud) ben la porte est ensuite ouverte à plein d'évolutions
1) on peut y rajouter le nb d'éléments => hop, finie la statique
2) on peut y rajouter l'élément courant, le dernier, l'élément moyen, bref plein de drapeaux utiles pour tes algo

Donc je te propose la structure suivante

Code C :

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

1
2
3
4
typedef struct {
    cell *racine;
    size_t nbElem;
} t_arbre;

Et maintenant pour tout le reste ton code en sera allégé. Imaginons par exemple que tu veuilles modifier le premier élément Avec ta solution, tu as, dans ton main, un truc de ce type
cell *Arbre=... (ok, le premier élément est créé)
Puis tu appelles la fonction qui doit modifier Arbre. Comme toute fonction qui doit modifier qqchose, on doit lui passer l'adresse de cette chose
modif(&Arbre)
Et la fonction devra définir un paramètre de type cell ** puisqu'elle modifie un pointeur. Et dans toute ta fonction tu te battras avec tes **

Avec ma soluce, tu as dans ton main un truc de ce type
t_arbre Arbre;

Je passe mon arbre à ma fonction => modif(&Arbre)

Et la fonction modif reçoit juste un pointeur sur un t_arbre => modif(t_arbre *arbre)
Elle aura alors accès à arbre->racine qu'elle pourra modifier, à arbre->nbElem. Bref que des avantages ensuite...

Petit squelette ( je me lâche)

Code C :

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
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
typedef struct s_cell{
	int content;
	int support;
	struct s_cell* father;
	struct s_cell** children;
} t_cell;
 
typedef struct {
	t_cell *racine;
	size_t nbElem;
} t_arbre;
 
void freeArbre(t_arbre *arbre)
{
	if (arbre == NULL) return;
	freeCell(arbre->racine);
	initArbre(arbre);
}
 
void freeCell(t_cell *cell)
{
	t_cell **pt;
	int i;
	if (cell == NULL) return;
	if (cell->children)
	{
		for (i=0; pt=cell->children; i < cell->content; i++, pt++)
			freeCell(*pt);
	}
	free(cell);
}
 
void initArbre(t_arbre *arbre)
{
	if (arbre == NULL) return;
	arbre->racine=NULL;
	arbre->nbElem=0;
}
 
void affichArbre(t_arbre *arbre)
{
	if (arbre == NULL) return;
	affichCell(arbre->racine);
}
 
void affichCell(t_cell *cell)
{
	t_cell **pt;
	int i;
	if (cell == NULL) return;
	printf("\n");
	printf("Cellule 0x%x\n", cell);
	printf("content: %d\n", cell->content);
	printf("support: %d\n", cell->support);
	printf("father: 0x%x\n", cell->father);
	if (cell->children)
	{
		for (i=0; pt=cell->children; i < cell->content; i++, pt++)
			affichCell(*pt);
	}
}
 
 
t_cell* create_new_cell(int content, int support)
{
	t_cell* result = (t_cell*)malloc(sizeof(t_cell));
	if (result == NULL) return NULL;
	result->children = (cell**) malloc(sizeof(cell)*(ITEM_MAX - content));
	if (result->children == NULL && ITEM_MAX - content > 0)
	{
		free(result);
		return NULL;
	}
 
	int i;
	t_cell **pt;
	for (i = 0, pt=result->children; i< ITEM_MAX - content; i++, pt++)
		*pt = NULL;
	// Effectivement, un calloc serait certainement plus approprié
 
  	result->content = content;
	result->support = support;
	result->father = NULL;
	return result;
}
 
int main()
{
	t_arbre Arbre;
	arbreInit(&Arbre);
	affichArbre(&Arbre);
	...
}

J'aurais bien continué mais je commence à manquer d'idée. Mais tu vois le principe ? De toutes petites fonctions très basiques, très maniables que tu peux appeler quand tu veux. Plus c'est basique et maniable plus c'est réutilisable. En fait, c'est la base de la philosophie objet...

[Babcool]

Hum, tout d'abord, désolé pour la static , en fait elle n'est la que pour me permettre de voir si ca plante à la première alloc ou plus tard, et avoir une approximation d'une nombre d'alloc faite. Donc bien évidemment, elle ne sera plus la dans la version finale (et en plus, le seul endroit ou elle est utilisé est le printf du cas d'erreur).

Pour ce qui est du exit, ces fonctions ayant pour but de tester la structure, elles ne seront pas diffusées et dans le cas présent, je préfère faire mon exit ici plutot que de gérer le cas de retour NULL... Mais dans le cas général, je suis tout a fait d'accord pour éviter au maximum des exits perdu comme ça...

Pour l'oubli du test que le premier malloc a bien fonctionné, je vais l'ajouter desuite, il manque effectivement ^^.

Au niveau de l'orientation objet, on gagnerait en clarté, mais est ce qu'on ne perdrait pas au niveau de l'efficacité? En général, je fais surtout du C++/Java, donc j'ai plutôt tendance à tout faire en objet, et justement, ici j'ai évité pour éviter de trop faire d'appel de fonction à tout va... Après, je sais pas si j'y gagne vraiment ou pas...

cell *Arbre=... (ok, le premier élément est créé)
Puis tu appelles la fonction qui doit modifier Arbre. Comme toute fonction qui doit modifier qqchose, on doit lui passer l'adresse de cette chose
modif(&Arbre)
Et la fonction devra définir un paramètre de type cell ** puisqu'elle modifie un pointeur. Et dans toute ta fonction tu te battras avec tes **

Y'a un ptit truc que je ne suis pas là, car je ne manipule que des pointeurs (cell*) en général. Je ne vois pas pourquoi j'aurais à utiliser des cell**.

En général, mes fonctions prennent un cell* en entrée et travaillent sur l'objet pointé sans en modifier l'adresse. Et quand j'ai des allocs à faire ou autre, je renvois une valeur que j'alloue en sortie de fonction dans mon pointeur (enfin, je le fais jamais, mais si j'avais à le faire, je ferais comme ça... ). Il vaut mieux privilégier le passage d'un cell** pour éviter d'avoir un retour?

J'en reviens aussi un ptit coup à ma question initiale, pour le malloc, y'a quelque chose à faire? (en restant dans la mémoire vive, et en utilisant le swap si besoin), sachant que je tourne effectivement sur ma machine perso, donc pas de quota, et les droits root pour faire des modifs si besoin...

[Sve@r]

Au niveau de l'orientation objet, on gagnerait en clarté, mais est ce qu'on ne perdrait pas au niveau de l'efficacité? En général, je fais surtout du C++/Java, donc j'ai plutôt tendance à tout faire en objet, et justement, ici j'ai évité pour éviter de trop faire d'appel de fonction à tout va... Après, je sais pas si j'y gagne vraiment ou pas...

Arf, maintenant on a des PC bien puissants. Tu peux te lâcher à faire plein de petites fonctions...

Y'a un ptit truc que je ne suis pas là, car je ne manipule que des pointeurs (cell*) en général. Je ne vois pas pourquoi j'aurais à utiliser des cell**.

Cela pourrait arriver si, par malheur, tu avais dans l'idée de modifier ta première cellule. Bon, pour les arbres c'est rare (on va même dire "ça n'arrive jamais") mais je tiens cette idée des listes chainées. Dans ce cas, ça peut arriver.

Imagine l'hypothèse suivante: tu programmes ta liste chainée
J'imagine que dans ce cas, tu commences par mémoriser ton début. Donc tu as un pointeur sur la première cellule de la liste

Code c :

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

t_cell *prem;

Puis dès que tu as un élément nouveau à insérer, je pense que ta suite logique de ton code sera de l'insérer de cette façon

Code C :

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

insere(prem, nouveau)

Maintenant il te faut écrire la fonction qui insère un élément à sa place. Cette fonction reçoit
- le premier élément (puisqu'il lui faut parcourir la liste)
- l'élément à insérer
La fonction fera un truc ressemblant à ceci

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
void insere(t_cell *prem, t_cell *elem)
{
    t_cell *current;
 
    // Recherche position nouveau
    while (...)
 
    // Insertion élément à sa place
    elem->next=current->next;
    current->next=elem;
}

Et là tu regardes ta fonction et à ce moment là, tu te rends compte que l'élément à insérer pourrait s'insérer avant le premier. Dans ce cas, le premier est remplacé. Mais dans la déclaration de la fonction, elle ne peut pas modifier le premier élément (puisqu'elle n'a reçu qu'une copie de ce premier).

T'es alors obligé de modifier ta fonction en considérant qu'elle pourrait modifier le premier élément. Dans ce ca, elle recevra l'adresse de ce premier (puisque, c'est un des principes de base, une fonction qui modifie une variable doit recevoir l'adresse de cette variable)

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
void insere(t_cell **prem, t_cell *elem)
{
   // Si l'élément s'insère en premier
   if (elem->valeur < (*prem)->valeur)
   {
        // L'élément arrivé prend la place du premier
        (*prem)=current;
 
         // L'élément arrivé pointe sur le premier (qui est devenu le second)
         elem=>next=(*prem)
   }
}

Et maintenant, te faut appeler cette fonction de cette façon

Code C :

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

insere(&prem, nouveau)

Et te voilà embarqué dans à manipuler des cell ** parce que t'as pas pensé que avoir une structure (oserais-je dire "un objet") pour manipuler ta liste était une bonne idée. C'est pas obligatoire... mais c'est super pratique (aussi pratique qu'un cintre pour transporter ses chemises est plus pratique que les tenir par le col...)

J'en reviens aussi un ptit coup à ma question initiale, pour le malloc, y'a quelque chose à faire? (en restant dans la mémoire vive, et en utilisant le swap si besoin), sachant que je tourne effectivement sur ma machine perso, donc pas de quota, et les droits root pour faire des modifs si besoin...

Désolé, là ça me dépasse. Tu devrais essayer d'évaluer le nombre de noeuds que t'auras au total et faire un petit test avec un malloc de n * taille_d'un_noeud voir si ce test tient la charge...