Dynamische Speicherzuordnung und Speicherverwaltung

In einem durchschnittlichen Spiel gibt es Hunderte oder vielleicht Tausende von Objekten in der Szene. Ist es völlig korrekt, Speicher für alle Objekte, einschließlich Schusswaffen (Aufzählungszeichen), dynamisch über die Standardeinstellung new () zuzuweisen ?

Soll ich einen Speicherpool für die dynamische Zuweisung erstellen oder muss ich mich nicht darum kümmern? Was ist, wenn die Zielplattform mobile Geräte sind?

Benötigen Sie in einem Handyspiel einen Speichermanager ? Vielen Dank.

Verwendete Sprache: C ++; Wird derzeit unter Windows entwickelt, soll aber später portiert werden.

In einem durchschnittlichen Spiel gibt es Hunderte oder vielleicht Tausende von Objekten in der Szene. Ist es völlig korrekt, Speicher für alle Objekte, einschließlich Schusswaffen (Kugeln), dynamisch über die Standardeinstellung new () zuzuweisen?

Das hängt wirklich davon ab, was Sie mit "richtig" meinen. Wenn Sie den Begriff ganz wörtlich nehmen (und jedes Konzept der Korrektheit des implizierten Designs ignorieren), dann ist dies durchaus akzeptabel. Ihr Programm wird gut kompiliert und ausgeführt.

Es kann eine suboptimale Leistung erbringen, aber es kann auch eine gute Leistung erbringen, um ein versandfähiges, unterhaltsames Spiel zu sein.

Soll ich einen Speicherpool für die dynamische Zuweisung erstellen oder muss ich mich nicht darum kümmern? Was ist, wenn die Zielplattform mobile Geräte sind?

Profil und sehen. In C ++ ist die dynamische Zuweisung auf dem Heap normalerweise eine "langsame" Operation (dh, der Heap wird nach einem Block geeigneter Größe durchsucht). In C # ist dies normalerweise eine extrem schnelle Operation, da es sich nur um ein Inkrement handelt. Unterschiedliche Sprachimplementierungen weisen unterschiedliche Leistungsmerkmale in Bezug auf Speicherzuweisung, Fragmentierung bei Freigabe usw. auf.

Das Implementieren eines Memory Pooling-Systems kann mit Sicherheit zu Leistungssteigerungen führen. Da mobile Systeme im Vergleich zu Desktop-Systemen in der Regel weniger leistungsfähig sind, können Sie auf einer bestimmten mobilen Plattform möglicherweise mehr Vorteile erzielen als auf einem Desktop. Aber auch hier müssten Sie sich profilieren und sehen, ob Ihr Spiel derzeit langsam ist, aber die Speicherzuweisung / -freigabe auf dem Profiler nicht als Hotspot angezeigt wird. Sie müssen eine Infrastruktur implementieren, um die Speicherzuweisung und den Zugriff zu optimieren. Sie bekommen nicht viel für Ihr Geld.

Benötigen Sie in einem Handyspiel einen Speichermanager? Vielen Dank.

Nochmals profilieren und sehen. Läuft dein Spiel jetzt gut? Dann brauchen Sie sich keine Sorgen zu machen.

Abgesehen von all diesen Vorsichtsmaßnahmen ist die Verwendung der dynamischen Zuweisung für alles nicht unbedingt erforderlich, und es kann daher vorteilhaft sein, sie zu vermeiden - sowohl wegen der potenziellen Leistungssteigerungen als auch wegen der Zuweisung von Speicher, den Sie nachverfolgen und schließlich freigeben müssen bedeutet, dass Sie es nachverfolgen und schließlich freigeben müssen, was möglicherweise Ihren Code kompliziert.

