ZFX + Developia

Ich bin ja von euch an einigen Stellen bereits darauf aufmerksam gemacht worden, dass es performance-technisch nicht unbedingt ideal ist, wenn ich meine Objekt (Kollisions-Objekte) alle mittels "new" einfach auf dem Heap erstelle. Ich habe zwar einen Vektor angelegt, doch dieser speichert blos die Zeiger auf die Objekte - nicht die Objekte selbst. Und die Zeiger sind für mich auch wichtig, um einfach mit den Objekten arbeiten zu können und diese in verschiedene Funktionen zu "schicken". Nur ist es ja so, dass wenn ich ein Objekt direkt in einem Vektor anlege (quasi als Alternative), ich nicht mehr mit dessen Adresse arbeiten darf. Denn wenn ich richtig informiert bin, ist dabei nicht garantiert, dass das Objekt auch tatsälich immer an dieser Stelle im Speicher bleibt, oder ob der std::vector aus Gründen des Speicher-Management nicht einfach mal "umschichtet". Im Gegensatzt zur "new" Methode auf dem Heap - wo garantiert ist, dass ich mit einem Zeiger immer gültig auf das Objekt zugreifen kann.

Wie kriege ich es denn nun hin, dass meine Objekte möglichst in Reihe im Speicher liegen und ich diese per Zeiger erreichen kann? Kann ich irgendwie Einfluss darauf nehmen, wo Speicher reserviert wird?

Eine andere Frage am Rande:
Es scheint ja gängige Praxis zu sein, dass man Vektoren als Referenzen übergibt. Wie kann das gut gehen, wenn nicht garantiert ist, dass sich der Speicherort der Elemente nicht ändert? Oder ändert sich einfach die Startadresse des Vektores nicht mehr - im Gegensatz zu den Adressen der Elemente?

Gruss starcow

Einfach ein Array von Objekten mittels new [] anlegen.

Mirror hat geschrieben: ↑22.10.2020, 00:35 Einfach ein Array von Objekten mittels new [] anlegen.

Also quasi auf Reserve? Die Anzahl der Objekte ist ja dynamisch und kann sich natürlich laufend ändern...

Ich nutze dafür eine Bucket List. Die reserviert immer einen Block bestimmter minimaler Größe (z. B. für 32 Objekte) und verkettet die Blöcke untereinander. Beim Traversieren hat man – so lange die Liste voll ist – nur jedes 32. Objekt einen Sprung.

Gibt’s AFAIK nicht in der Standardbibliothek, die müsstest du also wo anders suchen (oder selber schreiben).

Wenn du auf Speicher-Layout optimieren möchtest, ist es übrigens wesentlich effektiver, von Klassen wegzugehen und direkt alles als Struct-of-Arrays aufzuziehen. Insbesondere auch wegen der Möglichkeit, dann SIMD einzusetzen.

Wenn du einen Vektor per Referenz übergibst, hast du einen Zeiger auf einen Zeiger. D.h. wenn sich der Vektor-interne Zeiger auf seinen Speicher ändert ist das kein Problem, da du nicht auf die Objekte direkt sondern nur auf den Zeiger auf die Objekte zugreifst.

Und du kannst ja durchaus per Zeiger auf die Objekte im Vektor direkt zugreifen. Die Zeiger werden nur dann ungültig, wenn du den Vektor veränderst, also z.B. Objekte hinzufügst oder löschst (wobei natürlich auch nicht garantiert ist, dass die Zeiger ungültig werden, du solltest aber natürlich trotzdem immer so tun, als sei das der Fall).

Es gibt halt fundamentale Grenzen: Du kannst nicht immer alle Objekte dicht gepackt hintereinander im Speicher haben, Objekte hinzufügen und löschen und dafür sorgen, dass sich Speicheradressen nie ändern. Das wird sich auch nicht ändern, aber in der Praxis brauchst du halt vielleicht nicht alle 3 Kriterien ganz so dringend.

Was Jonathan sagt.

