Ecrire un gestionnaire de mémoire rapide et intelligent - Page 1

Après la recherche de l'algorithme de hachage donnant le meilleur rapport homogénéité/vitesse sur des chaînes (réelles ), j'aimerais discuter des algorithmes d'allocation mémoire.

Je cherche une méthode qui permet d'allouer des milliers de petits (disons 128 octets max) blocs de mémoire quasiment instantanément (c'est pour construire des arbres). La libération des blocs doit être possible individuellement, mais cela restera rare.

La consommation mémoire de cet algo doit rester négligeable, car il tournera sur un système limité (184 ko de RAM). L'idéal serait qu'il ne consomme pas plus de 6 octets par bloc alloué.

En cas de libération, il faut éviter la fragmentation de la RAM afin de ne pas se retrouver avec plein de petits blocs qui empêcheraient d'allouer des blocs de taille plus importante (et puis cela ralentirait certainement le temps d'allocation).

Tout dépend des contraintes d'utilisation. Quelles sont elles ?

Qu'appelles-tu des contraintes ?

J'aimerais pouvoir allouer environ 10.000 blocs, qui auront une taille moyenne de 12 octets je pense.
La plupart des blocs seront petits (entre 4 et 12 octets)
On peut imposer un maximum sur la taille des blocs. Disons qu'une limite de 128 octets me conviendra.
Ils doivent tous se situer à une adresse paire et leur taille sera toujours paire.

L'allocation d'un bloc doit se faire en un minimum d'opérations.

Quand est-ce que c'est alloué, quand c'est libéré ?
Sont-ils libérés dans le sens contraire d'allocation ?
Y a-t-il des variables à durée de vie locales ? Globales ? Mélange des deux ? Peut-on le savoir à l'avance ?
Etc.

Martial : Le garbage (rassembler les blocs alloués pour obtenir des grandes plages libres) ne sera pas possible je pense. En effet, les blocs alloués seront fixes. Quand le "macro bloc" qui contient les autres ressemblera à un gruyère, on ne pourra donc pas faire grand chose.

Le reste de tes questions dépend justement de la solution qu'on trouvera. Sachant que l'allocation doit être la plus rapide possible, il vaut mieux gérer la fragmentation à la libération

La priorité : la rapidité d'allocation. La mémoire consommée par l'algo (overhead sur chaque bloc) doit être faible, pas plus de 6 octets.


PpHd : je réponds dans 2 mn


[edit du ./3] : la taille moyenne passe à 12 octets.

Je pense que la réponse à toutes tes questions a été donnée (indirectement parfois), relis le ./2, le ./3 et le ./6

PpHd : En général, il y aura des longues séquences d'allocation (genre 100 allocations) avant qu'on demande une libération. Les libérations seront anarchiques (n'importe quel bloc pourra être libéré entre 2 séquences).

Mis à part ces libérations minoritaires, la plupart des blocs auront la même durée de vie (je prévois d'ailleurs d'implémenter une fonction de libération massive des blocs).

Perso je vois une gestion de la mémoire comme ceci :
On possède une zone mémoire de taille fixe en puissance de 2 soit 64 Ko par exemple. Le principe est de découper celle-ci en différents blocs (de taille en puissance de 2 et de nombre décroissant).
Par exemple :

32 de 2 octets
28 de 4 octets
26 de 8 octets
22 de 16 octets
18 de 32 octets
...
Bon en gros le principe (je ne sais plus le nom de la suite ou la méthode mathématiques) est d'avoir un nombre de blocs qui soit en concordance avec la taille moyenne d'allocation afin d'éviter une trop grande dispersion des données en mémoire. Si trop de petits blocs avec des allocations moyennes assez conséquentes cela entraine une mémoire (gruyère), le contraire, une mémoire "perdue".

Connaissant la distribution de la table d'allocation (la fameuse suite à trouver) et connaissant la taille de l'allocation il devient facile d'allouer les blocs utiles (ni trop de petits bloc ni un bloc de trop grande taille)...

Je sais pas si j'ai été clair.

La libération devient facile aussi. Connaissant l'adresse il devient facile de connaitre la suite de blocs alloués et de les marquer comme libérés. La difficulté c'est le garbage collect mais inutile dans ton cas.

ton truc c'est le buddy system et c'est merdique à implémenter proprement.

je te propose un algo qui alloue des blocs en multiples d'une taille de base (4-8-16-etc octets) et qui utilise un bitmap pour repérer les zones utilisées.

Je connais pas ses performances, mais je peux te le passer si tu veux l'évaluer. La taille du buffer dans lequel il "nage" n'a pas besoin d'être une puissance de 2 (juste un multiple du bloc de base, et encore je sais pas vraiment si c'est nécessaire)

