Si je veux allouer des millions d'objets d'une classe évidemment, Aussi, je suppose que cela ne devrait pas utiliser de fonctions virtuelles?
Et à quel point est coûteux pour Y a-t-il d'autres conseils pour faire des millions de foo , et je veux être efficace de la mémoire et du temps, comment dois-je concevoir la classe foo ?
foo ne doit pas contenir de nombreuses données de membre.
foo d'une classe de base? Et de plusieurs classes de base?
FOO Objets très efficaces?
8 Réponses :
Regardez le Modèle de flyweight . Book Gof fait un bien meilleur travail que Wikipedia Pour expliquer le motif, cependant.
Je ne pense pas qu'il y ait beaucoup à dire sur la conception de votre classe pour des millions d'allocations. Oui, il y a la limite de mémoire évidente, donc si vous avez une quantité de mémoire correcte, cela pourrait être une véritable préoccupation pour vous, sinon vous risqueriez toujours de manquer de mémoire. Un pointeur sur la table virtuelle est juste que, un pointeur (4 ou 8 octets sur une architecture 32 ou 64 bits), pas sûr que ce soit le cas en héritage multiple. Les fonctions virtuelles appelantes ont les frais généraux de la recherche virtuelle (et Mlle de cache supplémentaire, si vous ne l'utilisez pas récemment), mais uniquement pour les fonctions virtuelles, et ils ne peuvent jamais être inlinés.
S'il y a beaucoup de valeurs répétées, vous souhaiterez peut-être aussi avoir une structure de données distincte également (motif voleur de vol). Et pour l'efficacité, assurez-vous d'avoir un constructeur et des opérateurs d'affectation légers (inliné), en particulier si vous souhaitez utiliser des vecteurs STL et similaires.
Ce sont tous des trucs assez simples, alors maintenant pour ma véritable suggestion:
Qu'est-ce qui va vraiment tuer votre gestion de la mémoire est si vous obtenez une fragmentation, où vous pourriez tout à coup un tas de mémoire, mais quand même de mettre vos objets (pas assez d'espace contigu). Si vous avez beaucoup d'allocation entrelacée, cela pourrait devenir un véritable problème afin que vous puissiez vouloir examiner de grands blocs d'objets, les garder dans une piscine et la réutilisation. Ou utilisez un allocator personnalisé (nouvel opérateur), où vous prévenez un bloc de mémoire qui est un multiple de la taille de votre objet et utilisez-le pour vos objets.
Je suis d'accord. Flyweight + objet-piscine et objet réutiliser.
D'accord. En outre, s'il y a une possibilité possible de les rendre immuables, cela permettrait une réutilisation. Il peut être possible de vous éloigner avec des milliers d'objets référencés dans des millions d'emplacements. Difficile de savoir sans avoir plus d'informations sur le domaine problématique.
Dans la mesure où un objet peut être dit être efficace du tout, il devrait être petit si beaucoup de choses sont créées, et des opérations communes à ce sujet doivent être inlinables si beaucoup d'appels sont faits. En termes de mémoire, des fonctions virtuelles coûtent généralement 4 ou 8 octets (la taille d'un pointeur) par objet pour la première, libre par la suite. Comme d'autres l'ont dit, Flyweight est une façon de rendre des objets plus petits, s'ils contiennent des données en double qui peuvent être partagées. Si vos millions d'objets ne contiennent pas de données en double, oubliez-la.
Plus correctement, c'est le code qui est efficace ou inefficace. Les appels virtuels coûtent probablement certains frais d'appel, mais il appartient au code d'appel, pas de la classe, combien de fois chaque fonction membre est appelée. Dans tous les cas, l'inlinage est l'endroit où les gains de vitesse sont des gains de vitesse et les fonctions virtuelles ne sont qu'un moyen d'obstruer un site d'appel particulier bénéficiant de l'inlinisation. Si votre conception est simplifiée en ayant 27 fonctions de membre virtuel, chacune est appelée une fois par mois, mais garantissant que les 2 fonctions appelées des millions de fois une seconde peuvent être inlinées par l'appelant, alors il n'est pas nécessaire d'éviter les fonctions virtuelles .
Les classes de base coûtent à peu près la même chose qu'un objet membre du même type. Avec multiples héritage, Tout ce qui dit, la principale chose que vous souhaitez faire est de faire fonctionner du code dès que possible, qui imite raisonnablement la création d'objets et les caractéristiques d'appel de votre code fini. Ensuite, vous saurez quel type de performance que vous envisagez - si votre opération critique apparaît plus ou moins rapidement avec les fonctions virtuelles dans, il n'y a aucun point à venir avec un schéma de conception contorqué juste pour les éviter. Si votre profileur vous dit que tout le temps est consacré à la création d'objets, ne les utilisez pas une fois que vous les avez, vous devez rechercher une allocation, pas les fonctions membres.
La raison pour obtenir une estimation tôt est que vous ne voulez pas perdre de temps à concevoir quelque chose qui ne fonctionnera certainement pas. Des repères de base ("puis-je appeler static_cast pourrait cesser d'être un NO-OP car il s'agit généralement d'un héritage unique, mais cela ne vaut probablement pas la peine d'être inquiétant. Héritage virtuel et dynamic_cast peut être intéressant en termes de quantité de travail effectuée au moment de l'exécution, mais uniquement sur une échelle similaire à celle des fonctions de membre virtuel.
neuf mille fois une seconde une seconde? Un million de fois une seconde? Tout aussi vite de plusieurs threads simultanément?") Peut se nourrir dans le processus de conception, mais bien sûr Impossible d'optimiser correctement jusqu'à ce que vous ayez une version plausible de votre code actuel.
La principale chose est de minimiser l'utilisation de Nouveau et Supprimer en maintenant les objets utilisés dans une piscine et en les utilisant. Ne vous inquiétez pas des fonctions virtuelles. Les frais généraux de les appeler sont généralement triviaux par rapport à tout ce qui se passe dans votre programme.
Et le coût de la mémoire des fonctions virtuelles est minimal - un pointeur unique par objet (sur le VFTABLE). Vous devriez être capable d'éliminer cela en n'ayant pas de fonctions virtuelles.
@kyoryu: Droite. Et je ne pouvais pas dire quel est le nombre d'objets actifs d'état d'équilibre, donc je ne pouvais donc pas dire si la taille est même une question.
juste pour clarifier un point sur les allocateurs personnalisés.
Avec le nouveau L'idée est d'effectuer un appel à Si vous conservez un pool de Dans le C ++ PL2E, STROSTRUP parle d'octets 'sur ma machine' , vous devrez donc faire les expériences vous-même: combien de mémoire est réellement prise pour allouer un seul < Code> FOO avec Rechercher des allocateurs de la piscine (par exemple, boost ) ou des petits allocateurs d'objets (par exemple, Loki ). Nouveau , vous êtes susceptible d'obtenir un peu de frais généraux, c'est-à-dire une mémoire supplémentaire allouée au-dessus de la taille (FOO) . Ce que vous voulez vraiment arriver, c'est répandre cette surcharge sur plusieurs FOO s.
neuf pour allouer un seul bloc d'octets assez gros pour contenir 100 ou 1 000 d'entre eux (ou plus?) de contigus foo s, puis allouer un seul foo s de cela.
FOO S, vous risquez toujours de souffrir d'une mémoire de mémoire sur chaque instance, même si c'est plus rapide.
Nouveau ?
Bon point, mais vous n'avez pas besoin de regarder au-delà de la norme. std :: deque
Concernant l'allocation de vos objets de classe, jetez un coup d'œil à la boost Bibliothèque piscine , qui peut être plus efficace pour de nombreuses allocations de petits objets que les nouveaux objets ordinaires / Supprimer via l'allocateur système. Cela peut également les rester plus proches ensemble en mémoire. Le Une autre chose à considérer est lorsque les objets vont être créés - par exemple, que vous sachiez à l'avance combien vous aurez besoin (et donc un système de mise en commun / réutilisation tel que décrit par d'autres serait utile) , ou si vous savez simplement qu'il y aura O (1m) d'entre eux requis à différents moments. La création de grandes numéros en une fois devrait être beaucoup plus rapide que l'attribution de beaucoup d'entre eux individuellement. De mon propre travail, j'ai souvent trouvé que l'allocation de mémoire répétée pour de nombreux petits objets apparaît comme un gros goulot d'étranglement dans le profilage.
Je suggérerais de gréer une application de test qui simulera le nombre d'allocations dont vous avez besoin et de comparaître les différentes stratégies. Vous devrez peut-être combiner plus d'un. fast_pool_allocator est très pratique comme une implémentation d'allocator C ++ que vous pouvez facilement déposer dans votre application pour évaluer l'avantage. Je suggérerais d'utiliser des allocateurs de toute façon, car cela facilitera la comparaison des différents schémas d'allocation.
D'autres ont mentionné le modèle de piles de vol, mais depuis que vous avez marqué cela pour C ++, je regarderais boost.flyweight . Sa conception convient à votre besoin et si vous devez réinventer la roue, vous pouvez toujours consulter sa source pour plus de détails.
Pour ce que ça vaut la peine ... Vous pouvez également gagner de l'utilisation d'un autre idiome.
Je connais le modèle S'il semble étrange, pensez à l'objet string dans bien sûr, Bien sûr, c'est très La collecte des ordures étant un autre sujet, je préfère vous laisser avec l'idée d'un flyweight est tout à fait la rage, mais vous pouvez également bénéficier de ne pas attribuer ces Des millions d'objets. python . Comme dans de nombreuses langues récentes, string est immuable dans python . Bien sûr, l'objet que vous manipulez peut changer, mais le vrai string ne: Votre poignée est simplement déplacée simplement. python a automatique Collection à ordures qui facilite beaucoup plus facilement, mais cela pourrait fonctionner pour vous aussi. Voici un croquis: Classe de base immuable Core (expose Seuls les méthodes const ) et une poignée mutable (qui change simplement la classe principale qu'elle pointe sur lorsqu'il est invité à changer).
Avoir des fonctions virtuelles n'ajoute que 4 autres octets à l'objet (8 pour 64 bits). Dériver de la classe de base ne coûte rien. (Ceux-ci assument un héritage unique.)
Vous devriez également rechercher une allocation plus rapidement en utilisant un allocator personnalisé.
Ce que vous devriez faire dépend de ce que vous faites. Que faites-vous?
Comment ces objets vont-ils être utilisés? Peuvent-ils être immuables? Ont-ils des identités fortes ou sont-ils surtout des valeurs? Sans connaître les contraintes, il est difficile de donner de bons conseils.
L'immuabilité n'est pas nécessaire, je pense, car il peut y avoir une différence entre une poignée mutable et un état immuable. Trop long pour expliquer ici donc je le mettais dans une réponse ci-dessous.
J'ai vu un bon nombre de questions sur le tri "Je dois faire une zillion de cela" Comment puis-je le faire zoomer? Malheureusement, ils sont souvent de la forme "algorithme A avoir besoin de kerjillions d'objet O mais j'ai oublié que la sélection des algorithmes fait partie du problème et je suis donc bloqué à propos de O". O puits.
@Matthieu M: Non, ce n'est pas nécessaire , mais c'est un outil utile (comme vous l'avez utilisé dans votre exemple, un seul niveau caché). Le point général n'était pas "Peut-on les rendre immuables", nous devons-nous en savoir plus sur le problème pour proposer une solution. ' Il y a un certain nombre de façons de s'attaquer à cela, mais de choisir une personne dont nous avons besoin de connaître les contraintes du problème réel.
@KYORYU: Je suis d'accord avec la nécessité des connaissances, je viens de souligner que la partie immutabilité semble moins importante que le reste. Il serait effectivement agréable d'avoir plus d'informations sur le problème lui-même, peut-être (comme suggéré par MSW), car nous pourrions alors suggérer une solution qui n'implique pas de créer des millions d'articles, et c'est le cas que nous faisons, car les solutions pouvaient être beaucoup Plus spécialisé.
@Matthieu M: Je pense que nous sommes sur la même page. La seule raison pour laquelle j'ai même posé une question sur l'immutabilité, c'est que si c'est une possibilité, il ouvre des options très des options rapides et faciles en termes de flyweights / réutilisation de l'objet. C'était une sorte d'optimisation débutante :)