Design Pattern fürs Pointer-Speichern

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

'nabend zusammen :)

Folgendes Szenario: In meinem Framework will ich den aktuellen Spielzustand in Savegames speichern und später wieder laden. Ein wichtiger Teil des Spielzustandes sind Entities, generische Objekte in der Spielwelt die aus verschiedenen Component-Objekten bestehen. Nun braucht man ab und zu, beispielsweise in einer dieser Komponenten, einen Zeiger auf andere Spielobjekte, z.B. ein Ziel, das ich gerade angreife. Entities können zerstört werden, wodurch Zeiger auf sie ungültig werden.
Zur Laufzeit wird dieses Problem durch weak_ptr gelöst. Diese bieten die Möglichkeit, bzw. den Zwang, die Gültigkeit eines Zeigers mit überschaubaren Kosten zu überprüfen und sind sehr nett zu benutzen. (Ich halte diese Variante für wesentlich robuster und einfacher als sich alle Objekte zu merken, die auf einen zeigen, und diese vor der Zerstörung zu benachrichtigen.) Soweit alles gut.

Mein Speichersystem ist momentan über eine Archive-Klasse implementiert, die für verschiedene Typen und Aggregate (z.B. ein std::vector eines andern Typs) Lade- und Speicherfunktionen bietet. Mein reicht also ein Archive-Objekt einmal überall rum, dabei schreibt z.B. ein Entity all seine Werte hinein und reicht es dann an seine Komponenten weiter, damit diese ihre Werte in das Archive schreiben. Das funktioniert soweit auch zufriedenstellend.

Aber was mache ich nun mit meinen weak_ptr'n? Man könnte damit anfangen, allen Entities (ich brauche denke ich zunächst nur Zeiger auf Entities) eine fortlaufende ID zu geben, und statt dem Zeiger dann diese ID zu speichern, die man nach dem Laden wieder benutzen kann um die Speicheradresse zu erfragen. Idealerweise sollte dieser Lookup natürlich nur einmal geschehen. Allerdings kann man das nicht direkt tun, es kann ja sein, dass Objekt A vorne in der Datei steht und auf Objekt B zeigt, dass weiter hinten ist - die ID kann also erst aufgelöst werden, nachdem alle Entities geladen wurden.

Mit fallen spontan drei Lösungen ein:
  • Ich könnte jetzt analog zur Ladefunktion jedem Objekt für Phase 2 eine weitere Ladefunktion geben. In den allermeisten Fällen wird diese leer sein, bzw. nur die entsprechende Funktion aller Unterklassen aufrufen. Viel nervige Arbeit und potentiell anfällig für Fehler.
  • Ich ersetze meine weak_ptr durch ein Objekt, dass entweder eine ID oder einen weak_ptr speichert. Beim ersten Dereferenzieren wird der ID-Lookup vorgenommen. Der weak_ptr kommt schon immer mit dem Existenztest (aber diesen Preis muss man wohl zahlen), aber immer einen zweiten Test durchführen zu müssen hört sich nicht soo elegant an (ggf. könnte man den Test auch durch ein Umbiegen von Funktionszeigern ersetzen - wäre das dann toll?)
  • Beim Laden registriert man eine Callback-Funktion (z.B. ein Lambda). Am Ende des Ladevorgangs kann das Archive bzw. der SceneManager dann diese CallbackListe abarbeiten und die Zeiger entsprechend setzen. Einzige Voraussetzung dabei wäre, dass sich während dem Laden die Adresse des weak_ptrs nicht ändern darf (damit der Callback gültig bleibt), aber es ist schwer sich einen Fall vorzustellen, bie dem dies nicht so sein sollte.
Was meint ihr? Welche Variante ist die beste? Oder gibt es vielleicht noch eine vierte?
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Spiele Programmierer »

Sehr gute Frage mit der ich mich schon öfter rumgeärgert habe.

Vorweg: Ich denke es gibt keinen Königsweg. Egal wie man es macht, es ist immer leicht fehleranfällig.

Zu den von dir genannten Möglichkeiten möchte ich noch drei ergänzen:
  • Falls dies mit deinem Objektsystem kompatibel ist, gibt es noch die Möglichkeit erst alle Objekte zu allokieren und danach zu laden. Damit dies klappt, musst du die absolut essentiellen Daten (z.B. für den Konstruktuor) in der Datei vorher ablegen. Dann erstellst du erstmal alle Objekte und füllst diese dann danach mit Leben. Das ganze bedeutet, dass die eigentlichen Laderoutinen immer vollständig alle Objekte zur Verfügung haben. Natürlich darf man nicht versehentlich noch nicht geladene Daten lesen, aber ich fürchte zumindest wenn es Zykel zwischen den Objekten gibt, ist das Problem schon rein mathematisch offensichtlich unlösbar.
  • Falls du bei dir keine Zykel zwischen den Objekten hast, könntest du die Objekte auch einfach in der richtigen Reihenfolge laden. Entweder machst du vor dem Speichern eine topologische Sortierung, oder du lädst Objekte rekursiv in der Reihenfolge, in dem du sie benötigst in dem du in der Datei herumspringst. Ich denke der Nachteil ist offensichtlich: Man kann keine Zykel haben. Außerdem braucht man für die Variante mit topologischer Sortierung zusätzliche (potentiell eher fehleranfällige) APIs, um die Zusammenhänge zu klären. Andererseits bei der Rekursionsmethode kann potentiell natürlich theoretisch der Stapel überlaufen, wenn in deinem Spiel lange Objektketten möglich sind.
  • Eine weitere Möglichkeit die ich sehe ist es, die Darstellung der Zeiger selbst zu ändern, sodass man diese direkt abspeichern kann. Ich stelle mir eine Zeigerklasse vor, die intern den relativen Abstand zu ihrer eigenen Speicherposition speichert anstatt die absolute Position. Mit einem eigenen Allokator packt man das ganze dann in einem kontinuierlichen Speicherblock und zum Speichern schreibt man alles einfach 1:1 in eine Datei oder man verwendet gleich Memory-Mapped-Files. Ich denke mit dieser Variante kann man extrem schnell speichern und man kann (nach ein paar Low-Level-Zeiger-Spielchen) fast ohne zusätzlichen Code alles speichern. Nachteil ist natürlich, dass das Ganze dazu neigt ungewollte Dinge abzuspeichern, die man nicht speichern will. Evt. hat (oder hätte) man sonst in den Objekten z.B. noch Informationen für das Rendering die man nicht speichern will. Oder es gibt Lücken zwischen den Objekten. Man nimmt die Fragmentierung damit ja praktisch immer mit, auch wenn man zwischenzeitlich die Anwendung schließt. Außerdem sind komplizierte Container usw. evt. nervig neuzuerfinden, wenn man das braucht. Theoretisch ist das auch nicht so portabel (insbesondere für Big-Endian-Architekturen), wobei ich denke, dass dieser Nachteil heutzutage zunehmend irrelevant wird.