ouch meme avec un simple bitmap pour savoir si une "page" est alloué ou non 10000 bloc fait en gros 1Ko (et on ne stoque que l'état d'une page :/)

tu es sur de vouloir allouer 10 000 bloc ?

(oui 1Ko peut paraitre ridicule, mais si c'est pour une machine avec peu de mémoire ça peut vite etre critique..)

edit: cross

Arf merci je ne me souvenais plus du nom.
Mais quoi qu'il en soit je me souviens que cet algorithme était au contraire facile à implémenter et surtout adapté au arbres binaires (je crois que c'est pour cela que Thibaut veut avoir un gestionnaire de mémoire).

Buddy memory allocation utilise lui aussi un bitmap pour représenter les blocs...

http://en.wikipedia.org/wiki/Buddy_memory_allocation

geogeo (./12) :
Buddy memory allocation utilise lui aussi un bitmap pour représenter les blocs...

Tu es bien obligé de stoquer d'une maniere ou d'une autre les zones mémoire que tu propose.. ko<a href='javascript:;' onclick='getPost(event,104147,12)'>./13</a>

De toute maniere la mémoire sans MMU est obligé de se segmenter, ou alors il faut utiliser des handles comme dans le TIOS pour eviter les pbm de pointeurs qui sont modifié.

Oui mais ici il se moque de la réallocation ? Donc inutile de penser au Garbage Collect et à la réallocation. Oui en effet mon algo devient complexe si on prend en compte ces deux fonctions. Encore une fois il n'est adapté qu'à l'allocation d'arbres binaires et non pour tout types de données.

Au vue des différentes contraintes que tu m'as exposé, et en particulier un ratio de 100 allocations pour 1 libération, n'importe quelle méthode fera l'affaire.
Même une simple pile qui ne libère jamais devrait pouvoir faire l'affaire. Ca te coutera 1% de ta mémoire. La taille d'un bitmap qui pointe vers les zones libres.

Le problème du bitmap, c'est qu'il faut chercher dedans, ça rend pas l'allocation très rapide. A moins qu'il y ait une manière efficace de s'y prendre ?

geogeo : Je ne pense pas que ton idée soit très souple telle quelle, mais elle est à creuser. On peut peut-être déboucher sur un truc intéressant.

Godzil (./11) :
ouch meme avec un simple bitmap pour savoir si une "page" est alloué ou non 10000 bloc fait en gros 1Ko (et on ne stoque que l'état d'une page :/)

tu es sur de vouloir allouer 10 000 bloc ?
(oui 1Ko peut paraitre ridicule, mais si c'est pour une machine avec peu de mémoire ça peut vite etre critique..)

Eh bien j'ai calculé et si on part sur des clusters de 4 octets et une taille moyenne de bloc de 12 octets, ça nous fait une table de 3750 octets pour 10.000 blocs. On a donc un overhead de 0,37 octets par bloc, ce qui respecte remarquablement bien notre contrainte (6 octets d'overhead max)

Ca dépend de la taille des clusters squalyl appelle ça des "zones" dans son post :

squalyl (./10) :
je te propose un algo qui alloue des blocs en multiples d'une taille de base (4-8-16-etc octets) et qui utilise un bitmap pour repérer les zones utilisées.

Je ne sais pas quel est le terme le plus approprié ?

Thibaut (./20) :
Je ne sais pas quel est le terme le plus approprié ?

http://en.wikipedia.org/wiki/Memory_pool