Grundsätzlich erstmal: Fragmentierung gibt's heutzutage nicht mehr wirklich. Man beschrieb damit das Problem, dass der Adressraum so langsam zerstückelt wurde, wenn man ständig kleine Objekte allokiert und hier und da mal aus der Mitte wieder was rausgelöscht hat. Das war aber nur in 32Bit-Exen ein Problem. Ich vermute mal, Du programmierst Desktop oder Handy im Jahre 2020, und da ist 64bit üblich, und damit hast Du bis zum Hitzetod des Universums genug Adressraum.

Dann gibt's da die "weichen" Faktoren: Cache-Kohärenz. Das ist der leichte Performance-Vorteil, den Du dadurch bekommst, wenn alle für eine Aufgabe nötigen Daten schön nah beieinander liegen. Da schrieb Krishty ja bereits, wie die finale Lösung in extrem performance-bewussten Programmen aussieht: Structures of Arrays. Ich bin da inkonsequenter und mache Arrays of Structures, weil ich diese Programmiermethode bequemer finde.

Schrompf hat geschrieben: ↑22.10.2020, 11:31 Structures of Arrays. Ich bin da inkonsequenter und mache Arrays of Structures, weil ich diese Programmiermethode bequemer finde.

Das finde ich spannend. Ich dachte bisher immer nur an AoS (ich habe mich zugegebener Maßen auch nur kaum damit beschäftigt). Beim Unity3D Entity-Component-System wird soweit ich weiß auch AoS gemacht, es sei denn die basteln da noch was im Nachhinein um. Ich hätte jetzt gedacht, dass das den meisten Entwicklern so geht und "offsets"/"strides" für das Bespielen der Register bei solchen "Massen"-Operationen i.d.R. dazugehören.

Ah, das hier war informativ: https://gain-performance.com/2017/06/15 ... perations/

Ich hab die Frage jetzt auch erstmal so verstanden wie Kristhy, dass starcow momentan std::vector<std::unique_ptr<...>> verwendet und auf std::vector<...> umsteigen möchte, aber weiterhin stabile Zeiger zu den Objekten in den Vektor bewahren will.

Um beliebig viele Objekte hinzuzufügen ist die Lösung von Kristhy gut.

Eine Alternative Methode ist es sehr viel Speicher zu reservieren (z.B. 100 GB, mit mmap/VirtualAlloc) und dann nur soweit zu füllen wie man ihn wirklich braucht. Der Vorteil hiervon ist, dass die Iteration als einfaches Array wieder trivial ist und man die dass man die Objekte sehr effizient im Vektor via ihrem Index nachschlagen kann. Der Nachteil ist, dass man unterschiedliche APIs für Windows und Linux (bzw. generell POSIX) verwenden muss und das man besonders bei 32 Bit Anwendungen mit wenig Adressraum ggf. nicht sorglos genug Speicher reservieren kann, der auf jeden Fall ausreicht.

Egal ob die Krishtys-Blockmethode oder die Speicherreservationsmethode verwendest, möchte ich folgendes zu bedenken geben: Du kannst dann nicht mehr einfach Objekt löschen. Normalerweise würde ja ein "Loch" im Array entstehen. Du musst also entweder leere Dummy-Objekte an der Stelle einfügen (was sehr nervig zu verwalten ist und sehr ungünstig für die Sprungvorhersage und SIMD) oder ein anderes Objekt dorthin verschieben (normalerweise das letzte Objekt der Liste). Und im zweiten Fall musst du wieder Objekte verschieben! Dieses Problem ist sehr nervig. Du musst dann alle anderen Objekte die auf dein Objekt verweisen aktualisieren. Das kann man zwar auch automatisch im Move-Konstruktur anstoßen, aber die Verweise hin und zurück, damit du überhaupt weißt, wer einen Zeiger besitzt der aktualisiert werden muss, sind sehr nervig zu verwalten. Wenn die Verweise von den anderen Objekte nicht ganz so Performance-kritisch sind, kann man auch noch einen Hilfszeiger einrichten. Also du kannst deinem Objekt ein std::unique_ptr<MyClass*> geben und (nur) diesen Zeiger bei Verschiebungen aktualisieren. Andere Objekte dürfen dann nur indirekt auf das Objekt via diesem Hilfszeiger verweisen, der automatisch aktualisiert wird. Das ist nicht ganz so ätzend zu implementieren, aber der Preis ist natürlich, dass der Weg von anderen Objekten aus zu deinem Objekt nun eine doppelte Dereferenzierung erfordert und langsamer geworden ist. Wenn das auch performancekritisch ist, ist das auch nicht optimal.

