Lohnt es sich, Partikelpools in verwalteten Sprachen zu verwenden?

10

Ich wollte einen Objektpool für mein Partikelsystem in Java implementieren, dann fand ich diesen auf Wikipedia. Um es anders auszudrücken: Objektpools sollten in verwalteten Sprachen wie Java und C # nicht verwendet werden, da Zuweisungen im Vergleich zu Hunderten in nicht verwalteten Sprachen wie C ++ nur zehn Operationen erfordern.

Aber wie wir alle wissen, kann jede Anweisung die Spielleistung beeinträchtigen. Beispiel: Ein Pool von Clients in einem MMO: Die Clients betreten und verlassen den Pool nicht zu schnell. Partikel können sich jedoch innerhalb einer Sekunde zehnmal erneuern.

Die Frage ist: Lohnt es sich, einen Objektpool für Partikel (insbesondere solche, die sterben und schnell neu erstellt werden) in einer verwalteten Sprache zu verwenden?

Gustavo Maciel
quelle

Antworten:

14

Ja ist es.

Die Zuteilungszeit ist nicht der einzige Faktor. Die Zuweisung kann Nebenwirkungen haben, z. B. das Auslösen eines Speicherbereinigungsdurchlaufs, der sich nicht nur negativ auf die Leistung auswirkt, sondern auch die Leistung unvorhersehbar beeinflusst. Die Einzelheiten hierzu hängen von Ihrer Sprache und der Wahl der Plattform ab.

Durch das Pooling wird im Allgemeinen auch die Referenzlokalität für die Objekte im Pool verbessert, indem beispielsweise alle Objekte in zusammenhängenden Arrays gehalten werden. Dies kann die Leistung verbessern, während der Inhalt des Pools (oder zumindest der Live-Teil davon) iteriert wird, da sich das nächste Objekt in der Iteration tendenziell bereits im Datencache befindet.

Die übliche Weisheit, zu versuchen, jegliche Zuordnung in Ihren innersten Spielschleifen zu vermeiden, gilt auch in verwalteten Sprachen (insbesondere auf dem 360, wenn Sie XNA verwenden). Die Gründe dafür unterscheiden sich nur geringfügig.


quelle
+1 Sie haben jedoch nicht angesprochen, ob es sich bei der Verwendung von Strukturen lohnt: Im Grunde ist dies nicht der Fall (durch das Zusammenführen von Werttypen wird nichts erreicht). Stattdessen sollten Sie ein einzelnes (oder möglicherweise eine Reihe von) Array haben, um sie zu verwalten.
Jonathan Dickinson
2
Ich habe die Struktur nicht angesprochen, da das OP die Verwendung von Java erwähnt hat, und ich bin nicht so vertraut damit, wie Werttypen / Strukturen in dieser Sprache funktionieren.
In Java gibt es keine Strukturen, nur Klassen (immer auf dem Heap).
Brendan Long
1

Für Java ist es nicht so hilfreich, Objekte * zu bündeln, da der erste GC-Zyklus für noch vorhandene Objekte sie im Speicher neu mischt, sie aus dem "Eden" -Raum verschiebt und dabei möglicherweise die räumliche Lokalität verliert.

  • In jeder Sprache ist es immer nützlich, komplexe Ressourcen zu bündeln, deren Zerstörung und Erstellung ähnlicher Threads sehr teuer ist. Diese können es wert sein, zusammengefasst zu werden, da die Kosten für das Erstellen und Zerstören fast nichts mit dem Speicher zu tun haben, der dem Objekthandle für die Ressource zugeordnet ist. Partikel passen jedoch nicht in diese Kategorie.

Java bietet eine schnelle Burst-Zuweisung mithilfe eines sequentiellen Allokators, wenn Sie Objekte schnell dem Eden-Raum zuordnen. Diese Strategie der sequentiellen Zuweisung ist superschnell und schneller als mallocin C, da nur der bereits direkt zugewiesene Speicher zusammengefasst wird. Sie hat jedoch den Nachteil, dass Sie keine einzelnen Speicherblöcke freigeben können. Es ist auch ein nützlicher Trick in C, wenn Sie Dinge nur superschnell zuweisen möchten, beispielsweise für eine Datenstruktur, in der Sie nichts entfernen müssen, einfach alles hinzufügen und dann verwenden und das Ganze später wegwerfen müssen.

