La mémoire algorithme d'allocation convient le mieux pour la performance et la critique des applications c++?

Je pose cette question pour déterminer l'allocation de la mémoire de l'algorithme donne de meilleurs résultats avec les performances des applications critiques, comme les moteurs de jeu, ou des applications embarquées. Les résultats sont en fait dépend pourcentage de mémoire fragmentée et le temps-le déterminisme de la demande de mémoire.

Il existe plusieurs algorithmes dans les livres de texte (par exemple, Copain d'allocation de mémoire), mais il y a aussi d'autres comme TLSF. Donc, concernant l'allocation de la mémoire des algorithmes disponibles, celui qui est le plus rapide et cause moins de fragmentation. BTW, les éboueurs devraient pas être inclus.

Veuillez également noter que cette question n'est pas sur le profilage, elle vise simplement à trouver le meilleur algorithme pour un programme donné.

  • Existe-il d'autres exigences, comme combien de temps vous allez vous accrocher à des éléments, à quelle fréquence vous allouer/libérer/et la taille des allocations? Je ne sais pas assez sur des algorithmes différents, mais je peux imaginer des scénarios où ceux-ci pourraient être décisifs dans le choix entre l'utilisation d'une méthode de répartition vs un autre en raison de la taille de la comptabilité des structures, le temps que les coûts w/ allocation/désallocation de l'algorithme, etc.
  • Morgan-Graham minimum de temps d'exécution et de fragmentation de la mémoire sont les besoins les plus importants. D'autres, à ce stade, peut être mis au rebut.
  • Ne pas faire de cette question une réponse parce que c'est un cliché, mais: utilisez la valeur par défaut. Si (si) de la performance devient un problème, de profil. Seulement quand cela s'avère un goulot d'étranglement dans l'allocation de la mémoire serait un bricoleur avec l'allocation de la mémoire.
  • Une chose à garder à l'esprit est que, même si les jeux vidéo ont une interactivité en temps réel, cela ne signifie pas qu'ils ont les mêmes besoins que les applications en temps réel (par l'ensemble de l'industrie de la définition). Par exemple, dans un programme temps réel, il peut être acceptable pour permettre une hausse de la moyenne des temps d'exécution si une garantie peut être faite que la répartition complète en vertu d'un nombre maximal de cycles de processeur. Jeu vidéo optimisations ont tendance à faire soit en réduisant ou en évitant l'allocation des tout-ensemble, ou simplement en réduisant la moyenne de l'exécution, plutôt que d'essayer de donner un cycle de comptage de garantie.
  • La raison pour laquelle je mentionne cela, c'est que certaines personnes sont en mentionnant "temps réel" dans leurs réponses. Je n'ai pas vraiment voir "en temps réel" dans votre question...
  • Il fut un temps où la question posée à propos de la performance en temps réel et de la fragmentation.

InformationsquelleAutor baris.aydinoz | 2011-02-07
  1. 15

    Tout dépend de l'application. Serveur d'applications qui peuvent effacer toute la mémoire relatif à une demande particulière à certains moments vous avez un autre accès à la mémoire motif que les jeux vidéo, par exemple.

    Si il en existe un algorithme d'allocation de mémoire qui a toujours été le meilleur pour les performances et la fragmentation, ne serait-ils pas la mise en œuvre de malloc et new toujours choisir cet algorithme?

    De nos jours, il est généralement préférable de supposer que les personnes qui ont écrit de votre système d'exploitation et des bibliothèques d'exécution n'étaient pas en état de mort cérébrale; et, sauf si vous avez de drôles d'accès à la mémoire motif de ne pas essayer de les battre.

    Au lieu de cela, essayez de réduire le nombre d'allocations (ou de réaffectations) que vous faites. Par exemple, j'utilise souvent un std::vector, mais si je sais à l'avance le nombre d'éléments qu'il aura, je peux réserve que tous d'un coup. C'est beaucoup plus efficace que de le laisser grandir "naturellement" par le biais de plusieurs appels à push_back().

    Beaucoup de gens venant de langues où new signifie simplement "gimme un objet" va allouer des choses pour aucune bonne raison. Si vous n'avez pas à le mettre sur le tas, n'appelez pas new.

    Comme pour la fragmentation: il dépend encore. Malheureusement je ne trouve pas le lien, mais je me souviens d'un post de blog de quelqu'un de chez Microsoft qui a travaillé sur un serveur C++ de l'application, qui a souffert de la fragmentation de la mémoire. L'équipe a résolu le problème en allouant de la mémoire de deux régions. Mémoire pour l'ensemble des demandes viennent de la région A jusqu'à ce qu'il était plein (demandes de libérer de la mémoire comme d'habitude). Lorsque la région était pleine, toute la mémoire serait allouée à partir de la région B. Par la zone B était plein, la région était complètement vide à nouveau. Cela a résolu leur problème de la fragmentation.

    Veut-il résoudre le vôtre? Je n'ai aucune idée. Vous travaillez sur un projet qui propose plusieurs requêtes indépendantes? Vous travaillez sur un jeu?

    Comme pour déterminisme: il dépend encore. Quel est votre délai? Ce qui se passe quand vous ratez la date limite (les astronautes perdus dans l'espace? la musique en cours de lecture commence à sonner comme des ordures?)? Il y a temps réel allocateurs, mais rappelez-vous: "en temps réel" signifie "fait une promesse au sujet de respecter un délai," pas nécessairement "rapide".

    Je n'ai tout simplement venir à travers un post décrivant les différentes choses que Facebook a fait à la fois d'accélérer et de réduire la fragmentation dans jemalloc. Vous pouvez trouver cette discussion intéressante.

    • mais ce temps-déterminisme et de la fragmentation, de l'utilisation de la mémoire heap finira par conduire à la fragmentation et la perte de déterminisme. BTW, merci pour le lien.
    • La Fragmentation, à l'instar de tous les autres paramètres, dépend de l'application. Par exemple, il est trivial de montrer que, si toutes les subventions sont de la même taille (par exemple 16 octets), alors pas de fragmentation peut se produire (la mi-sane allocateur).
    InformationsquelleAutor Max Lybbert
  2. 5

    Barış:

    Votre question est très générale, mais voici ma réponse/orientation:

    Je ne sais pas pour les moteurs de jeu, mais pour l'embarqué et le temps réel, les applications, Les objectifs généraux d'un algorithme d'allocation sont les suivantes:

    1 - Borné temps d'exécution: Vous devez savoir à l'avance dans le pire des cas, l'allocation de temps de sorte que vous pouvez planifier votre temps réel les tâches en conséquence.

    2 - une rapidité d'exécution: Ainsi, plus le mieux, évidemment

    3 - Toujours attribuer: en Particulier, temps réel, la sécurité des applications critiques, toutes les demandes doivent être satisfaites. Si vous demande un peu d'espace mémoire et d'obtenir un pointeur null: de la difficulté à!

    4 - Réduire la fragmentation: Bien que cela dépend de l'algorithme utilisé, en général, moins fragmentée allocations de fournir de meilleures performances, en raison d'un certain nombre de raisons, y compris la mise en cache des effets.

    Dans la plupart des systèmes critiques, vous n'êtes pas autorisé à allouer dynamiquement de la mémoire pour commencer. L'analyse de vos besoins et de déterminer la valeur maximale de votre utilisation de la mémoire et de consacrer une grande partie de la mémoire dès que votre application démarre. Si vous ne pouvez pas, alors l'application n'a même pas commencer, si elle démarre, pas de nouveaux blocs de mémoire sont alloués au cours de l'exécution.

    Si la vitesse est un sujet de préoccupation, je vous recommande une approche similaire. Vous pouvez mettre en place un pool de mémoire qui gère votre mémoire. La piscine pourrait initialiser un nombre "suffisant" bloc de mémoire dans le début de votre demande et pour répondre à vos demandes de mémoire à partir de ce bloc. Si vous avez besoin de plus de mémoire, la piscine peut faire un autre -sans doute grand - répartition (en prévision de plus de demandes de mémoire), et de votre demande, vous pouvez commencer à utiliser ce nouveau mémoire allouée. Il existe différents de la mémoire mise en commun des régimes qui l'entourent, et la gestion de ces piscines est un tout autre sujet.

    Que pour quelques exemples: VxWorks RTOS utilisé pour employer un premier ajustement algorithme d'allocation d'où l'algorithme analysé une liste liée de trouver un assez grand bloc libre. Dans VxWorks 6, elles utilisent un meilleur ajustement de l'algorithme, où l'espace libre est gardé dans un arbre et les allocations de parcourir l'arbre pour un assez grand bloc libre. Il y a un livre blanc intitulé Memory Allocation in VxWorks 6.0, par Zoltan Laszlo, que vous pouvez trouver par une recherche sur Google, qui a plus de détails.

    Pour en revenir à votre question sur la vitesse/la fragmentation: Cela dépend vraiment de votre application. Les choses à considérer sont:

    • Vous allez faire beaucoup de très petites allocations, ou relativement plus grands?

    • Seront les allocations de venir en rafales, ou réparti de manière égale tout au long de l'application?

    • Quelle est la durée de vie de la les allocations?

    Si vous vous posez cette question parce que vous allez mettre en place votre propre allocateur, vous devriez probablement le concevoir de telle manière que vous pouvez changer les sous-jacents de l'allocation/désallocation de l'algorithme, car si la vitesse/la fragmentation est vraiment critique dans votre application, vous allez avoir à expérimenter avec différents allocateurs. Si je devais recommander quelque chose sans savoir de vos besoins, j'aimerais commencer avec TLSF, car il a de bonnes caractéristiques globales.

    InformationsquelleAutor SomethingBetter
  3. 3

    Que d'autres déjà écrit, il n'est pas "optimale" algorithme pour chaque application. Il a déjà été prouvé que, pour tout algorithme, vous pouvez trouver une séquence d'affectation qui sera la cause d'une fragmentation.

    Ci-dessous j'écris quelques trucs à mon jeu de l'expérience de développement:

    Éviter les allocations si vous pouvez

    Une des pratiques courantes dans le développement d'un jeu, le terrain a été (et, dans une certaine mesure est toujours) pour résoudre l'allocation dynamique de la mémoire des problèmes de performances en évitant les allocations de mémoire comme une peste. Il est très souvent possible d'utiliser la pile en fonction de la mémoire à la place - même pour les tableaux dynamiques bien souvent, vous pouvez venir avec un devis qui permettra de couvrir 99 % des cas pour vous et vous avez besoin d'allouer seulement lorsque vous êtes au-dessus de cette limite. Une autre approche communément utilisée est "preallocation": une estimation de la quantité de mémoire dont vous aurez besoin dans une fonction ou un objet, créer une sorte de petit et simpliste "local tas de" vous allouer à l'avant et effectuer les affectations individuelles à partir de ce tas seulement.

    Allocateur de mémoire bibliothèques

    Une autre option est d'utiliser une partie de la mémoire de l'allocation des bibliothèques - ils sont généralement créés par des experts dans le domaine pour s'adapter à des besoins particuliers, et si vous avez semblable requiremens, ils peuvent répondre à vos exigences.

    Multithreading

    Il y a un cas particulier, dans lequel vous trouverez le "par défaut" OS/CRT allocateur effectue mal, et c'est le multithreading. Si vous utilisez Windows, en conscience à la fois l'OS et de la CRT allocateurs fourni par Microsoft (y compris l', par ailleurs excellent, Bas de Segment de Fragmentation) sont actuellement de blocage. Si vous souhaitez effectuer des threading, vous avez besoin pour réduire l'allocation autant que possible, ou d'utiliser certaines des solutions de rechange. Voir Peut multithreading accélérer l'allocation de la mémoire?

    InformationsquelleAutor Suma
  4. 3

    La meilleure pratique est d'utiliser tout ce que vous pouvez utiliser pour rendre la chose fait dans le temps (dans votre cas de défaut de l'allocateur). Si le tout est très complexe à écrire des tests et des échantillons qui seront émuler les pièces de l'ensemble de la chose. Ensuite, exécutez les tests de performances et de repères pour trouver les goulots des bouteilles (probablement ils vont rien à voir avec l'allocation de la mémoire :).
    À partir de ce point, vous allez voir exactement ce que les ralentissements de votre code et pourquoi. Uniquement basé sur de telles précis de connaissances, vous pouvez toujours optimiser quelque chose et choisir un algorithme sur un autre. Sans tests, c'est juste une perte de temps puisque vous ne pouvez pas même de mesurer combien votre optimisation de l'accélération de votre application (en fait, une telle "prématuré" optimisations peuvent vraiment ralentissement c').

    L'allocation de mémoire est une chose complexe, et il dépend de nombreux facteurs. Par exemple, une telle allocation est simple et super rapide mais peut être utilisé seulement dans un nombre limité de situations:

    char pool[MAX_MEMORY_REQUIRED_TO_RENDER_FRAME];
char *poolHead = pool;

void *alloc(size_t sz) { char *p = poolHead; poolHead += sz; return p; }
void free() { poolHead  = pool; }

    N'est donc pas "le meilleur algorithme jamais".

    • merci pour la réponse, mais cette question n'est pas liée avec le profilage, il s'agit de la meilleure mémoire de l'algorithme d'allocation pour des besoins
    • Ok, alors envisager de ma piscine est basée sur la mise en œuvre la plus rapide possible, car il s'adapte à vos exigences 🙂
    • la question peut ne pas l'intention d'être sur le profilage. Comme vous le doit en déduire les réponses jusqu'à présent, le profilage est essentiel, car il est pas de "one size fits all" meilleure solution. C'est comme l'achat de vêtements: si vous ne mesurez pas, vous êtes lié pour finir avec quelque chose qui ne vous convient pas.
    • Un exemple concret pour les jeux, c'est que vous voulez une répartition différente de la stratégie pour le modèle/données d'image que pour des particules individuelles dans un système de particules. Dans un système de particules, tous vos objets sont de la même taille, et de minuscules. Alors que le modèle/données d'image est souvent variable de taille moyenne (peut-être pas les textures, mais ça dépend du jeu), et toujours beaucoup plus grande que les particules individuelles. Modèle/données d'image a tendance à être chargée qu'une seule fois, et conservés pendant un certain temps, alors que les particules apparaissent et disparaissent sans cesse. Vous pouvez avoir différentes sous-allocateur algorithmes pour chaque.
    InformationsquelleAutor wonder.mice
  5. 0

    Une contrainte qui vaut la peine de mentionner, qui n'a pas encore été mentionnés, est multi-threading: Standard allocateurs doit être mis en œuvre à l'appui de plusieurs threads, toutes allocation/désallocation simultanément, et de passer des objets à partir d'un thread à l'autre afin qu'il soit libéré par un thread différent.

    Comme vous l'avez peut-être deviné à partir de cette description, il est une tâche délicate à mettre en œuvre un allocateur qui gère l'ensemble de ce bien. Et il ne fait performance de coût car il est impossible de satisfaire à toutes ces contraintes sans communication inter-thread (= atomique variables et serrures) qui est assez coûteux.

    En tant que tel, si vous pouvez éviter la simultanéité dans vos allocations, vous avez une bonne chance de mettre en œuvre votre propre allocateur de manière significative surpasse la norme allocateurs: une fois, j'ai fait moi-même, et il m'a sauvé environ 250 cycles de PROCESSEUR par une répartition assez simple allocateur est basé sur un numéro de fixe de la taille des pools de mémoire pour les petits objets, l'empilement des objets libres avec un intrusive liste liée.

    Bien sûr, éviter la simultanéité est probablement pas pour vous, mais si vous ne l'utilisez pas, de toute façon, l'exploitation de ce fait peut-être quelque chose vaut la peine d'y penser.

    InformationsquelleAutor cmaster