Insbesondere in Ihrem ursprünglichen Beispiel haben Sie "Aufzählungszeichen" genannt, die in der Regel häufig erstellt und zerstört werden, da in vielen Spielen viele Aufzählungszeichen verwendet werden und die Aufzählungszeichen sich schnell bewegen und so schnell (und häufig) das Ende ihrer Lebensdauer erreichen heftig!). Die Implementierung eines Pool-Allokators für diese und ähnliche Objekte (z. B. Partikel in einem Partikelsystem) kann daher in der Regel zu Effizienzgewinnen führen und ist wahrscheinlich der erste Ort, an dem die Verwendung der Pool-Allokation in Betracht gezogen wird.

Es ist unklar, ob Sie eine Speicherpoolimplementierung als von einem "Speichermanager" verschieden betrachten - ein Speicherpool ist ein relativ genau definiertes Konzept, daher kann ich mit einiger Gewissheit sagen, dass sie ein Vorteil sein können, wenn Sie sie implementieren . Ein "Speichermanager" ist in Bezug auf seine Verantwortung etwas vager, daher muss ich sagen, dass es von Ihrer Meinung nach abhängt, ob ein "Speichermanager" erforderlich ist oder nicht.

Wenn Sie beispielsweise einen Speichermanager als eine Sache betrachten, die nur Aufrufe von new / delete / free / malloc / whatever abfängt und Diagnosen dazu bereitstellt, wie viel Speicher Sie zuweisen, was Sie auslaufen usw. - dann kann dies nützlich sein Tool für das Spiel, während es in der Entwicklung ist, um Ihnen zu helfen, Lecks zu beheben und Ihre optimalen Speicherpoolgrößen zu optimieren, und so weiter.

Ich habe nicht viel zu Joshs hervorragender Antwort hinzuzufügen, aber ich werde dies kommentieren:

Soll ich einen Speicherpool für die dynamische Zuweisung erstellen oder muss ich mich nicht darum kümmern?

Zwischen den Speicherpools und dem Aufruf newjeder Zuweisung besteht ein Mittelweg . Sie können beispielsweise eine festgelegte Anzahl von Objekten in einem Array zuweisen und diese anschließend mit einem Flag versehen, um sie später zu "zerstören". Wenn Sie mehr zuweisen müssen, können Sie diejenigen überschreiben, für die das Flag "Destroyed" gesetzt ist. Diese Art von Dingen ist nur geringfügig komplexer zu verwenden als Neu / Löschen (da Sie zu diesem Zweck 2 neue Funktionen haben würden), ist jedoch einfach zu schreiben und kann Ihnen große Vorteile bringen.

Ist es völlig korrekt, Speicher für alle Objekte, einschließlich Schusswaffen (Aufzählungszeichen), dynamisch über die Standardeinstellung new () zuzuweisen?

Nein natürlich nicht. Keine Speicherzuordnung ist für alle Objekte korrekt . Der Operator new () ist für die dynamische Zuordnung vorgesehen. Dies ist nur dann sinnvoll, wenn die Zuordnung dynamisch sein muss, entweder weil die Lebensdauer des Objekts dynamisch ist oder weil der Typ des Objekts dynamisch ist. Wenn Typ und Lebensdauer des Objekts statisch bekannt sind, sollten Sie es statisch zuordnen.

Je mehr Informationen Sie über Ihre Zuordnungsmuster haben, desto schneller können diese Zuordnungen über spezialisierte Zuordnungen wie Objektpools vorgenommen werden. Dies sind jedoch Optimierungen, die Sie nur vornehmen sollten, wenn bekannt ist, dass sie erforderlich sind.

Es ist eine Art Echo auf Kylotans Vorschlag, aber ich würde empfehlen, dies auf der Datenstrukturebene zu lösen, wenn möglich, nicht auf der unteren Allokatorebene, wenn Sie helfen können.

