Seite 1 von 1

C++ - Organisation/Verwaltung von millionen Objekten

Verfasst: 12.04.2017, 19:51
von Goderion
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?

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

Verfasst: 12.04.2017, 20:49
von Krishty
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?

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

Verfasst: 12.04.2017, 21:30
von Goderion
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.

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

Verfasst: 13.04.2017, 09:48
von RustySpoon
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.

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

Verfasst: 13.04.2017, 10:03
von Schrompf
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 :-)

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

Verfasst: 13.04.2017, 11:58
von Krishty
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.)

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

Verfasst: 13.04.2017, 12:17
von Schrompf
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.

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

Verfasst: 13.04.2017, 12:29
von Goderion
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: 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.

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

Verfasst: 13.04.2017, 12:54
von Krishty
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 ;) )

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

Verfasst: 13.04.2017, 13:18
von Goderion
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.

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

Verfasst: 13.04.2017, 13:21
von Schrompf
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: 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?

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

Verfasst: 13.04.2017, 14:26
von Goderion
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.

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

Verfasst: 13.04.2017, 15:55
von Krishty
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.

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

Verfasst: 13.04.2017, 16:51
von Goderion
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: 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 

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

Verfasst: 13.04.2017, 17:46
von Krishty
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 ...

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

Verfasst: 13.04.2017, 19:13
von Goderion
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: 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: 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: 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: 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.

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

Verfasst: 14.04.2017, 01:27
von Krishty
Entschuldige, was sind Kontrollfunktionen?

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

Verfasst: 14.04.2017, 09:30
von smurfer
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.

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

Verfasst: 14.04.2017, 11:24
von Goderion
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.

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

Verfasst: 14.04.2017, 11:35
von smurfer
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.

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

Verfasst: 15.04.2017, 11:52
von Goderion
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.