Wenn es Querverweise zwischen Objekten gibt, gibt es meiner Meinung nach auch gar keine wirklich optimale Lösung.

Noch ein paar Gedanken bezüglich "Structure of Arrays":
Ich würde den "Structure of Arrays"-Ansatz nicht nur für extreme Performance empfehlen. Meiner Erfahrung nach ist das nicht die Art Optimierung mit der man nach vergeblichen Suchen noch ein paar Prozent Effizienz rauskratzen kann (das wäre das ich dann als "extrem" bezeichnen würde), sondern eher die Art wie man ein Modul strukturiert, so dass es um ein Vielfaches schneller läuft.

Ich würde den Ansatz immer empfehlen, wenn man sehr viele Objekte gleicher Bauart hat und ganz besonders, wenn man SIMD verwenden kann/will. Das ist ein wichtiges Kriterium um den Anwendungsfall zu identifizieren, und das Gegenteil kann auch ein Ausschlusskriterium sein. Wenn du z.B. eine GUI programmierst und vlt. ein paar duzend Buttons vom gleichen Typ hast, die noch dazu nicht gleichen Berechnungen durchmachen wozu SIMD geeignet wäre, dann ist der "Structure of Arrays"-Ansatz sicherlich wenig bis gar nicht profitabel. Er ist vlt. sogar kontraproduktiv. "Datenoriertierung" heißt übrigens nicht, überall blind "Structure of Arrays" hinzukleistern, sondern sich genau anzugucken WIE und WOFÜR die Daten benutzt werden und danach das Datenlayout zu optimieren. Wenn eine Operation auf einem einzelnen Objekt sehr viele Eigenschaften benützt (also nicht bloß besitzt, sondern auch zugreift), dann ist das verteilen auf mehrere Arrays gerade schlecht und man sollte gegenteilig "Arrays of Structures" für die die bessere Performance verwenden. Dann lohnt es sich eher zu schauen, dass diese verschiedenen Eigenschaften des selben Objekts sequentiell im Speicher liegen.

Ein konkretes Beispiel hierzu: Wenn man eine Hash-Table programmiert, könnte man denken, man macht am besten zwei parallele Arrays. Eins für die Hashes und eins für die Objekte. ABER: Das ist oft kontraproduktiv! In einer Hash-Table werden nach dem Hash sehr oft die Objekte zugegriffen. Insbesondere: Wenn es nicht mehr in den Cache passt, nützt das separate Array kaum etwas, weil trotzdem in den meisten Cache Lines noch ein Objekt liegt und deshalb fast alle Cache Lines benötigt werden. Deswegen ist in diesem Fall "Arrays of structure" für Hashtables i.d.R. effizienter (außer man benützt SIMD um z.B. die Hashes zu vergleichen, wie beispielsweise die Google-/Abseil-Hashmap). Zu dieser Thematik empfehle ich auch diesen Artikel von Malte Skarupke bzw. den zugehörigen CppCon-Vortrag.

Man kann übrigens auch einen Kompromiss-Weg gehen und einzelne Daten in eigene Arrays oder kleinere Strukturen packen, ohne gleich ALLE Eigenschaften als SoA auszulegen.

Chromanoid hat geschrieben: ↑22.10.2020, 12:11 Ah, das hier war informativ: https://gain-performance.com/2017/06/15 ... perations/

Es gibt in sehr neuen Intel-CPUs in AVX512 (und teilweise AVX2) spezielle Befehle/Intrinsics für Gather- und Scatter-Operationen, die relativ zu früher sehr effizient sind. Simple Lade- und Speicheroperationen sind trotzdem noch besser. Und die Gather-Befehle (AMD unterstützt bisher nur AVX2) haben sehr maue Performance auf AMD-CPUs.

