C++ - Organisation/Verwaltung von millionen Objekten

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.

C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 12.04.2017, 19:51

Hallo.

Mein Projekt verfügt über ein Hauptobjekt Welt. Diese Welt hat eine oder mehrere Karten. In den Karten gibt es Objekte. Objekte können weitere Objekte beinhalten, z.B. wenn das Objekt ein Behälter (Kiste, Beutel, Truhe, usw.) ist.
Die "Haupthierarchie" ist daher sehr einfach, wie vermutlich bei den meisten Programmen, die eine Welt/Spielwelt darstellen möchten: Welt -> Karte/Level -> Objekt -> Objekt -> usw..

Ein Objekt verfügt direkt nur über die Eigenschaften/Attribute, die zu 99% in allen Objekten vorkommen, wie z.B. Größe (XYZ) und Gewicht (gramm). Alle weiteren Informationen, Definitionen und Beschreibungen werden dem Objekt direkt zugeordnet, bzw. verfügt das Objekt über Möglichkeiten, diese Informationen zu speichern. Es gibt zwar Basisobjekte, die in erster Linie dazu dienen ein Objekt zu erzeugen, aber in der Regel halten die Objekte die meisten Informationen nochmal/redundant. Durch diese Redundanz kann ich z.B. zwei Objekte durch das gleiche Basisobjekt erstellen, aber danach individuell anpassen. Ich hatte anfangs versucht, diese Redundanz zu vermeiden, indem ich z.B. bestimmte Daten erst "verdopple" wenn ich sie anpassen möchte, aber das hat die ganze Sache extrem verkompliziert und war letzten Endes nicht schneller, verbrauchte nur weniger Speicher.

Die Objekte und dazugehörigen Daten/Informationen werden alle durch einen Speichermanager erzeugt und verwaltet. Jede Klasse hat einen Verweis/Zeiger/Weakpointer auf die Welt, wo der Speichermanager "liegt". Fällt der Referenzzähler auf 0, wird eine Delete-Funktion aufgerufen, diese ruft dann die entsprechende Freigabefunktion/Free von der Welt auf. Die Freigabefunktion führt den Destruktor von der freizugebenden Instanz aus und erledigt die weiteren Arbeiten, um den Speicher freizugeben.

Diese Vorgehensweise macht die ganze Angelegenheit extrem schnell, ich teste das immer mit den Daten der Spieleklassiker Ultima 7 und Serpent Isle. (https://www.gog.com/game/ultima_7_complete)
Für Ultima 7 werden beim Laden der Spielwelt 3.361.485 Klassen/Instanzen erstellt und miteinander verknüpft. Bei Serpent Isle sind es 3.956.333 Klassen/Instanzen. In beiden Fällen ist die gesamte Welt in wenigen Sekunden geladen. Das Objekt-System ist noch in der Entwicklung und ich gehe davon aus, dass in der finalen Version über 5.000.000 Klassen/Instanzen erstellt werden.

Das verwendete System ist zwar extrem schnell, hat aber auch seine Nachteile, wie z.B. dass der Speichermanager und die Welt/Karte/Objekte nicht threadsafe sind. Ich muss, sobald ich Daten lesen/ändern/erstellen/freigeben möchte, die Welt sperren (CriticalSection).
Ich kann mir aber auch nicht vorstellen, dass es Programme mit vielen Daten gibt, die multithreaded sind, aber die Daten ohne einen zentralen Sperrmechanismus bearbeiten. Ich habe das zwar nicht getestet, aber ich gehe davon aus, dass wenn ich z.B. die Daten und Speichermanager threadsafe mache, die Performance hart in den Keller geht.

Habt ihr eine Idee wie ich das besser lösen könnte?
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 12.04.2017, 20:49

Goderion hat geschrieben:Ich kann mir aber auch nicht vorstellen, dass es Programme mit vielen Daten gibt, die multithreaded sind, aber die Daten ohne einen zentralen Sperrmechanismus bearbeiten. Ich habe das zwar nicht getestet, aber ich gehe davon aus, dass wenn ich z.B. die Daten und Speichermanager threadsafe mache, die Performance hart in den Keller geht.

Habt ihr eine Idee wie ich das besser lösen könnte?
Was willst du denn multithreaded machen? Rendering dürfte kein Problem sein, das manipuliert/löscht ja keine Objekte. Gameplay? Physik?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 12.04.2017, 21:30

Krishty hat geschrieben:Was willst du denn multithreaded machen? Rendering dürfte kein Problem sein, das manipuliert/löscht ja keine Objekte. Gameplay? Physik?

Im Mainthread werden die Daten beim Verarbeiten der GUI-Nachrichten genutzt.
1. Situation - Rendering: Die Welt wird gesperrt und es werden die nötigen Daten gesammelt und an ein Rendersystem übermittelt, dass die Daten in einer Kommandoliste so ablegt, dass nur noch Grafikinformationen vorhanden sind und keine Verweise mehr auf die Weltdaten erforderlich sind. Ein andere Thread nimmt dann diese Daten, verarbeitet diese weiter und gibt sie letzten Endes an Direct3D9 weiter.
2. Situation - Benutzereingaben: Der Benutzer verändert ständig die Weltdaten, entweder durch den Editor oder als Spieler.

Im Logikthread werden die Daten bezüglich Gameplay, Physik und KI verarbeitet, was wie bei den Benutzereingaben zu alle möglichen Änderungen führen kann.

Es gibt also mindestens 2 voneinander unabhängig laufende Threads, die die gleichen Daten lesen und manipulieren, was eine Zugriffskontrolle unabdingbar macht.
Ich könnte die Logik auch im gleichen Thread/Mainthread laufen lassen, aber ich erhoffe mir dadurch eine besser Performance, vor allem wenn die Logik viel berechnen muss (Pathfinding, etc.). Das ist ja auch der Grund und Nutzen von Multithreading.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon RustySpoon » 13.04.2017, 09:48

Das wird man so pauschal nicht beantworten können. Das hängt sehr stark davon ab, wie du deine Welt organsierst und was da wann simuliert/aktualisiert wird. In der Regel wirst du ja nicht bei jedem Update über alle Objekte drüber rennen und die volle Latte an Physik/AI/etc. berechnen, sondern das irgendwie in Abhängigkeit von Sichtbarkeit/Entfernung zum Spieler/etc. vereinfachen.

Angenommen, du weißt welche Objekte zwingend aktualisiert werden müssen, dann wäre in der Umsetzung das eine Extrem immer die komplette Welt zu sperren, das andere immer jedes Objekt einzeln. Ersteres führt dazu, dass Multithreading praktisch nutzlos ist, letzteres induziert einen riesigen Speicher- und Verwaltungsoverhead. Ergo wirst du irgendein Mittelding fahren wollen, wo immer hinreichend große Objektgruppen auf einmal gesperrt werden. Aber bei der Größe und Zusammensetzung dieser Objektgruppen wirst du um viel experimentieren und messen nicht drumherum kommen.
Benutzeravatar
RustySpoon
Establishment
 
Beiträge: 279
Registriert: 17.03.2009, 14:59
Wohnort: Dresden

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Schrompf » 13.04.2017, 10:03

Zusätzlich zum "Kann man pauschal so nicht sagen" will ich hinzufügen: Du musst kleiner granularisieren. Das Rendering z.B. ist eine rein lesende Operation auf der Spielwelt. Du könntest also z.B. stressfrei 8 oder wasweißichwieviele Jobs starten, die gleichzeitig über disjunkte Teile der Welt iterieren und die DrawCalls einsammeln. Das Cullen kann man parallelisieren. Mit DX11/DX12/Vulkan/Mantle kann man selbst das Rendern parallelisieren. Daten-Parallele Aufgaben haben immer den Vorteil, dass sie viel besser mit der Hardware skalieren als themen-parallele Aufgaben.

Ansonsten: ja, new ist schnell. Ein paar Millionen Allokationen pro Sekunde sind machbar. Für mich damals überraschend war die Erkenntnis, dass das dazugehörige delete deutlich langsamer ist.

Evtl. wäre es für solche Jobs aber besser, zumindest während der initialen Einrichtung einen Custom Allokator einzusetzen, der linear aus einem großen Speicherblock schöpft. Das hat zusätzlich den Vorteil, dass alle Daten schön nah beieinander liegen und damit cache-freundlicher sind. Aber wenn Du viel auf virtuelle Funktionen setzt, ist Dir Cache-Freundlichkeit wahrscheinlich eh nicht so wichtig.

Und poste mal Screenshots, wenn's was zu zeigen gibt :-)
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3747
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 13.04.2017, 11:58

Ich wollte auch erst RustySpoons Extrem vorschlagen: Jedes Objekt einzeln locken und alle Threads drauf loslassen. 99,9 % der Zeit werden Rendering und KI nicht auf das selbe Objekt zugreifen, und da ist ein SpinLock (idealerweise nicht aufwändiger implementiert als atomic<char>) von der Zugriffszeit her so gut wie kostenlos. Ich sehe nur zwei Probleme:

1. Bei 5 mio Objekten macht das 5 MiB zusätzliche Cache-Belastung pro Frame, schlägt also schon auf den Magen.

2. Objekte können zyklische Abhängigkeiten haben (je nachdem, wie deine KI/Physik funktionieren) und du würdest dann zwangsläufig in das Problem rekursiver Locks laufen, und das ist hässlich. (Andererseits ist Re-entrancy in Spiellogik auch ohne Multi-Threading schön ein hässliches Problem.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Schrompf » 13.04.2017, 12:17

Naja, und bei Spielen würde man z.B. ne KI schreiben, indem man die nahesten x Feinde sucht und eine Bewegung nach deren Position ermittelt. Das wäre dann der Zugriff auf State von anderen Objekten, während das andere Objekt potentiell gerade selbst agiert. Battlefield hat (ab der 4, glaube ich) darum jeden internen State von InGame Entities gedoppelt und betreibt Double Buffering von Frame zu Frame. Entities zur Laufzeit zu erzeugen und zu löschen ist ein lösbares Problem - im einfachsten Fall speichert man einfach solche Aktionen und führt sie erst am Ende des Update Cyles aus, oder am Anfang des nächsten. Musste ich eh schon immer machen, auch ohne meine Spiellogik tatsächlich zu parallelisieren, aber ich habe die Gründe vergessen.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3747
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 13.04.2017, 12:29

Vielen Dank für die Antworten!

RustySpoon hat geschrieben:Das wird man so pauschal nicht beantworten können. Das hängt sehr stark davon ab, wie du deine Welt organsierst und was da wann simuliert/aktualisiert wird. In der Regel wirst du ja nicht bei jedem Update über alle Objekte drüber rennen und die volle Latte an Physik/AI/etc. berechnen, sondern das irgendwie in Abhängigkeit von Sichtbarkeit/Entfernung zum Spieler/etc. vereinfachen.

Bei Ultima 7 befinden sich z.B. 237.886 Objekte auf der Karte/Level, die alles jedes mal durchzugehen wäre wirklich Wahnsinn. Es gibt spezielle Strukturen/Klassen, mit der die Logik verwaltet wird. Für jede Aktion gibt es einen Prozess, der dann in jedem Logik-Frame bis zur Vollendung ausgeführt/fortgesetzt wird.

RustySpoon hat geschrieben:Angenommen, du weißt welche Objekte zwingend aktualisiert werden müssen, dann wäre in der Umsetzung das eine Extrem immer die komplette Welt zu sperren, das andere immer jedes Objekt einzeln. Ersteres führt dazu, dass Multithreading praktisch nutzlos ist, letzteres induziert einen riesigen Speicher- und Verwaltungsoverhead.

Auch beim Sperren der gesamten Welt sollte meinem Plan zufolge Multithreading nicht nutzlos sein. Der Logigthread soll ähnlich wie beim Rendering wenn möglich erstmal die nötigen Weltdaten sammeln, die Sperrung (CriticalSection verlassen) aufheben, "Zeug" berechnen, wieder sperren und Änderungen vornehmen. Wenn der Logikthread beim gesamten Prozess die Welt sperren würde, dann wäre ein extra Thread dafür wirklich nutzlos.

RustySpoon hat geschrieben:Ergo wirst du irgendein Mittelding fahren wollen, wo immer hinreichend große Objektgruppen auf einmal gesperrt werden. Aber bei der Größe und Zusammensetzung dieser Objektgruppen wirst du um viel experimentieren und messen nicht drumherum kommen.

Ich werde das wohl testen müssen, wenn alle Aktionen/Prozesse fertig sind und schauen, ob ein extra Thread "reicht", um trotz einer kompletten Sperrung durch Multithreading einen Performancebonus rauszuholen.
Die Objekte die für das Rendering benötigt oder durch Benutzereingaben verändert werden könnten, lassen sich ja auf der Karte recht einfach geographisch ermitteln, jetzt muss ich mir überlegen, wie ich eine partielle Sperrung realisieren könnte.

Schrompf hat geschrieben:Zusätzlich zum "Kann man pauschal so nicht sagen" will ich hinzufügen: Du musst kleiner granularisieren. Das Rendering z.B. ist eine rein lesende Operation auf der Spielwelt. Du könntest also z.B. stressfrei 8 oder wasweißichwieviele Jobs starten, die gleichzeitig über disjunkte Teile der Welt iterieren und die DrawCalls einsammeln. Das Cullen kann man parallelisieren. Mit DX11/DX12/Vulkan/Mantle kann man selbst das Rendern parallelisieren. Daten-Parallele Aufgaben haben immer den Vorteil, dass sie viel besser mit der Hardware skalieren als themen-parallele Aufgaben.

Die Aussage von Krishty hat mich schon stutzig gemacht. Auch wenn nur ein Thread die Daten ändert und ein anderer Thread die Daten nur liest, kann es doch ohne eine Sperrung zu unvorhersehbaren Fehlern führen?
Der Renderer hat gerade alle Objekte eingesammelt, die gezeichnet werden müssen. Zur gleichen Zeit wird aber eines von den Objekten durch den Logikthread gelöscht.
Die Objekte in einem Container werden durch eine Liste gehalten. Wenn jetzt der Renderer gerade die Liste durchgeht und währenddessen der Logikthread ein Objekt aus der Liste löscht oder hinzufügt, kann es zu Fehlern führen.

Schrompf hat geschrieben:Ansonsten: ja, new ist schnell. Ein paar Millionen Allokationen pro Sekunde sind machbar. Für mich damals überraschend war die Erkenntnis, dass das dazugehörige delete deutlich langsamer ist.

Dazu habe ich mir auch viele Gedanken gemacht, inwiefern ein eigener Speichermanager wirklich sinnvoll ist.

new hat den großen Vorteil, dass es threadsafe ist und die Erstellung und Zerstörung der Instanzen quasi unabhängig von allem anderen durchgeführt werden kann.
Ein Speichermanager ist nicht threadsafe und die Objekte, die durch ihn verwaltet werden, benötigen alle einen kleinen Mehraufwand in der Entwicklung.

Aus diversen Gründen (Sicherheit, Analyse, Validierung, Debugging) brauche ich für jede Klasse/Objektart einen Verwalter, der die Objekte erzeugt und löscht. Ein Objekt/Instanz darf nicht außerhalb des Verwalters erstellt oder gelöscht werden.
Diese Bedingung macht so gut wie alle Vorteile von new gegenüber einem eigenen Speichermanager zunichte und dann sehe ich keinen Grund mehr, auf diesen zu verzichten, zumal er auch deutlich schneller ist.

Schrompf hat geschrieben:Evtl. wäre es für solche Jobs aber besser, zumindest während der initialen Einrichtung einen Custom Allokator einzusetzen, der linear aus einem großen Speicherblock schöpft. Das hat zusätzlich den Vorteil, dass alle Daten schön nah beieinander liegen und damit cache-freundlicher sind.

Mit Custom Allokator ist gemeint, das man den new operator überschreibt? Inwiefern kann ich so die Speicherreservierung beschleunigen? Die Objekte können vielleicht Anfangs auf einem großen Speicherblock kommen, aber wie lösche ich danach ein Einzelnes aus diesem Block?

Schrompf hat geschrieben:Aber wenn Du viel auf virtuelle Funktionen setzt, ist Dir Cache-Freundlichkeit wahrscheinlich eh nicht so wichtig.

Die Objekte liegen schon durch den Speichermanager, der intern mit Blöcken arbeitet, ebenfalls dicht beieinander, quasi in einer Reihe pro Block.
Virtuelle Funktionen "sollten" eigentlich bis auf die Delete-Funktion, nicht vorkommen, aber aus irgendeinem Grund werden AddRef und Release völlig sinnlos per vtable aufgerufen.
Die Objekte werden folgendermaßen definiert:
Code: Ansicht erweitern :: Alles auswählen
class InterfaceObject
{
public:
        virtual Void AddRef(Void) = 0;
        virtual Void Release(Void) = 0;
};

class ClassObject : public InterfaceObject
{
public:
        ClassObject(Void)
        {
                m_ReferenceCount = 0;
        }

        Void AddRef(Void)
        {
                ++m_ReferenceCount;
        }

        Void Release(Void)
        {
                --m_ReferenceCount;

                if (0 == m_ReferenceCount)
                {
                        Delete();
                }
        }

private:
        virtual Void Delete(Void) = 0;

        Int32 m_ReferenceCount;
};

class ClassGameObject : public ClassObject
{
private:
        Void Delete(Void)
        {
        }
};

typedef TemplateWeakPointer2<ClassGameObject> wpGameObject;
typedef TemplateSmartPointer2<ClassGameObject> spGameObject;

Eigentlich dürfte er beim Aufruf von AddRef oder Release nicht den vtable heranziehen, außer man macht es durch einen Zeiger vom Typ InterfaceObject.
InterfaceObjekt muss aber weiter bestehen, es gibt noch andere Basis-Objekt-Klassen, die von InterfaceObject erben, wie z.B. eine Version mit thread-sicherem Referenzzähler.
Wenn ich keinen Weg finde, dem Compiler diesen Unfug auszutreiben, werde ich für die Spieldaten-Objekte einen extra BasisObjekt/ClassObject programmieren, InterfaceObject sollte für die eigentlich eh nicht nötig sein.

Schrompf hat geschrieben:Und poste mal Screenshots, wenn's was zu zeigen gibt :-)

Die Welt wird schon bis auf wenige Fehler korrekt gerendert, ist aber halt Ultima 7, bzw. Serpent Isle. Hab mal einen Screenshot in den Anhang gepackt.
Dateianhänge
u7zfx.png
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 13.04.2017, 12:54

Was Custom Allocators angeht: Windows stellt via HeapCreate() Speicher-Manager zur Verfügung. Die sind thread-safe, low-fragmentation, unterstützen alloc/realloc/free, und sind 100 % kompatibel zu Application Verifier & Co. (Debugging-Traum).

Sie sind nicht ganz so platzeffizient wie ein eigener Manager, der aus einem Block schöpft, aber sie sind bereits fertig da. (Schonmal einen Page Heap selber programmiert? Zum Haareraufen.)

Wenn man dem Level einen eigenen Heap gibt, dauert das Freigeben keine 100k Takte (natürlich nur, so lange man den Heap direkt zerstört, und nicht die Objekte darauf einzeln ;) )
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 13.04.2017, 13:18

Ah, mich schon immer gefragt, wozu man einen "extra" Heap per HeapCreate erzeugen sollte, aber nie genauer geguckt was man damit eigentlich alles machen kann.

Wegen dem sinnlosen benutzen vom vtable, was tut der Compiler da nur? wenn ich AddRef und Release mit __forceinline versehe, dann wird in der Release-Version der vtable nicht mehr genutzt.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Schrompf » 13.04.2017, 13:21

Goderion hat geschrieben:Die Aussage von Krishty hat mich schon stutzig gemacht. Auch wenn nur ein Thread die Daten ändert und ein anderer Thread die Daten nur liest, kann es doch ohne eine Sperrung zu unvorhersehbaren Fehlern führen?

Jupp. Am häufigsten sind die logischen Fehler, wenn halt mehrere Leser auf die Daten zugreifen, und jeder Leser potentiell andere Ergebnisse bekommen kann. Wenn Du das Ding dann nur an ner anderen Stelle renderst, ist das unkritisch. Wenn sich daraus KI-Verhalten ableitet oder die Kollisionsprüfung abweichende Ergebnisse liefert, kann das richtig Ärger geben.

Und seltener, aber ebenso möglich, sind direkte Lesefehler: Der Lese-Thread liest die Zahl und bekommt einen Wert, der völliger Quatsch ist. Also z.B. war ein Int vorher bei 0x0000ffe7 und würde danach 0x00010013 haben. x86 (und auch sonst niemand, glaube ich) garantiert nicht, dass die 4Byte des Integers atomar gelesen werden. Du könntest also, wenn der eine Core liest, während der andere schreibt, auch theoretisch ne 0x0001ffe7 lesen, also zwei Byte des alten Wertes und zwei Byte des neuen Wertes. Und das würde man selbst beim simplen Rendering sehen, wenn das Sprite plötzlich einen Meter im Off wäre.

Der Renderer hat gerade alle Objekte eingesammelt, die gezeichnet werden müssen. Zur gleichen Zeit wird aber eines von den Objekten durch den Logikthread gelöscht.
Die Objekte in einem Container werden durch eine Liste gehalten. Wenn jetzt der Renderer gerade die Liste durchgeht und währenddessen der Logikthread ein Objekt aus der Liste löscht oder hinzufügt, kann es zu Fehlern führen.

Joa, aber wie gesagt: verzögertes Erstellen/Löschen musste ich selbst in meinen Single-Threaded-Spielen schon einbauen. Habe aber wie gesagt vergessen, warum ich das tun musste.

Aus diversen Gründen (Sicherheit, Analyse, Validierung, Debugging) brauche ich für jede Klasse/Objektart einen Verwalter, der die Objekte erzeugt und löscht. Ein Objekt/Instanz darf nicht außerhalb des Verwalters erstellt oder gelöscht werden.
Diese Bedingung macht so gut wie alle Vorteile von new gegenüber einem eigenen Speichermanager zunichte und dann sehe ich keinen Grund mehr, auf diesen zu verzichten, zumal er auch deutlich schneller ist.


Wie gesagt: das kannst Du machen, wie Du möchtest. Ich empfände es als unangenehm, nix mehr auf dem Stack anlegen zu können. Da kannst Du auch gleich Java schreiben.

Mit Custom Allokator ist gemeint, das man den new operator überschreibt? Inwiefern kann ich so die Speicherreservierung beschleunigen? Die Objekte können vielleicht Anfangs auf einem großen Speicherblock kommen, aber wie lösche ich danach ein Einzelnes aus diesem Block?

Ich meine einen Custom Allocator, wie Du ihn z.B. an std::vector<> übergeben kannst. Man kann auch den globalen new-Operator überschreiben, aber pro Klasse jedesmal den new-Operator zu überschreiben finde ich mühsam. Und den könnte man dann im Burst-Modus laufen lassen:

Code: Ansicht erweitern :: Alles auswählen

void* alloc() {
  if( istBeimLadenDerWelt )
    return einStückAusDemGroßenBlob;
  else
    return HeapAlloc(...);
}

void free(void* p) {
  if( p ist ImGroßenBlob )
    // nix zu tun
  else
    return HeapFree(...);
}
 


Vielleicht stelle ich mir das auch zu einfach vor, aber im kleineren Maßstab habe ich sowas schon gemacht und es hat mir enorme Gewinne gebracht.

Die Welt wird schon bis auf wenige Fehler korrekt gerendert, ist aber halt Ultima 7, bzw. Serpent Isle. Hab mal einen Screenshot in den Anhang gepackt.

Ist doch cool! Willst Du das Spiel mal komplett nachbauen oder soll das ein reiner Viewer bleiben?
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3747
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 13.04.2017, 14:26

Schrompf hat geschrieben:Joa, aber wie gesagt: verzögertes Erstellen/Löschen musste ich selbst in meinen Single-Threaded-Spielen schon einbauen. Habe aber wie gesagt vergessen, warum ich das tun musste.

Mmmh... ich glaube ich habe da eine grobe Idee. Ich könnte ein System entwickeln, dass das von dir erwähnte verzögerte löschen/verändern der Daten realisiert.
Alle Änderungen werden quasi erst gebuffert. Die Sperre wäre dann etwas komplexer und würde nur darauf abzielen, das nicht gleichzeigt geschrieben und gelesen wird, mehrfaches/gleichzeitiges Lesen aber erlaubt ist.
Rendering und Logik könnten dann tatsächlich parallel laufen, erst das Ändern der Daten würde das kurz "unterbrechen".

Schrompf hat geschrieben:Wie gesagt: das kannst Du machen, wie Du möchtest. Ich empfände es als unangenehm, nix mehr auf dem Stack anlegen zu können. Da kannst Du auch gleich Java schreiben.

Das mit dem Stack verstehe ich nicht, das hat doch nichts mit dem Thema new/WindowsHeap vs. eigener Speichermanager zu tun, oder?

Ich benutze den Speichermanager auch nicht für Alles. Normale Objekte, wie Dateien, Texturen, CriticaelSections, usw., die ich nicht in Massen verwalte, werden normal mit new erstellt und delete gelöscht.
Momentan werden da zwar auch noch virtuelle Delete-Funktionen aufgerufen, aber da die dort eigentlich komplett überflüssig sind, werde ich die wohl Stück für Stück ändern und auf virtuelle Destruktoren setzen.
Ich wusste überhaupt nicht, dass man Destruktoren virtuell machen kann, dass habe ich quasi erst durch euch erfahren, daher muss ich dazu erst rumtesten und werde das dann anwenden.

Schrompf hat geschrieben:Ist doch cool! Willst Du das Spiel mal komplett nachbauen oder soll das ein reiner Viewer bleiben?

Mein Hauptziel ist eine funktionsfähige flexible Spieleengine. Die Ultima-Daten nutze ich primär zu Testzwecken, da diese recht komplex sind.
Es wäre aber ein Traum, wenn ich es schaffen würde, mit der Engine Ultima 7/Serpent Isle spielen zu können, da diese zu meinen Lieblingsspielen gehören.
Die meisten Daten von Ultima sind eigentlich ziemlich simpel, aber das Quest -und Dialogsystem scheinen komplexer zu sein, bisher habe ich bei denen immer kapituliert.
Es gibt ein Projekt, dass Ultima 7/Serpent Isle "nachprogrammiert" hat und sich damit auch spielen lässt, Exult (http://exult.sourceforge.net/).
Im Prinzip sind dort alle Informationen zu finden, man muss sich nur die Mühe machen, diese zu analysieren und zu verstehen.
Vielleicht wage ich mich nochmal an das Quest -und Dialogsystem, wenn die Engine fertig ist. Das wäre schon geil, mir fallen zahlreiche Verbesserungen ein, die das Spielerlebnis von Ultima extrem verbessern könnten.
Die Originalversion/Exultversion finde ich schon fast unspielbar, alles ruckelig und zuckelig und lahm. Die Originalversion läuft mit 5 FPS. ^^

Falls jemand Ultima 6, Ultima 7 oder Serpent Isle besitzt, könnte ich bei Interesse eine Testversion der Engine hochladen.
Ich glaube die Daten zu Ultima darf ich selber nicht einfach so verteilen, Copyright usw., und ohne Ultima-Daten ist die Engine so interessant wie ein Gemälde von einem Punkt.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 13.04.2017, 15:55

Schrompf hat geschrieben:Und seltener, aber ebenso möglich, sind direkte Lesefehler: Der Lese-Thread liest die Zahl und bekommt einen Wert, der völliger Quatsch ist. Also z.B. war ein Int vorher bei 0x0000ffe7 und würde danach 0x00010013 haben. x86 (und auch sonst niemand, glaube ich) garantiert nicht, dass die 4Byte des Integers atomar gelesen werden. Du könntest also, wenn der eine Core liest, während der andere schreibt, auch theoretisch ne 0x0001ffe7 lesen, also zwei Byte des alten Wertes und zwei Byte des neuen Wertes. Und das würde man selbst beim simplen Rendering sehen, wenn das Sprite plötzlich einen Meter im Off wäre.
Am Rande: Doch, x86 hat strenge Garantien mit einigen Einschränkungen (z.B. bzgl. Alignment), sogar strengere als die meisten anderen Architekturen (Alle Integer-Typen mit vernünftiger Ausrichtung lesen ist sogar ohne lock-Präfix atomar!). Allerdings muss man das auch dem Compiler mitteilen, indem man std::atomic nutzt.

Goderion hat geschrieben:Wegen dem sinnlosen benutzen vom vtable, was tut der Compiler da nur? wenn ich AddRef und Release mit __forceinline versehe, dann wird in der Release-Version der vtable nicht mehr genutzt.
Falls das wirklich geht, würde ich es definitiv hinter einem Makro verstecken und gut dokumentieren. Ich wüsste nicht, was virtual __forceinline bedeuten soll, denn das eine schließt das andere aus.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 13.04.2017, 16:51

Krishty hat geschrieben:Falls das wirklich geht, würde ich es definitiv hinter einem Makro verstecken und gut dokumentieren. Ich wüsste nicht, was virtual __forceinline bedeuten soll, denn das eine schließt das andere aus.

Ich setze nicht bei der Deklaration von virtual AddRef und virtual Release in InterfaceObject das __forceinline, sondern bei der Definition von AddRef und Release in ClassObject.

EDIT: Das mit dem Makro ist eine gute Idee, sonst frage ich mich in einem Jahr, warum ich das gemacht habe. :?
Code: Ansicht erweitern :: Alles auswählen
// Erst das Definieren der Funktionen AddRef, Release, usw. mit __forceinline sorgen dafür, dass diese in der Release-Version nicht mehr über den VTable aufgerufen werden. Compilerbug?
#define NO_VTABLE __forceinline
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 13.04.2017, 17:46

Mal eine ganz dumme Frage: Wenn du die Funktionen in einer abgeleiteten Klasse mit __forceinline, überschreibst, und dann die überschriebene Version durch die Basisschnittstelle aufrufst, ruft der Compiler dann auch mit Optimierungen die korrekte Version (die überschriebene) auf? Das klingt mir sehr anfällig für Compiler-Bugs ...
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 13.04.2017, 19:13

Krishty hat geschrieben:Mal eine ganz dumme Frage: Wenn du die Funktionen in einer abgeleiteten Klasse mit __forceinline, überschreibst, und dann die überschriebene Version durch die Basisschnittstelle aufrufst, ruft der Compiler dann auch mit Optimierungen die korrekte Version (die überschriebene) auf? Das klingt mir sehr anfällig für Compiler-Bugs ...


Jetzt steig ich langsam nicht mehr durch ... :?

Die ersten beiden Tests mit deaktivierten Kontrollfunktionen scheinen gleich zu sein, die Tests mit aktivierten Kontrollfunktionen sind aber unterschiedlich.
Ich denke ich werde den "Weltobjekten" eine neue Basis-Klasse spendieren, wo es kein virtual AddRef und virtual Release mehr geben wird, benötige ich an den Stellen eh nicht, damit sollte das Problem beseitigt sein.
Ich habe für Interessierte/Neugierige mal den Assembler-Code für alle 4 Tests hier per Spoiler eingefügt.

Assembler bei deaktivierten Kontrollfunktionen und ohne __forceinline:
Code: Ansicht erweitern :: Alles auswählen
Void Test(InterfaceObject* pInterface, ClassObject* pObject)
{
00163222 mov edi,ecx
00163224 mov esi,edx
00163226 mov eax,dword ptr [edi]
00163228 cmp eax,offset ClassTest::`vftable' (01D80DCh)
0016322D jne Test+0ABh (01632CBh)
pInterface->AddRef();
00163233 inc dword ptr [edi+4]
00163236 mov eax,dword ptr [edi]
00163238 cmp eax,offset ClassTest::`vftable' (01D80DCh)
0016323D jne Test+0B2h (01632D2h)
pInterface->AddRef();
00163243 inc dword ptr [edi+4]
00163246 mov eax,dword ptr [esi]
00163248 cmp eax,offset ClassTest::`vftable' (01D80DCh)
0016324D jne Test+0BBh (01632DBh)

pObject->AddRef();
00163253 inc dword ptr [esi+4]
00163256 mov eax,dword ptr [esi]
00163258 cmp eax,offset ClassTest::`vftable' (01D80DCh)
0016325D jne Test+0C4h (01632E4h)
pObject->AddRef();
00163263 inc dword ptr [esi+4]
00163266 mov eax,dword ptr [edi]
00163268 mov edx,dword ptr [eax+4]
0016326B cmp eax,offset ClassTest::`vftable' (01D80DCh)
00163270 jne Test+0CDh (01632EDh)

pInterface->Release();
00163272 add dword ptr [edi+4],0FFFFFFFFh
00163276 jne Test+5Dh (016327Dh)
00163278 mov ecx,edi
0016327A call dword ptr [eax+10h]
0016327D mov eax,dword ptr [edi]
0016327F mov edx,dword ptr [eax+4]
00163282 cmp eax,offset ClassTest::`vftable' (01D80DCh)
00163287 jne Test+0D3h (01632F3h)
pInterface->Release();
00163289 add dword ptr [edi+4],0FFFFFFFFh
0016328D jne Test+74h (0163294h)
0016328F mov ecx,edi
00163291 call dword ptr [eax+10h]
00163294 mov eax,dword ptr [esi]
00163296 mov edx,dword ptr [eax+4]
00163299 cmp eax,offset ClassTest::`vftable' (01D80DCh)
0016329E jne Test+0D9h (01632F9h)

pObject->Release();
001632A0 add dword ptr [esi+4],0FFFFFFFFh
001632A4 jne Test+8Bh (01632ABh)
001632A6 mov ecx,esi
001632A8 call dword ptr [eax+10h]
001632AB mov eax,dword ptr [esi]
001632AD pop edi
001632AE mov edx,dword ptr [eax+4]
001632B1 cmp eax,offset ClassTest::`vftable' (01D80DCh)
001632B6 jne Test+0A4h (01632C4h)
pObject->Release();
001632B8 add dword ptr [esi+4],0FFFFFFFFh
001632BC jne Test+0A9h (01632C9h)
001632BE mov ecx,esi
001632C0 pop esi
001632C1 jmp dword ptr [eax+10h]
001632C4 mov ecx,esi
001632C6 pop esi
001632C7 jmp edx
001632C9 pop esi
}
001632CA ret
pInterface->AddRef();
001632CB call dword ptr [eax]
001632CD jmp Test+16h (0163236h)
001632D2 mov ecx,edi
pInterface->AddRef();
001632D4 call dword ptr [eax]
001632D6 jmp Test+26h (0163246h)
001632DB mov ecx,esi

pObject->AddRef();
001632DD call dword ptr [eax]
001632DF jmp Test+36h (0163256h)
001632E4 mov ecx,esi
pObject->AddRef();
001632E6 call dword ptr [eax]
001632E8 jmp Test+46h (0163266h)
001632ED mov ecx,edi

pInterface->Release();
001632EF call edx
001632F1 jmp Test+5Dh (016327Dh)
001632F3 mov ecx,edi
pInterface->Release();
001632F5 call edx
001632F7 jmp Test+74h (0163294h)
001632F9 mov ecx,esi

pObject->Release();
001632FB call edx
001632FD jmp Test+8Bh (01632ABh)


Assembler bei deaktivierten Kontrollfunktionen und mit __forceinline:
Code: Ansicht erweitern :: Alles auswählen
Void Test(InterfaceObject* pInterface, ClassObject* pObject)
{
00FF3222 mov edi,ecx
00FF3224 mov esi,edx
00FF3226 mov eax,dword ptr [edi]
00FF3228 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF322D jne Test+0ABh (0FF32CBh)
pInterface->AddRef();
00FF3233 inc dword ptr [edi+4]
00FF3236 mov eax,dword ptr [edi]
00FF3238 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF323D jne Test+0B2h (0FF32D2h)
pInterface->AddRef();
00FF3243 inc dword ptr [edi+4]
00FF3246 mov eax,dword ptr [esi]
00FF3248 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF324D jne Test+0BBh (0FF32DBh)

pObject->AddRef();
00FF3253 inc dword ptr [esi+4]
00FF3256 mov eax,dword ptr [esi]
00FF3258 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF325D jne Test+0C4h (0FF32E4h)
pObject->AddRef();
00FF3263 inc dword ptr [esi+4]
00FF3266 mov eax,dword ptr [edi]
00FF3268 mov edx,dword ptr [eax+4]
00FF326B cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF3270 jne Test+0CDh (0FF32EDh)

pInterface->Release();
00FF3272 add dword ptr [edi+4],0FFFFFFFFh
00FF3276 jne Test+5Dh (0FF327Dh)
00FF3278 mov ecx,edi
00FF327A call dword ptr [eax+10h]
00FF327D mov eax,dword ptr [edi]
00FF327F mov edx,dword ptr [eax+4]
00FF3282 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF3287 jne Test+0D3h (0FF32F3h)
pInterface->Release();
00FF3289 add dword ptr [edi+4],0FFFFFFFFh
00FF328D jne Test+74h (0FF3294h)
00FF328F mov ecx,edi
00FF3291 call dword ptr [eax+10h]
00FF3294 mov eax,dword ptr [esi]
00FF3296 mov edx,dword ptr [eax+4]
00FF3299 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF329E jne Test+0D9h (0FF32F9h)

pObject->Release();
00FF32A0 add dword ptr [esi+4],0FFFFFFFFh
00FF32A4 jne Test+8Bh (0FF32ABh)
00FF32A6 mov ecx,esi
00FF32A8 call dword ptr [eax+10h]
00FF32AB mov eax,dword ptr [esi]
00FF32AD pop edi
00FF32AE mov edx,dword ptr [eax+4]
00FF32B1 cmp eax,offset ClassTest::`vftable' (010680DCh)
00FF32B6 jne Test+0A4h (0FF32C4h)
pObject->Release();
00FF32B8 add dword ptr [esi+4],0FFFFFFFFh
00FF32BC jne Test+0A9h (0FF32C9h)
00FF32BE mov ecx,esi
00FF32C0 pop esi
00FF32C1 jmp dword ptr [eax+10h]
00FF32C4 mov ecx,esi
00FF32C6 pop esi
00FF32C7 jmp edx
00FF32C9 pop esi
}
00FF32CA ret
pInterface->AddRef();
00FF32CB call dword ptr [eax]
00FF32CD jmp Test+16h (0FF3236h)
00FF32D2 mov ecx,edi
pInterface->AddRef();
00FF32D4 call dword ptr [eax]
00FF32D6 jmp Test+26h (0FF3246h)
00FF32DB mov ecx,esi

pObject->AddRef();
00FF32DD call dword ptr [eax]
00FF32DF jmp Test+36h (0FF3256h)
00FF32E4 mov ecx,esi
pObject->AddRef();
00FF32E6 call dword ptr [eax]
00FF32E8 jmp Test+46h (0FF3266h)
00FF32ED mov ecx,edi

pInterface->Release();
00FF32EF call edx
00FF32F1 jmp Test+5Dh (0FF327Dh)
00FF32F3 mov ecx,edi
pInterface->Release();
00FF32F5 call edx
00FF32F7 jmp Test+74h (0FF3294h)
00FF32F9 mov ecx,esi

pObject->Release();
00FF32FB call edx
00FF32FD jmp Test+8Bh (0FF32ABh)


Assembler mit aktivierten Kontrollfunktionen und ohne __forceinline:
Code: Ansicht erweitern :: Alles auswählen
Void Test(InterfaceObject* pInterface, ClassObject* pObject)
{
01273230 push esi
01273231 push edi
01273232 mov edi,ecx
01273234 mov esi,edx
01273236 mov eax,dword ptr [edi]
01273238 mov edx,dword ptr [eax]
0127323A cmp eax,offset ClassTest::`vftable' (012EB13Ch)
0127323F jne Test+0DCh (0127330Ch)
pInterface->AddRef();
01273245 lea eax,[edi+4]
01273248 cmp eax,dword ptr [eax]
0127324A je Test+33h (01273263h)
0127324C push offset string L"objectvalidation fai"... (012ADFE4h)
01273251 push 0
01273253 push 0
01273255 push 0
01273257 xor edx,edx
01273259 xor ecx,ecx
0127325B call Kernel::ErrorMessage (012776D0h)
01273260 add esp,10h
01273263 inc dword ptr [edi+8]
01273266 mov eax,dword ptr [edi]
01273268 mov edx,dword ptr [eax]
0127326A cmp eax,offset ClassTest::`vftable' (012EB13Ch)
0127326F jne Test+0E3h (01273313h)
pInterface->AddRef();
01273275 lea eax,[edi+4]
01273278 cmp eax,dword ptr [eax]
0127327A je Test+63h (01273293h)
0127327C push offset string L"objectvalidation fai"... (012ADFE4h)
01273281 push 0
01273283 push 0
01273285 push 0
01273287 xor edx,edx
01273289 xor ecx,ecx
0127328B call Kernel::ErrorMessage (012776D0h)
01273290 add esp,10h
01273293 inc dword ptr [edi+8]
01273296 mov eax,dword ptr [esi]
01273298 mov edx,dword ptr [eax]
0127329A cmp eax,offset ClassTest::`vftable' (012EB13Ch)
0127329F jne Test+0ECh (0127331Ch)

pObject->AddRef();
012732A1 lea eax,[esi+4]
012732A4 cmp eax,dword ptr [eax]
012732A6 je Test+8Fh (012732BFh)
012732A8 push offset string L"objectvalidation fai"... (012ADFE4h)
012732AD push 0
012732AF push 0
012732B1 push 0
012732B3 xor edx,edx
012732B5 xor ecx,ecx
012732B7 call Kernel::ErrorMessage (012776D0h)
012732BC add esp,10h
012732BF inc dword ptr [esi+8]
012732C2 mov eax,dword ptr [esi]
012732C4 mov edx,dword ptr [eax]
012732C6 cmp eax,offset ClassTest::`vftable' (012EB13Ch)
012732CB jne Test+0F2h (01273322h)
pObject->AddRef();
012732CD lea eax,[esi+4]
012732D0 cmp eax,dword ptr [eax]
012732D2 je Test+0BBh (012732EBh)
012732D4 push offset string L"objectvalidation fai"... (012ADFE4h)
012732D9 push 0
012732DB push 0
012732DD push 0
012732DF xor edx,edx
012732E1 xor ecx,ecx
012732E3 call Kernel::ErrorMessage (012776D0h)
012732E8 add esp,10h
012732EB inc dword ptr [esi+8]

pInterface->Release();
012732EE mov eax,dword ptr [edi]
012732F0 mov ecx,edi
012732F2 call dword ptr [eax+4]
pInterface->Release();
012732F5 mov eax,dword ptr [edi]
012732F7 mov ecx,edi
012732F9 call dword ptr [eax+4]

pObject->Release();
012732FC mov eax,dword ptr [esi]
012732FE mov ecx,esi
01273300 call dword ptr [eax+4]
pObject->Release();
01273303 mov eax,dword ptr [esi]
01273305 mov ecx,esi
01273307 pop edi
01273308 pop esi
01273309 jmp dword ptr [eax+4]
pInterface->AddRef();
0127330C call edx
0127330E jmp Test+36h (01273266h)
01273313 mov ecx,edi
pInterface->AddRef();
01273315 call edx
01273317 jmp Test+66h (01273296h)
0127331C mov ecx,esi

pObject->AddRef();
0127331E call edx
01273320 jmp Test+92h (012732C2h)
01273322 mov ecx,esi
pObject->AddRef();
01273324 call edx
01273326 jmp Test+0BEh (012732EEh)
}


Assembler mit aktivierten Kontrollfunktionen und mit __forceinline
Code: Ansicht erweitern :: Alles auswählen
Void Test(InterfaceObject* pInterface, ClassObject* pObject)
{
00D63582 mov edi,ecx
00D63584 mov esi,edx
00D63586 mov eax,dword ptr [edi]
00D63588 mov edx,dword ptr [eax]
00D6358A cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D6358F jne Test+22Ch (0D637ACh)
pInterface->AddRef();
00D63595 lea eax,[edi+4]
00D63598 cmp eax,dword ptr [eax]
00D6359A je Test+33h (0D635B3h)
00D6359C push offset string L"objectvalidation fai"... (0D9DFE4h)
00D635A1 push 0
00D635A3 push 0
00D635A5 push 0
00D635A7 xor edx,edx
00D635A9 xor ecx,ecx
00D635AB call Kernel::ErrorMessage (0D67FB0h)
00D635B0 add esp,10h
00D635B3 inc dword ptr [edi+8]
00D635B6 mov eax,dword ptr [edi]
00D635B8 mov edx,dword ptr [eax]
00D635BA cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D635BF jne Test+233h (0D637B3h)
pInterface->AddRef();
00D635C5 lea eax,[edi+4]
00D635C8 cmp eax,dword ptr [eax]
00D635CA je Test+63h (0D635E3h)
00D635CC push offset string L"objectvalidation fai"... (0D9DFE4h)
00D635D1 push 0
00D635D3 push 0
00D635D5 push 0
00D635D7 xor edx,edx
00D635D9 xor ecx,ecx
00D635DB call Kernel::ErrorMessage (0D67FB0h)
00D635E0 add esp,10h
00D635E3 inc dword ptr [edi+8]
00D635E6 mov eax,dword ptr [esi]
00D635E8 mov edx,dword ptr [eax]
00D635EA cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D635EF jne Test+23Ch (0D637BCh)

pObject->AddRef();
00D635F5 lea eax,[esi+4]
00D635F8 cmp eax,dword ptr [eax]
00D635FA je Test+93h (0D63613h)
00D635FC push offset string L"objectvalidation fai"... (0D9DFE4h)
00D63601 push 0
00D63603 push 0
00D63605 push 0
00D63607 xor edx,edx
00D63609 xor ecx,ecx
00D6360B call Kernel::ErrorMessage (0D67FB0h)
00D63610 add esp,10h
00D63613 inc dword ptr [esi+8]
00D63616 mov eax,dword ptr [esi]
00D63618 mov edx,dword ptr [eax]
00D6361A cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D6361F jne Test+245h (0D637C5h)
pObject->AddRef();
00D63625 lea eax,[esi+4]
00D63628 cmp eax,dword ptr [eax]
00D6362A je Test+0C3h (0D63643h)
00D6362C push offset string L"objectvalidation fai"... (0D9DFE4h)
00D63631 push 0
00D63633 push 0
00D63635 push 0
00D63637 xor edx,edx
00D63639 xor ecx,ecx
00D6363B call Kernel::ErrorMessage (0D67FB0h)
00D63640 add esp,10h
00D63643 inc dword ptr [esi+8]
00D63646 mov eax,dword ptr [edi]
00D63648 mov edx,dword ptr [eax+4]
00D6364B cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D63650 jne Test+24Eh (0D637CEh)

pInterface->Release();
00D63656 lea eax,[edi+4]
00D63659 cmp eax,dword ptr [eax]
00D6365B je Test+0F4h (0D63674h)
00D6365D push offset string L"objectvalidation fai"... (0D9DFE4h)
00D63662 push 0
00D63664 push 0
00D63666 push 0
00D63668 xor edx,edx
00D6366A xor ecx,ecx
00D6366C call Kernel::ErrorMessage (0D67FB0h)
00D63671 add esp,10h
00D63674 cmp dword ptr [edi+8],0
00D63678 jne Test+111h (0D63691h)
00D6367A push offset string L"Null == Value" (0D9E018h)
00D6367F push 0
00D63681 push 0
00D63683 push 0
00D63685 xor edx,edx

pInterface->Release();
00D63687 xor ecx,ecx
00D63689 call Kernel::ErrorMessage (0D67FB0h)
00D6368E add esp,10h
00D63691 add dword ptr [edi+8],0FFFFFFFFh
00D63695 jne Test+11Eh (0D6369Eh)
00D63697 mov eax,dword ptr [edi]
00D63699 mov ecx,edi
00D6369B call dword ptr [eax+10h]
00D6369E mov eax,dword ptr [edi]
00D636A0 mov edx,dword ptr [eax+4]
00D636A3 cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D636A8 jne Test+257h (0D637D7h)
pInterface->Release();
00D636AE lea eax,[edi+4]
00D636B1 cmp eax,dword ptr [eax]
00D636B3 je Test+14Ch (0D636CCh)
00D636B5 push offset string L"objectvalidation fai"... (0D9DFE4h)
00D636BA push 0
00D636BC push 0
00D636BE push 0
00D636C0 xor edx,edx
00D636C2 xor ecx,ecx
00D636C4 call Kernel::ErrorMessage (0D67FB0h)
00D636C9 add esp,10h
00D636CC cmp dword ptr [edi+8],0
00D636D0 jne Test+169h (0D636E9h)
00D636D2 push offset string L"Null == Value" (0D9E018h)
00D636D7 push 0
00D636D9 push 0
00D636DB push 0
00D636DD xor edx,edx
00D636DF xor ecx,ecx
00D636E1 call Kernel::ErrorMessage (0D67FB0h)
00D636E6 add esp,10h
00D636E9 add dword ptr [edi+8],0FFFFFFFFh
00D636ED jne Test+176h (0D636F6h)
00D636EF mov eax,dword ptr [edi]
00D636F1 mov ecx,edi
00D636F3 call dword ptr [eax+10h]
00D636F6 mov eax,dword ptr [esi]
00D636F8 mov edx,dword ptr [eax+4]
00D636FB cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D63700 jne Test+260h (0D637E0h)

pObject->Release();
00D63706 lea eax,[esi+4]
00D63709 cmp eax,dword ptr [eax]
00D6370B je Test+1A4h (0D63724h)
00D6370D push offset string L"objectvalidation fai"... (0D9DFE4h)
00D63712 push 0
00D63714 push 0
00D63716 push 0
00D63718 xor edx,edx
00D6371A xor ecx,ecx
00D6371C call Kernel::ErrorMessage (0D67FB0h)
00D63721 add esp,10h
00D63724 cmp dword ptr [esi+8],0
00D63728 jne Test+1C1h (0D63741h)
00D6372A push offset string L"Null == Value" (0D9E018h)
00D6372F push 0
00D63731 push 0
00D63733 push 0
00D63735 xor edx,edx
00D63737 xor ecx,ecx
00D63739 call Kernel::ErrorMessage (0D67FB0h)
00D6373E add esp,10h
00D63741 add dword ptr [esi+8],0FFFFFFFFh
00D63745 jne Test+1CEh (0D6374Eh)
00D63747 mov eax,dword ptr [esi]
00D63749 mov ecx,esi
00D6374B call dword ptr [eax+10h]
00D6374E mov eax,dword ptr [esi]
00D63750 mov edx,dword ptr [eax+4]
00D63753 cmp eax,offset ClassTest::`vftable' (0DDB13Ch)
00D63758 jne Test+224h (0D637A4h)
pObject->Release();
00D6375A lea eax,[esi+4]
00D6375D cmp eax,dword ptr [eax]
00D6375F je Test+1F8h (0D63778h)
00D63761 push offset string L"objectvalidation fai"... (0D9DFE4h)
00D63766 push 0
00D63768 push 0
00D6376A push 0
00D6376C xor edx,edx
00D6376E xor ecx,ecx
00D63770 call Kernel::ErrorMessage (0D67FB0h)
00D63775 add esp,10h
00D63778 cmp dword ptr [esi+8],0
00D6377C jne Test+215h (0D63795h)
00D6377E push offset string L"Null == Value" (0D9E018h)
00D63783 push 0
00D63785 push 0
00D63787 push 0
00D63789 xor edx,edx
00D6378B xor ecx,ecx
00D6378D call Kernel::ErrorMessage (0D67FB0h)
00D63792 add esp,10h
00D63795 add dword ptr [esi+8],0FFFFFFFFh
00D63799 pop edi
00D6379A jne Test+22Ah (0D637AAh)
00D6379C mov eax,dword ptr [esi]
00D6379E mov ecx,esi
00D637A0 pop esi
00D637A1 jmp dword ptr [eax+10h]
00D637A4 pop edi
00D637A5 mov ecx,esi
00D637A7 pop esi
00D637A8 jmp edx
00D637AA pop esi
}
00D637AB ret
pInterface->AddRef();
00D637AC call edx
00D637AE jmp Test+36h (0D635B6h)
00D637B3 mov ecx,edi
pInterface->AddRef();
00D637B5 call edx
00D637B7 jmp Test+66h (0D635E6h)
00D637BC mov ecx,esi

pObject->AddRef();
00D637BE call edx
00D637C0 jmp Test+96h (0D63616h)
00D637C5 mov ecx,esi
pObject->AddRef();
00D637C7 call edx
00D637C9 jmp Test+0C6h (0D63646h)
00D637CE mov ecx,edi

pInterface->Release();
00D637D0 call edx
00D637D2 jmp Test+11Eh (0D6369Eh)
00D637D7 mov ecx,edi
pInterface->Release();
00D637D9 call edx
00D637DB jmp Test+176h (0D636F6h)
00D637E0 mov ecx,esi

pObject->Release();
00D637E2 call edx
00D637E4 jmp Test+1CEh (0D6374Eh)


Es sieht wohl so aus, als würde er vor der eigentlichen Funkion den vtable prüfen, damit den Objekttyp ermitteln und dann entsprechend fortfahren.
Ich werde vorerst __forceinline entfernen, bzw. das Makro leer definieren.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Krishty » 14.04.2017, 01:27

Entschuldige, was sind Kontrollfunktionen?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6560
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon smurfer » 14.04.2017, 09:30

Goderion hat geschrieben:
Schrompf hat geschrieben:Joa, aber wie gesagt: verzögertes Erstellen/Löschen musste ich selbst in meinen Single-Threaded-Spielen schon einbauen. Habe aber wie gesagt vergessen, warum ich das tun musste.

Mmmh... ich glaube ich habe da eine grobe Idee. Ich könnte ein System entwickeln, dass das von dir erwähnte verzögerte löschen/verändern der Daten realisiert.
Alle Änderungen werden quasi erst gebuffert. Die Sperre wäre dann etwas komplexer und würde nur darauf abzielen, das nicht gleichzeigt geschrieben und gelesen wird, mehrfaches/gleichzeitiges Lesen aber erlaubt ist.
Rendering und Logik könnten dann tatsächlich parallel laufen, erst das Ändern der Daten würde das kurz "unterbrechen".

Diesen Punkt von Schrompf und dir möchte ich nocheinmal hervorheben und ergänzen. Ich habe bei mir hervorragende Erfahrungen mit Multibuffern gemacht, da man sich außer beim Buffer-Swap um nichts kümmern muss und zu jeder Zeit einen konsistenten Zustand abgreifen kann.
Du kannst im Prinzip alle relevanten Objekte doppelt- (oder dreifach-) gepuffert erzeugen. Banales Beispiel: std::vector mit Objekten (oder Objektzeigern). Die Logik/Physik läuft auf dem Back-, das Rendering auf dem Frontbuffer. Ist die Logik/Physik mit ihrem Frame fertig, müssen lediglich die beiden Vektoren "geswappt" werden und auch nur dieser Schritt muss z.B. per Mutex gesichert sein (im einfachsten Fall ein Zeigerswap auf den Front- und Backbuffer). Bei mir sind die Frequenzen (z.B. Simulation 500Hz, Rendering 60 Hz) sehr unterschiedlich, hier lohnt sich mindestens ein Triple-Buffer. Die Simulation aktualisiert dann munter mit 500 Hz zwischen Back- und Middle-Buffer und ab und an tauscht die Grafik die Zeiger von Front- und Middle. Falls Du bei deiner Physik auf vergangene Zustände zugreifen und dies komplett über den Buffer abdecken möchtest, wird das Ganze zum "Quadruple"-Buffer. Klingt dramatischer als es ist, hier wird das erste mal ein Kopieren der Zustände benötigt, um einen korrekten vergangenen Zustand zu bekommen (bei einem Swap würde ich einen Frame überspringen). Am Ende sieht das Ganze etwa so aus:
Buffer[0] Simulation(t)
-> Kopie (Simulationsthread)
Buffer[1] Simulation(t-1)
-> Swap (Simulationsthread, geschützt)
Buffer[2] "Austauschbuffer" (t-2)
-> Swap (Renderingthread, geschützt)
Buffer[3] Rendering(t-3)
Das (t-3) sollte auch nicht stören, da es sich auf die Simulationsfrequenz bezieht und die Grafikaktualisierung in diesem Fall deutlich langsamer passiert.
smurfer
 
Beiträge: 60
Registriert: 25.02.2002, 15:55

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 14.04.2017, 11:24

Krishty hat geschrieben:Entschuldige, was sind Kontrollfunktionen?

Mit Kontrollfunktionen meine ich Funktionen die diverse Dinge überprüfen.
Jedes Objekt hat z.B. einen Zeiger auf sich selbst. Im ersten Konstruktor wird dieser gesetzt und im letzten Destruktor "genullt". Die Prüfung ist natürlich nicht narrensicher, aber kostet so gut wie nix und die Wahrscheinlichkeit "falsche" Objekte zu erkennen, ist damit sehr hoch.
Die ganze Funktionalität (an/aus) solcher "Kontrollfunktionen" lässt sich innerhalb der gesamten Projektgruppe über ein Define steuern.

smurfer hat geschrieben:Diesen Punkt von Schrompf und dir möchte ich nocheinmal hervorheben und ergänzen. Ich habe bei mir hervorragende Erfahrungen mit Multibuffern gemacht, da man sich außer beim Buffer-Swap um nichts kümmern muss und zu jeder Zeit einen konsistenten Zustand abgreifen kann.
Du kannst im Prinzip alle relevanten Objekte doppelt- (oder dreifach-) gepuffert erzeugen. Banales Beispiel: std::vector mit Objekten (oder Objektzeigern). Die Logik/Physik läuft auf dem Back-, das Rendering auf dem Frontbuffer. Ist die Logik/Physik mit ihrem Frame fertig, müssen lediglich die beiden Vektoren "geswappt" werden und auch nur dieser Schritt muss z.B. per Mutex gesichert sein (im einfachsten Fall ein Zeigerswap auf den Front- und Backbuffer). Bei mir sind die Frequenzen (z.B. Simulation 500Hz, Rendering 60 Hz) sehr unterschiedlich, hier lohnt sich mindestens ein Triple-Buffer. Die Simulation aktualisiert dann munter mit 500 Hz zwischen Back- und Middle-Buffer und ab und an tauscht die Grafik die Zeiger von Front- und Middle. Falls Du bei deiner Physik auf vergangene Zustände zugreifen und dies komplett über den Buffer abdecken möchtest, wird das Ganze zum "Quadruple"-Buffer. Klingt dramatischer als es ist, hier wird das erste mal ein Kopieren der Zustände benötigt, um einen korrekten vergangenen Zustand zu bekommen (bei einem Swap würde ich einen Frame überspringen). Am Ende sieht das Ganze etwa so aus:
Buffer[0] Simulation(t)
-> Kopie (Simulationsthread)
Buffer[1] Simulation(t-1)
-> Swap (Simulationsthread, geschützt)
Buffer[2] "Austauschbuffer" (t-2)
-> Swap (Renderingthread, geschützt)
Buffer[3] Rendering(t-3)
Das (t-3) sollte auch nicht stören, da es sich auf die Simulationsfrequenz bezieht und die Grafikaktualisierung in diesem Fall deutlich langsamer passiert.

Die Idee klingt gut, aber ich weiß nicht, wie ich das in meiner Situation anwenden soll.
In einem Level/Karte existieren ca. 250.000 Objekte. Jedes Objekt selber kann je nachdem was es darstellt, 10 bis 100 weitere Objekte/Definitionen besitzen. Handelt es sich dabei um einen Container (Beutel, Rucksack, Truhe, usw.) können es weit über mehrere tausend Objekte sein.
Die Objekte werden über drei Wege im Level gespeichert, wenn sie sich direkt auf der Karte/Level befinden und nicht in einem Container:
1. Octree für Kollisionsberechnungen
2. Quadtree für das Rendering
3. Pro Feld/Zelle, die ein Objekt überdeckt (Z wird hier ignoriert), für das Pathfinding

Ein Objekt existiert somit im Octree, im Quadtree und wenn es z.B. 4 Felder überdeckt, 4 mal als Listeneintrag.

Im Logikthread brauche ich z.B. für die KI alle Daten, die gesamte Karte mit allen Objekten. Mir fällt keine Idee ein, wie ich die Objekte irgendwie sinnvoll buffern könnte und noch weniger, wie ich dann diesen Buffer synchronisiere.
Mein Ansatz wäre eher der, dass die Logik die Änderungen nicht direkt vornimmt, sondern in so eine Art Kommandoliste packt. Die Kommandos sind sehr simpel, wie z.B. reduziere Mana um 10, Bewege Objekt nach X, usw..
Grob gesagt, alle Berechnungen werden im Logikthread vorgenommen, die nötigen Änderungen in primitiver Form gesammelt und dann in einem Rutsch angewandt.
Die Logik braucht dann z.B. 5 ms zum Berechnen und 1 ms zu Ändern der Daten.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon smurfer » 14.04.2017, 11:35

Goderion hat geschrieben:Mein Ansatz wäre eher der, dass die Logik die Änderungen nicht direkt vornimmt, sondern in so eine Art Kommandoliste packt. Die Kommandos sind sehr simpel, wie z.B. reduziere Mana um 10, Bewege Objekt nach X, usw..
Grob gesagt, alle Berechnungen werden im Logikthread vorgenommen, die nötigen Änderungen in primitiver Form gesammelt und dann in einem Rutsch angewandt.
Die Logik braucht dann z.B. 5 ms zum Berechnen und 1 ms zu Ändern der Daten.

Ja, eine Queue abzuarbeiten ist auch ein guter Ansatz (ob nun einzeln oder ergänzend zum Buffer). Du kannst für die Kommandos eine concurrent_queue wie z.B. https://github.com/ikiller1/moodycamel-ConcurrentQueue verwenden oder einfach die Queue doppelt puffern. Bei mir besitzt beispielsweise jedes (Thread-)Modul eine Kommando-Queue (concurrent_queue). Über ein Engine-globales Kommando-Interface werden Funktionsaufrufe automatisch in die korrekte Queue einsortiert. Das Abarbeiten der Aufträge übernimmt dann der jeweilige Thread.
smurfer
 
Beiträge: 60
Registriert: 25.02.2002, 15:55

Re: C++ - Organisation/Verwaltung von millionen Objekten

Beitragvon Goderion » 15.04.2017, 11:52

Vielen Dank für die Antworten/Hinweise!

smurfer hat geschrieben:Ja, eine Queue abzuarbeiten ist auch ein guter Ansatz (ob nun einzeln oder ergänzend zum Buffer). Du kannst für die Kommandos eine concurrent_queue wie z.B. https://github.com/ikiller1/moodycamel-ConcurrentQueue verwenden oder einfach die Queue doppelt puffern. Bei mir besitzt beispielsweise jedes (Thread-)Modul eine Kommando-Queue (concurrent_queue). Über ein Engine-globales Kommando-Interface werden Funktionsaufrufe automatisch in die korrekte Queue einsortiert. Das Abarbeiten der Aufträge übernimmt dann der jeweilige Thread.

Ich glaube die concurrent_queue ist für meine Zwecke übertrieben und overpowered. Die Kommando-Liste/Array wäre ja nur ein einfache lineare Aneinanderreihung von Befehlen. Der Logikthread hat meinem Plan zufolge 2 Phasen.
1. Phase: Lesezugriff auf die Daten anfordern. Objekte lesen, Logik berechnen und die Kommandoliste füllen.
2. Phase: Schreibzugriff auf die Daten anfordern. Kommandoliste auf Daten anwenden.
Demnach wird es nie einen Moment geben, wo mehr als ein Thread gleichzeigt auf die Kommandoliste zugreift. Ich denke das wäre in meinem Fall auch sinnlos.
Die Logik darf nicht schon das nächste "Frame" berechnen, bevor die zuvor erstellte Kommandoliste angewandt wurde.
Die Kommandoliste existiert nur, um die Zeit der "Vollsperrung" der Daten so kurz wie möglich zu halten.

Schrompf hat geschrieben:Zusätzlich zum "Kann man pauschal so nicht sagen" will ich hinzufügen: Du musst kleiner granularisieren. Das Rendering z.B. ist eine rein lesende Operation auf der Spielwelt. Du könntest also z.B. stressfrei 8 oder wasweißichwieviele Jobs starten, die gleichzeitig über disjunkte Teile der Welt iterieren und die DrawCalls einsammeln. Das Cullen kann man parallelisieren. Mit DX11/DX12/Vulkan/Mantle kann man selbst das Rendern parallelisieren. Daten-Parallele Aufgaben haben immer den Vorteil, dass sie viel besser mit der Hardware skalieren als themen-parallele Aufgaben.

Das klingt interessant. Ich bin mir nicht sicher was mit disjunkte Teile gemeint ist, die Weltdaten, bzw. Renderdaten liegen alle pro Karte/Level in einem Quadtree. Spontan würde mir nur die Idee einfallen, dass ich z.B. die zu rendernde Fläche aufteile und ein Thread rendert die linke Seite und der andere die rechte Seite.
Was meinst Du hier mit Cullen? Ist das nicht nur bei 3D-Anwendungen interessant?
Ich nutze momentan das allerneuste DirectX9! ;)
Ein wechsel zu DX11/DX12/Vulkan/Mantle wäre vermutlich einfach zu realisieren, da ich das Rendersystem strikt vom Rest der Engine getrennt habe.

Ich habe auch nochmal auf diversen Geräten und virtuellen Maschinen new/HeapAlloc/WindowsHeap vs eigener Speichermanager getestet.
Auf meinem Hauptrechner (i7 6700K @4500 - Windows 10) braucht die gesamte Initialisierung mit HeapAlloc ca. 2 Sekunden und der Speichermanager ca. 1,5 Sekunden.
Den größten Unterschied konnte ich auf einem ASUS EeeBook X206HA mit einem Intel Atom x5-Z8350, 4x 1.44GHz feststellen, ca. 17 Sekunden braucht HeapAlloc, der eigene Speichermanager ca. 10 Sekunden.
Die Speicherauslastung war mit HeapAlloc nur 20 bis 30 MB größer, meiner Meinung nach nicht der Rede wert.
Für mich ein etwas ernüchterndes Ergebnis, ich habe zwar noch keine weiteren Tests gemacht, erwarte da aber auch keine großen Unterschiede.
Mein aktuelles Fazit dazu lautet daher: Eigener Speichermanager nett, aber für eine neues Projekt lohnt das vermutlich nicht.
In meinem Fall möchte ich für die Objekte, die massenweise erzeugt und wieder freigegeben werden, so oder so Fabrikfuntionen/Verwalter haben, ohne diese "Fabriken" würde ich den Gebrauch vom Speichermanager vermutlich stark reduzieren oder ihn komplett entfernen.
Benutzeravatar
Goderion
 
Beiträge: 82
Registriert: 16.09.2012, 12:02


Zurück zu Programmiersprachen, Quelltext und Bibliotheken

Wer ist online?

Mitglieder in diesem Forum: Baidu [Spider], Bing [Bot] und 1 Gast