Pourquoi les compilateurs n'essaient-ils pas d'allouer de la mémoire contiguë (si possible) lorsque le vecteur est plein ?

Question

Quand std::vector est pleine, une nouvelle mémoire est allouée. D'après ce que j'ai lu, la nouvelle capacité croît selon une progression géométrique (mais cela n'a rien à voir avec la question), puis les anciennes informations sont copiées dans la nouvelle région de mémoire, et l'ancienne est libérée.

Sur la base de cette hypothèse, mes questions sont les suivantes :

1. Pourquoi les compilateurs n'essaient-ils pas de voir s'il y a suffisamment de mémoire libre contiguë à la fin de notre fichier std::vector d'en allouer une partie à la fin de notre année de travail. std::vector et ne perdez pas de temps à copier ?

2. Est-ce que des gens ont essayé d'implémenter cela, mais il a été décidé que cela ne valait pas la peine de le faire ? (en moyenne/toujours)

3. Y a-t-il d'autres raisons, plus subtiles, pour lesquelles cela ne se produit pas ?

Answer 1

C'est une combinaison de vos points 2) et 3).

On a d'abord raisonné (je ne peux pas dire quelle mesure a été prise à l'époque) que les avantages étaient rares et pas si importants. Vous ne pouvez augmenter (significativement) la mémoire que si aucune allocation n'a lieu après l'allocation initiale, et le coût de la croissance d'un vecteur est amorti.

Cependant, beaucoup ont fait remarquer que même ce scénario n'est pas si rare, et qu'il peut améliorer considérablement les performances et empêcher la fragmentation de la mémoire. Il y a donc eu un proposition en 2006 .

C'est là que les raisons les plus subtiles sont apparues. Le premier problème est que les conteneurs n'allouent pas la mémoire par eux-mêmes, mais utilisent un allocateur pour le faire. Dans un premier temps, l'interface de l'allocateur doit donc être modifiée. Ceci est difficile car, comme d'autres l'ont noté, realloc ne peut être utilisé que si le type contenu est trivial. Pour être généralement utile, nous aurions besoin d'une fonction de bas niveau différente pour faire croître la mémoire (une qui ne réalloue que si cela peut être fait sur place, voir la proposition pour plus de détails). Le problème est que toutes les plates-formes ne fournissent pas une telle fonction, et nous aurions donc besoin que Posix ou le standard C en fournisse une d'abord.