Lorsque vous utilisez MALLOC pour allouer la mémoire, est-il généralement plus rapide de faire plusieurs mallocs de plus petits morceaux de données ou moins de mallocs de plus gros morceaux de données? Par exemple, disons que vous travaillez avec un fichier image contenant des pixels noirs et des pixels blancs. Vous êtes itérant à travers les pixels et souhaitez enregistrer la position X et Y de chaque pixel noir dans une nouvelle structure qui a également un pointeur sur les valeurs x et y précédentes des pixels X et Y. Serait-ce généralement plus rapide de itérer à travers les pixels allouant une nouvelle structure pour chaque valeurs X et Y du pixel noir avec les pointeurs, ou seraient-ils plus rapides d'obtenir un nombre de pixels noirs en itération d'une fois, puis affectant une grande Chunk de la mémoire à l'aide d'une structure contenant uniquement les valeurs X et Y, mais aucun pointeur, puis itération à nouveau, sauvegarder les valeurs X et Y dans ce tableau? Je suppose que certaines plates-formes pourraient être différentes que d'autres quelles sont plus rapides, mais que pense que tout le monde serait généralement plus rapide?
14 Réponses :
En règle générale, l'allocation de gros morceaux de mémoire moins de temps sera plus rapide. Il y a des frais généraux impliqués chaque fois qu'un appel à malloc () est fait.
Pour plus d'informations, consultez le papier Usenix de Bonwick sur l'allocation de dalles. Usenix.org/publications/Library/Procedesd/bos94/full_paper S / ...
Cela dépend:
Si je me souciais, je le mesurerais! Si je me souciais vraiment beaucoup et que je ne pouvais pas deviner, alors je pourrais implémenter les deux, et mesurer au temps d'exécution sur la machine cible et adaptez-le en conséquence.
En général, je supposerais que moins de vaut mieux: mais il existe des implémentations de la bibliothèque de la taille et de la bibliothèque d'exécution de sorte qu'une allocation (suffisamment) une grande allocation sera déléguée à la (relativement lente) O / S. Alors qu'une petite allocation (suffisamment) sera servie à partir d'un tas (relativement rapide) déjà alloué.
Et comment savez-vous - en général - que votre système a une si merveille-bibliothèque?
Pour citer Chrisw: "Si je me souciais, je le mesurerais!"
@ All + Auteur: Je suis juste curieux du fait que quelqu'un pose une question ici et accepte une réponse de quelqu'un qui nous dit lui-même, qu'il ne se souciait pas (Dionadar lui cité). Je sais, nous ne faisons pas la science ici, mais pourquoi demander du tout dans cette situation?
@ Juergen Ce que j'ai dit à l'Op, peut-être d'une manière maladroite, était-ce que j'étais imo s'il se soucie, alors il devrait le tester. Il est possible (et même peut-être intéressant) de deviner, mais la réponse réelle est spécifique à la plate-forme.
@Chrisw: Je ne pense pas que le KOP veut le mesurer, quand il a demandé.
@Juergen Aussi je n'ai pas répondu à votre premier commentaire à propos d'avoir "une si merveille-bibliothèque" parce que je ne l'ai pas compris. Peut-être que est la voie à suivre en général, ni de avoir il "en général": avoir une bibliothèque particulière est une situation spécifique . Cela dit, ce que j'ai dit à propos de la délégation de l'O / S si la demande est suffisamment grande, je pense que la bibliothèque de temps d'exécution MSVC (par exemple).
@Juergen Ma réponse était qu'il peut deviner (et la plupart des gens qui devinent devineront que c'est la moins d'allocations qui seront plus rapides); mais que s'il veut vraiment, veut vraiment savoir à coup sûr, il devrait le mesurer (ou, au moins, dire à quelle bibliothèque d'exécution qu'il utilise): et étant donné qu'il veut spécifiquement savoir en général , le fait est qu'il n'y a pas de réponse générale garantie.
@ALL: À propos de toutes les réponses de chacun étaient bonnes, si je pouvais composer une réponse de leur part et voter, je le ferais. Fondamentalement, je l'ai donné à Chrisw parce qu'il était le premier à répondre à ce que «généralement» moins est meilleur, c'est ce que je demandais, bien que peut-être peut-être mal. Les problèmes de référence et de fragmentation étaient ceux que je n'avais pas pensé et j'apprécie ces réponses ainsi que les réponses de Juergen soulignent que Malloc est général en vigueur. Merci à tous ceux qui ont répondu!
@ EMI1FABER: Votre méthode est donc pour voquer simplement voter le premier up qui dit le bon mot d'arrivée? Indépendamment de l'autre contenu de la réponse. Je ne peux tout simplement pas compléter une telle méthode. J'espère que vous n'avez pas de travail scientifique ... J'espère que cela aussi pour les autres upvotes ici.
Wow, je ne savais pas que les votes sur Stackoverflow ont tellement content de ... Ne vous inquiétez pas du front scientifique, je viens d'écrire un logiciel pour les banques - sur le système financier!
Allocation de grands blocs est plus efficace; De plus, étant donné que vous utilisez des blocs contigus plus importants, vous avez une plus grande localité de référence et la traversée de votre structure en mémoire une fois que vous avez générée, il devrait également être plus efficace! En outre, l'allocation de grands blocs devrait aider à réduire la fragmentation de la mémoire.
Notez que les blocs plus importants peuvent vous faire pire fragmentation si / lorsque vous les interdisez.
@Javier: En général, la classique d'un bloc de plus grand qui consiste en des blocs plus petits est préférable à la fragmentation puis affectant / transposant ces blocs plus petits par eux selfues. Je ne peux pas le prouver dans plus de 500 caractères, mais vous ne pouvez pas prouver votre déclaration audacieuse.
Comme déjà mentonné, MALLOC est coûteux, alors moins sera probablement plus rapide. De plus, travailler avec les pixels, sur la plupart des plates-formes auront moins de cache-faute et sera plus rapide. Cependant, il n'y a aucune garantie sur toutes les plateformes
Allocation de mémoire est le travail. La quantité de travail effectuée lors de l'attribution d'un bloc de mémoire est typiquement indépendante de la taille du bloc. Vous le faites d'ici.
@ovanes: autant que je comprends, vous racontez le contraire de Neil. De plus, vous n'essayez pas de battre le compilateur, mais une routine de bibliothèque. Donc, votre point est faux ici. Lorsque votre problème de répartition est ce complexe, que vous ne pouvez pas battre cette routine (je ne vois pas cela de la question), que vous n'êtes pas en difficulté, oui! Ou vous devriez étudier certains livres.
dans le général Malloc est cher. Il doit trouver un morceau de mémoire approprié à partir de laquelle allouer la mémoire et garder une trace des blocs de mémoire non contigus. Dans plusieurs bibliothèques, vous trouverez de petits allocateurs de mémoire qui tentent de minimiser l'impact en affectant un bloc important et en gérant la mémoire dans l'allocateur.
Alexandrescu traite du problème dans "Moderne C ++ Design" et dans la bibliothèque Loki si vous souhaitez jeter un coup d'œil à une de ces libs.
Sauf les problèmes de vitesse Il existe également le Problème de fragmentation de la mémoire .
Cette question est l'une des pragmatismes, j'ai peur; C'est-à-dire que cela dépend.
Si vous avez beaucoup de pixels, seuls quelques-uns sont noirs que les comptant peuvent être le coût le plus élevé.
Si vous utilisez c ++, lequel Vos tags suggèrent que vous êtes, je suggérerais fortement d'utiliser STL, quelque chose comme STD :: Vector.
La mise en œuvre du vecteur, si je me souviens bien, utilise une approche pragmatique de l'allocation. Il existe quelques heuristiques pour les stratégies d'allocation, une information informative est la suivante: Dans ce cas, vous doublette la quantité de mémoire allouée chaque fois que vous réalloc.
Cela signifie que les réaffectations sont progressivement de moitié en fréquence. Votre implémentation STL aura été bien réglée, donc si vous pouvez l'utiliser, faites!
Je ne suis pas d'accord. Vous iTerez-vous de toute façon à travers les pixels - N'essayez pas de sauvegarder l'itération supplémentaire de compter les pixels à stocker. La réaffectation et la copie d'un STD :: Vecteur de la scène prend plus de temps.
Mais bien sûr, il est toujours fonction du nombre de pixels que vous stockez, c'est combien vous devez parcourir.
À côté de la surcharge d'affectation elle-même, l'allocation de plusieurs petits morceaux peut entraîner de nombreuses manques de cache, tandis que si vous pouviez itérer à travers un bloc contigu, les chances sont meilleures.
Le scénario que vous décrivez demande préallocation d'un grand bloc, IMHO.
bien que allouant de grands blocs est plus rapide par octet de la mémoire allouée, il ne sera probablement pas plus rapide si vous n'augmentez pas artificiellement la taille d'allocation uniquement pour le couper vous-même. Vous ne faites que dupliquer la gestion de la mémoire.
Il est plus rapide de ne pas affecter du tout au code sensible à la performance. Allouez la mémoire que vous allez avoir besoin une fois à l'avance, puis utilisez et réutilisez-la autant que vous le souhaitez.
L'allocation de la mémoire est une opération relativement lente en général, alors ne le faites pas plus souvent que nécessaire.
"Je peux allouer-it-tout" (vraiment, je peux!)
Nous pouvons la philosophie sur certaines implémentations spéciales, qui accélèrent considérablement les petites allocations ... oui! Mais en général, cela tient:
MALLOC doit être général. Il doit mettre en œuvre tous les types d'allocations. C'est la raison pour laquelle il est considérablement lent! Ce pourrait être que vous utilisez une bibliothèque spéciale de super-duper Kinky-Duper, qui accélère les choses, mais également celles-ci ne peuvent pas faire des merveilles, car elles doivent mettre en œuvre MALLOC dans son spectre complet.
La règle est, lorsque vous avez plus de codage d'allocation spécialisée, vous êtes Ainsi, lorsque vous êtes capable d'allouer la mémoire dans des blocs plus gros dans votre codage (et cela ne vous coûte pas beaucoup), vous pouvez accélérer considérablement les choses. Aussi - comme mentionné par d'autres personnes - vous obtiendrez beaucoup moins de fragmentation de la mémoire, qui accélère également les choses et peut coûter moins de mémoire. Vous devez également voir que MALLOC a besoin de mémoire supplémentaire pour chaque morceau de mémoire, il vous revient (oui, les routines spéciales peuvent réduire ceci ... mais vous ne savez pas! Qu'est-ce que cela fait vraiment à moins que vous ne l'ai vraiment mis en place vous-même ou vous êtes acheté -Library).
Un autre point à considérer est de savoir comment cela interagit avec le filetage. À l'aide de MALLOC, plusieurs fois dans une application simultanée filetée sont une traînée majeure sur la performance. Dans cet environnement, vous ferez mieux d'un allocator évolutif comme celui utilisé dans Intel's Blocs de construction de fil ou HOARD . La limitation majeure avec MALLOC est qu'il existe un seul verrou global que tous les threads subissent. Il peut être si grave que l'ajout d'un autre fil ralentit considérablement votre application.
Faites une itération sur les pixels pour compter le nombre d'entre eux à stocker. Ensuite, allouez un tableau pour le nombre exact d'éléments. C'est la solution la plus efficace.
Vous pouvez utiliser std :: vecteur pour la gestion de la mémoire plus facile (voir la procédure de réserve std :: vecteur ::). Remarque: la réserve allouera probablement un peu (probablement jusqu'à 2 fois) plus de mémoire, alors nécessaire.