Quel est le taux de croissance idéal pour une baie allouée dynamiquement ?

Question

C++ a std :: vector et Java a ArrayList, et de nombreux autres langages ont leur propre forme de tableau alloué dynamiquement.Lorsqu'un tableau dynamique manque d'espace, il est réaffecté dans une zone plus grande et les anciennes valeurs sont copiées dans le nouveau tableau.Une question centrale pour les performances d’un tel tableau est la vitesse à laquelle la taille du tableau augmente.Si vous ne grandissez toujours que suffisamment pour s'adapter à la poussée actuelle, vous finirez par réaffecter à chaque fois.Il est donc logique de doubler la taille du tableau ou de la multiplier par, disons, 1,5x.

Existe-t-il un facteur de croissance idéal ?2x ?1,5x ?Par idéal, j'entends une performance d'équilibrage mathématiquement justifiée et une mémoire gaspillée.Je me rends compte qu'en théorie, étant donné que votre application pourrait avoir n'importe quelle distribution potentielle de poussées, cela dépend quelque peu de l'application.Mais je suis curieux de savoir s'il existe une valeur qui est "généralement" la meilleure, ou qui est considérée comme la meilleure dans le cadre d'une contrainte rigoureuse.

J'ai entendu dire qu'il y avait un article à ce sujet quelque part, mais je n'ai pas réussi à le trouver.

Answer 1

Elle dépendra entièrement de cas d'utilisation. Avez-vous souciez plus le temps la copie des données gaspillée autour (et en réaffectant les tableaux) ou la mémoire supplémentaire? Combien de temps le tableau va durer? Si ça ne va pas être pour longtemps, en utilisant un tampon plus grand peut-être une bonne idée - la peine est de courte durée. Si ça va traîner (par exemple en Java, d'entrer dans les générations plus âgées et plus) qui est de toute évidence plus d'une pénalité.

Il n'y a pas une telle chose comme un « facteur de croissance idéal. » Il ne suffit pas théoriquement application dépendante, il est définitivement dépend de l'application.

2 est un facteur de croissance assez commun - je suis sûr que ce que ArrayList et List<T> dans .NET utilise. ArrayList<T> en Java utilise 1.5.

EDIT: Comme Erich souligne, Dictionary<,> .NET utilise « double la taille puis augmenter le nombre premier » de sorte que les valeurs de hachage peuvent être répartis raisonnablement entre seaux. (Je suis sûr que je l'ai vu récemment des documents suggérant que les nombres premiers ne sont pas en fait ce grand pour distribuer des seaux de hachage, mais c'est un argument pour une autre réponse.)

Answer 2

Je me souviens avoir lu il y a de nombreuses années pourquoi la version 1.5 est préférée à deux, du moins en ce qui concerne le C++ (cela ne s'applique probablement pas aux langages gérés, où le système d'exécution peut déplacer les objets à volonté).

Le raisonnement est le suivant :

1. Supposons que vous commenciez avec une allocation de 16 octets.
2. Lorsque vous en avez besoin de plus, vous allouez 32 octets, puis libérez 16 octets.Cela laisse un trou de 16 octets en mémoire.
3. Lorsque vous en avez besoin de plus, vous allouez 64 octets, libérant ainsi les 32 octets.Cela laisse un trou de 48 octets (si les 16 et 32 ​​étaient adjacents).
4. Lorsque vous en avez besoin de plus, vous allouez 128 octets, libérant ainsi les 64 octets.Cela laisse un trou de 112 octets (en supposant que toutes les allocations précédentes sont adjacentes).
5. Et ainsi de suite.

L’idée est qu’avec une expansion 2x, il n’y a aucun moment où le trou résultant sera suffisamment grand pour être réutilisé pour la prochaine allocation.En utilisant une allocation de 1,5x, nous obtenons ceci :

1. Commencez avec 16 octets.
2. Lorsque vous en avez besoin de plus, allouez 24 octets, puis libérez les 16, laissant un trou de 16 octets.
3. Lorsque vous en avez besoin de plus, allouez 36 octets, puis libérez les 24, laissant un trou de 40 octets.
4. Lorsque vous en avez besoin de plus, allouez 54 octets, puis libérez les 36, laissant un trou de 76 octets.
5. Lorsque vous en avez besoin de plus, allouez 81 octets, puis libérez les 54, laissant un trou de 130 octets.
6. Lorsque vous en avez besoin de plus, utilisez 122 octets (arrondis au supérieur) à partir du trou de 130 octets.

Answer 3

Idéalement (dans la limite comme n → ∞), il est le ratio or : φ = 1,618 ...

Dans la pratique, vous voulez quelque chose près, comme 1.5.

La raison en est que vous voulez être en mesure de réutiliser anciens blocs de mémoire, pour tirer profit de la mise en cache et éviter de faire constamment le système d'exploitation vous donner plus de pages de mémoire. L'équation que vous avait à résoudre pour assurer ce qui réduit à x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ , dont la solution approche x = φ pour les grandes n .

Answer 4