In einem aktuellen Spiel verwende ich aktuell eine Amalgamation aus dem ersten Vorschlag in der Liste und dem dritten in deiner Liste. Wenn das Objekt bereits geladen wurde, ist der Zeiger direkt verfügbar. Andernfalls wird die Position in eine Liste gestellt und wird beizeiten aktualisiert, wenn das Objekt denn verfügbar wird. Mein erster Vorschlag hat sich leider als nicht ausreichend herausgestellt, da es in dem Spiel eine Hierarchie von drei Objekt-Kategorien gibt, bei denen jeweils die vorherigen bereits geladen sein müssen, um die späteren zu konstruieren. Das Ganze ist insbesondere, damit man überhaupt weiß, wieviel Speicher allokiert werden muss. Mit der Zeit hat sich leider herausgestellt, dass es auch nicht ausreicht nur Zeiger von Objekten in eine Kategorie zuzulassen, die bereits geladen wurden...

Die Bilanz bisher ist aber leider relativ negativ. Im ganzen Code gibt es wahrsacheinlich keine andere API die so feheleranfällig/kompliziert ist. Das Ganze wird auch dadurch verschlimmert, dass das Speichersystem so konzipiert ist, dass Variablen deklarativ registriert werden können und dann automatisch geladen werden. Klingt praktisch, aber alles in allem ist es vor allem Irre kompliziert. Außerdem ist auch schon das genau von dir angesprochene Problem aufgetreten: Objekte dürfen nicht mehr verschoben werden, WENN es nachzuliefernde Zeiger gibt. Zum Beispiel wurden manchmal Objekte erstmal in lokalen Variablen geladen und dann nochmal verschoben/kopiert! Insbesondere kopieren ist lustig, da man das auch gar nicht so leicht einfach dadurch vermeiden kann, in dem man vorher einfach einen Speicherbereich fixiert. In Situationen bei denen nur selten ein verzögert-geladener-Zeiger auftritt, hat man so wunderbare Fehler, die lange unentdeckt bleiben können. Auch gibt es manchmal Situationen, bei denen das Objekt, welches einen Zeiger besitzt und gerade geladen wurde, plötzlich aufhört überhaupt zu existieren. Zum Beispiel, da nach dem Laden des Zeigers bei dem Objekt eine Speicherstand-Inkompatbilität festgestellt wurde, die nicht ignoriert/behoben werden kann und das Objekt daher wieder gelöscht werden muss. In dem Fall darf man natürlich nicht mit einem Dangling-Pointer versuchen später irgendwelche Zeiger nachzuliefern! Speichern/Laden ist ja auch ein bisschen orthogonal zur Spiellogik und da übersieht man solche Zusammenhänge auch mal schnell.

Wenn ich nochmal von vorne anfangen würde, würde ich glaube ich versuchen ob man nicht doch irgendwie alle Objekte sofort erstellen kann um alle Zeiger direkt zu laden. Evt. muss man zusätzliche Daten redundant speichern und eine zweite "Konstruktor-Methode" anlegen, mit der das Objekt später "richtig" initialisiert wird, aber wahrscheinlich besser als irgendwelche Nachlade-Listen mitzuschleppen.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Krishty »

Spiele Programmierer hat geschrieben: 23.02.2021, 01:36Eine weitere Möglichkeit die ich sehe ist es, die Darstellung der Zeiger selbst zu ändern, sodass man diese direkt abspeichern kann. Ich stelle mir eine Zeigerklasse vor, die intern den relativen Abstand zu ihrer eigenen Speicherposition speichert anstatt die absolute Position. Mit einem eigenen Allokator packt man das ganze dann in einem kontinuierlichen Speicherblock und zum Speichern schreibt man alles einfach 1:1 in eine Datei oder man verwendet gleich Memory-Mapped-Files. Ich denke mit dieser Variante kann man extrem schnell speichern und man kann (nach ein paar Low-Level-Zeiger-Spielchen) fast ohne zusätzlichen Code alles speichern.
Fun Fact ohne Wertung: Visual C++ unterstützt das nativ via __based. Eines der Features, die ich schon immer mal ausprobieren wollte, aber ganz genau weiß, dass ich damit die Tore zur Hölle aufstoßen würde :)

Der Artikel zeigt auch noch eine weitere Möglichkeit auf: Du kannst deinen Allokator reproduzierbar schreiben, da VirtualAlloc() und MapViewOfFile() eine Basisadresse akzeptieren. Die merkst du dir und kannst beim nächsten Laden alle Zeiger 1:1 wiederverwenden.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von xq »

Generell würde ich einfach ein Pointer→ID-Mapping anlegen, und einfach mit "first come, first serve" serialisieren. Aber noch eine wichtige Frage:
Sind deine Entities alle gleich (as in: alles eine instanz der selbe Klasse, üblich bei ECS) oder hast du einen Vererbungsbaum und musst dementsprechend einen Typ mit deserialisieren?
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4252
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Chromanoid »

Ich weiß nicht, ob das hier schon vorgeschlagen wurde - ich denke xq könnte das meinen, oder?

Bau in Dein Archive ein writeObjectWeakPtr / readObjectWeakPtr ein. Da steckst Du dann deine Pointer rein. Beim Schreiben merkst Du Dir eine Liste mit Pointer zu Stelle in Ausgabe-Datei. Schreibst Du ein Object was noch nicht geschrieben wurde, schreibst Du es komplett rein statt dem Pointer, hast Du es schon geschrieben, schreibst Du nur die "Adresse" in die Datei rein. Beim Lesen gehst Du umgekehrt vor. Du pflegst beim Lesen eine Liste mit "Adresse in Datei" zu Pointer im Speicher. Damit das ganze klappt, musst Du beim Schreiben und Lesen noch einen "Header" reinschreiben/auslesen, der angibt ob es sich um ein Objekt oder eine Adresse handelt. So in der Art machen das viele Standardbibliotheken.
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Spiele Programmierer »

Krishty hat geschrieben: 23.02.2021, 02:07Fun Fact ohne Wertung: Visual C++ unterstützt das nativ via __based. Eines der Features, die ich schon immer mal ausprobieren wollte, aber ganz genau weiß, dass ich damit die Tore zur Hölle aufstoßen würde :)

Der Artikel zeigt auch noch eine weitere Möglichkeit auf: Du kannst deinen Allokator reproduzierbar schreiben, da VirtualAlloc() und MapViewOfFile() eine Basisadresse akzeptieren. Die merkst du dir und kannst beim nächsten Laden alle Zeiger 1:1 wiederverwenden.
Sehr interessant! Leider sieht es aber so aus, als ob weder GCC noch Clang da etwas Vergleichbares anbieten. Daher müsste man bei portabler Software ja dann doch wieder manuell schreiben. Es sei denn, __based hat massive Vorteile bei der MSVC Kompilierzeit/Qualität des generierten Codes. In dem Fall könnte man beides verwenden. :/

