Complexité temporelle de l'allocation de mémoire

Question

Quelle est la complexité temporelle de l'allocation de mémoire dynamique avec new, malloc, etc.? Je sais très peu de choses sur la façon dont les allocateurs de mémoire sont mis en œuvre, mais je suppose que la réponse est que cela dépend de la mise en œuvre. Par conséquent, veuillez répondre aux cas / implémentations les plus courants.

Modifier: Je me souviens vaguement d'avoir entendu dire que l'allocation de segment de mémoire est illimitée dans le pire des cas, mais je m'intéresse beaucoup au cas moyen / typique.

Answer 1

Lorsque vous utilisez la notation O, vous devez comprendre qu’il est souvent très important de comprendre ce que n est. Si le n est quelque chose lié à quelque chose que vous pouvez contrôler (par exemple: le nombre d’éléments dans une liste que vous voulez trier), alors il est logique de le regarder de près.

Dans la plupart des implémentations de segment de mémoire, votre n correspond au nombre de blocs de mémoire contigus gérés par le gestionnaire. Décidément, il s’agit non du contrôle du client. Le seul n que le client contrôle réellement est la taille de la mémoire qu'il souhaite. Cela n’a souvent aucun rapport avec le temps que prend l’allocateur. Un n grand peut être alloué aussi rapidement qu'un petit n , ou cela peut prendre beaucoup plus de temps, voire être inutilisable. Tout cela pourrait changer pour le même n en fonction de la manière dont les allocations et désallocations précédentes des autres clients sont entrées. Donc, à moins que vous n'implémentiez un segment de mémoire, alors la bonne réponse est qu'il ne s'agit pas -déterministe .

C'est pourquoi les programmeurs en temps réel essaient d'éviter l'allocation dynamique (après le démarrage).

Answer 2

La complexité temporelle d'un allocateur de segment de mémoire peut être différente sur différents systèmes, en fonction de l'objectif pour lequel ils sont en train d'optimiser.

Sur les systèmes de bureau, l’allocateur de tas utilise probablement plusieurs stratégies différentes, notamment la mise en cache des allocations récentes, des listes de recherche pour les tailles d’allocation communes, des groupes de blocs de mémoire présentant certaines caractéristiques de taille, etc. fragmentation gérable. Voir les notes concernant l'implémentation malloc de Doug Lea pour un aperçu des différentes techniques utilisées: http: //g.oswego.edu/dl/html/malloc.html

Pour les systèmes plus simples, une stratégie de premier ajustement ou de meilleur ajustement peut être utilisée, les blocs libres étant stockés dans une liste chaînée (ce qui donnerait un temps O (N), N étant le nombre de blocs libres). Mais un système de stockage plus sophistiqué, tel qu'une arborescence AVL, pourrait être utilisé pour pouvoir localiser des blocs libres en temps O (log N) ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).

Un système temps réel peut utiliser un allocateur de pile, tel que TLSF (ajustement de séparation à deux niveaux), dont le coût d’allocation est O (1): http://www.gii.upv.es/tlsf/

Answer 3

Je pense que ce serait généralement O (n) où n est le nombre de blocs de mémoire disponibles (car vous devez scanner les blocs de mémoire disponibles pour en trouver un qui convient).

Ceci étant dit, j'ai constaté des optimisations plus rapides, notamment la gestion de plusieurs listes de blocs disponibles en fonction de leur taille (les blocs de moins de 1k sont dans une liste, les blocs de 1k à 10k dans une autre liste). et ainsi de suite).

Ceci est toujours O (n) cependant, juste avec un plus petit n.

Je serais intéressé de voir votre source comme quoi une allocation de tas est illimitée (si vous entendez par là que cela pourrait prendre une éternité).

Answer 4

Il suffit de vérifier le fonctionnement typique des allocateurs.

Un allocateur de bump-the-pointeur fonctionne dans O (1) , et il s’agit d’un petit ' 1 '.

Pour un allocateur à stockage séparé, l'attribution de k octets signifie "retourner le premier bloc de la liste ( n )". où List ( n ) est la liste des blocs de n octets où n > = k . Il est possible de constater que List ( n ) est vide, de sorte qu'un bloc de la liste suivante (List ( 2n )) doit être scindé avec les deux blocs résultants de n octets placés dans la liste ( n ), et cet effet pourrait défiler à travers toutes les tailles disponibles, permettant ainsi complexité de O (ns) où ns est le nombre de tailles différentes disponibles, et ns = log (N) où N est la taille de la plus grande taille de bloc disponible, donc même cela serait petit. Dans la plupart des cas, en particulier après qu’un certain nombre de blocs ont été alloués et libérés, la complexité est O (1) .

Answer 5

Seulement deux remarques:

• TLSF est O (1) dans le sens où il n'a pas boucle simple; et gère jusqu'à 2 Go. Bien que ce soit vraiment difficile à croire, il suffit de vérifier le code.

• Il n’est pas vrai que le "meilleur ajustement" politique (trouver le bloc serré) est la plus appropriée pour obtenir une petite fragmentation. Il est loin d’être trivial de démontrer cette affirmation. En fait, cela n’a pas été formellement prouvé, mais de nombreuses preuves vont dans ce sens. (beau sujet de recherche).