Außerdem ist Cache-Effizienz ein wichtiger Punkt. Wenn du sehr viele Objekte verarbeiten willst, passt nicht mehr alles immer perfekt in den Cache. Deshalb entstehen Latenz- und, besonders übel, Throughput-Probleme dabei, die Daten zur CPU zu bringen. Latenz-Probleme kannst du auch mit Prefetch-Instruktionen lindern bzw. macht die CPU hier ohnehin bereits oft automatisch einen guten Job, aber Throughput-Probleme sind katastrophal. Hier hilft dann nur noch geschickteres Datenlayout wie z.B. mit "Structure of Arrays". (Wenn man beispielsweise das obige Beispiel mit dem Hilfszeiger, um Zeigerinvalidierung zu vermeiden, anschaut: Hier wird man zur Laufzeit diesen Hilfszeiger wahrscheinlich nur sehr selten vom Objekt aus zugreifen. Deshalb würde es den Cache ein bisschen entlasten, wenn man ganzen Hilfszeiger in ein eigenes Array packt im SoA-Stil.)

Wiedermal die geballte Kompetenz hier! Super, vielen Dank :D (und ein extra Dankeschön an dich, "Spiele Programmierer", für die sehr ausführliche Erklärung)!

Spiele Programmierer hat geschrieben: ↑22.10.2020, 16:25 Ich hab die Frage jetzt auch erstmal so verstanden wie Kristhy, dass starcow momentan std::vector<std::unique_ptr<...>> verwendet und auf std::vector<...> umsteigen möchte, aber weiterhin stabile Zeiger zu den Objekten in den Vektor bewahren will.

Ich finde den Weg mit Vektoren, die nur Zeiger enthalten (ich arbeite mit raw pointern) grundsätzlich sehr angenehm und würde davon nur abrücken, wenn sich dadurch klare Performance-Verbesserungen ergäben.
Die Begriffe AoS und SoA waren mir bis jetzt nicht bekannt, werde aber nun suchen, was ich dazu an Beispielen finden kann. Es klingt jeden Falls - auch ganz unabhängig von meinem Vorhaben - nach einem wichtigen Konzept, welches es ohnehin zu kennen gilt.
Noch nicht ganz klar ist mir, welche Performance-Vorteile sich dadurch gewinnen lassen, wenn man das Data-Layout entsprechend anpasst. Eher kosmetischer Art - oder, wie du es schreibst "Spiele Programmiere", substanziell?
Als Obergrenze visiere ich an die 1000 Kollisions-Objekte an: Charakteren und Geschosse. Werde wohl aber in den meisten Szenen nicht über 100 hinauskommen. Die Frage ist halt, ob ich mein Programm entsprechend umbauen soll. Keine Frage, dass diese Technik grundsätzlich wichtig zu kennen ist - aber als Anfänger, wie ich einer bin, läuft man bekanntlich schnell Gefahr, "vom Hundertsten ins Tausendste" zu geraten.
Bei 10% oder mehr, würde ich aber unbedingt die überlegenere Technik mitnehmen wollen.

Jonathan hat geschrieben: ↑22.10.2020, 10:51 Wenn du einen Vektor per Referenz übergibst, hast du einen Zeiger auf einen Zeiger. D.h. wenn sich der Vektor-interne Zeiger auf seinen Speicher ändert ist das kein Problem, da du nicht auf die Objekte direkt sondern nur auf den Zeiger auf die Objekte zugreifst.

Und du kannst ja durchaus per Zeiger auf die Objekte im Vektor direkt zugreifen. Die Zeiger werden nur dann ungültig, wenn du den Vektor veränderst, also z.B. Objekte hinzufügst oder löschst (wobei natürlich auch nicht garantiert ist, dass die Zeiger ungültig werden, du solltest aber natürlich trotzdem immer so tun, als sei das der Fall).

Danke für die Klärung, das macht natürlich Sinn! Ist es denn nicht trotzdem etwas "heiss", mittels Adresse auf Vektoren-Elemente zuzugreifen, selbst unter der Prämisse, dies nur zutun, wenn der Vektor nicht verändert wurde? Kann es nicht sein, dass der Vektor aus "Daten-Management-Gründen" sich zwischen drin mal entschliesst, sich besser zu organisieren? Ist denn garantiert, das dies nur passiert, wenn sich tatsächlich etwas ändert hat?

