Pourquoi les tableaux ne peuvent pas être coupées ?

Question

Sur la Documentation MSDN sur le site, il est dit ce qui suit au sujet de l' Array.Resize méthode:

Si newSize est plus grande que la Longueur de l'ancien tableau, un nouveau tableau est alloués et tous les éléments sont copiés à partir de l'ancien tableau à l' nouveau.

Si newSize est inférieure à la Longueur de l'ancien tableau, un nouveau tableau est alloués et les éléments sont copiés à partir de l'ancien tableau à la nouvelle jusqu'à ce que le nouveau est rempli; le reste des éléments de l'ancien tableau sont ignorés.

Un tableau est une suite de blocs de mémoire contigus. Si nous avons besoin d'un plus grand tableau, je comprends que nous ne pouvons pas ajouter de la mémoire, car la mémoire à côté, c'est peut-être déjà revendiquée par d'autres données. Nous avons donc à réclamer une nouvelle séquence de blocs de mémoire contigus avec les plus grande taille, copier nos entrées et de retirer notre plainte de l'ancien espace.

Mais pourquoi créer un nouveau tableau avec une taille plus petite? Pourquoi le tableau non seulement à enlever sa revendication de la dernière blocs de mémoire? Alors il serait un O(1) opération au lieu de O(n), comme il est maintenant.

A-t-elle quelque chose à voir avec la façon dont les données sont organisées sur un ordinateur de l'architecture ou de niveau physique?

Answer 1

La mémoire inutilisée n'est pas réellement utilisé. C'est le travail de tout segment de la mise en œuvre de garder une trace de trous dans le tas. Au minimum, le gestionnaire a besoin de savoir la taille du trou et a besoin de garder une trace de leur emplacement. Que toujours frais au moins 8 octets.

Dans .NET, Système.Objet joue un rôle clé. Tout le monde sait ce qu'il fait, ce n'est pas aussi évident qu'il continue à vivre après un objet est collecté. Les deux champs supplémentaires dans l'objet de l'en-tête (syncblock et le type de poignée), puis tournez vers l'arrière et vers l'avant pointeur de la précédente/suivante bloc libre. Il dispose également d'une taille minimale de 12 octets en mode 32 bits. Garantit qu'il existe toujours suffisamment d'espace pour stocker le bloc libre de taille après l'objet est collecté.

Donc, vous voyez probablement le problème maintenant, la réduction de la taille d'un tableau ne garantit pas qu'un trou est créé, qui est assez grand pour s'adapter à ces trois domaines. Rien de ce qu'il pourrait faire, mais de jeter un "ne peut pas faire une" exception. Dépend aussi du nombre de bits du processus. Entièrement trop moche à prendre en compte.

Answer 2

Pour répondre à votre question, il a à voir avec la conception de la gestion de la mémoire système.

En théorie, si vous avez écrit votre propre système de mémoire vous pourrait tout à fait concevoir qu'il se comporte exactement comme vous l'avez dit.

La question devient alors, pourquoi n'était-il pas été conçu de cette façon. La réponse est que la gestion de la mémoire système fait un compromis entre l'utilisation efficace de la mémoire et de performances.

Par exemple, la plupart de la mémoire des systèmes de gestion de ne pas gérer la mémoire vers le bas à l'octet. Au lieu qu'ils cassent la mémoire en 8 KO morceaux. Il y a des tas de raisons à cela, dont la plupart sont autour de la performance.

Une des raisons ont à voir avec la façon dont le processeur se déplace de la mémoire autour. Par exemple, disons que le processeur était beaucoup mieux lors de la copie d'8 KO de données à un moment, puis il a été à la copie de 4 KO. Ensuite, il ya un avantage de performance de stocker les données dans 8 KO morceaux. Ce serait une conception du commerce hors basé sur l'architecture du PROCESSEUR.

Il y a aussi algorithmique de la performance des arbitrages. Par exemple, dire à partir de l'étude du comportement de la plupart des applications que vous trouvez que 99% des applications d'allouer des blocs de données qui sont 6 KO 8 KO.

