Le temps de la complexité de l'allocation de mémoire
Quelle est la complexité temporelle de l'allocation dynamique de la mémoire à l'aide de nouvelles, malloc, etc.? Je sais très peu de choses sur la façon dont la mémoire allocateurs 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 à certains des plus communs de cas et de mises en œuvre.
Edit:
J'ai vaguement le souvenir d'avoir entendu que l'allocation de tas est illimitée dans le pire des cas, mais je suis vraiment intéressé à la moyenne/typique cas.
Vous devez vous connecter pour publier un commentaire.
L'une des choses que vous avez à réaliser lorsque l'on traite avec O la notation, c'est 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 triée), alors il est logique de regarder dur.
Dans la plupart des tas implémentations, votre n est le nombre de blocs contigus de la mémoire du manager est de la manipulation. C'est décidément pas quelque chose de typiquement sous contrôle du client. La seule n le client a vraiment de contrôle sur la taille de la partie de la mémoire qu'elle veut. Souvent, cela n'a aucun rapport avec la quantité de temps que l'allocateur prend. Un grand n pourrait être rapidement réparti comme un petit n, ou il peut prendre beaucoup plus de temps, ou peut-être même unservicable. Tout cela pourrait changer pour le même n en fonction de l'évolution des dotations et deallocations d'autres clients sont arrivés. Donc vraiment, sauf si vous êtes à la mise en œuvre d'un segment, alors la bonne réponse est qu'il est non-déterministe.
C'est pourquoi dur en temps réel les programmeurs essayez d'éviter l'allocation dynamique (après le démarrage).
La complexité du temps pour un segment de l'allocateur peut être différent sur différents systèmes, en fonction de ce qu'ils pourraient être optimiser pour.
Sur les systèmes de bureau, le segment de l'allocateur utilise probablement un mélange de différentes stratégies, y compris la mise en cache récente allocations, lookaside des listes pour la commune de la répartition des tailles, des bacs de segments de mémoire avec certaines caractéristiques, etc. pour essayer de garder un moment d'attribution, mais aussi garder la fragmentation gérable. Voir les notes de Doug Lea la fonction malloc de la mise en œuvre pour un aperçu des différentes techniques qui sont utilisées: http://g.oswego.edu/dl/html/malloc.html
Pour des systèmes plus simples, une stratégie de premier de la forme ou de meilleur ajustement peut être utilisé, avec les blocs libres stockées sur une liste chaînée (ce qui donnerait un temps O(N) fois, N étant le nombre de blocs libres). Mais en plus sophistiqué système de stockage comme un arbre AVL peut être utilisé pour être en mesure de localiser les blocs libres en O(log N) temps (http://www.oocities.org/wkaras/heapmm/heapmm.html).
Un système en temps réel peut utiliser un tas allocateur comme TLSF (Deux au Niveau de Séparer Fit), qui est un O(1) répartition des coûts: http://www.gii.upv.es/tlsf/
Je pense qu'il serait généralement en O(n) où n est le nombre de blocs de mémoire (puisque vous devez analyser la disposition des blocs de mémoire de trouver un convenable).
Cela dit, j'ai vu des optimisations qui peuvent le rendre plus rapide, plus précisément à la gestion de plusieurs listes de blocs en fonction de leur taille varie (de sorte que les blocs de moins de 1k sont dans une liste, les blocs de 1k à 10k sont dans une autre liste, et ainsi de suite).
C'est toujours en O(n) cependant, juste avec un petit n.
Je serais curieux de voir votre source qu'il y a un tas d'allocation d'démesuré (si, par que, vous voulez dire qu'il pourrait prendre une éternité).
Il suffit de voir la façon dont les allocateurs de travail.
Une bosse-la-pointeur allocateur travaille dans O(1), et c'est un petit " 1' à l'.
Pour un distincts de stockage de l'allocation, l'allocation de k octets signifie "retour du premier bloc de la Liste(n)" où la Liste(n) est la liste des blocs de n octets où n >= k. à trouver cette Liste(n) est vide, alors qu'un bloc à partir de la liste suivante (Liste(2n)) doit être réparti avec les deux résultant des blocs de n octets d'être mis sur Liste(n), et cet effet pourrait se propagent dans toutes les tailles disponibles, pour une complexité de O(ns) où ns est le nombre de différentes tailles disponibles, et ns = log (N) où N est la taille de la taille du plus grand bloc disponible, de sorte que même ce serait des petits. Dans la plupart des cas, surtout après un certain nombre de blocs ont été attribués et libéré, la complexité est O(1).
Juste deux remarques:
TLSF est O(1) dans le sens que l'on n'a pas une seule boucle; et gère jusqu'à 2 go.
Bien qu'il est vraiment difficile à croire, il suffit de cocher le code.
Il n'est pas vrai que le "meilleur" de la politique (trouver le serré block) est le plus approprié pour
réaliser de petites fragmentation.
Il est loin d'être négligeable pour démontrer cette affirmation, en fait, il n'a pas été formellement démontré, mais il y a beaucoup de témoignages qui vont dans ce sens. (beau sujet de recherche).