inline void add(const DataStruct& rhs) {
using namespace boost::assign;
vec.reserve(vec.size() + 3);
vec += rhs.a, rhs.b, rhs.c;
}
The above function was executed for about 17000 times and it performed (as far as I can see. There was some transformation involved) about 2 magnitudes worse with the call to vector::reserve. I always was under the impression that reserve can speed up push_back even for small values but this doesn't seem true and I can't find any obvious reasons why it shouldn't be this way. Does reserve prevent the inlining of the function? Is the call to size() too expensive? Does this depend on the platform? I'll try and code up some small benchmark to confirm this in a clean environment.Compiler: gcc (GCC) 4.4.2 with -g -O2
6 Réponses :
Utilisez uniquement la réserve si vous savez à l'avance, combien il sera utilisé.
réserve devra copier votre vecteur entier ...
Si vous faites un push_back et que le vecteur est trop petit, il fera une réserve (Vec.Size () * 2).
Si vous ne connaissez pas à l'avance la taille de votre vecteur et si vous avez besoin d'un accès aléatoire, envisagez d'utiliser STD :: DEQUE.
Ce n'est pas une heuristique. Est prouvé que, en moyenne, l'insertion d'un nouvel élément est O (1). Lisez tout livre sur une analyse amortie (par exemple. Introduction aux algorithmes).
Eh bien .. Je pense que ce serait juste de dire que c'est une heuristique prouvée mathématiquement avoir la meilleure performance dans le cas moyen.
Vous pouvez prouver la même chose avec la multiplication de 3 au lieu de deux. Mais je le modifierai de toute façon si cela vous dérange beaucoup.
Je dirais que ce n'est ni une heuristique ni un algorithme. C'est une stratégie qui fonctionne bien pour beaucoup de scénarios d'utilisation.
Je lis quelque chose quelque part où se multiplier par 1,5 a fonctionné mieux. Je ne me souviens pas d'où, quelles hypothèses qu'ils faisaient, ou quoi que ce soit comme ça. De toute évidence, la multiplication par une constante plus constante réduit le nombre de réaffectations et utilise la mémoire moins efficacement.
Il est également vrai que, pour la multiplication de la taille par N sur l'échappement, une copie supplémentaire est effectuée pour chaque n-1 appels push_back par conséquent, multiplication pour 1,5 fonctionne exactement deux fois plus lentement.
Multiplier la taille allouée actuelle par toute constante (en plus 0) entraînera une croissance logarithmique. Changer la constante est simplement la syntonisation, la performance Big O est toujours la même. 1.5 favorise les plus petits vecteurs, 2 favorise plus grand. Ils ont choisi 2 parce que c'est un beau nombre rond dans des terres informatiques et tout réglage serait sans signification car mon utilisation diffère de la vôtre. Si vous avez besoin de régler le comportement, vous pouvez facilement intervenir le comportement par défaut à l'aide de la taille () et de la réserve ().
"Ils ont choisi 2" - Qui? Dinkumware a choisi 1.5. Notez que l'analyse de Pavel Shutve est fausse (probablement due à une formulation médiocre). Si vous développez un million de vecteur d'élément par un facteur n == 1.5 , vous pouvez évidemment ajouter 500.000 éléments, pas n-1 == 0.5 0.5
La mise en œuvre de Facebook de std :: vecteur utilise une valeur inférieure à 2 de sorte que le conteneur pourrait théoriquement "réutiliser" l'espace laissé des allocations précédentes. Un facteur de croissance de 2 garantit que l'espace requis pour chaque allocation est toujours un peu plus que la somme de tous les espaces que vous avez alloués jusqu'à présent (par tailleof (t) octets), ce qui signifie que le Le vecteur se débarrassera toujours en mémoire, en supposant que la mise en œuvre alloue la mémoire linéairement. Un facteur de croissance inférieur à 2 peut utiliser l'espace que les allocations précédentes ont abandonné.
Vous utilisez uniquement Sinon, utilisez simplement réserve () si vous connaissez à l'avance le nombre d'éléments. Dans ce cas réserve () espace pour tous les éléments à la fois.
push_back () et s'appuyer sur la stratégie par défaut - il réaffectera de manière exponentielle et réduira grandement le nombre de réaffectations à un coût de la consommation de mémoire légèrement sous-optimale.
Déplacez la réserve en dehors de l'ajout.
Chaque fois que vous invoquez "Ajouter", vous réservez au moins 3 éléments supplémentaires. Selon la mise en œuvre du vecteur, ce pourrait augmenter la taille de la matrice de support presque chaque fois que vous appelez "Ajouter". Cela revient certainement à la différence de performance que vous décrivez. La bonne façon d'utiliser la réserve est quelque chose comme:
implémentation de GCC de réserve () allouera un nombre exact d'éléments, tandis que push_back () va cultiver du tampon interne de manière exponentielle en le doublant, de sorte que vous vaincez la croissance exponentielle. et forcer la réaffectation / copie sur chaque itération. Exécutez votre test sous lTroce ou Valgrind et voir le numéro de MALLOC () appels.
+1. Je viens de vérifier les sources de GCC et je vais écrire de la même manière.
La croissance exponentielle du tampon via Push_back () garantie par la norme ou la mise en œuvre définie?
Non, la croissance exponentielle n'est pas garantie par la norme, c'est un détail de mise en œuvre, comme ce comportement particulier de réserve ().
La croissance exponentielle est garantie efficacement par la norme, car il s'agit du seul moyen raisonnable d'obtenir un amortissement O (1) Comportement pour Push_back (des solutions déraisonnables incluent l'affectation de toute mémoire;))
Le comportement de GCC peut également expliquer: en vous laissant régler exactement la taille attendue, ils vous permettent de ne pas perdre de mémoire dans les cas où vous savez en fait combien vous aurez besoin.
J'ai toujours pensé que la croissance exponentielle appliquée à réserve aussi, et que réserve vient de garantir l'allocation d'élément préalez-vous et n'échoue pas plus tard avec un push_back à la mémoire épuisée. Rencontrer la même surprise d'Asker aujourd'hui, j'ai un peu souhaité qu'il y ait une variante qui garantit une allocation ultérieure (au moins pour la POD) mais présenterait toujours la croissance naturelle.
Si cela vous importe, méfiez-vous que «exponentiel» ne signifie pas toujours doubler la capacité sur emplace_back - certaines implémentations deviennent à 1,5 fois.
Si vous avez profilé le code, je parie que vous verriez que le + = = est très rapide, le problème est que la réserve vous tue. Vous ne devriez vraiment utiliser que la réserve lorsque vous avez une connaissance de la taille du vecteur. Si vous pouvez deviner à l'avance, faites une réserve, sinon allez avec le push_back par défaut.
Quand STD :: vecteur doit la réaffecter, il augmente sa taille d'allocation par N * 2, où n est sa taille actuelle. Cela se traduit par un nombre logarithmique de réallocs que le vecteur grandit.
Si, au lieu de cela, le vecteur de STD :: a développé son espace alloué par une quantité constante, le nombre de réallocs augmenterait linéairement lorsque le vecteur grandit.
Ce que vous avez fait est essentiellement parce que le vecteur augmente par une quantité constante 3, ce qui signifie une croissance linéaire. Linéaire est évidemment pire que logarithmique, en particulier avec de gros chiffres.
Généralement, la seule croissance mieux que la logarithmique est constante. C'est pourquoi le comité des normes a créé la méthode de la réserve. Si vous pouvez éviter tous les réallocs (constants), vous effectuerez mieux que le comportement logarithmique par défaut.
Qui a dit que vous voudrez peut-être envisager les commentaires de Herb Sutter sur la préférence STD :: Deque Overque www. gotw.ca/gotw/054.htm
Avez-vous essayé de réserver de l'espace pour 17000 * 3 entrées? Il peut y avoir des frais généraux avec votre appel de fonction supplémentaire, qui pourrait expliquer la différence.
@splicer: Le nombre était dû aux TestData. Le nombre réel d'appels est variable.
Mon point était que ce que vous faites est seulement efficace avec des nombres plus importants. La réponse de James Schek vous donne un moyen de le faire avec un nombre variable d'appels, tant que vous connaissez le total pour commencer. Sinon, vous feriez mieux de laisser la mise en œuvre par défaut la gérer pour vous.
Appelez-vous ajouter () sur la même instance de classe? Dans ce cas, vous grandissez VEC par 3 pour chaque ajoutent alors que la poussée en elle-même augmenterait la VEC beaucoup moins fréquemment.