Si le système de mémoire qui vous a permis d'allouer et de libérer de 4 ko, il serait parti avec un avec gratuit de 4 ko morceau que 99% des allocations de ne pas être en mesure d'utiliser. Si, au lieu de plus de alloués à 8 KO, même si seulement 4 KO sont nécessaires, il serait beaucoup plus réutilisable.

Considérons encore une autre conception. Dire que vous avez une liste de positions de mémoire libres qui pourraient être de toute taille et une demande a été faite pour allouer de 2 ko de mémoire. Une approche possible serait de regarder à travers votre liste de libérer de la mémoire et en trouver un qui est au moins égal à 2 ko en taille, mais ne vous regardez à travers l'ensemble de la liste pour trouver que le plus petit bloc, ou vous trouvez le premier qui est assez grand et l'utiliser.

La première approche est plus efficace, mais plus lent, la seconde approche est de moins en moins efficace mais plus rapide.

Il devient encore plus intéressant dans des langages tels que C# et Java qui ont "réussi de la mémoire". Dans un mémoire gérée par le système de la mémoire n'est pas encore libéré; il s'arrête juste à s'habituer, ce qui le garbage collector plus tard, dans certains cas, beaucoup plus tard, détecte et la libère.

Pour plus d'informations sur la gestion de la mémoire et de l'allocation que vous voudrez peut-être consulter cet article sur Wikipedia:

https://en.wikipedia.org/wiki/Memory_management

Answer 3

Je cherchais une réponse à votre question car j'ai trouvé que c'était une question très intéressante. J'ai trouvé cette réponse qui a une intéressante première ligne:

Vous ne pouvez pas libérer d'une partie d'un tableau permet uniquement d' free() un pointeur que vous avez obtenu à partir d' malloc() et quand vous faites cela, vous aurez l'ensemble de l'allocation que vous avez demandé.

Donc en fait le problème est le registre qui garde la mémoire est allouée. Vous ne pouvez pas simplement une partie du bloc que vous avez alloué, vous devez les libérer entièrement ou vous n'avez pas libre du tout. Cela signifie que dans le but de libérer de la mémoire, vous devez déplacer les données de la première. Je ne sais pas si .NET gestion de la mémoire n'quelque chose de spécial à ce sujet, mais je pense que cette règle s'applique à la CLR.

Answer 4

Je pense que c’est parce que l’ancien tableau n’est pas détruit. Il est toujours là s’il est référencé ailleurs et il est toujours accessible. C’est pourquoi le nouveau tableau est créé dans un nouvel emplacement mémoire.

Exemple :

Tirages :

Answer 5

Il y a deux raisons pour la définition de realloc comme il est: d'Abord, il est absolument clair qu'il n'y a aucune garantie que l'appel à realloc avec une plus petite taille sera de retour le même pointeur. Si votre programme fait cette hypothèse, votre programme est cassé. Même si le pointeur est le même 99,99% du temps. Si il y a un gros bloc en plein milieu de beaucoup d'espace vide, provoquant la fragmentation du segment, puis realloc est libre de se déplacer hors de la voie, si possible.

Deuxièmement, il existe des implémentations où il est absolument nécessaire de le faire. Par exemple, MacOS X est une application où un gros bloc de mémoire est utilisée pour allouer malloc blocs de 1 à 16 octets, un autre grand bloc de mémoire pour malloc blocs de 17 à 32 octets, un malloc pour les blocs de 33 à 48 octets, etc. Il est donc très naturellement que tout changement de taille qui reste dans la plage de dire 33 à 48 octets renvoie le même bloc, mais en changeant soit 32 ou 49 octets doit réaffecter le bloc.

Il n'y a aucune garantie quant à la performance de realloc. Mais dans la pratique, les gens ne font pas la taille un peu plus petit. Les principaux cas sont: Allouer de la mémoire à une estimation de la limite supérieure de la taille, le remplir, puis de les redimensionner à la réalité de beaucoup plus petite taille. Ou allouer de la mémoire, puis la redimensionner à quelque chose de très petit, quand il n'est pas plus nécessaire.