Wenn man die zweite Variante mit VirtualAlloc/MapViewOfFile benutzt, gibt es da eigentlich eine Möglichkeit einen Speicherbereich vorab zu reservieren? In einer Windows-PE-Datei/Linux-ELF-Datei gibt es so ein Feature meines Wissens nämlich nicht. Ich hatte da jedenfalls schonmal für einen ganz anderen Anwendungsfall geschaut und nichts gefunden. Und ohne so eine Funktionalität könnte es wegen ASLR ja dazu kommen, dass beim Programmstart dein Wunschort schon belegt ist...

Ein weiterer Nachteil bei der zweiten Variante ist noch, dass man dann natürlich nicht zwei Dateien gleichzeitig im selben Programm öffnen kann.

Außerdem gibt es noch einen allgemeinen Nachteil bei dem Verfahren, an den ich gestern Abend gar nicht mehr gedacht habe: In C++ muss man tierisch aufpassen, dass das Speicher-Layout passt. Wenn man nicht mehr in die Standard-Layout-Typ-Kategorie fällt, kann es theoretisch mit verschiedenen Compilern (und noch theoretischer sogar schon mit verschiedenen Compiler-Versionen) zu inkompatiblen Speicherständen führen. Außerdem darf man nicht long benutzen, das bei Linux/Windows verschieden groß ist (Okay, davon lässt man am besten eh die Finger!). Ebenso size_t, wenn es zwischen 32 Bit und 64 Bit transferierbar sein soll. Ich denke das kann man alles regeln, aber direkt entspannt abspeichern sieht anders aus und es ist mal wieder for allem eins: Fehleranfällig. Jedenfalls wenn Speicherstände zwischen verschiedenen PCs und Versionen deiner Software kompatibel sein sollen, muss man da wirklich aufpassen.
xq hat geschrieben: 23.02.2021, 09:38 Generell würde ich einfach ein Pointer→ID-Mapping anlegen, und einfach mit "first come, first serve" serialisieren. Aber noch eine wichtige Frage:
Sind deine Entities alle gleich (as in: alles eine instanz der selbe Klasse, üblich bei ECS) oder hast du einen Vererbungsbaum und musst dementsprechend einen Typ mit deserialisieren?
Ah, das ist auch ein interessanter Vorschlag. Das ist ja im Prinzip eine Erweiterung von meinem zweiten Vorschlag.

Ich denke, dadurch kann man die etwas weniger hübsche Situation vermeiden, dass in einem Objekt noch ungeladene Daten vorliegen und das Objekt schon sichtbar ist.

Die Schwierigkeit, dass sich das nur elegant via Rekursion implementieren lässt und dadurch je nachdem wie dein Spiel so aufgebaut ist immer Stapelüberlaufe möglich werden, ist aber so weit ich das sehe, weiterhin vorhanden. Ein weiterer Nachteil ist auch noch, dass man "objektorientiert" laden muss und dabei auch noch ständig in der Datei hin- und herspringt. Dadurch scheidet es für meine Anwendung leider aus.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Krishty »

Spiele Programmierer hat geschrieben: 23.02.2021, 18:21Wenn man die zweite Variante mit VirtualAlloc/MapViewOfFile benutzt, gibt es da eigentlich eine Möglichkeit einen Speicherbereich vorab zu reservieren? In einer Windows-PE-Datei/Linux-ELF-Datei gibt es so ein Feature meines Wissens nämlich nicht. Ich hatte da jedenfalls schonmal für einen ganz anderen Anwendungsfall geschaut und nichts gefunden. Und ohne so eine Funktionalität könnte es wegen ASLR ja dazu kommen, dass beim Programmstart dein Wunschort schon belegt ist...
Naja, bei 48–64 Bits Adressraum auf aktuellen Maschinen würde ich mir um Bibliotheken keine Sorge machen. Falls du 1 GiB an Daten brauchst, hast du eine 1:262144-Chance (oder besser). Falls du sichergehen möchtest, wird es natürlich sehr schmutzig.
Spiele Programmierer hat geschrieben: 23.02.2021, 18:21Ein weiterer Nachteil bei der zweiten Variante ist noch, dass man dann natürlich nicht zwei Dateien gleichzeitig im selben Programm öffnen kann.
… stimmt absolut, danke!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Vielen Dank für die ganzen Antworten schonmal.
Chromanoid hat geschrieben: 23.02.2021, 10:25 Bau in Dein Archive ein writeObjectWeakPtr / readObjectWeakPtr ein. Da steckst Du dann deine Pointer rein. Beim Schreiben merkst Du Dir eine Liste mit Pointer zu Stelle in Ausgabe-Datei. Schreibst Du ein Object was noch nicht geschrieben wurde, schreibst Du es komplett rein statt dem Pointer, hast Du es schon geschrieben, schreibst Du nur die "Adresse" in die Datei rein. Beim Lesen gehst Du umgekehrt vor. Du pflegst beim Lesen eine Liste mit "Adresse in Datei" zu Pointer im Speicher. Damit das ganze klappt, musst Du beim Schreiben und Lesen noch einen "Header" reinschreiben/auslesen, der angibt ob es sich um ein Objekt oder eine Adresse handelt. So in der Art machen das viele Standardbibliotheken.
Ok, aber das lässt doch weiterhin die Frage offen, wie man beim Laden mit Zeigern umgeht, die noch nicht geladen wurden. Denn zu Beginn kennt man die Speicherposition ja noch nicht, außer man weiß, wo das Objekt einmal im Speicher landen wird, etwa weil man ihn bereits allokiert hat.
Also im wesentlichen ist das ja auch mein ursprünglicher Vorschlag (man schreib eine ID anstatt des Zeigers, wo die ID herkommt kann man sich ja noch überlegen), aber die Reihenfolge bei der Auflösung dieser IDs muss man dann eben noch beachten.


Bisher sagen mir diese ganzen low-Level Lösungen glaube ich nicht so zu. Sicherlich mögen die effizient sein, aber meine Ladezeit ist ganz klar Asset-dominiert. Ich schreibe derzeit auch ohnehin keine ganzen Objektblöcke binär in die Datei sondern wirklich Variable für Variable. Zum einen weil noch ein paar Sicherheitsmechanismen eingebaut sind die erkennen wenn man versucht Dinge aus der Datei zu lesen, die da nie reingeschrieben wurden (damit man eine vernünftige Fehlermeldung anstatt eines Crashs bekommt), zum anderen speichern Objekte teilweise wirklich nur einen Teil ihrer Eigenschaften in die Datei (e.g. Infos über die Bounding Box die bei jedem Laden aus einem potentiell veränderten Mesh kommen).