Une approche en répondant à des questions comme celui-ci est juste « tricher » et regardez ce que les bibliothèques populaires faire, sous l'hypothèse qu'une bibliothèque largement utilisée est, à tout le moins, ne pas faire quelque chose d'horrible.

Il suffit donc de vérifier très rapidement, Ruby (1.9.1-p129) semble utiliser 1.5x lors de l'ajout d'un tableau, et Python (2.6.2) utilise 1.125x plus une constante (dans Objects/listobject.c ):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize ci-dessus est le nombre d'éléments dans le tableau. Notez bien que newsize est ajouté à new_allocated, de sorte que l'expression des bitshifts et opérateur ternaire est vraiment juste calculer la sur-allocation.

Answer 5

Disons que vous cultivez la taille du tableau par x. Ainsi, supposons que vous commencez avec la taille T. La prochaine fois que vous développer le tableau de sa taille sera T*x. Ensuite, il sera T*x^2 et ainsi de suite.

Si votre objectif est d'être en mesure de réutiliser la mémoire qui a été créé avant, vous voulez vous assurer que la nouvelle mémoire que vous allouez est inférieure à la somme de la mémoire précédente vous DEALLOCATED. Nous avons donc cette inégalité:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Nous pouvons retirer T des deux côtés. Nous obtenons ceci:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Officieusement, ce que nous disons est que, à l'allocation de nth, nous voulons que notre toute la mémoire désallouée précédemment pour être supérieure ou égale à la nécessité de la mémoire à l'allocation nième afin que nous puissions réutiliser la mémoire désallouée précédemment.

Par exemple, si nous voulons être en mesure de le faire à la 3e étape (à savoir, n=3), nous avons

x^3 <= 1 + x 

Cette équation est vrai pour tous les x de telle sorte que 0 < x <= 1.3 (à peu près)

Voyez ce que nous obtenons pour xons différents n est ci-dessous:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Notez que le facteur de croissance doit être inférieure à 2 depuis x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Answer 6

Cela dépend vraiment. Certaines personnes analysent les cas d'utilisation communs pour trouver le nombre optimal.

Je l'ai vu 1,5x 2,0x phi x, et la puissance de 2 utilisé avant.

Answer 7

Si vous avez une distribution sur des longueurs de tableau, et vous avez une fonction d'utilité qui indique combien vous aimez perdre de l'espace en fonction de perdre du temps, alors vous pouvez certainement choisir une stratégie Redimensionnement optimale (et le dimensionnement initial).

La raison est utilisé multiple simple, constante, est évidemment de sorte que chaque append a amorti constante de temps. Mais cela ne signifie pas que vous ne pouvez pas utiliser un rapport différent (plus) pour les petites tailles.

Dans Scala, vous pouvez remplacer loadfactor pour les tables de hachage bibliothèque standard avec une fonction qui ressemble à la taille actuelle. Bizarrement, les tableaux redimensionnables doublent juste, qui est ce que la plupart des gens dans la pratique.

Je ne connais pas de doublement (ou 1,5 * ing) des tableaux qui attrapent effectivement des erreurs de mémoire et croissent moins dans ce cas. Il semble que si vous aviez une très vaste gamme unique, vous voulez le faire.

J'ajouterai que si vous gardez les tableaux redimensionnables assez longtemps, et vous en faveur de l'espace au fil du temps, il peut être judicieux de façon spectaculaire overallocate (pour la plupart des cas) au départ, puis réattribuer exactement la bonne taille lorsque vous avez terminé.

Answer 8

Je suis d'accord avec Jon Skeet, même mon ami theorycrafter insiste sur le fait que cela peut être prouvé être O (1) lors du réglage du facteur 2x.

Le rapport entre le temps de processeur et la mémoire est différente sur chaque machine, et de sorte que le facteur varie tout autant. Si vous avez une machine avec giga-octets de RAM et un processeur lent, la copie des éléments à un nouveau tableau est beaucoup plus cher que sur une machine rapide, ce qui pourrait à son tour avoir moins de mémoire. Il est une question qui peut répondre en théorie, pour un ordinateur uniforme, ce qui dans les scénarios réels ne marche pas vous aider du tout.

Answer 9

Je sais qu'il est une vieille question, mais il y a plusieurs choses que tout le monde semble manquer.

Tout d'abord, cela est la multiplication par 2: taille << 1. Ceci est la multiplication par quoi que ce soit entre 1 et 2: int (float (taille) * x), où x est le nombre, * est flottant mathématiques points, et le processeur doit exécuter des instructions supplémentaires pour la coulée entre flotteur et int. En d'autres termes, au niveau de la machine, ce qui double prend une seule instruction très rapide pour trouver la nouvelle taille. En multipliant par quelque chose entre 1 et 2 nécessite au moins une instruction de jeter la taille à un flotteur, une instruction à multiplier (qui est la multiplication flottante, donc il faut probablement au moins deux fois plus de cycles, sinon 4 ou même 8 fois plus), et une instruction à rejetterait int, et qui suppose que votre plate-forme peut réaliser des opérations mathématiques flottant sur les registres à usage général, au lieu d'exiger l'utilisation de registres spéciaux. En bref, vous devriez vous attendre le calcul pour chaque attribution à prendre au moins 10 fois plus longtemps comme un simple décalage vers la gauche. Si vous copiez beaucoup de données au cours de la réallocation cependant, cela pourrait ne pas faire beaucoup de différence.

