Handles

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.

Handles

Beitragvon Krishty » 03.02.2016, 15:43

Ich kämpfe wegen meiner APIs gerade mit dem Thema, also halte ich hier mal meine Erkenntnisse fest:

Handles müssen konstant sein

So lange der API-Nutzer nicht explizit was an einem Objekt ändert, darf sich dessen Handle auch nicht verändern. Das ist so offensichtlich, dass man es eigentlich nicht einmal sagen muss. Aber es ist auch so fundamental, dass fast alle Design-Entscheidungen davon abhängen, also muss man sich dessen immer bewusst sein. Vor allem scheidet die Adresse eines Ziels als sein Handle aus, wenn es in einem Array liegt, sonst hat man

  Handle obj1 = createObject();
  Handle obj2 = createObject(); // obj1
wurde soeben verschoben, weil intern das Array reallokiert wurde
  // Crash


Handles niemals verfolgbar machen

Manch einer löst das Problem, indem Handles ihre Kopierkonstruktoren und Zuweisungsoperatoren überschreiben und dem Ziel dann mitteilen, wo sie gerade liegen. Das Ziel führt Liste darüber. Wird das Ziel verschoben, kann es alle seine Handles anpassen. Das ist aus so vielen Gründen eine Schnapsidee, dass ich nur die wichtigsten aufzähle:
  1. Es funktioniert nur in der Sprache, in der man es entwickelt. Der erstbeste Python-Port der API wird das Handle bloß als beliebig kopierbare Zahl ansehen, und dann kracht es überall.
  2. Man weiß nicht, wo der API-Nutzer das Handle speichert. Wenn sich mitten im Programm ein Wert ändert, der in einem const-Array liegt, kann ordentlich was in die Brüche gehen.
  3. OMG die Komplexität
Wenn man das irgendwo liest, sollte man davon ausgehen, dass das nur der Vollständigkeit halber erwähnt wird und nicht, weil es funktioniert. (Tut es nur unter sehr engen Rahmenbedingungen z.B. in Smart Pointers oder Garbage Collection.)


Doppelte Indirektion

Konstante Handle-Adressen erreicht man quasi immer nur durch doppelte Indirektion: Ein Handle ist ein Zeiger auf einen anderen Zeiger zum eigentlichen Ziel. Wird das Ziel verschoben, muss nur der zweite Zeiger angepasst werden. Der erste (also das Handle) ändert sich nicht.

Die meisten Sprachen mit Garbage Collection arbeiten so, damit Objektreferenzen gültig bleiben selbst wenn der Garbage Collector im Hintergrund alles kompaktiert. (Ausnahmen unter engen Bedingungen z.B. für lokale Variablen, jaja.)

Man kann argumentieren, dass man das Problem so bloß um eine Ebene verschoben hat: Statt die Adresse des Zielobjekts konstant zu halten, muss man nun die Adresse des Zwischenzeigers konstant halten. Tatsächlich tappt man da leicht in Fragmentierung. Das Argument ist aber: Wenn ich eine Datenstruktur habe, die Adressen konstant hält (z.B. ein Array, das nur wachsen kann), ist das Hauptproblem verschwendeter Speicher. Aber beim Speichern des Zwischenzeigers ist die Verschwendung viel viel geringer als beim Speichern des eigentlichen Zielobjekts.

Egal, wie man es sonst macht – Hash Tables, oder die Adresse eines Containers mit einem Index in den Container als Handle herumreichen - man hat immer doppelte Indirektion. Anders geht’s garnicht.


Zeiger > Indizes

Wer das Problem vermeiden will, indem er Indizes herumreicht (die ändern sich ja nicht, wenn das Array verschoben wird): Indizes sind scheiße weil sie keine vollständigen Referenzen sind. Man muss immer irgendwie an das Array kommen, auf das man sich bezieht. Wenn das nicht gerade eine globale Variable ist, ist das knifflig. Wenn man die Adresse des Arrays mit herumreicht, verschwendet man Speicher (sizeof(Array *) + sizeof(int) > sizeof(Object *)). Und die doppelte Indirektion hat man immernoch, bloß schlecht versteckt.

Ich mein’s ernst: Es ist die Hölle. Jedes Mal, wenn man was im Objekt nachgucken will, muss man das scheiß passende Array finden. Man wird verrückt.


Debugging

Beim Debugging sollte man die erste Indirektion geschlossener Handles immer allokiert lassen. So kann man bei einem ungültigen Handle Use-After-Free von komplettem Garbage oder verwechselten Handle-Typen unterscheiden. Call Stacks drin speichern ist ebenfalls hilfreich.


Reference Counting

Habe ich wegen persönlicher Abneigung noch nicht ausprobiert (ist für mich immer die letzte Fluchtmöglichkeit, wenn man den Überblick über Besitzverhältnisse aufgegeben hat). Könnte zwingend notwendig sein, wenn Handles an verschiedene Plug-Ins verteilt werden. Mal sehen.


P.S.: Objekte wandern nicht nur im Speicher, wenn sie in Arrays liegen. Bei mir hier werden Raumschiffe, die weit vom Spieler entfernt sind, in einfachere (kleinere!) Datenstrukturen verschoben (Detailabstufung für KI und Simulationstiefe). Das bringt einen enormen Geschwindigkeitsvorteil, aber man will nicht, dass sich dann das Handle des Raumschiffs ändert. Alles so Sachen, die man bei der ersten Planung übersieht.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6476
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Zurück zu Algorithmen und Datenstrukturen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast