Croissance géométrique des allocations
Quand on alloue une structure de taille croissante en progression géométrique, il vaut mieux le faire avec un facteur inférieur au nombre d’or
J’ai vu cette idée mentionnée pour la première fois dans une discussion sur news:comp.lang.c++.moderated.
Quand on a une structure telle que les std::vector du C++, il est courant d’augmenter la
taille en utilisant une progression géométrique. Cela permet de conserver une complexité en
temps constant pour l’ajout. La mémoire utilisée est donc : 
, 
, 
, . . .
où 
est l’allocation initiale et 
le facteur de la progression (donc 
). Pour diminuer les risques
d’avoir de la mémoire inutilisée, on désire que la prochaine allocation, de 
, puisse se faire
dans l’espace libéré précédemment, soit 
. La première allocation 
étant un facteur
commun, on peut le simplifier. Il faut donc :
étant supérieur à 1, pour 
tendant vers l’infini 
tend aussi vers l’infini, on peut donc ignorer
et il reste
inéquation du second degré dont qui est vraie pour
Naturellement, rien ne garanti que l’allocateur pourra effectivement réutiliser la mémoire libérée. En particulier, il ne pourra pas le faire si elle ne forme pas un bloc contigu, ce qui est probable si d’autres allocations ont lieu entre les réallocations du vecteur.
Plus 
est petit, moins il faudra utiliser de blocs précédemment utilisés. Pour 
(racine de 
), les deux derniers blocs suffisent ; pour 
(racine de
) il faut les trois derniers et pour 
(racine de 
) il
faut les quatre derniers blocs. En pratique, des facteurs de 
et 
sont les plus faciles à
programmer, il suffit d’ajouter le quart ou la moitié de la taille déjà allouée.
Historique
- 11 octobre 2006
- version initiale
- 15 octobre 2006
- absence de garantie de réutilisation, valeur numérique de
et quelques
bornes supplémentaires.
- 25 février 2009
- clarification et utilisation de TEX4ht pour avoir une version HTML.