Zykel auflösen und erkennen ist auch schwer. Ich denke dabei nichtmal primär an die Algorithmen, aber wie gesagt, Referenzen können in Unterobjekten von Unterobjekten von Entities vorkommen, ich bräuchte also zunächst einmal sehr viel Boilerplatecode um überhaupt zu wissen, wo meine Referenzen sind, bevor ich irgendeine Zykelanalyse starten kann. Alleine auf diesen ersten Schritt habe ich schon keinen Bock.

Aktuell finde ich glaube ich noch die Methode mit dem Callback am nettesten, vor allen Dingen weil sie minimalinvasiv ist. Ich weiß noch nicht, ob ich das ID-Management über die Archive oder SceneManager Klasse machen will, aber in jedem Fall hört sich das nach etwas an, was man sehr nett kapseln kann. Und in der Regel sollten alle Objekte beim Laden soweiso nur Werte kopieren und keine Logik ausführen, wodurch dieser kurze Moment des unvollständigen Initialisiertseins unproblematisch sein dürfte.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von xq »

Okay, da hier alles etwas komplizierter ist und meine Frage noch nicht so wirklich beantwortet wurde:

Wir sind in C++, brauchen also sowieso irgendein ID=>Typ-Mapping, um überhaupt die Daten in die korrekten Klassen deserialisieren zu können (oder wir haben keine Vererbung, Entities sind flat und alle vom gleichen Typ und machen das Problem um Faktoren trivialer)

Mein Gedanke in Pseudocode:

Serialisierung:

Code: Alles auswählen

struct SerializeMapper
{
    uint32_t limit = 0;
    Map<void*, uint64_t> entity_mappings;
    
    template<typename T>
    uint64_t get(T * ptr) // returns id with pointer type and unique index
    {
        auto id_or_null = entity_mappings.get(item);
        if(id_or_null != null) {
            return id_or_null | (ptr->typeId() << 32);
        }
        limit += 1;
        entity_mappings.insert(item, limit);
        return limit | (ptr->typeId() << 32);
    }
};

void serialize(OutputStream stream, List<Entity*> entities)
{
    SerializeMapper mapper;
    for(Entity * entity in entities)
    {
        stream.write(mapper.get(entity));
        for(auto property : entity->properties)
        {
            if(property.type == entity_pointer)
            	stream.write(mapper.get(property.value));
        }
    }
}
Deserialisierung:

Code: Alles auswählen

struct DeserializeMapper
{
    Map<uint32_t, char*> entity_mappings;
    
    template<typename T>
    char * get(uint64_t id) // returns 
    {
        uint32_t index = id & 0xFFFFFFFF;
        auto ptr_or_null = entity_mappings.get(index);
        if(ptr_or_null != null) {
            return ptr_or_null;
        }
        uint32_t type_id = (id >> 32);
        char * ptr = malloc(getSizeOfType(type_id));
        entity_mappings.insert(index, ptr);
        return ptr;
    }
};

List<Entity*> deserialize(InputStream stream, )
{
    List<Entity*> entities;
    DeserializeMapper mapper;
    
    while(true)
    {
        uint64_t id = stream.read(uint64_t);
        
        void * entity_ptr = mapper.get(id);
        
        new (entity_ptr) TheRightEntityType;
        
        for(auto property : entity->properties)
        {
            if(property.type == entity_pointer) {
            	property.value = mapper.get(stream.read(uint64_t));
            }
        }
    }
    
    for(Entity * entity in entities)
    {
        stream.write(mapper.get(entity));
        for(auto property : entity->properties)
        {
            if(property.type == entity_pointer)
            	stream.write(mapper.get(property.value));
        }
    }
}
Die Pointer müssen ja zur Zeit der Initialisierung noch nicht valide sein, also kannst du einfach den Speicher für deine Entities allozieren, aber uninitialisiert lassen und die Entities einfach linear aus deinem Stream lesen. Wenn du eine Entity liest, initialisierst du deren Speicher. Dass der Speicher an der Stelle schon von einer vorherigen Entity alloziert wurde, spielt ja keine Rolle.

Grüße
xq
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4252
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Chromanoid »

Jonathan hat geschrieben: 24.02.2021, 15:56 Ok, aber das lässt doch weiterhin die Frage offen, wie man beim Laden mit Zeigern umgeht, die noch nicht geladen wurden.
Das verstehe ich nicht. Diesen Fall gibt es nicht. Beim Schreiben schreibst Du beim ersten "Serialisieren" eines Pointers immer direkt das Objekt (Feld für Feld). Sobald Du das zweite Mal darauf stößt schreibst Du bspw. die Adresse in der Datei bzw. eine ID, die beim ersten Schreiben vergeben wurde (gemerkt in einer Map Pointer -> ID). Du musst da lediglich einen kleinen Header einbauen, der angibt, ob es sich um das Objekt direkt handelt oder um eine ID. Beim Lesen musst Du das Objekt beim ersten Einlesen auch gleich allokieren und die Adresse in einer Map für die ID merken. Beim nächsten Mal wenn Du auf den Pointer triffst, hast Du es ja schon allokiert und kannst einfach den bereits entstandenen Pointer aus der Hilfs-Map (ID->Pointer) setzen. Das Verfahren kann automatisch mit Zyklen umgehen.

Sonst lese Dir vielleicht mal https://docs.oracle.com/en/java/javase/ ... tream.html durch. Hier der Quellcode https://github.com/openjdk-mirror/jdk7u ... tream.java / https://github.com/openjdk-mirror/jdk7u ... tream.java

Beim Schreiben der Adresse in der Datei als ID kannst Du sogar von unterschiedlichen Punkten im Graphen beim Deserialisieren starten - z.B. falls Du noch einen Index für wichtige Objekte einbauen möchtest. Kann man z.B. machen in dem man am Anfang der Datei Platz für einen Header in der Datei lässt, der dann auf den Index verweist. Dann kann man alles in einem Rutsch durchschreiben (Index ganz am Ende) und muss am Ende nur den Header-Platzhalter mit der Adresse des Index überschreiben (oder man setzt einen Verweis ans Ende der Datei, was ich aber nicht so schön finde).
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Ok, ich glaube ich verstehe, was du meinst. Wenn man zwei Objekte hat (A, B) und A zeigt auf B und dieser Zeiger ist irgendwo in der 'Mitte' vom Objekt gepspeichert, dann schreibt man A nicht komplett in die Datei, sondern schreibt B als Bestandteil und nicht als Referenz von A in die Datei. Beim Laden von A 'unterbricht' man den Ladevorgang dann und lädt erst B vollständig, bevor man den Rest von A liest. Ich war davon ausgegangen, dass A und B kompakt für sich und nacheinander in der Datei stehen.

Ich überlege gerade noch wie das mit der Ownership der Objekte aussieht. Momentan benutze ich shared_ und weak_ptr, vielleicht trifft das hier aber besonders auf die Situation mit unique_ptr und normalen Zeigern zu: Der Ladealgorithmus muss am Anfang der Besitzer der Objekte sein, gibt den Besitz aber ab, sobald der entsprechende unique_ptr geladen wird. Ich sehe gerade kein prinzipielles Problem mit der Umsetzung, das ist aber auf jeden Fall etwas, worauf man achten muss. Insbesondere wenn man davon ausgehen will, dass Laden auch mal fehlschlagen kann und man dann garantieren will, dass keine Leaks entstehen.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4252
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Chromanoid »

Ja bzgl. sowas musste ich mir nie Gedanken machen, da ich schon lange nicht mehr ohne automatisches Memory Management gearbeitet habe... Vielleicht kann man sonst auch Informationen zu Ownership mit speichern. Wenn du die Routinen mehr oder weniger selbst schreibst, könntest du auch den (ggf. thread lokalen) Managern der Entities das Allokieren überlassen. Dann kannst du da vielleicht einiges an Problemen hin auslagern.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Hm, mir fällt da noch ein Problem ein: Was, wenn ich einen Zeiger auf ein Objekt A speicher, dass nicht per unique_ptr o. ä. gehalten wird, sondern Member eines anderen Objektes B ist? In diesem Fall muss ich sicherstellen, dass Objekt B zuerst geladen wird, da ich ansonsten Objekt A z.B. per new erstellen müsste und danach seine Speicheradresse nicht mehr ändern kann.

Bisher sieht mein System so aus, dass ich nur unique_ptr speichern und laden kann, denn die kann man immer direkt und ohne Fallunterscheidung abfrühstücken. Meine Objekte haben durchaus ein paar Zeiger, aber dann eher auf den SceneManager oder so, und die werden außerhalb der Laderoutine gesetzt. Wenn ich einen Spielstand lade will ich ja eben nicht absolut alles neu laden, die GUI bleibt z.B. unverändert bestehen. Deshalb ist eine Lösung, die komplette Objekthierarchien serialisiert nicht das, was ich brauche oder will. Ich denke also, dass ich weiterhin das Laden von Rohzeigern nicht generell unterstützen will und die Zeiger auf Entities als Sonderfall behandle (vermutlich durch die oben skizzierte Callback-Lösung). Das ist bisher (und auf absehbare Zeit) der einzige Fall, wo ich das brauche, und wenn man ein allgemeines System implementiert besteht vielleicht die Gefahr, dass es irgendwann auf eine Art verwendet wird, die nicht robust ist und komische Dinge macht.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Spiele Programmierer »

Ich verstehe das Problem nicht, welches du bei dem Lösungsvorschlag von Chromanoid siehst.

Die Besitzverhältnisse sind zur Ladezeit, soweit ich das sehe, doch eigentlich fast egal. Auch sagt ja niemand, dass du die gesamte Objekthierarchie neuladen willst/musst. Ich verstehe die Lösung so, dass du nach wie vor Member für Member manuell serialisierst in den entsprechenden Lade-/Speicherroutinen. Wenn du einen Zeiger speichern willst (und egal welches Besitzverhältnis vorliegt), guckst du
  • beim Speichervorgang in einer dem Speichern globalen Liste nach, ob das Objekt schon gespeichert wurde. Falls ja, speicherst du eine ID die das bereits gespeicherte Objekt identifiziert. Das könnte z.B. auch ein Byte-Offset in die geschriebene Datei sein oder eine fortlaufende Nummer, die bei jedem Objekt mitgespeichert wird.
  • beim Ladevorgang schaust du, ob du das Objekt direkt laden muss oder ob es bereits vorher gespeichert wurde und nur eine ID/fortlaufende Nummer vorliegt. Im ersten Fall lädst du das Objekt und reihst es in eine Liste ein, so dass spätere Verweise wieder identifiziert werden können. Im zweiten Fall schaust du in eben diese Liste und setzt nur den Zeiger zu dem bereits geladenen Objekt.
Besitzverhältnisse sind meiner Ansicht nach hier kein Problem. Wenn der erste Zeiger der geladen werden soll keinen Besitz hast, ist einfach die Ladeklasser der Besitzer bis du den späteren Besitzer gefunden hast. Das könnte man entweder mit einem strd::variant mit verschiedenen Zeigerklassen und einem "Deleter" lösen, oder man schreibst eine kleine eigene Klasse dafür. Ich habe das immer ConditionalPtr genannt. Im Prinzip ein std::unique_ptr mit optionalen "Deleter".

Das echte Problem sehe ich eher an der potentiell unbeschränkte Rekursion und der relativ hohe Komplextität der Beziehungen zwischen den Objekten, die mal ziemlich unübersichtlich werden könnte.

Mein persönlicher Favorit ist immernoch der erste Vorschlag meiner Liste. Die anderen hast du ja bereits ausgeschlossen (vermutlich zu recht. Ich habe sie vor allem auch der Vollständigkeit wegen erwähnt), aber zu meinem ersten Punkt hast du noch nichts gesagt. Kannst du die Objekte vor dem Beginn des eigentlichen Ladevorgangs erstellen und danach laden? Wenn du keine groß verschachtelten Objekthierarchien hast, sollte das nicht so schwer sein und insgesamt ist die Sache meiner Meinung nach am wenigsten konfus.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Bzgl. Besitzer:
Ja, das mit dem unique_ / raw ptr sollte man lösen können, mit etwas zusätzlichem Aufwand. Aber was, wenn ein Objekt ein Member eines anderen ist und gar nicht für sich alleine per new erstellt werden kann? Dann muss man dessen Besitzer auf jeden Fall zu erst erstellen. Der Fall kommt vermutlich nicht oft vor, und ist auch für mich gerade irrelevant, aber es geht mir dabei ein bisschen ums Prinzip, wie man so ein allgemeines System bauen würde.


Bzgl. Lösung Nummer 1:
Jo, das stimmt. Ich werde mir mal anschauen was es bedeuten würde, das einzubauen. Gut möglich, dass ich es so mache :)
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
smurfer
Establishment
Beiträge: 195
Registriert: 25.02.2002, 14:55

Re: Design Pattern fürs Pointer-Speichern

Beitrag von smurfer »

Wie schon zuvor erwähnt sind Handles in Form von IDs recht hilfreich. In der Handle-ID können auch noch weitere Informationen gespeichert werden, maßgeblich ein Zähler, der Aufschluss über die Gültigkeit gibt. Hier ist ein wie ich finde sehr schöner Artikel zur Implementierung von Handles:

https://www.gamasutra.com/view/feature/ ... hp?print=1
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Ich habe vorhin meinen Spielstand meiner gut funktionierenden Siedlung in Landvogt 2 geladen und sie ist sofort den Bach runter gegangen, weil alle Waren die gerade transportiert wurden wegen der hier beschriebenen Problematik nicht Teil des Savegames und somit verloren waren :D
Ich werde das jetzt also endlich auch mal implementieren und erzähle dann nochmal, für welchen Ansatz ich mich entschieden habe, und wie es mir damit ging.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

