Discussion :

[theyoks]

Bonsoir,

Comment dire ... je suis désespéré !

Je suis étudiant dans une école d'informatique qui a la folie de nous faire recorder le malloc.

Seul contrainte n'utiliser que brk et sbrk et getpagesize.

Avec mon binôme on est partie sur l’idée de faire une sorte de graphe je m'explique.

On fait deux liste chaînée, une liste chaînée de page et une liste chaînée dans la page pour les segments.

la taille de la page est calcule par rapport a la taille que l'on peut allouer c'est a dire que si on veut allouer 200 octet on cree une page de 4096 octet parce que sur notre système getpagesize renvoi 4096.

Et dans une page on a une liste chaînée de x segment.

En gros ça donne :

Page ---> Page ---> Page ---> Page ---> Page ---> Page ---> Page ---> Page ---> NULL
|
|
SEG
|
|
SEG
|
|
SEG
|
|
SEG
|
|
NULL

Sans rentrer dans le détail du code ça fonctionne très bien a une seul exception, c'est ultra ultra lent.

On c'est débrouillé pour ne faire que un sbrk par création de page, on ne fait que un seul sizeof dans tous le programme qu'on garde en mémoire.

On limite au maximum le nombre de boucle etc...

En gros on est arrive au maximum de l'optimisation que notre niveaux de C nous permet donc je fais appel a vous pour réfléchir a un nouveau procédé que celui que j'appelle "un graphe" pour recoder le malloc.

J’espère avoir été suffisamment claire dans mon explication je suis prêt a clarifier ce qui ne le serait pas.

Cordialement.

PS : si je n'ai pas posté au bon endroit, j'en suis désolé.

[gerald3d]

Je pense que la lenteur vient dans l'utilisation des listes chaînées.

Comme tu connais la taille de chaque page tu pourrais peut être utiliser un tableau en lieu et place des listes chaînées. Ce n'est qu'une simple idée. Peut être que la mise en place est plus simple à dire qu'à faire.

[theyoks]

Je suis entièrement d'accord sur le fait que la lenteur viennent des listes.

Le tableau pour y remédier, pourquoi pas mais la force des listes est que tu ne connais pas la taille final et que tu peux rajouter des maillons a la volée.

L’idée est de stocké l'adresse retourné par sbrk ainsi que une (des) infos sur la taille alloué ou autres...

Les listes chaînée nous ont paru en premier lieu la meilleur idée seulement pour 1 000 000 de malloc de 1 il faut 20 bonnes minutes a notre programme pour tout alloue et libérer, on essai de parcourir nos listes le plus intelligemment possible mais on a beau faire sur 1 000 000 de maillon ça prend des ressources...

Je ne sais pas quel conteneur serait le plus adapté a de gros contenu j'y réfléchis toujours.

Cordialement.

[gerald3d]

Les tables de hash pour les temps d'accès. Accès en temps constant. Maintenant il faut réfléchir à la taille flexible.

Quelques questions me taraudent et ca fait mal ).

• Comment allouez-vous l'espace mémoire pour chaque élément de la liste?
• Si tu fais deux allocations de 100 octets par exemple, alloues-tu 2 pages ou bien ton système est-il capable d'allouer ces 2 blocs dans la même page?

[Sve@r]

Je suis entièrement d'accord sur le fait que la lenteur viennent des listes.

Le tableau pour y remédier, pourquoi pas mais la force des listes est que tu ne connais pas la taille final et que tu peux rajouter des maillons a la volée.

Non. La force des listes c'est que tu peux ajouter des éléments intermédiaires sans avoir à tout décaler derrière.
Si tes éléments ne sont pas triés et que tu les rajoutes donc qu'en fin de ton ensemble, alors un tableau est bien plus efficace. Et si tu ne connais pas sa taille à l'avance alors tu peux l'agrandir à la demande via realloc (bon, ça va être difficile d'appeler realloc dans un environnement où il est sensé ne pas exister mais comme à la base j'ai du mal à percevoir comment tu fais pour allouer un nouveau maillon de ta liste sans appeler malloc...)

[Elboras]

Pour info, dans le livre de référence fait par Kernighan & Ritchie sur le langage C, il y à une partie sur la programmation en C d'un memory allocator, plutôt simple.

de mémoire c'est un first fit, au pire un best fit vraiment classique, un cas d'école, pas quelque chose d'optimisé comme dans nos systèmes.

Je suppose que tu es soit à Epita soit à Epitech pour avoir un projet de ce genre.

Bon courage pour ton projet