Thibaut (./18) :
Le problème du bitmap, c'est qu'il faut chercher dedans, ça rend pas l'allocation très rapide. A moins qu'il y ait une manière efficace de s'y prendre ?

Avec la méthode de squalyl c'est simple et efficace, tu parcours juste le bitmap en cherchant le premier bit libre depuis l'endroit de la dernière allocation -- tant que ta mémoire est remplie à moins de 80% ça n'aura aucun effet sur les performances

Merci pour l'URL, je vais lire ça cette aprèm !

[edit] J'ai pas résisté et j'ai lu Je vais être en retard encore

Memory pools allow dynamic memory allocation comparable to malloc or C++'s operator new. As those implementations suffer from fragmentation because of variable block sizes, it can be impossible to use them in a real time system due to performance.

Je pensais que les MMU sur les systèmes modernes permettaient de régler tous les problèmes de fragmentation !?


geogeo : C'est pour une structure arborescente, mais pas du tout binaire. Ca partira dans tous les sens.

pollux> ah j'y avais même pas pensé, en fait à chaque malloc() je cherche depuis le début

le buddy system, moi, il m'a pété les c*ouilles pendant 3 semaines, parce qu'il empêche d'allouer des blocs de taille puissance de 2. Sinon, il faut encore des structures de données pour stocker les pointeurs vers des zones.

mais si tu fais une vraie alloc buddy system dans un pool unique, bin le début de chaque bloc contient une info libre/occupé et la puissance de 2 du bloc, donc si tu fais un malloc(64) bin il faut 65 octets et il va en allouer 128

edit: rien dit

(si ce n'est que le pbm reste pour une application dans son espace mémoire)

Thibaut (./22) :
Je pensais que les MMU sur les systèmes modernes permettaient de régler tous les problèmes de fragmentation !?

Comme le dit la phrase pas éditée du message de Godzil, tu mélanges deux problèmes distincts :
1) l'allocation de pages mémoire par le système aux processus
2) la gestion par ces processus de leur mémoire en interne

Le problème n°1 se fait au travers des fonctionnalités des MMU, et effectivement n'est pas affectée de fragmentations.

Le problème n°2 dépend complètement du processus. Chacun, une fois réservé ses pages mémoire, les gère comme il veut (à commencer par la façon de les réserver, brk() ou des mappings indépendants, type mmap()). En l'occurence, GLIBC offre aux développeurs un système d'allocation d'espace à l'intérieur de ces pages mémoire. C'est ce mécanisme qui est sujet à la fragmentation.
D'ailleurs, lorsque des contraintes spécifiques sont rencontrées, il est fréquent que les développeurs n'utilisent pas le mécanisme proposé par GLIBC et implémentent le leur. Exemple : les moteurs de particules font quasiment tous ça, ayant besoin d'allouer et libérer rapidement de très grands nombres d'objets de taille identique.

spectras (./25) :
Le problème n°1 se fait au travers des fonctionnalités des MMU, et effectivement n'est pas affectée de fragmentations.

donc c'est pas plus coûteux de dire que l'espace virtuel est l'une des (2^20)! permutations quelconques de 4 Go par pages de 4 ko, plutôt que de dire que l'espace virtuel est formé de 10 gros blocs qui correspondent à 10 gros blocs physiques ?

ptet c'est moins compréhensible?

dit autrement, ça coûte pas plus cher d'avoir 2^20 blocs différents plutôt que 10 blocs ?

Pas en temps CPU. En consommation mémoire oui, mais pas parce que l'espace est gaspillé, juste parce que les métadonnées prennent une place plus importante.

D'accord, merci spectras

Jusqu'ici j'imaginais que les nouveaux processeurs résolvaient tous ces problèmes. Je suis surpris que ces problèmes de gestion soient toujours résolus par le software.

Mais tous les programmes C++/Pascal, qui allouent et redimensionnent des blocs en mémoire pour la moindre des opérations (ex : opération sur une chaîne de caractères), comment se débrouillent-ils ?
Au bout d'un certain nombre d'opérations, ça doit devenir très lent !?