Du nimmst einfach das:
https://github.com/serialization/ogss

Beschreibst deine zu speichernden Entitäten so:
https://github.com/tyr-lang/tir/tree/master/spec
oder so:
https://github.com/serialization/ogss/b ... elds.skill

Lässt dir eine C++-Implementierung generieren und lebst für immer glücklich und zufrieden.
Wenn du die Spezifikation erweiterst werden dir die alten Savegames beim Laden per zeroinitialization erweitert.
Und wenn du einen Editor dafür in Java bauen willst, kannst du dir eine Java-Implementierung generieren und direkt drauf aufsetzen.

Im Prinzip musst du nur entscheiden, ob du die direkte für die Serialisierung erzeugst oder direkt drauf arbeitest. Es gibt gute Argumente für beides.
Hier: https://github.com/tyr-lang/sleipnir
Arbeite ich direkt drauf, weil der genierte Code Iteratoren über die Instanzen gibt und es bei mir nur sein kann, dass es verwaltete Instanzen gibt.
Wenn du mehrere Dateien hättest oder es auch nicht verwaltete Instanzen geben könnte, würde ich empfehlen beim Serialisieren zu kopieren, weil man relativ viel Lebenszeit verbraten kann, einen abgeschlossenen Graph zu bekommen.

Für OGSS würde ich begrenzten Support anbieten; hab' aber ewig keinen Bug mehr gefunden.

EDIT: Gibt auch einen Viewer für Binärdateien, hab' aber aufgehört daran zu arbeiten, als ich an Tyr weiterarbeiten durfte; für einfache Dateien und Probleme reicht das aber: https://github.com/serialization/ogssView2
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Wie kann ich am besten testen, ob ein Objekt schon gespeichert wurde, bzw. es eindeutig identifizieren?

Mein erster Gedanke war, einfach seine Adresse zu nehmen. Aber in Vererbungshierarchien kann der ja unterschiedlich sein, wenn man beispielsweise einen Zeiger vom Basisklassentyp auf ein vererbtes Objekt hat. Ich bin auf dynamic_cast<void*>(&obj) gestoßen, aber das funktioniert auch nur für polymorphe Typen. Ist das Problem für nicht-polymorphe Typen überhaupt lösbar?
Prinzipiell könnte man sich natürlich mithilfe von std::is_polymorphic eine Funktion basteln, die den dynamic_cast ausführt, wenn dies möglich ist und ansonsten direkt die Adresse nimmt (oder wäre ein static_cast<void*>() irgendwie von Vorteil?), und dem Anwender eben vorschreibt, dass ein Objekt und all seine Zeiger darauf den selben Typen haben müssen.

Alternativ könnten natürlich auch alle zu speichernden Objekte von einer Basisklasse abgeleitet sein, die dafür Unterstützung bietet, aber eine derartige Limitierung wollte ich eigentlich vermeiden.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

Wieso willst du nicht OGSS nehmen?

Aber um deine Frage zu beantworten:
In C++ kannst du für Einfachvererbungshierarchien this als hashkey verwenden, d.h. du machst eine std::unordered_map<void*> und bitcastest einfach die Zeiger dahin.
Generell musst du dir überlegen, was dein Identitätsbegriff ist. Ist ein char* erlaubt? Ist ein char* und ein std::string dasselbe, wenn sie denselben Inhalt haben?
Was ist mit Containern?
Willst du auch komplexe Flache Objekte erlauben?
Willst du Zeiger auf primitive erlauben (z.B. double*)? Gelten dann andere Regeln?

Ohne zu wissen, was du genau machen willst, kann dir das keiner sagen. Sehr wahrscheinlich willst du aber entweder Zeiger haben, die du eben nach void* bitcastest und dann nur über bit-äquivalenz prüfst und sonst alle anderen Werte verschieden sind. Die einzige übliche Ausnahme sind Strings.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Lord Delvin hat geschrieben: 23.07.2021, 14:57 Wieso willst du nicht OGSS nehmen?
Ich wollte eigentlich nacher schreiben, wie ich es jetzt umgesetzt habe, musste dann aber diese Zwischenfrage zur Implementierung stellen.
Gegen OGSS sprach für mich primär, dass ich nicht mein ganzes Framework umschreiben wollte. Das Zeiger-Speichern brauche ich gerade nur an einer kleinen Stelle und ansonsten habe ich eine funktionierende Lösung die an vielen Stellen bereits erfolgreich verwendet wird. Die nun zu erweitern erschien mir zeitsparender. Dazu kommt, dass OGSS jetzt nur mäßig anhand einiger Beispiele Dokumentiert zu sein scheint, was den Einstieg weiter verzögern würde.

Nun zu den Implementierungsdetails:
Ich will nicht alles unterstützen. Zeiger sind strict in besitzende (unique_ptr) und referenzierende (raw ptr) eingeteilt, d.h. für jede Object* Referenz muss zwingend irgendwo ein unique_ptr<Object> gespeichert werden. shared_ptr und weak_ptr werden dann ähnlich behandelt, da ist dann halt der erste shared_ptr der gespeichert/geladen wird der besitzende und alle weitere shared_ptr auf das selbe Objekt werden als referenzierend betrachtet.
Beim Speichern werden für alle Zeiger eindeutige IDs generiert und in die Datei geschrieben. Beim Laden werden alle besitzenden Zeiger direkt geladen, die referenzierenden werden zwischengespeichert und nachdem die ganze Datei eingelesen wurde (und garantiert ist, dass alle Objekte geladen wurden) schließlich passend gesetzt. (Also im Wesentlichen eine verbesserte Variante von Lösungsidee Nr. 3 aus dem Ausgangspost).

Bezüglich this-Pointer: Habe ich dich richtig Verstanden, dass wenn man in der Einfachvererbungshierarchien hoch- oder runter-casted (durch static_cast) sich der Zeiger niemals ändert, sondern nur der Typ? Dann dürfte ja nichts passieren.

Aber wann geht es nicht mehr?

Code: Alles auswählen

class A //base class
class B //interface
class C : public A, public B
Hier dürfte ein C-Objekt ja aus einem A und einem B Objekt bestehen. D.h. wenn ich C zu A caste ändert sich der Zeiger nicht, wenn ich aber C zu B caste verschiebt sich der Zeiger. Wenn ich allerdings einen B Zeiger bekomme, kann ich den zunächst nicht von einem B oder C Objekt unterscheiden. Außer B ist polymorph (und damit C auch), dann kann ich einen dynamic_cast<void*> verwenden um direkt auf die oberste Ebene zu kommen (in diesem Falle also C).

Ich denke für mich ist es ok, Mehrfachvererbung auszuschließen. In diesem Falle sollte ich also immer mit einem static_cast<void*> glücklich werden. Ein Vorteil ist ja auch, dass Ich am Ende des Speichervorgangs feststellen kann ob zu jeder Referenz ein Objekt geschrieben wurde. Der besitzende Zeiger muss ja immer vom größten Typ sein, und ich sehe keinen Fall, wo dieses System fehlschlagen kann, ohne das man es bemerkt.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

Jonathan hat geschrieben: 23.07.2021, 15:51
Lord Delvin hat geschrieben: 23.07.2021, 14:57 Wieso willst du nicht OGSS nehmen?
Ich wollte eigentlich nacher schreiben, wie ich es jetzt umgesetzt habe, musste dann aber diese Zwischenfrage zur Implementierung stellen.
Gegen OGSS sprach für mich primär, dass ich nicht mein ganzes Framework umschreiben wollte. Das Zeiger-Speichern brauche ich gerade nur an einer kleinen Stelle und ansonsten habe ich eine funktionierende Lösung die an vielen Stellen bereits erfolgreich verwendet wird. Die nun zu erweitern erschien mir zeitsparender. Dazu kommt, dass OGSS jetzt nur mäßig anhand einiger Beispiele Dokumentiert zu sein scheint, was den Einstieg weiter verzögern würde.
Das sehe ich ein. Ich bin der Autor, ich kann dir helfen, wenn du willst; ist aber nur ein Angebot.

Jonathan hat geschrieben: 23.07.2021, 15:51 Bezüglich this-Pointer: Habe ich dich richtig Verstanden, dass wenn man in der Einfachvererbungshierarchien hoch- oder runter-casted (durch static_cast) sich der Zeiger niemals ändert, sondern nur der Typ? Dann dürfte ja nichts passieren.

Aber wann geht es nicht mehr?

Code: Alles auswählen

class A //base class
class B //interface
class C : public A, public B
Also erstmal: wenn B ein interface sein soll, dann musst du "class C : public A, virtual public B" nehmen.
Bei der Semantik von virtual inheritance kann ich aber nur davon abraten. Ich kann mir auch nicht vorstellen, dass der Einfachvererbungstrick dann noch funktioniert.
Tatsächlich ist die Antwort, dass du es auf für dein Beispiel für keinen deiner Typen machen darfst, da es sein kann, dass du eine C-Instanz in der Hand haben kannst, sie aber wie eine der anderen aussieht. Mir ist nicht ganz klar, inwieweit das Speicherlayout an der Stelle definiert ist und was davon einfach so gemacht wird, wie ich es kenne. An so Stellen will man sich aber wirklich nicht auf das aktuelle Layout des aktuellen Compilers verlassen.

Ein ähnliches Problem hast du eigentlich auch mit Templates. Da ist meine Erfahrung aber, dass der Compiler nichts macht, was dir entgegenwirkt. Streng genommen gibt es keinen Grund anzunehmen, dass man einen unique_ptr<A> nach unique_ptr<void*> o.ä. casten kann.
Letztlich scheint das für Pointer aber immer zu gehen. Falls hier irgendwer eine Aussage aus den Tiefen des C++-Standards hätte, würde mich das natürlich interessieren ;)

In C++ hast du auf jeden Fall keine Wildcards, was manche Sachen etwas kompliziert macht. Du musst dir aber sowieso überlegen, wie du die Objekte wieder Rekonstruierst. Das kannst du vielleicht nutzen, um dir eine Basisklasse zu erzeugen, die dir dann in gewisserweise auch das Cast-Problem abnimmt, weil du nicht nach void* sondern zu der Basiskasse castest.
Jonathan hat geschrieben: 23.07.2021, 15:51 Der besitzende Zeiger muss ja immer vom größten Typ sein, und ich sehe keinen Fall, wo dieses System fehlschlagen kann, ohne das man es bemerkt.
Solange deine Speicherverwaltung auch sonst richtig ist und du jedes Objekt, dass du irgendwann mal siehst auch schreibst, dann ja.
Serialisierung und Stop-the-world mark&copy GC ist eigentlich dasselbe.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Alexander Kornrumpf »

Lord Delvin hat geschrieben: 23.07.2021, 17:04
Das sehe ich ein. Ich bin der Autor, ich kann dir helfen, wenn du willst; ist aber nur ein Angebot.
Ich habe mehrmals auf den Link geklickt und bin jedes Mal an der fehlenden Readme.md abgeprallt.

Versteh mich nicht falsch, für mich musst du nichts hinzufügen, es geht mir nur darum dass es quasi standard ist, auf github direkt auch irgendein getting started sehen zu können.
smurfer
Establishment
Beiträge: 195
Registriert: 25.02.2002, 14:55

Re: Design Pattern fürs Pointer-Speichern

Beitrag von smurfer »

Hi,

