Discussion :

[Wizard50]

Coucou tout le monde,

Alors voilà ma petite question du jour :

J'aimerais savoir si en C, pour une adresse mémoire x (sur 32 ou 64 bits), il est possible de dire si cette adresse mémoire est disponible afin d'y "réserver" un emplacement pour stocker y octets.
Plus précisément, j'aimerais savoir s'il existe un moyen de faire un malloc(int adresse, int size) qui me retourne NULL si l'adresse n'est pas disponible ou l'adresse si l'emplacement a pu être réservé ?

Merci de votre aide !

[Obsidian]

Bonjour,

Pas en C standard, à ma connaissance. Par contre, c'est possible dans une certaine mesure en programmation système. Les appels mmap() et shmat(), par exemple, permettent de spécifier une adresse d'implantation en mémoire. Cependant, il s'agit en général d'une adresse indicative : si le système ne peut pas implanter un segment à cette adresse précise, il va choisir la plus proche utilisable.

Par curiosité, pourquoi cherches-tu à faire cela ?

[Wizard50]

Tout d'abord, merci grandement pour ta réponse Obsidian ! J'ai lu la doc de mmap() et je pense que rien que cette fonction pourrait m'aider énormément

Je ne suis pas vraiment autorisé à donner des détails du pourquoi je veux faire ça, je suis désolé Mais je peux en dire un peu quand même : disons que je cherche à concevoir une structure type arbre. Comme tu le sais surement, les implémentations d'arbres sont pointer-intensive et j'essaye de réduire l'utilisation de pointeurs au maximum. Disons que à un certain moment de mon programme, pour donner un exemple, je sais que je dois stocker une structure de taille y octets à une adresse qui termine par exemple par 8 bits donnés, par exemple xxxxxxxx xxxxxxxx xxxxxxxx 01010011. Les 24 premiers bits importent peu dans mon cas, du moment que je peux stocker à cette adresse y octets. Il faudrait que je puisse répéter cette opération au moins quelques centaines de millions de fois. Du coup, je m'interroge fortement sur la faisabilité de cette méthode.

[Obsidian]

Tu n'es pas forcément obligé d'utiliser des pointeurs pour construire ton arbre si tu es capable de référencer tes nœuds d'une autre manière. Il ne s'agit que d'un modèle particulier de structures de données. Par contre, effectivement, si tu fais une centaine de millions de malloc() dans ton programme, tu vas engendrer beaucoup d'overhead et tu risques d'épuiser rapidement ta RAM si la stratégie d'allocation de ton système n'est pas efficace. C'est encore plus vrai si tu dois les libérer et les réallouer à la volée tout au long de ton programme car alors, le système ne pourra pas déplacer les blocs alloués pour « défragmenter » la mémoire et optimiser son exploitation.

Si en revanche tous tes nœuds ont le même format, celui d'une structure, tu peux en revanche allouer une plage continue avec malloc() et t'en servir comme un grand tableau de n structures. Dans tes nœuds, tu ne stockes alors plus les pointeurs vers les nœuds enfants mais simplement leur index dans le tableau. Ainsi, toutes ces références se rapportent au début du tableau et tu peux éventuellement étendre et déplacer celui-ci avec realloc() si nécessaire.

[souviron34]

Pas en C standard, à ma connaissance.

Je me demande si, en faisant un mini alloc, ou au contraire en récupérant au tout départ la mémoire occupée par le process loadé et la taille de ce qui est disponible, puis en faisant un realloc sur une adresse calculée à partir de ça ça ne marcherait pas ?

Mais je peux en dire un peu quand même : disons que je cherche à concevoir une structure type arbre. Comme tu le sais surement, les implémentations d'arbres sont pointer-intensive et j'essaye de réduire l'utilisation de pointeurs au maximum.

Tu n'es pas forcément obligé d'utiliser des pointeurs pour construire ton arbre si tu es capable de référencer tes nœuds d'une autre manière.

Comme le dit Obsidian, le plus facile est de faire des "noeuds" (ou feuilles de l'arbre) indépendants : les allocations vont être petites, les trous générés lorsqu'une est détruite de la même taille qu'une création, et donc ça sera le plus eficace, et en vitesse et en occupation.

En terme de vitesse et mémoire globale, tout dépend de ce que tu fais : si tu connais à l'avance le nombre total de feuilles, c'est faisable de tout allouer d'un coup. Mais si ton tableau est grand et que tu dois le ré-allouer, tu vas créer de gros trous qui vont épuiser très vite la mémoire... (un free ne libère pas les trous, sauf si l'adresse est la dernière allouée par le programme)... De plus si une réallocation doit se faire, c'est tout le tableau qui devra être bougé en mémoire, et donc N opérations de copie... Donc même en vitesse c'est pas évident qu'on y gagne..

Une chose faisable (je l'ai faite une fois) est de stocker des "limites", des adresses de "noeuds" élémentaires qui pour toi sont significatives et bougent peu, dans un tabealu (si elles sont peu nombreuses).. Je te donne un exemple : soit un tableau de N structures, chaque structure ayant un temps assoicé, le tout durant une certaine période (ça peut être 1h, 1 mois, 1 an, 10 ans, 1000 ans..). Admettons que je veuille regrouper ces structures par 1/10 de l'intervalle couvert par la période, et leur affecter par exemple une couleur différente à l'affichage, et faire avancer l'affichage en fonction du temps qui passe. Je peux très bien stocker juste l'adresse des "limites" des intervalles (des "noeuds" se trouvant aux limites) dans un tableau d'adresses. et explorer de chaque côté de cette adresse (via next ou previous) jusqu'à ce que je change de "bin". Dans ce cas, je vais modifier les couleurs des structures dont les adresses ont été explorées SEULEMENT, et stocker uniquement la dernière adresse trouvée, en lieu et place de celle avec laquelle j'ai démarré l'exploration... : ça m'évite de tout explorer d'une part, et d'autre part j'ai une limite "modifiable" qui en fait est une adresse d'un noeud, mais stockée dans un tableau.....


Peut-être que cet exemple pourrais t'aider....

[Wizard50]

Merci à vous deux pour vos réponses !

Effectivement, je crains les mêmes problèmes que ceux évoqués par Obsidian : overhead, épuisement de la RAM, mauvaise stratégie d'allocation, etc etc ... Surtout que mes noeuds sont générés à la volée, impossible donc de connaitre à l'avance le nombre de noeuds à allouer.
L'idée d'Obsidian évoqué en second, à savoir stocker uniquement un indice d'un tableau me plait beaucoup, je pourrai peut-être l'adapter à mon idée d'arbre.
Un contributeur du forum, que je remercie encore, m'a même évoqué l'idée d'utiliser un système de memory pool (http://en.wikipedia.org/wiki/Memory_pool), un malloc() adapté pour une allocation dynamique de bloc de taille fixe. Qu'en pensez-vous ? Cela pourrait aider dans l'idée d'Obsidian de créer un tableau de structure que l'on réalloue. Un realloc() avec ce memory pool serait probablement plus efficace qu'un realloc standard non ? Cela reviendrai (peut-être) à l'idée évoqué en premier par souviron34.
Pour ta deuxième idée souviron34, je suis désolé, je ne vois pas comment je pourrai l'adapter à mon idée.