PhysicEngine, Fragen zur Datenstruktur

[dmdjt]

Hallo liebe Leute!

Ich lese schon einige Jahre hier mit und kam eigentlich nie wirklich dazu etwas zu erfragen, weil sich durch einiges stöbern praktisch alles klären lässt.
Jetzt hab ich mich hinreißen lassen ein kleines Spiel zu programmieren, das zu einem gewissen Teil auf einer PhysicEngine (nur Feder-Masse-Dämpfung) aufbauen soll.

Die Engine selbst hab ich schön objektorientiert aufgebaut und funktioniert auch ungefähr so, wie ich es mir erwartet habe.

Nur zu langsam um ein ganzes Spiel darauf basieren zu lassen. Selbst wenn es nur 2D ist.

Jetzt möchte ich sie umbauen und mich um die Daten selbst kümmern - möglichst ohne Flexibilität zu verlieren.

Die Daten liegen dann etwa in der Form im Speicher:

Delphi-Quellcode:

x,y,z: array of double;
//alle Werte mit dem gleichen Index gehören zu einem Objekt

Soweit, so gut. Auch Löschen ist zuerst einmal kein Problem, weil die Reihenfolge in der ich durchiteriere, eigentlich egal ist.

Ich möchte aber, dass sich mehrere Objekte Koordinaten teilen können.
Eine Feder muss die Koordinaten einer Masse lesen können, um die Kräfte berechnen zu können.
Außerdem brauche ich eine Liste von Kräften, die an einer Masse angreifen (Schwerkraft, verschiedene Federn,...).
Ich hab also haufenweise Querverweise.
Und genau da wird das Löschen von Elementen zu einem riesigen Problem:
Lösche ich irgendwelche Koordinaten aus dem Array, zeigen alle auf Koordinaten nach diesen zeigende Elemente auf einen falschen Index.

Ich würde es gerne vermeiden, alle Pointer zu kontrollieren, ob sie angepasst werden müssen.
Statt einfachem Löschen und Neuaufbauen aller Arrays würde ich so oder so einfach das zu löschende Element durch das letzte ersetzen. Dann zeigen auch praktisch alle Pointer auf die richtige Stelle im Array.
Aber die Pointer, die vorhin auf das letzte Element gezeigt haben, müssen geändert werden... und möglicherweise noch existierende Pointer auf das gelöschte Element müssen auch entfernt werden.
Das Problem mit dem letzten Element würde ich mit einem Referenzzähler und einer "Nachsendeadresse", einem Pointer auf die neue Position lösen. Wenn die Nachsendeadresse <> nil ist, werden die Pointer aktualisiert und der Referenzzähler dekrementiert. Ist der Zähler bei 0, wird das Element gelöscht oder als gelöscht markiert.

Ich weiß nur nicht, wie ich die Pointer die noch auf das gelöscht Element zeigen, entfernen kann?!

Denke ich da überhaupt zu umständlich und gibt einen einfach Weg für die ganze Geschichte?

Oder bin ich überhaupt komplett auf dem Holzweg?

Ich wäre für so ziemlich jede Anregung dankbar!