Gruss, starcow

So wie du es jetzt beschreibst, hört es sich für mich nicht unbedingt danach an, dass ein Optimalfall für SoA vorliegt. Einige hundert Objekte müssten sowieso in die "größeren" der CPU Caches passen. Cache-Optimierungen sind nie ganz verkehrt, aber ich rechne eher nicht mit etwas Weltbewegenden von deiner Beschreibung.

Kannst du noch ein bisschen mehr dazu schreiben, welche Daten du speichern möchtest und welche Art der Berechnungen du durchführen möchtest?

Die Anzahl der Objekte ist so nieder, dass ich aber eher nicht damit rechne das irgendeine Form von spezieller Optimierung notwendig ist.

Solltest du doch mehr Objekte machen wollen oder spezielle Berechnungen machen, die sehr Speicher- und Rechenintensiv sind, wäre mein erster Gedanke nur hierfür einen extra Vektor anzulegen. Also das du, z.B. alle Daten die für die Kollision relevant sind, separat in ihrem Datenlayout optimiert ablegst, so dass du hier gut SIMD verwenden kannst. Für die eigentlichen Objekte kannst du dann ja einfach hin und zurück verweisen. Das Problem mit dem Verschieben ist dann stark vereinfacht und die kannst die komplizierte Spiellogik so lassen wie sie jetzt auch ist.

EDIT:
Wobei, damit sich der obigen Vorschlag mit vielen Objekten lohnt, muss es aber so sein, dass viele Objekte nur die einfachere Berechnung benötigen. Sonst lädt man ja doch alles in den Cache und der Vorteil besteht nur noch für SIMD.

starcow hat geschrieben: ↑29.10.2020, 15:06Kann es nicht sein, dass der Vektor aus "Daten-Management-Gründen" sich zwischen drin mal entschliesst, sich besser zu organisieren? Ist denn garantiert, das dies nur passiert, wenn sich tatsächlich etwas ändert hat?

Ja, ist garantiert. Siehe: https://en.cppreference.com/w/cpp/container/vector (unter Iterator invalidation).

Spiele Programmierer hat geschrieben: ↑29.10.2020, 16:13 Kannst du noch ein bisschen mehr dazu schreiben, welche Daten du speichern möchtest und welche Art der Berechnungen du durchführen möchtest?

Sehr gern!
Ich arbeite die Kollisions-Objekte-Liste einfach chronologisch durch. Der Algorithmus beginnt damit, dass er erstmal abfragt, welche weiteren Objekte in der selben Zelle(n) liegen (spatial hashing). Das sind wenns hoch kommt, vielleicht 4 Linien und 4 weitere Charakteren.
Zu jedem Dieser Objekte wird nun ein kleines Data-Struct erstellt (auf dem Heap). Dort drin gespeichert ist die Distanz zum Objekt und ein Einheitsvektor, der die Richtung zum nächstliegenden Punkt von diesem Objekt weist. Die Zeiger der Kollisionsobjekte werden nun zudem in verschiedene "Behälter" (Vektoren) einsortiert. Je nachdem, ob sie eine minimale Distanz-Toleranz unterschreiten (die Distanz wurde ja bereits berechnet), werden sie als "Kontakt-Objekte" in den Kontakt-Vektor einsortiert oder in einen, der alle weiter entfernten Objekte "sammelt".
Die Data-Structs werden gelöscht, nachdem dieser Algorithmus endet und der nächste Kandidat an die Reihe kommt.

Die Anzahl der Objekte ist so nieder, dass ich aber eher nicht damit rechne das irgendeine Form von spezieller Optimierung notwendig ist.

Solltest du doch mehr Objekte machen wollen oder spezielle Berechnungen machen, die sehr Speicher- und Rechenintensiv sind, wäre mein erster Gedanke nur hierfür einen extra Vektor anzulegen. Also das du, z.B. alle Daten die für die Kollision relevant sind, separat in ihrem Datenlayout optimiert ablegst, so dass du hier gut SIMD verwenden kannst. Für die eigentlichen Objekte kannst du dann ja einfach hin und zurück verweisen. Das Problem mit dem Verschieben ist dann stark vereinfacht und die kannst die komplizierte Spiellogik so lassen wie sie jetzt auch ist.