En second lieu, et probablement le gros kicker: Tout le monde semble supposer que la mémoire qui est libéré est à la fois contigu à lui-même, ainsi que contigu à la mémoire nouvellement allouée. À moins que vous Préallocation toute la mémoire vous et l'utiliser comme une piscine, ce qui est presque certainement pas le cas. Le système d'exploitation peut parfois finissent par faire, mais la plupart du temps, il va être assez fragmentation de l'espace libre que tout système de gestion de la mémoire de la moitié décente sera en mesure de trouver un petit trou où votre mémoire Juste en forme. Une fois que vous arrivez à mordit vraiment des morceaux, vous êtes plus susceptibles de se retrouver avec des pièces contiguës, mais d'ici là, vos allocations sont assez grand pour que vous ne les faites pas assez souvent pour qu'il importe plus. En bref, il est amusant d'imaginer que l'utilisation un nombre idéal permettra l'utilisation la plus efficace de l'espace mémoire libre, mais en réalité, il ne va pas se produire à moins que votre programme est en cours d'exécution sur le métal nu (comme, il n'y a pas OS dessous faisant toutes les décisions).

Ma réponse à la question? Non, il n'y a pas de nombre idéal. Il est si application spécifique que personne ne tente vraiment même. Si votre objectif est l'utilisation de la mémoire idéale, vous êtes à peu près pas de chance. Pour les performances, les allocations moins fréquentes sont mieux, mais si nous sommes allés juste avec cela, nous pourrions multiplier par 4 ou même 8! Bien sûr, quand les sauts Firefox d'utiliser 1 Go à 8 Go en un seul coup, les gens vont se plaindre, de sorte que ne fait même pas de sens. Voici quelques règles de base que je passeraient bien:

Si vous ne pouvez pas optimiser l'utilisation de la mémoire, au moins ne pas perdre les cycles de processeur. 2 est multiplier par au moins un ordre de grandeur plus rapide que faire des calculs en virgule flottante. Il pourrait ne pas faire une énorme différence, mais il fera une différence au moins (surtout au début, au cours des allocations plus fréquentes et plus petites).

Ne pas overthink il. Si vous venez de passer 4 heures à essayer de comprendre comment faire quelque chose qui a déjà été fait, vous venez de perdre votre temps. Totalement honnêtement, il y avait une meilleure option que * 2, il aurait été fait dans la classe de vecteur C ++ (et beaucoup d'autres endroits) il y a des décennies.

Enfin, si vous vraiment veulent optimiser, ne pas transpirer les petites choses. De nos jours, personne ne se soucie de 4Ko de mémoire gaspillée, à moins qu'ils travaillent sur les systèmes embarqués. Lorsque vous arrivez à 1 Go d'objets qui sont entre 1 et 10 Mo. chacun, doublement est probablement beaucoup trop (je veux dire, ce qui est entre 100 et 1000 objets). Si vous pouvez estimer le taux d'expansion prévu, vous pouvez niveler vers un taux de croissance linéaire à un certain point. Si vous prévoyez environ 10 objets par minute, puis à la croissance de 5 à 10 tailles d'objets par étape (une fois toutes les 30 secondes à une minute) est probably bien.

Qu'est-ce que tout cela revient à dire, ne pense pas au-dessus, d'optimiser ce que vous pouvez, et personnaliser à votre application (et plate-forme) si vous devez.

Answer 10

Encore deux cents

• La plupart des ordinateurs ont la mémoire virtuelle! Dans la mémoire physique, vous pouvez avoir des pages au hasard partout qui sont affichés comme un seul espace contigu dans la mémoire virtuelle de votre programme. La résolution de l'indirection se fait par le matériel. l'épuisement de la mémoire virtuelle était un problème sur les systèmes 32 bits, mais il est vraiment pas un problème. Ainsi, le remplissage trou est pas une préoccupation plus (à l'exception des environnements particuliers). Depuis Windows 7, même Microsoft prend en charge 64 bits sans effort supplémentaire. @ 2011
• O (1) est atteint avec un r > 1 facteur. la preuve mathématique fonctionne même non seulement pour 2 en tant que paramètre.
• r = 1,5 peut être calculé avec old*3/2 donc il n'y a pas besoin d'opérations en virgule flottante. (Je dis /2 parce que les compilateurs remplacera avec décalage de bits dans le code assembleur généré s'ils l'entendent.)
• MSVC a pour r = 1,5, de sorte qu'il existe au moins une majeure compilateur qui n'utilise 2 sous forme de rapport.

Comme mentionné par quelqu'un 2 se sent mieux que 8. Et 2 se sent mieux que 1.1.

Mon sentiment est que 1,5 est un bon choix par défaut. Autre que cela dépend du cas particulier.