(P.S:
Natürlich hab ich auch Listen ausprobiert. Aber die scheinen doch DEUTLICH langsamer als Arrays zu sein

[mkinzler]

Ich würde einen Record für einen Punkt erstellen und dann einenn Array/eine Liste dafür erstellen.

Delphi-Quellcode:

type
  TPunkt = Record
    x,y,z,n: Double;
  end;

var
  Punkte : Array of TPunkt;

Und die Flächen verweisen dann auf Punkte und Objekte bestehen aus Flächen.

[Namenloser]

Hi, ich würde erst mal einen Profiler hernehmen, um zu schauen, was überhaupt genau der Flaschenhals ist. Nicht, dass du viel Energie in die Optimierung der falschen Stelle investierst.

Arrays sind in der Regel eine gute Wahl, wenn es um Performance geht.

Falls das Löschen und anschließende Updaten der Referenzen wirklich der Flaschenhals ist, dann würde mir spontan die Lösung einfallen, einfach beim Löschen Lücken im Array zu lassen, statt sie direkt wieder zu füllen. Das Array wird dann zwar etwas fragmentieren, aber so schlimm ist das nicht. Wenn ein neues Element eingefügt wird, dann wird es einfach in die erste freie Lücke eingefügt.

[dmdjt]

Danke für die schnelle Antwort!

Mit Rrecord hab ich es schon probiert. Da brauchen die Zugriffe im Schnitt 10% länger.

Außerdem löst das mein Problem mit dem verschobenen Index leider nicht :-(

[dmdjt]

Wow, das geht ja schnell! Danke!

Das Problem am Löschen ist, das zwischenzeitlich immer wieder einzelne Elemente gelöscht werden müssen... und dann mit einem neuen Abschnitt im Spiel doch auch wieder eine größere Menge. Das resultiert dann in plötzlichen Rucklern. Ich dachte mir auch, dass ich die Elemente einfach im Array belassen könnte und sie einfach als gelöscht markiere. Ab so steigt dann der Speicherverbrauch unvorhersehbar, wenn ich mich im Spiel hin -und herbewege. Es ist mir irgendwie unsympathisch, wenn ich nicht ungefähr vorhersehen kann, was sich im Hintergrund tut.

Ich hab mir jetzt gedacht, ich lasse einfach einen "Generationszähler" mitlaufen. Immer wenn ein Element in einem Array ersetzt wird, steigt der Zähler an. Referenzen gelten nur für eine bestimmte Generation.

Hat vielleicht Jemand noch eine bessere Idee?

Hat vielleicht Jemand noch eine bessere Idee als meine?

[Namenloser]

Zitat:

Zitat von dmdjt (Beitrag 1269455)

Das Problem am Löschen ist, das zwischenzeitlich immer wieder einzelne Elemente gelöscht werden müssen... und dann mit einem neuen Abschnitt im Spiel doch auch wieder eine größere Menge. Ich dachte mir auch, dass ich die Elemente einfach im Array belassen könnte und sie einfach als gelöscht markiere. Ab so steigt dann der Speicherverbrauch unvorhersehbar, wenn ich mich im Spiel hin -und herbewege. Es ist mir irgendwie unsympathisch, wenn ich nicht ungefähr vorhersehen kann, was sich im Hintergrund tut.

Das sollte eigentlich nicht passieren. Du darfst nur nicht neue Elemente immer am Ende des Arrays einfügen (und es ggf. vergrößern). Merke dir die freien Stellen und füge neue Elemente dort ein. Solange es noch irgendwo eine Lücke gibt, darf das Array nicht vergrößert werden.

Dann sollte das Array irgendwann seine maximale Größe erreichen und anschließend nicht weiter wachsen.

Wenn es dir immer noch unsympatisch ist, dass womöglich recht viel Speicher belegt wird, der eigentlich nicht genutzt wird, dann kannst du ja in regelmäßigen Abständen das Array "komprimieren" (bzw. defragmentieren) und zurechtschrumpfen. Wird sich aber wahrscheinlich nicht lohnen.

[dmdjt]

Namenloser, lieben Dank fürs Nehmen meiner Ängste! :D

Das hab ich nämlich komplett übersehen.

[Aphton]

Bei soetwas zeitkritischem ist das Ändern der Größe eines Arrays (De-Allozieren) kontraproduktiv.. Daher ist es besser, dass man z.B. ein Array mit einer fixen Länge dynamisch anlegt; man merkt sich mit einer Zusatzvariable die "eigentliche" Länge und vergrößert/verkleinert immer um das Doppelte/Halbe, wenn eine Grenze erreicht wird.

Wenn zusätzlich die Reihenfolge der Elemente des Arrays keine Rolle spielen, so kann man das Löschen einzelner Elemente dadurch erreichen, indem man das letzte Element des Arrays dem zu löschenden Element zuweist und die Längenvariable reduziert.

Au0erdem - "x, y, z: Array of Double" ist totaler Quatsch! Bitte nimm den "TPunkt" Datentyp.

[Dejan Vu]

Du kannst dein Record erweitern:

Delphi-Quellcode:

Type
  TDaten = record x,y,z,n : double; del : integer end;

// wenn del= 0 ist, dann ist der record gültig
// ansonsten enthält 'del' den Index des nächsten freien Platzes im Array oder -1
var
  ListenGroesse,
  ersterFreierPlatz : Integer; // = -1 am Anfang, oder wenn es keine freie Stelle gibt

Procedure Initialisieren;
Begin
  ListenGroesse := 0;
  ersterFreierPlatz := -1;
End;

Procedure Loeschen (Index : Integer)
begin
  if Liste[Index].Del != 0 then raise Exception.Create('Platz schon gelöscht');
  Liste[Index].Del = ersterFreierPlatz;
  ersterFreierPlatz := Index;
End;

Function NeuerPlatz : Integer;
Begin
  if ersterFreierPlatz = -1 then begin
    if ListenGroesse = MaximaleListenGroesse then raise Exception.Create('Speicherüberlauf');
    ListenGroesse := ListenGroesse + 1;
    Result := ListenGroesse - 1;
  end else begin
    Result := ersterFreierPlatz;
    ersterFreierPlatz := Liste[Result].Del;
    Liste[Result].Del := 0;
  end
end;

Die Idee von Aphton ist noch einfacher, aber genau dann falsch, wenn Du dir merkten musst, das z.B. am Index #5 eine Kuh ist. Denn wenn die Kuh am Ende der Liste ist und ein Element wird gelöscht (z.B. #2, dann wandert die Kuh ja in das Element #2). Und wenn Du dann später die Kuh suchst, isse wech (bzw. nach #2 gewandert).

[dmdjt]

Im Prinzip scheint sich mir damit alles beantwortet zu haben.

Wenn ich ein Element lösche, dann markiere ich es als gelöscht.
Ich denke, das werde ich mit einem Zeiger machen, der falls nicht gelöscht 0 ist, und ansonsten auf das nächste, belegte Element zeigt. Vielleicht ist das ja nützlich wenn es größere Löcher geben sollte, muss ich testen. Ansonsten einfach nur als gelöscht markieren.
Wenn ein Element neu belegt wird, dann erhöhe ich einen Zähler um verbleibende Zeiger als ungültig zu erkennen. Ein Byte sollte reichen, weil ansich alle Zeiger nach einer Runde einmal verwendet - und damit getestet worden sein müssten
Fragmentierung sollte, glaube ich, kein großes Problem sein. Das bedeutet nur wenn viele Elemente gelöscht wurden einen unnötigen Aufwand - und genau da gibt es weniger zu berechnen - und beim Hinzufügen neuer Elemente. Das wird aber vermutlich auch keine Probleme bereiten.

Jetzt muss ich noch aufpassen, dass ich nicht durch Verwaltungsaufwand langsamer als vorher werde :D

Aber falls ich irgendwas übersehen haben sollte, oder es weitere Vorschläge gibt, wäre ich natürlich auch unheimlich dankbar!

[Medium]

Zitat:

Zitat von Aphton (Beitrag 1269462)

Au0erdem - "x, y, z: Array of Double" ist totaler Quatsch! Bitte nimm den "TPunkt" Datentyp.

Bei dieser Art der Verarbeitung ist es kein Quatsch. Das wichtigste ist dabei, dass man so schnell wie nur möglich durch alle Punkte durchrauschen kann, und wenn man sich dabei die Dereferenzierung zu Records spart, ist gar nicht mal so wenig gewonnen. Ich hatte mal aus Spaß eine Stoff-Simulation gebaut (ich komm gerade ums Verrecken nicht mehr auf den Namen vom Algo), und bin am Ende ebenfalls bei Arrays für X und Y (war nur 2D) gelandet, und habe die Relationen mittels Pointern hergestellt. Damit war dann auch ein "Kreuz-Verfedertes" Tuch mit 80x80 Vertices noch schnell genug auf dem Core2Duo damals für ~30fps.
Die "saubere" Vorversion mit Kapeslung und allem ganz hübsch in Hochglanz kam da bei weitem nicht hinter her. So lange man nachher nach aussen alles schön verpackt, finde ich es hier ausnahmsweise mal okay die Datentypen dem Zweck unterzuordnen.

[dmdjt]

Aphton:

Mir ist klar, wie das aussieht und dass es wirklich, wirklich nicht schön ist. Aber wenn ich die so anlege und nicht in einem Record, scheint es zumindest in meinem Test etwa 10% schneller zu sein.

Delphi-Quellcode:

x,y,z : array of double;
z[i] := x[i]*y[i];

//vs.
a: array of TPoint;
a[i].z := a[i].x*a[i].y;

Anstatt das letzte Element zu verschieben, will ich es ja eh einfach nur als gelöscht markieren und dann beim Erstellen eines neuen Elements neu befüllen und reaktivieren. Davor hatte ich vor Namenlosers Einwand irgendwie ein ungutes Gefühl... aber eigentlich ist es eh ganz klar.
Auf die Art hab ich auch von außerhalb der Engine eine immer gültige Adresse für ein bestimmtes Element und kann dort so tun, als würde ich mit Objekten hantieren.

Dejan Vu:

Danke für die Tipperei!

Vom Prinzip her werde ich es ganz ähnlich aufbauen.

Ich hab weniger ein Problem das ganze umzusetzen, als dass ich mich vor ein paar Problemen beim Design wiedergefunden habe.

Danke übrigens an alle :)

[dmdjt]

Der Algo hieß ziemlich sicher Verlet Integration ;-)

Habs davor einfach per Euler versucht, aber das wird einfach zu instabil. Deswegen muss man Dämpfungen unnatürlich hoch einstellen und alles wirkt wie unter Wasser oder Honig :D

[Aphton]

Ok, meinetwegen...
Aber in 98% aller Fälle ist das Unfug, da es nicht notwendig ist, solche Optimierungen bereits zu machen. Erst makro, dann micro - vlt habe ich mich beim TE auch nur vertan und er ist auch schon soweit und hat alle Makro-Probleme optimiert..

Edit: Ok, nochmal zurück zu dem; so ganz überzeugt bin ich nicht.
Die Verwendung von Structs/Records sollte in deinem Fall schon schneller sein, wenn man überlegt..:
Array[INDEX] ==> <Größe_Array_Datentype> * Index
--> 3 Multiplikationen schon allein für die Indizierung von x, y und z..
Hätte man stattdessen vergleichsweise ein Record benützt, so hätte man nur 1x Multiplikation für die Indizierung und 2x Additionen für die Offsets im Record/Struct (für x wird nichts addiert, da es sich am Anfang befindet).
Jetzt sagt bloß nicht, dass 1x Mul & 2x Add langsamer ist als 3x Mul
oO

Hab hier kein Delphi zur Hand, deshalb weiß ich leider ned, was der genau für nen Assembler Code ausspuckt, könnte das ganze aber mit C++ testen..

[dmdjt]

Das würde mich ziemlich interessieren!

Assembler verstehe ich zu wenig... und das beißt mir jetzt ein wenig in den A****. Meine Erfahrungen sind leider nie über PIC-Assembler gestiegen. Insofern würde mich das wirklich sehr interessieren!
Von dem her, was Du da schreibst, klingt es mehr als logisch.

Ich bilde mir ein, im Laufe meiner Recherchen gelesen zu haben, dass dieser Aufbau dem Prozessor/Pipeline/ka was entgegenkommt. Aber das habe ich zu wenig verstanden und eher überlesen. Wenn ich es wieder finde, poste ich es.

Ich kann mir allerdings sehr gut vorstellen, dass der Compiler nur eine einzelne Multiplikation daraus macht, weil die Array-Elemente alle double sind und der index auch überall der gleiche ist.
Falls er das so optimiert, dann wäre es auch nur eine Multiplikation + 2x Add.
Vielleicht gleicht sich dann das eine Add durch die Dereferenzierung und weil er die Abstände fürs struct (für die 2 Add) mittragen muss aus?

[Medium]

Verlet! Danke :)

Ich vermute fast, das bei Arrays der schwerer wiegende Anteil ist, dass diese hübsch am Stück im Speicher liegen und nacheinander sehr effizient abgefuttert werden können, auch wenn die Referenzierung am Ende vielleicht mehr Aufwand ist. (Wen das stört, der kann über ein Array auch noch mit Pointer-Arithmetik iterieren, wieder ein Sparpotenzial, dass eine Sammlung von "losen" Records nicht böte.)