Hier ein einfaches Beispiel, wie Sie vermeiden können, Foosein Array mit Löchern und miteinander verknüpften Elementen wiederholt zuzuweisen und freizugeben (dies auf "Container" -Ebene anstelle einer "Allokator" -Ebene zu lösen):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Etwas in diesem Sinne: eine einfach verknüpfte Indexliste mit einer freien Liste. Mit den Index-Links können Sie entfernte Elemente überspringen, Elemente in konstanter Zeit entfernen und auch freie Elemente mit Einfügung in konstanter Zeit zurückfordern / wiederverwenden / überschreiben. Um die Struktur zu durchlaufen, gehen Sie wie folgt vor:

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

Und Sie können die obige Art der "verknüpften Anordnung von Löchern" -Datenstruktur mit Vorlagen verallgemeinern, neue und manuelle Dtor-Aufrufe platzieren, um die Notwendigkeit der Kopierzuweisung zu vermeiden, Destruktoren aufzurufen, wenn Elemente entfernt werden, einen Forward-Iterator bereitzustellen usw. I Ich habe mich dafür entschieden, das Beispiel sehr C-artig zu halten, um das Konzept klarer darzustellen und auch, weil ich sehr faul bin.

Das heißt, diese Struktur neigt dazu, sich in der räumlichen Lokalität zu verschlechtern, nachdem Sie Dinge zu / von der Mitte entfernt und viel eingefügt haben. Zu diesem Zeitpunkt können Sie über die nextLinks entlang des Vektors vor- und zurückgehen und Daten, die zuvor aus einer Cache-Zeile innerhalb derselben sequenziellen Überquerung entfernt wurden, erneut laden (dies ist bei jeder Datenstruktur oder jedem Allokator unvermeidlich, der das Entfernen in konstanter Zeit ermöglicht, ohne Elemente beim Zurückfordern zu mischen Leerzeichen von der Mitte mit Einfügung in konstanter Zeit und ohne die Verwendung eines parallelen Bitsets oder eines removedFlags). Um die Cache-Freundlichkeit wiederherzustellen, können Sie eine Kopier- und Auslagerungsmethode wie folgt implementieren:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Jetzt ist die neue Version wieder Cache-freundlich zum Durchlaufen. Eine andere Methode besteht darin, eine separate Liste von Indizes in der Struktur zu speichern und diese regelmäßig zu sortieren. Eine andere Möglichkeit ist die Verwendung eines Bitsets, um anzugeben, welche Indizes verwendet werden. Dadurch durchlaufen Sie den Bit-Satz immer in sequentieller Reihenfolge (um dies effizient zu tun, prüfen Sie jeweils 64-Bit, z. B. mit FFS / FFZ). Das Bit-Set ist das effizienteste und nicht störendste, da nur ein paralleles Bit pro Element erforderlich ist, um anzugeben, welche verwendet und welche entfernt werden, anstatt 32-Bit- nextIndizes zu erfordern. Das Schreiben ist jedoch am zeitaufwändigsten (dies wird nicht der Fall sein) Seien Sie schnell beim Durchlaufen, wenn Sie jeweils ein Bit überprüfen. Sie müssen FFS / FFZ verwenden, um ein gesetztes oder nicht gesetztes Bit sofort unter 32+ Bits gleichzeitig zu finden, um die Bereiche der belegten Indizes schnell zu bestimmen.

Diese verknüpfte Lösung ist im Allgemeinen am einfachsten zu implementieren und nicht aufdringlich (Änderungen Foozum Speichern eines removedFlags sind nicht erforderlich ). Dies ist hilfreich, wenn Sie diesen Container für die Arbeit mit einem beliebigen Datentyp verallgemeinern möchten, wenn Sie sich nicht um diese 32-Bit-Version kümmern Gemeinkosten pro Element.

Soll ich einen Speicherpool für die dynamische Zuweisung erstellen oder muss ich mich nicht darum kümmern? Was ist, wenn die Zielplattform mobile Geräte sind?

Need ist ein starkes Wort und ich arbeite voreingenommen in sehr leistungskritischen Bereichen wie Raytracing, Bildverarbeitung, Partikelsimulationen und Mesh-Verarbeitung, aber es ist relativ teuer, jugendliche Objekte zuzuweisen und freizugeben, die für eine sehr leichte Verarbeitung wie Aufzählungszeichen verwendet werden und Partikel einzeln gegen einen Allzweckspeicherzuordner mit variabler Größe. Da Sie in der Lage sein sollten, die oben genannte Datenstruktur in ein oder zwei Tagen zu verallgemeinern, um alles zu speichern, was Sie möchten, wäre es meiner Meinung nach ein lohnender Austausch, solche Kosten für die Heap-Zuweisung / -Deallocation direkt von der Bezahlung für jede einzelne Kleinigkeit zu streichen. Zusätzlich zur Reduzierung der Zuordnungs- / Freigabekosten erhalten Sie eine bessere Referenzlokalität bei der Überquerung der Ergebnisse (weniger Cachefehler und Seitenfehler).

Was Josh über GC anbelangt, habe ich die GC-Implementierung von C # nicht so genau untersucht wie die von Java, aber GC-Zuweiser haben häufig eine anfängliche ZuordnungDas ist sehr schnell, da hierfür ein sequentieller Allokator verwendet wird, der keinen Speicher in der Mitte freigibt (fast wie bei einem Stapel können Sie keine Objekte in der Mitte löschen). Dann zahlt es sich für die teuren Kosten aus, einzelne Objekte in einem separaten Thread tatsächlich entfernen zu können, indem der Speicher kopiert und der zuvor zugewiesene Speicher insgesamt gelöscht wird (z. B. den gesamten Stapel auf einmal zerstören, während die Daten in eine Art verknüpfte Struktur kopiert werden). Da dies jedoch in einem separaten Thread erfolgt, werden die Threads Ihrer Anwendung nicht unbedingt so stark blockiert. Dies birgt jedoch erhebliche versteckte Kosten für ein zusätzliches Indirektionsniveau und den allgemeinen Verlust des LOR nach einem anfänglichen GC-Zyklus. Es ist eine andere Strategie, um die Zuweisung zu beschleunigen - machen Sie es im aufrufenden Thread billiger und erledigen Sie dann die teure Arbeit in einem anderen. Dafür benötigen Sie zwei Indirektionsebenen, um auf Ihre Objekte zu verweisen, anstatt auf eine, da diese zwischen der ersten Zuweisung und einem ersten Zyklus im Speicher gemischt werden.

Eine andere Strategie in ähnlicher Weise, die in C ++ etwas einfacher anzuwenden ist, besteht darin, die Objekte in den Hauptthreads nicht freizugeben. Füge einfach weiter Daten hinzu und füge sie hinzu und füge sie am Ende einer Datenstruktur hinzu, die es nicht erlaubt, Dinge aus der Mitte zu entfernen. Markieren Sie jedoch die Dinge, die entfernt werden müssen. Dann könnte ein separater Thread die teure Arbeit erledigen, eine neue Datenstruktur ohne die entfernten Elemente zu erstellen und dann die neue atomar gegen die alte auszutauschen. Ein Großteil der Kosten für das Zuweisen und Freigeben von Elementen kann z Separater Thread, wenn Sie davon ausgehen können, dass die Anforderung zum Entfernen eines Elements nicht sofort erfüllt werden muss. Das macht das Freigeben nicht nur für Ihre Threads billiger, sondern auch die Zuweisung, da Sie eine viel einfachere und langwierigere Datenstruktur verwenden können, die niemals Fälle aus der Mitte entfernen muss. Es ist wie ein Container, der nur eine benötigtpush_backFunktion zum Einfügen, eine clearFunktion zum Entfernen aller Elemente und swapzum Austauschen von Inhalten mit einem neuen, kompakten Container, der entfernte Elemente ausschließt; Das ist alles, was das Mutieren angeht.