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

         --
    1----5--
?      2      1[618[[[

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 : n   0   , n   1   , n   2   , . . .n n est l’allocation initiale et  le facteur de la progression (donc 1  ). Pour diminuer les risques d’avoir de la mémoire inutilisée, on désire que la prochaine allocation, de         1
n   , puisse se faire dans l’espace libéré précédemment, soit P  !1
     0 n . La première allocation n  étant un facteur commun, on peut le simplifier. Il faut donc :

 !X1            1
      6
    0
---!1-        1
  !1  6
              2       1
   !1 6       !
  1        6        2!1

1      6   2 ! 1--

 étant supérieur à 1, pour  tendant vers l’infini  tend aussi vers l’infini, on peut donc ignorer -1
  et il reste

1      6   2

inéquation du second degré dont qui est vraie pour

            --            --
!1--   1-!--5-5    5 1-----5 - ?
  ?      2           2

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 51[324  [[[ (racine de 351 ), les deux derniers blocs suffisent ; pour 51[465 [[[ (racine de 4          2
  51   ) il faut les trois derniers et pour 51[534 [[[ (racine de 5          2    3
  51   ) il faut les quatre derniers blocs. En pratique, des facteurs de 1[25  et 1[5  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.