Ich will das auch gar nicht beschönigen, das sieht am Ende etwas aus wie Code aus den 80ern. Aber das ist einer der seltenen Fälle, wo ich es aus eigener Erfahrung mit Ausprobieren mehrerer Varianten gerechtfertigt finde. (Grafikkarten legen sich ihre Streams intern nach Möglichkeit nicht ohne Grund aehr ähnlich aus. Stream-Processing macht bei den üblichen Architekturen einfach was aus.)

[dmdjt]

Das komische ist, dass p: array of Tpoint langsamer als x,y,z: of double ist. Zumindest bei dem oben beschrieben Test.

Ich verstehe davon leider zu wenig und hab nie den richtigen Zugang gefunden. Da fehlt mir einiges...:-(

[Aphton]

Zitat:

Zitat von Medium (Beitrag 1269480)

Verlet! Danke :)

Ich vermute fast, das bei Arrays der schwerer wiegende Anteil ist, dass diese hübsch am Stück im Speicher liegen und nacheinander sehr effizient abgefuttert werden können, auch wenn die Referenzierung am Ende vielleicht mehr Aufwand ist.

Das ist genauso auch bei Array of Record's der Fall.
Ein Rekord gibt ja nur an, wie viel Speicher benötigt wird und wie man an die einzelnen Elemente rankommt (Delphi-Record <> Delphi-Class)

Ich habs nun getestet und erstaunlicherweise ist deine Variante doch schneller..

Code:

#define ARR_SIZE 1024 * 1024 /* 1mb */
#define REPETITIONS   3000

double x[ARR_SIZE];
double y[ARR_SIZE];
double z[ARR_SIZE];
point xyz[ARR_SIZE];

int main(int argc, char **args) {
   const double val = 123.456;

   // cpu-warmup
   for (int i = 0; i < REPETITIONS; i++) { }

   // test #1
   int t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++)
      for (int j = 0; j < ARR_SIZE; j++)
         x[j] = y[j] = z[j] = val;
   t = get_tick_count_ms() - t;
   printf("Test #1\t %dms\t x[], y[], z[]\n", t);

   // test #2
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      double *x_ptr = &x[0];
      double *y_ptr = &y[0];
      double *z_ptr = &z[0];
      for (int j = 0; j < ARR_SIZE; j++)
         *x_ptr++ = *y_ptr++ = *z_ptr++ = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t x_ptr, y_ptr, z_ptr\n", t);

   // test #3
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      for (int j = 0; j < ARR_SIZE; j++)
         xyz[j].x = xyz[j].y = xyz[j].z = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t xyz[]\n", t);

   // test #4
   t = get_tick_count_ms();
   for (int i = 0; i < REPETITIONS; i++) {
      point *xyz_ptr = &xyz[0];
      for (int j = 0; j < ARR_SIZE; j++)
         xyz_ptr++->x = xyz_ptr->y = xyz_ptr->z = val;
   }
   t = get_tick_count_ms() - t;
   printf("Test #2\t %dms\t xyz_ptr\n", t);
}

Code:

Test #1    12338ms    x[], y[], z[]
Test #2    11623ms    x_ptr, y_ptr, z_ptr
Test #2    17074ms    xyz[]
Test #2    13396ms    xyz_ptr

[Namenloser]

@Aphton: Ich weiß nicht mehr genau, wo ich es ursprünglich gelesen hatte, aber für hohe Performance wird soweite ich weiß gerade empfohlen, Structs of Arrays zu verwenden statt Arrays of Structs. Den genauen Grund weiß ich nicht mehr, aber es hatte glaube ich irgendwas mit Cache und Vectorization zu tun (wobei der Delphi-Compiler letzteres wohl sowieso nicht unterstützt).