Gute Frage - und für mich nicht leicht zu beantowrten, ob das ganze rechenintensiv ist. In der Summe kommt sicherlich einiges zusammen, aber ganz oft kürzen sie die Routinen auch extrem ab, weil z.B die Distanz zum nächsten Punkt grösser ist, als die geplante Bewegung (und somit eine Kollision a priori ausgeschlossen werden kann). Es ist in erster Linie etwas Vektorgemoetrie (Skalarprodukt, normalisieren, Schnittlinien berechnen, etc.).

Jonathan hat geschrieben: ↑29.10.2020, 17:44 Ja, ist garantiert. Siehe: https://en.cppreference.com/w/cpp/container/vector (unter Iterator invalidation).

Ok! Sehr gut! Danke :-)

Rein aus deiner Beschreibung gewinnst du denke ich erstmal am meisten wenn du auf new und delete während der abfrage verzichtest und die datenstruktueren die du aufm dem heap anlegst wiederverwendest
Also ein gross genuges array zu programmstart anlegen und die darin enthalten Objekte immer wieder nutzen

Krishty hat geschrieben: ↑22.10.2020, 09:59 Ich nutze dafür eine Bucket List. Die reserviert immer einen Block bestimmter minimaler Größe (z. B. für 32 Objekte) und verkettet die Blöcke untereinander. Beim Traversieren hat man – so lange die Liste voll ist – nur jedes 32. Objekt einen Sprung.

Gibt’s AFAIK nicht in der Standardbibliothek, die müsstest du also wo anders suchen (oder selber schreiben).

Ist man nicht mit einer std::deque dicht dran? Es gibt zumindest immer wieder Artikel, die die Implementierung so beschreiben und es als lohnenswerte Alternative zum std::vector darstellen.

smurfer hat geschrieben: ↑31.10.2020, 08:26Ist man nicht mit einer std::deque dicht dran? Es gibt zumindest immer wieder Artikel, die die Implementierung so beschreiben und es als lohnenswerte Alternative zum std::vector darstellen.

Stimmt, tut es! Habe ich ganz vergessen.

Matthias Gubisch hat geschrieben: ↑31.10.2020, 08:09 Rein aus deiner Beschreibung gewinnst du denke ich erstmal am meisten wenn du auf new und delete während der abfrage verzichtest und die datenstruktueren die du aufm dem heap anlegst wiederverwendest
Also ein gross genuges array zu programmstart anlegen und die darin enthalten Objekte immer wieder nutzen

Verstehe... du meinst also auf dem heap halten und am Ende der Prozedur "ausnullen"? Gilt das nicht als extrem unsauber?

starcow hat geschrieben: ↑31.10.2020, 00:08 Sehr gern!
Ich arbeite die Kollisions-Objekte-Liste einfach chronologisch durch. Der Algorithmus beginnt damit, dass er erstmal abfragt, welche weiteren Objekte in der selben Zelle(n) liegen (spatial hashing). Das sind wenns hoch kommt, vielleicht 4 Linien und 4 weitere Charakteren.
Zu jedem Dieser Objekte wird nun ein kleines Data-Struct erstellt (auf dem Heap). Dort drin gespeichert ist die Distanz zum Objekt und ein Einheitsvektor, der die Richtung zum nächstliegenden Punkt von diesem Objekt weist. Die Zeiger der Kollisionsobjekte werden nun zudem in verschiedene "Behälter" (Vektoren) einsortiert. Je nachdem, ob sie eine minimale Distanz-Toleranz unterschreiten (die Distanz wurde ja bereits berechnet), werden sie als "Kontakt-Objekte" in den Kontakt-Vektor einsortiert oder in einen, der alle weiter entfernten Objekte "sammelt".
Die Data-Structs werden gelöscht, nachdem dieser Algorithmus endet und der nächste Kandidat an die Reihe kommt.

