Quel est le taux de croissance idéal pour un tableau alloué dynamicment?

C ++ a std :: vector et Java a ArrayList, et de nombreux autres langages ont leur propre forme de tableau alloué dynamicment. Lorsqu’un tableau dynamic manque d’espace, il est réalloué dans une zone plus grande et les anciennes valeurs sont copiées dans le nouveau tableau. Une question centrale à la performance d’un tel tableau est la vitesse de croissance du tableau. Si vous ne faites que grossir suffisamment pour répondre aux besoins actuels, vous finirez par vous réallouer à chaque fois. Il est donc logique de doubler la taille du tableau ou de le multiplier par 1,5.

Y a-t-il un facteur de croissance idéal? 2x? 1.5x? Par idéal, je veux dire mathématiquement justifié, le meilleur équilibre entre la performance et la mémoire gaspillée. Je me rends compte que théoriquement, étant donné que votre application pourrait avoir une dissortingbution potentielle de pushes, cela dépend quelque peu des applications. Mais je suis curieux de savoir s’il y a une valeur qui est “généralement” la meilleure, ou est considérée comme la meilleure dans une contrainte rigoureuse.

J’ai entendu dire qu’il y avait un article quelque part, mais je n’ai pas pu le trouver.

    Cela dépendra entièrement du cas d’utilisation. Vous souciez-vous davantage du temps perdu à copier les données autour (et à réallouer les baies) ou à la mémoire supplémentaire? Combien de temps le tableau va-t-il durer? Si cela ne va pas durer longtemps, utiliser un plus grand tampon peut être une bonne idée – la peine est de courte durée. Si cela continue (par exemple en Java, en passant par les générations plus âgées et plus âgées), c’est évidemment plus une pénalité.

    Il n’y a pas de “facteur de croissance idéal”. Ce n’est pas seulement théoriquement dépendant de l’application, c’est certainement dépendant de l’application.

    2 est un facteur de croissance assez courant – je suis presque sûr que c’est ce ArrayList et List dans .NET. ArrayList en Java utilise 1.5.

    EDIT: Comme Erich le souligne, Dictionary<,> dans .NET utilise “double la taille puis augmente au prochain nombre premier” afin que les valeurs de hachage puissent être réparties raisonnablement entre les compartiments. (Je suis sûr que j’ai récemment vu de la documentation suggérant que les nombres premiers ne sont pas vraiment parfaits pour dissortingbuer des compartiments de hachage, mais c’est un argument pour une autre réponse.)

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

    Le raisonnement est le suivant:

    1. Disons que vous commencez avec une allocation de 16 octets.
    2. Lorsque vous avez besoin de plus, vous allouez 32 octets, puis libérez 16 octets. Cela laisse un trou de 16 octets dans la mémoire.
    3. Lorsque vous avez besoin de plus, vous allouez 64 octets, libérant les 32 octets. Cela laisse un trou de 48 octets (si les 16 et 32 ​​étaient adjacents).
    4. Lorsque vous 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 que, avec une expansion de 2x, il n’y a aucun moment où le trou résultant sera assez grand pour être réutilisé pour la prochaine allocation. En utilisant une allocation 1.5x, nous avons ceci:

    1. Commencez avec 16 octets.
    2. Lorsque vous avez besoin de plus, allouez 24 octets, puis libérez le 16, laissant un trou de 16 octets.
    3. Lorsque vous avez besoin de plus, allouez 36 octets, puis libérez le 24, laissant un trou de 40 octets.
    4. Lorsque vous avez besoin de plus, allouez 54 octets, puis libérez le 36, laissant un trou de 76 octets.
    5. Lorsque vous avez besoin de plus, allouez 81 octets, puis libérez le 54, laissant un trou de 130 octets.
    6. Lorsque vous avez besoin de plus, utilisez 122 octets (arrondis vers le haut) depuis le trou de 130 octets.

    Idéalement (dans la limite de n → ∞), c’est le nombre d’or : ϕ = 1,618 …

    En pratique, vous voulez quelque chose de proche, comme 1.5.

    La raison en est que vous souhaitez pouvoir réutiliser des blocs de mémoire plus anciens, tirer parti de la mise en cache et éviter de faire en sorte que le système d’exploitation vous donne plus de pages de mémoire. L’équation que vous résoudrez pour vous assurer que cela se réduit à x n – 1 – 1 = x n + 1x n , dont la solution approche x = ϕ pour n large.

    Pour répondre à des questions comme celle-ci, une approche consiste simplement à «sortingcher» et à examiner ce que font les bibliothèques populaires, en supposant qu’une bibliothèque largement utilisée ne fasse, à tout le moins, rien d’horrible.

    Donc, vérifier très rapidement, Ruby (1.9.1-p129) semble utiliser 1.5x lors de l’ajout à 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 , donc l’expression avec l’opérateur bitshifts et ternary ne fait que calculer la surallocation.

    Disons que vous augmentez la taille du tableau de x . Supposons donc que vous commencez avec la taille T La prochaine fois que vous agrandirez le tableau, sa taille sera T*x . Alors ce sera T*x^2 et ainsi de suite.

    Si votre objective est de pouvoir réutiliser la mémoire créée auparavant, vous devez vous assurer que la nouvelle mémoire que vous allouez est inférieure à la sum de la mémoire précédente que vous avez libérée. 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 donc ceci:

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

    De manière informelle, ce que nous disons, c’est qu’à la nth allocation, nous voulons que toute notre mémoire précédemment désallouée soit supérieure ou égale à la mémoire nécessaire à la nième allocation afin que nous puissions réutiliser la mémoire précédemment désallouée.

    Par exemple, si nous voulons pouvoir le faire à la troisième étape (c.-à-d. n=3 ), alors nous avons

     x^3 <= 1 + x 

    Cette équation est vraie pour tout x tel que 0 < x <= 1.3 (grossièrement)

    Voyez ce que nous obtenons pour différents n 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érieur à 2 car x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2 .

    Cela dépend vraiment. Certaines personnes parsingnt les cas d’utilisation courants pour trouver le nombre optimal.

    J’ai vu 1,5 x 2,0 x phi x, et la puissance de 2 utilisé auparavant.

    Si vous avez une dissortingbution sur les longueurs de tableau, et que vous avez une fonction d’utilité indiquant à quel point vous aimez gaspiller de l’espace par rapport à perdre du temps, vous pouvez certainement choisir une stratégie optimale de redimensionnement (et de dimensionnement initial).

    La raison pour laquelle le multiple simple constant est utilisé est évidemment que chaque append ait un temps constant amorti. Mais cela ne signifie pas que vous ne pouvez pas utiliser un ratio différent (plus grand) pour les petites tailles.

    Dans Scala, vous pouvez remplacer loadFactor pour les tables de hachage de la bibliothèque standard avec une fonction qui examine la taille actuelle. Curieusement, les tableaux redimensionnables ne font que doubler, ce que font la plupart des gens dans la pratique.

    Je ne connais pas de tableaux doublés (ou 1,5 * ing) qui attrapent réellement des erreurs de mémoire et augmentent moins dans ce cas. Il semble que si vous aviez un énorme tableau unique, vous devriez le faire.

    J’appendai que si vous conservez les baies redimensionnables assez longtemps et que vous privilégiez l’espace au fil du temps, il peut être judicieux de procéder à une surallocation spectaculaire (dans la plupart des cas) et de les réaffecter terminé.

    Je suis d’accord avec Jon Skeet, même mon ami théoricien insiste sur le fait que cela peut être prouvé être O (1) lors de la définition du facteur à 2x.

    Le rapport entre le temps processeur et la mémoire est différent sur chaque machine et le facteur variera tout autant. Si vous avez une machine avec des gigaoctets de RAM, et un processeur lent, copier les éléments dans une nouvelle masortingce est beaucoup plus coûteux que sur une machine rapide, ce qui pourrait à son tour avoir moins de mémoire. C’est une question à laquelle on peut répondre en théorie, pour un ordinateur uniforme, ce qui, dans des scénarios réels, ne vous aide pas du tout.

    Je sais que c’est une vieille question, mais il y a plusieurs choses qui semblent manquer.

    Tout d’abord, il s’agit d’une multiplication par 2: size << 1. Il s’agit d’une multiplication entre 1 et 2: int (float (size) * x), où x est le nombre, le * est un calcul flottant et le processeur a pour exécuter des instructions supplémentaires pour le casting entre float et int. En d'autres termes, au niveau de la machine, le doublage nécessite une instruction unique très rapide pour trouver la nouvelle taille. En multipliant par quelque chose entre 1 et 2, il faut au moins une instruction pour convertir la taille en flottant, une instruction à multiplier (qui est la multiplication par flottant, donc il faut probablement au moins deux fois plus de cycles, voire quatre fois plus) , et une instruction à renvoyer dans int, et qui suppose que votre plate-forme peut effectuer des calculs flottants dans les registres d’usage général, au lieu d’utiliser des registres spéciaux. En bref, vous devez vous attendre à ce que le calcul de chaque allocation prenne au moins 10 fois plus de temps qu’un simple décalage à gauche. Si vous copiez beaucoup de données pendant la réallocation, cela pourrait ne pas faire une grande différence.

    Deuxièmement, et probablement le grand coup de pied: tout le monde semble supposer que la mémoire libérée est à la fois contiguë et contiguë à la mémoire nouvellement allouée. À moins que vous ne pré-allouiez toute la mémoire vous-même et que vous l’utilisiez ensuite comme un pool, ce n’est certainement pas le cas. Le système d’exploitation peut parfois le faire, mais la plupart du temps, il y aura suffisamment de fragmentation de l’espace libre pour qu’un système de gestion de la mémoire à moitié décent puisse trouver un petit trou où votre mémoire se contentera. Une fois que vous avez vraiment de gros morceaux, vous êtes plus susceptible de vous retrouver avec des pièces contiguës, mais à ce moment-là, vos allocations sont suffisamment importantes pour que vous ne les fassiez pas assez souvent pour que cela ait plus d’importance. En bref, il est amusant d’imaginer que l’utilisation d’un nombre idéal permettra d’utiliser au mieux l’espace mémoire libre, mais en réalité, cela ne se produira que si votre programme fonctionne sur le bare metal (comme dans, il n’existe pas de système d’exploitation). en dessous il prend toutes les décisions).

    Ma réponse à la question? Non, il n’y a pas de nombre idéal. Il est si spécifique à l’application que personne ne tente vraiment. Si votre objective est l’utilisation optimale de la mémoire, vous n’avez pratiquement plus de chance. Pour la performance, les allocations moins fréquentes sont meilleures, mais si nous allions juste avec cela, nous pourrions multiplier par 4 ou même 8! Bien sûr, lorsque Firefox passe de 1 Go à 8 Go en une seule fois, les gens vont se plaindre, ce qui n’a aucun sens. Voici quelques règles de base que j’irais bien si:

    Si vous ne pouvez pas optimiser l’utilisation de la mémoire, ne perdez pas au moins les cycles du processeur. Multiplier par 2 est au moins un ordre de grandeur plus rapide que de faire des calculs en virgule flottante. Cela ne fera peut-être pas une grande différence, mais cela fera au moins une différence (surtout au début, au cours des allocations plus fréquentes et moins importantes).

    Ne réfléchis pas trop. Si vous venez de passer 4 heures à essayer de faire quelque chose qui a déjà été fait, vous venez de perdre votre temps. En toute honnêteté, s’il y avait une meilleure option que * 2, cela aurait été fait dans la classe vectorielle C ++ (et dans de nombreux autres endroits) il y a plusieurs décennies.

    Enfin, si vous voulez vraiment optimiser, ne transpirez pas les petites choses. De nos jours, plus de 4 Ko de mémoire sont gaspillés, à moins qu’ils ne travaillent sur des systèmes embarqués. Lorsque vous obtenez 1 Go d’objects entre 1 Mo et 10 Mo chacun, doubler est probablement beaucoup trop (je veux dire, cela fait entre 100 et 1 000 objects). Si vous pouvez estimer le taux d’expansion attendu, vous pouvez le niveler à un taux de croissance linéaire à un moment donné. Si vous prévoyez environ 10 objects par minute, la croissance de 5 à 10 tailles d’object par étape (une fois toutes les 30 secondes à une minute) est probablement une bonne chose.

    En gros, ne pensez pas trop, optimisez ce que vous pouvez et personnalisez votre application (et votre plate-forme) si vous le souhaitez.

    Deux autres cents

    • La plupart des ordinateurs ont une mémoire virtuelle! Dans la mémoire physique, vous pouvez avoir des pages aléatoires partout qui sont affichées comme un seul espace contigu dans la mémoire virtuelle de votre programme. La résolution de l’indirection est effectuée par le matériel. L’épuisement de la mémoire virtuelle était un problème sur les systèmes 32 bits, mais ce n’est vraiment plus un problème. Donc, remplir le trou n’est plus une préoccupation (sauf les environnements spéciaux). Depuis Windows 7, même Microsoft prend en charge 64 bits sans effort supplémentaire. @ 2011
    • O (1) est atteint avec tout facteur r > 1. La même preuve mathématique ne fonctionne pas seulement pour 2 comme paramètre.
    • r = 1.5 peut être calculé avec l’ old*3/2 3/2, il n’y a donc pas besoin d’opérations en virgule flottante. (Je dis /2 parce que les compilateurs le remplaceront par des bits décalés dans le code assembleur généré s’ils le jugent bon.)
    • MSVC est allé pour r = 1.5, donc il y a au moins un compilateur majeur qui n’utilise pas 2 comme ratio.

    Comme mentionné par quelqu’un 2 se sent mieux que 8. Et aussi 2 se sent mieux que 1,1.

    Mon sentiment est que 1.5 est un bon défaut. Sinon, cela dépend du cas spécifique.