Comment fonctionnent la réallocation et la mémoire ?

StackOverflow https://stackoverflow.com/questions/362760

  •  21-08-2019
  •  | 
  •  

Question

J'ai deux questions.

  1. Faire realloc() et memcpy() copier les entrées d'un tableau dans un autre d'une manière plus rapide qu'une simple itération sur chaque élément O(N) ?Si la réponse est oui, quelle est selon vous sa complexité ?

  2. Si la taille allouée est inférieure à la taille originale, est-ce que realloc() copier les entrées ailleurs ou simplement les laisser car elles diminuent la taille du tableau ?

Était-ce utile?

La solution

1 - Non. Ils copient un bloc à la fois. Voir http://www.embedded.com/design/ configurables systèmes / 4024961 / Optimisation-Memcpy-vitesse améliore pour une très bonne analyse.

2 - Cela dépend la mise en œuvre. Voir http://www.gnu.org/software/ libtool / manuel / libc / changement de bloc-Size.html pour plus de détails glibc. « Dans plusieurs implémentations d'allocation, ce qui rend un bloc plus petit nécessite parfois copier »

Autres conseils

Regardons d'un peu plus près memcpy et, tant qu'on y est, en notation "grand O" ou Landau.

Tout d'abord, grand-O.Comme je l'ai mentionné ailleurs, il convient de rappeler la définition du grand O, à savoir qu'une fonction g(n) est dit être O(f(n)) quand il existe une constante k Pour qui g(n) ≤ kf(n).La constante vous permet d'ignorer les petits détails au profit de la partie importante.Comme tout le monde l'a noté, memcpy de n les octets seront Sur) dans la plupart des architectures normales, car peu importe ce que vous devez déplacer n octets, un morceau à la fois.Ainsi, une première implémentation naïve de memcpy en C pourrait s'écrire

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

C'est en fait Sur), et vous pourriez vous demander pourquoi nous nous soucions même d'une routine de bibliothèque.cependant, le truc à propos du bibliothèque les fonctions sont qu'elles sont l'endroit où les utilitaires spécifiques à la plate-forme sont écrits ;si vous souhaitez optimiser l'architecture, c'est l'un des endroits où vous pouvez le faire.Donc, en fonction de l'architecture, il peut y avoir des options de mise en œuvre plus efficaces ;par exemple, dans l'architecture IBM 360, il existe un MOVL l'instruction qui déplace les données est constituée de gros morceaux utilisant un microcode très hautement optimisé.Ainsi, à la place de cette boucle, une implémentation à 360° de memcpy pourrait ressembler à quelque chose comme

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(Au fait, rien ne garantit que ce soit exactement le bon code 360, mais cela servira d'illustration.) Cette implémentation regards aimer au lieu de faire n fait le tour de la boucle comme le faisait le code C, il exécute simplement 3 instructions.

Quoi vraiment ce qui arrive, c'est qu'il s'exécute O(n)micro instructions sous les couvertures.Qu'est-ce que c'est différent entre les deux est la constante k;parce que le microcode est beaucoup plus rapide, et comme il n'y a que trois étapes de décodage dans les instructions, il est dramatiquement plus rapide que la version naïve, mais c'est quand même Sur) -- c'est juste que la constante est plus petite.

Et c'est pourquoi vous pouvez faire bon usage de memcpy -- ce n'est pas asymptotiquement plus rapide, mais la mise en œuvre est aussi rapide que quelqu'un pourrait le faire sur cette architecture particulière.

  1. Il n'y a absolument aucun moyen de copier des éléments N plus vite que O (N). Toutefois, il pourrait être en mesure de copier plusieurs éléments à la fois, ou utiliser des instructions de processeur spéciales -. Il pourrait encore être plus rapide que vous pouvez faire vous-même
  2. Je ne suis pas sûr, mais je suppose que la mémoire est complètement réaffecté. C'est la plus sûre hypothèse, et il est probablement dépendant de la mise en œuvre de toute façon.

  1. La performance de ne peut pas vraiment memcpy mieux que O (N), mais il peut être optimisé afin qu'il surclasse la copie manuelle; par exemple, il pourrait être en mesure de copier 4 octets dans le temps qu'il vous faut pour copier 1 octet. De nombreuses implémentations sont écrites realloc dans l'assemblage en utilisant des instructions optimisées qui peuvent copier plusieurs éléments à un moment qui est généralement plus rapide que la copie des données d'un octet à la fois.

  2. Je ne comprends pas tout à fait cette question, si vous utilisez pour diminuer la <=> taille de la mémoire et Succeeds (renvoie une valeur non NULL), le nouvel emplacement contiendra les mêmes données que l'ancien emplacement des à la taille de la nouvelle demande. Si l'emplacement de mémoire a été modifiée à la suite de l'appel <=> (pas d'habitude lors de la diminution de la taille) le contenu sera copié, sinon aucune copie doit se produire que la mémoire n'a pas bougé.

  1. On peut conjecturer que memcpy pourrait être écrit de telle sorte qu'il se déplacerait grand nombre de bits autour. par exemple. Il est tout à fait possible de copier les données en utilisant les instructions SSE, s'il est avantageux.

Comme autre dit, il ne sera pas plus rapide que O (n), mais les systèmes de mémoire ont souvent une taille de bloc préféré, et aussi il est possible, par exemple, écrire la taille d'une ligne de cache à un moment.

En supposant que vous parlez glibc, et que vos questions dépendent la mise en œuvre, il est probablement préférable juste pour vérifier la source:

malloc.c

memcpy.c

La façon dont je l'ai lu, les réponses serait:

  1. O (N) --- il n'y a aucun moyen pour copier des éléments à mieux que le temps linéaire.
  2. De temps en temps de grands éléments seront copiés lors realloc () est utilisé pour les réduire.

x86 a des instructions spéciales pour la numérisation et correspondant à un octet / mot dans un bloc de mémoire aussi bien et qui peut être utilisé pour copier un bloc de mémoire (il est un processeur CISC après tout). Beaucoup de compilateurs C qui mettent en œuvre le langage assembleur en ligne et un pragma faire inline des fonctions entières ont pour beaucoup de nombreuses années profité de cela dans leurs fonctions de bibliothèque.

Les mem ceux utilisés pour la copie sont movsb / movsw en combinaison à l'instruction rep. 

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

Configuration enregistre avec des adresses src / trg et int count et vous allez loin.

Certains des points importants liés à la réallocation (vérifier sur dev c++) :void *realloc(void *ptr, size_t size);

  1. La fonction realloc() doit changer la taille de l'objet mémoire pointé par ptr à la taille spécifiée par size.

  2. Le contenu de l'objet doit rester inchangé jusqu'à la moindre des nouvelles et anciennes tailles.

  3. Si la nouvelle taille est plus grande, le contenu de la partie nouvellement allouée de l'objet n'est pas spécifié.

  4. Si size est 0 et que ptr n'est pas un pointeur nul, l'objet pointé est libéré.

  5. Si ptr est un pointeur nul, realloc() sera équivalent à malloc() pour la taille spécifiée.

  6. Si ptr ne correspond pas à un pointeur renvoyé précédemment par calloc(), malloc() ou realloc() ou si l'espace a déjà été libéré par un appel à free() ou realloc(), le comportement n'est pas défini.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top