Verstehe ich das richtig, dass du momentan für jede Kollision in jeden Update-Schritt ein Objekt auf dem Heap allokierst? Wenn dem so ist, solltest du das mal als erstes ändern. Zum Beispiel, kannst du die Informationen direkt in den Vektor einfügen, ohne sie vorher auf dem Heap zu erzeugen. Dann hast du extrem viele Allokationen gespart und die Cache-Lokalität verbessert, da die Kontaktobjekte ja wahrscheinlich bevorzugt gemeinsam verarbeitet werden.
Außerdem, nur für den Fall, dass du das noch nicht machst, solltest du schauen, dass du die temporären Vektoren des Algorithmus nicht vollständig zerstörst, sondern nur clearst. Sonst wird der Speicher immer neu angelegt. Das wäre verschwendete Arbeit.

Wenn du vor allem Zugriffe auf beliebige andere Objekte hast, bietet das lineare Ablegen für sich weniger Vorteile. Ich denke, das lohnt sich dann vor allem noch, wenn man die Objekte nach Position sortiert. In einem Projekt von mir, hat man mehr als eine 4-fache Performance-Steigerung gegenüber einer zufälligen Anordnung, wenn man nach Position sortiert. Die Sortierreihenfolge ist da einfach eine Z-Kurven-Anordnung nach der Position. Für statische Objekte kann man am Besten beim Speichern oder Laden sortieren. Für dynamische Objekte ist es ein schwieriger Tradeoff, wieviel Zeit man zum Sortieren verwenden möchte und wie man das ohne größere Ruckler progressiv macht.

Für Interaktionen zwischen Objekten habe ich gute Erfahrungen damit gemacht, die Interaktionen, während sie auftreten, in unterschiedliche Listen je nach Interaktionstyp einzusortieren. Dann spart man sich den Overhead, der durch die verschiedenen Sprünge zu den unterschiedlichen Abarbeitungsroutinen pro Objekt entstehen würde. Außerdem kann man dann Gather/Scatter-mäßig SIMD für die Interaktionen verwendet. Um SIMD zu verwenden, muss man ja normalerweise mehrere Objekte finden, die die gleiche Berechnung erfordern.

Das alles sind aber nur Vorschläge. Mir scheint, die Objektanzahl ist bei dir gering genug, dass Cache-Ineffizienz nur eine untergeordnete Rolle spielt. Meinem Verständnis nach, sollte das, was ich aus deinem Text entnehme, auch ohne große Optimierung möglich sein.

starcow hat geschrieben: ↑31.10.2020, 00:08 Gute Frage - und für mich nicht leicht zu beantowrten, ob das ganze rechenintensiv ist. In der Summe kommt sicherlich einiges zusammen, aber ganz oft kürzen sie die Routinen auch extrem ab, weil z.B die Distanz zum nächsten Punkt grösser ist, als die geplante Bewegung (und somit eine Kollision a priori ausgeschlossen werden kann). Es ist in erster Linie etwas Vektorgemoetrie (Skalarprodukt, normalisieren, Schnittlinien berechnen, etc.).

Das hört sich jetzt nicht so extrem an. Ich rechne da eigentlich nicht mit größeren Problemen.

Übrigens:
Mathematik ist extrem schnell auf der CPU. Und es gibt Möglichkeiten sie noch schneller zu machen wie SIMD. Nur als Referenzwert: Auf einem aktuellen Prozessor kann man in jedem CPU-Schritt (!) mit AVX 16 Gleitkommazahlen einfacher Genauigkeit addieren oder multiplizieren (d.h. z.B. auf einem Kern ~640 000 000 000 Additionen/Multiplikationen pro Sekunde). Das Problem ist in der Regel vor allem, dieses Potential zu nutzen. ;) z.B. wenn die Abkürzungen in deinen Code relativ zufällig genommen werden oder nicht, kosten die falschen Sprungvorhersagen so viel wie duzende Matheoperationen (potentiell mit SIMD). Wenn man kein SIMD verwendet, bleiben 7/8 ungenutzt. Wenn der Speicher von schlechteren Caches oder vom RAM geladen werden muss, kann die CPU auch brach liegen. Und so weiter.