hier wie ich finde ein sehr guter Artikel zu Handles (wie sie auch oft in ECS' verwendet werden), die sich sehr gut zum Serialisieren eignen.
https://gamesfromwithin.com/managing-d ... ationships

Das folgt weitgehend dem Konzept des erwähnten Pointer->ID mappings und ist hinreichend low-level (schnell), weit verbreitet und recht ausgereift.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

Alexander Kornrumpf hat geschrieben: 23.07.2021, 17:20
Lord Delvin hat geschrieben: 23.07.2021, 17:04
Das sehe ich ein. Ich bin der Autor, ich kann dir helfen, wenn du willst; ist aber nur ein Angebot.
Ich habe mehrmals auf den Link geklickt und bin jedes Mal an der fehlenden Readme.md abgeprallt.

Versteh mich nicht falsch, für mich musst du nichts hinzufügen, es geht mir nur darum dass es quasi standard ist, auf github direkt auch irgendein getting started sehen zu können.
Das sehe ich ein. Ist mir ehrlich gesagt nicht aufgefallen :-(
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

smurfer hat geschrieben: 23.07.2021, 19:18 hier wie ich finde ein sehr guter Artikel zu Handles (wie sie auch oft in ECS' verwendet werden), die sich sehr gut zum Serialisieren eignen.
https://gamesfromwithin.com/managing-d ... ationships

Das folgt weitgehend dem Konzept des erwähnten Pointer->ID mappings und ist hinreichend low-level (schnell), weit verbreitet und recht ausgereift.
Hm, ja, das scheint mir ein Ansatz zu sein, gleich eine ganze Reihe von Problemen zu lösen. Nur hab ich das meiste davon längst gelöst, jetzt alles umzustellen würde also nichts bringen:

Objekte verschieben: Das ist sicherlich toll, wenn man wirklich daten-orientiertes Speicherlayout benutzt, also z.B. alle Spielobjekte direkt hintereinander im Speicher liegen, so dass man sie Cache-Effizient verarbeiten kann. Dann muss diese Liste natürlich kompakt sein, d.h. man muss Objekte verschieben. Leider habe ich das kein solches Speicherlayout, sondern eben Entities mit komplizierten Component-Strukturen. Die sind alle auf dem Heap, weswegen ich nie das Problem habe, das Zeiger ungültig werden wenn ich meine Entity-Liste (die aus Pointern besteht) umsortiere.

Gültigkeit von Referenzen überwachen: Dafür verwende ich weak_ptr. An anderen Stellen weiß ich, dass z.B. der SceneManager immer länger existiert als jedes Entity, also tut es da ein raw-Pointer und man muss nie etwas überprüfen.

Speichern: Auch bei den Handles hat man doch das 'Problem', dass man die Objekte beim Laden neu erzeugen muss und dann in seine Handle-Liste die entsprechenden Pointer eintragen muss. Insgesamt scheint mir das auch nicht fundamental weniger Aufwand zu sein als meine aktuelle Lösung, beim Speichern dynamisch IDs zu erzeugen.

Ein Vorteil von meinem aktuellen Ansatz ist es aber denke ich, dass er etwas weniger invasiv ist. Handles haben ja auch eine doppelte Indirektion (Handle-Pointer-Objekt), genau wie weak_ptr (ein Zeiger für den Referenzzähler und einen Zeiger für das Objekt selber). Unique_ptr haben das aber nicht, sind also zur Laufzeit performanter und lassen sich dabei genau so gut speichern.

Derzeit bin ich mit dem Ansatz recht zufrieden, teste aber noch. Die Implementierung hat jetzt grob geschätzt weniger als 100 zusätzliche Zeilen gekostet, die Anzahl der Zeilen die wirklich was machen ist vielleicht halb so viel. Erkauft hab ich mir das natürlich damit, den Benutzer auf ein sehr klares Speichermanagement-Konzept zu beschränken (strikte Umsetzung der Owning- und Non-Owning-Pointer), aber da ich das vorher schon konsequent so gemacht habe, war das für mich keine Einschränkung. Normale Anwender kriegen sicherlich mit OGSS und ähnlichem mehr Features. Früher hatte ich auch tatsächlich mal boost-serialization verwendet, das wurde mir aber zu undurchsichtig (weil ganz viel durch Magie funktioniert, bis es eben irgendwann mal nicht funktioniert aber man gerade die Fälle wirklich nicht debuggen will) und man brauchte diese sack-großen Boost-Header absolut überall.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

Ich hab' jetzt mal zwei Dokutexte verfasst:
Readme und ein Tutorial.
Je nach Feedback kann ich das auch noch etwas ausbauen oder eben nicht.
Ich kann auch mal das Projekt insgesamt vorstellen, falls es hier jemanden interessiert. Waren in Summe bestimmt zehn Mannjahre Forschung und Entwicklung.

Dem ECS-Vorschlag kann ich nicht folgen. Wenn man keine sehr strikten Objektbegrenzungen hat, dann ist das dummes Zeug. Performant ist sowas eh nur bei sehr kleinen Graphen, also unter 10k Objekten. Für kleine Graphen würde ich mich aber eher an Java orientieren: https://docs.oracle.com/javase/8/docs/p ... tocol.html
Das ist an sich gut und wäre auch nach wie vor gut, wenn sie's nicht kolossal mit Customizing und Typisierung verkackt hätten.
Sowas hat in einer Sprache einfach nichts verloren. (transient, wer's nicht kannte)

Ein Problem ist sicher, dass man erstmal denkt man möchte *einfach nur* was speichern und wieder laden.
Dass man dabei eine ganze Reihe an Entscheidungen treffen kann und viele davon nicht mehr revidiert werden können, sieht man oft nicht.
Irgendwann fällt einem manchmal auf, dass die Lösung dann Probleme hat, wenn man zwei verschiedene Dateien lädt oder dass man doch mehr Typen oder mehr Objekte haben will, als man erstmal gedacht hat.
Oder du änderst irgendwo was und alle deine Daten sind nicht mehr lesbar.
Das würde mich jetzt bei Savegames tatsächlich stören.
Kann man aber auch mit ungetyptem JSON lösen.

@Cache-Effizienz: darüber würde ich wirklich nicht nachdenken. Ich hab's getan. Hat sehr viel Zeit gekostet. Bei der Analyse anderer Formate sind mir dann zwei überraschende Dinge aufgefallen: Erstens kannst du froh sein, wenn es überhaupt in allen Konstellationen funktioniert. Zweitens kannst du froh sein, wenn du n Objekte in O(n) Zeit lesen oder schreiben kannst. Man meint, es wäre nicht so schwer, aber da waren auch Lösungen erkennbar in nlogn oder n².
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Lord Delvin hat geschrieben: 25.07.2021, 16:22 Je nach Feedback kann ich das auch noch etwas ausbauen oder eben nicht.
Joah. Ich meine, ich habe das Problem für mich soweit jetzt erstmal gelöst, glaube ich. Mich würde es also nicht unbedingt aus Benutzer-Sicht interessieren, sondern wegen der Konzepte und Lösungen. Das Problem ist so ein wenig, dass ich realistisch gesehen jetzt kein 10-seitiges Paper dazu lesen würde. Aber eine Präsentation im Stil von "5 überraschende Probleme beim Speichern von Spielzuständen und wie wir sie lösten" fände ich vermutlich interessant. Vermutlich gab es eher 20 oder noch mehr interessante Probleme, aber interessante Probleme gibt es irgendwie auch überall, und wenn ich nicht gerade auf die Lösung angewiesen bin, ist es eher unwahrscheinlich, dass ich dazu ein halbes Buch lesen würde. Was ich vermutlich sagen will: Wegen mir musst du dir nicht super viel Mühe machen, reinschauen würde ich aber mal.

Aber du könntest natürlich ganz prinzipiell überlegen, ob du das Projekt noch pushen willst. Es dürfte ja auch diverse (internationale) Game-Dev Seiten geben, auf denen man das gewiss mal Bewerben könnte. Wäre ja vermutlich nett ein paar mehr User zu haben. Dafür bräuchte man vermutlich eher einen Artikel Richtung "5 Gründe, warum deine Savegames schlecht sind und eine Lösung für alle" :D
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Lord Delvin »

file:///home/feldentm/Downloads/final.pdf
§5.2.1 bis einschließlich §5.2.4.
Das erklärt, wie man Objektorientierung richtig und effizient macht.
Keine Ahnung, ob man es ohne Kontext verstehen kann.

Das Problem ist, wie gesagt, dass man es systematisch unterschätzt und kleine Entscheidungen deutliche Konsequenzen haben.

Wenn du ein konkretes Problem hast, das ich verstehe, versuche ich dir Tipps zu geben ;)
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Design Pattern fürs Pointer-Speichern

Beitrag von Jonathan »

Lord Delvin hat geschrieben: 25.07.2021, 20:42 file:///home/feldentm/Downloads/final.pdf
Du meinst wohl: https://elib.uni-stuttgart.de/handle/11682/9678
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Antworten