Aufgrund dieses Nachteils, dass einzelne Objekte nicht freigegeben werden können, kopiert der Java GC nach einem ersten Zyklus den gesamten vom Eden-Speicherplatz zugewiesenen Speicher mithilfe eines langsameren, allgemeineren Speicherzuordners, der Speicher zulässt, in neue Speicherbereiche in einzelnen Stücken in einem anderen Thread befreit werden. Dann kann es den im Eden-Raum als Ganzes zugewiesenen Speicher wegwerfen, ohne sich um einzelne Objekte zu kümmern, die jetzt kopiert wurden und an anderer Stelle im Speicher leben. Nach diesem ersten GC-Zyklus können Ihre Objekte im Speicher fragmentiert werden.

Da die Objekte nach diesem ersten GC-Zyklus fragmentiert werden können, gehen die Vorteile des Objektpoolings, wenn es hauptsächlich um die Verbesserung der Speicherzugriffsmuster (Referenzlokalität) und die Reduzierung des Zuordnungs- / Freigabe-Overheads geht, weitgehend verloren dass Sie in der Regel eine bessere Referenzlokalität erhalten, indem Sie ständig neue Partikel zuweisen und diese verwenden, während sie noch frisch im Eden-Raum sind und bevor sie "alt" und möglicherweise im Speicher verstreut werden. Es kann jedoch äußerst hilfreich sein (z. B. eine Leistung zu erzielen, die mit C in Java konkurriert), zu vermeiden, Objekte für Ihre Partikel zu verwenden und einfache alte primitive Daten zu bündeln. Für ein einfaches Beispiel anstelle von:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Mach so etwas wie:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Um den Speicher für vorhandene Partikel wiederzuverwenden, können Sie Folgendes tun:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Wenn das nthPartikel nun stirbt, um es wiederverwenden zu können, schieben Sie es wie folgt auf die freie Liste:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

Überprüfen Sie beim Hinzufügen eines neuen Partikels, ob Sie einen Index aus der freien Liste hinzufügen können:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

Es ist nicht der angenehmste Code, mit dem Sie arbeiten können, aber damit sollten Sie in der Lage sein, einige sehr schnelle Partikelsimulationen zu erhalten, wobei die sequentielle Partikelverarbeitung immer sehr cachefreundlich ist, da alle Partikeldaten immer zusammenhängend gespeichert werden. Diese Art von SoA-Repräsentant reduziert auch die Speichernutzung, da wir uns nicht um das Auffüllen, die Objektmetadaten für Reflexion / dynamischen Versand, kümmern müssen und heiße Felder von kalten Feldern trennen (zum Beispiel beschäftigen wir uns nicht unbedingt mit Daten Felder wie die Farbe eines Teilchens während des Physikdurchlaufs, daher wäre es verschwenderisch, sie in eine Cache-Zeile zu laden, nur um sie nicht zu verwenden und zu entfernen.

Um die Arbeit mit dem Code zu vereinfachen, lohnt es sich möglicherweise, eigene grundlegende Container mit veränderbarer Größe zu schreiben, in denen Arrays von Floats, Arrays von Ganzzahlen und Arrays von Booleschen Werten gespeichert sind. Auch hier können Sie keine Generika verwenden und ArrayListhier (zumindest seit meiner letzten Überprüfung), da dies GC-verwaltete Objekte erfordert, keine zusammenhängenden primitiven Daten. Wir möchten zusammenhängende Arrays verwenden int, z. B. nicht GC-verwaltete Arrays, Integerdie nach dem Verlassen des Eden-Raums nicht unbedingt zusammenhängend sind.

Bei Arrays von primitiven Typen, sind sie immer zusammenhängend sein garantiert, und so können Sie die äußerst wünschenswert Referenzlokalität erhalten (für die sequentiellen Partikel Verarbeitung macht es einen großen Unterschied) und all die Vorteile , die Objektverwaltung schaffen soll. Bei einem Array von Objekten ist es stattdessen etwas analog zu einem Array von Zeigern, die zunächst auf zusammenhängende Weise auf die Objekte zeigen, vorausgesetzt, Sie haben sie alle gleichzeitig im Eden-Raum zugewiesen, können aber nach einem GC-Zyklus überall auf das Objekt zeigen in Erinnerung behalten.


quelle
1
Dies ist eine schöne Zusammenfassung zu diesem Thema, und nach 5 Jahren Java-Codierung kann ich sie deutlich sehen. Java GC ist sicherlich nicht dumm, und es wurde auch nicht für die Spielprogrammierung entwickelt (da es sich nicht wirklich um Datenlokalität und andere Dinge kümmert), also spielen wir besser, wie es uns gefällt: P
Gustavo Maciel