• Hallo Gast, du möchtest medizinische Grundlagenforschung unterstützen und die Chance haben, ein Netzteil, Arbeitsspeicher oder eine CPU-Wasserkühlung von Corsair zu gewinnen? Dann beteilige dich zusammen mit dem PCGH-F@H-Team ab dem 21. September an der Faltwoche zum Weltalzheimertag! Wie das geht, erfährst du in der offiziellen Ankündigung.
  • Hallo Gast, du kaufst gerne günstig ein und erfährst oft vor deinen Freunden von interessanten Angeboten? Dann kannst du dein Talent als Schnäppchenjäger jetzt zu Geld machen und anderen PCGH-Lesern beim Sparen helfen! Schau einfach mal rein - beim Test der Community Deals!

Modulo - Rechenzeit

fadade

BIOS-Overclocker(in)
Hi,
wollte mal fragen ob jemand weiß, wie teuer (im Sinne von Rechenzeit) Modulo-Aufrufe sind?

Also z.B.
Code:
int rest = 21 % 5; //rest = 1
Die Frage ist mir überhaupt in den Sinn gekommen, da ich momentan in einer Echtzeitanwendung sehr viel mit Modulo und kleinen Zahlen, etwa [0; 10] arbeite und mir überlegt habe, dass folgende eigene Funktion vielleicht sinnvoller/günstiger wäre:
Code:
int Modulo(int zahl, int rest) {
     while(zahl > 0) {
          zahl -= rest;
     }

     //Differenz sollte nun <= 0 sein, da Schleife beendet, also für Rest das Vorzeichen umdrehen:
     return zahl * -1; //bzw. entsprechende Bit-Operation für int32
}
Mit dem genannten Eingabeintervall sollte die Funktion schlimmstenfalls in etwa 60 Takten oder so resultieren. Der Worst-Case tritt aber nur sehr selten ein, sodass ich praktisch statistisch mal von etwa 20Takten im Schnitt ausgehen würde ...

-> Ist das für (kleine) 32-Bit-Zahlen besser geeignet, als der Modulo-Operator?


PS: Zusatzfrage :D
Ist es noch einmal ein Stück schneller, wenn man mit byte, statt int32 arbeitet? Oder wird in aktuellen CPU-ALUs das eh alles auf 32Bit bzw. 64Bit erweitert?

PPS: Frohes Fest schonmal :)
 

mattinator

Volt-Modder(in)
Erstens optimieren die Compiler sowieso den Code, es sei denn Du programmierst in Assembler. Und außerdem sollte der Befehl evtl. sogar direkt in Hardware (CPU-Befehl) funktionieren.
 

cPT_cAPSLOCK

BIOS-Overclocker(in)
In Rechensystemen ist Modulo so einer der grundlegendsten Rechenbefehle. Viele Sachen laufen indirekt über den Modulo, da musst/kannst du nichts optimieren. Was genau müsste ich aber nochmal in meinem Info-Skript nachschauen... gerade bin ich dazu aber zu faul. Wie schon gesagt wurde wird eh alles durch den Compiler nochmal optimiert, es sei denn, du schreibst das alles direkt im Assembler. Lange Rechenzeit braucht der Modulo jedenfalls nicht.
 

max00

Freizeitschrauber(in)
Also etwas wie Modulo nachzubauen ist sicher nicht schneller wie die Standardimplementierung - das wird ja sowieso oft gebraucht (zumindest ich brauchs oft) und selbst in Mikrocontrollern gibts keine Probleme damit ;-)

Demnach schöne Weihnachten und viel Spaß beim Programmieren! :daumen:
 
TE
fadade

fadade

BIOS-Overclocker(in)
Alles klar, dann werde ich da meine "Optimierungsgelüste" etwas zurückhalten :D
Hatte nämlich gedacht, dass da evtl. auch nur irgendwelche Bitmuster (vom Teiler) mit der Zahl in einer Schleife solange interagieren, bis das Ergebnis feddich ist ...

Über die Implementierung in Hardware/Laufzeiten von Modulo habe ich in einem Skript zu Maschinenbefehlen auf aktuellen x86-CPUs nämlich irgendwie nichts gefunden :huh:
Aber wenn das selbst auf (kleineren?) MikroControllern vorhanden ist wird das schon passen.
 

bingo88

PCGH-Community-Veteran(in)
Ich hatte mal eben was schnell zusammengeklöppelt, mit GCC und Standardsettings kompiliert und da kam auch sowas (Bitshift und Division) bei raus. Der ASM Output der Modulo Operation war jedenfalls wesentlich kürzer als der der "ausgerollten" Schleife. Wie sagte schon Donald Knuth: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." Optimierungen machen nur da Sinn, wo dein Programm (zu) langsam läuft.
 
TE
fadade

fadade

BIOS-Overclocker(in)
Hat die reine Länge des ASM-Codes denn eigentlich so erstmal nichts zu bedeuten, sondern ist nur ein Anhaltspunkt für die Laufzeit? Sprich wenn ich 100 "NOP"s (oder wie diese Leerzyklen heißen) habe und 99 "MOVE"s kann es ja trotzdem sein, dass ein MOVE mehr Takte braucht, als ein "NOP" ... wenn das denn überhaupt stimmt; Rechnerarchitektur ist schon wieder ein Semester her :ugly:

Aber das mit der Disassembly hab ich mir vorhin auch mal grob angeschaut und die Schleife ist bei mir auch wesentlich länger.
 

Skysnake

Lötkolbengott/-göttin
Hi,
wollte mal fragen ob jemand weiß, wie teuer (im Sinne von Rechenzeit) Modulo-Aufrufe sind?

Also z.B.
Code:
int rest = 21 % 5; //rest = 1
Die Frage ist mir überhaupt in den Sinn gekommen, da ich momentan in einer Echtzeitanwendung sehr viel mit Modulo und kleinen Zahlen, etwa [0; 10] arbeite und mir überlegt habe, dass folgende eigene Funktion vielleicht sinnvoller/günstiger wäre:
Code:
int Modulo(int zahl, int rest) {
     while(zahl > 0) {
          zahl -= rest;
     }

     //Differenz sollte nun <= 0 sein, da Schleife beendet, also für Rest das Vorzeichen umdrehen:
     return zahl * -1; //bzw. entsprechende Bit-Operation für int32
}
Mit dem genannten Eingabeintervall sollte die Funktion schlimmstenfalls in etwa 60 Takten oder so resultieren. Der Worst-Case tritt aber nur sehr selten ein, sodass ich praktisch statistisch mal von etwa 20Takten im Schnitt ausgehen würde ...

-> Ist das für (kleine) 32-Bit-Zahlen besser geeignet, als der Modulo-Operator?


PS: Zusatzfrage :D
Ist es noch einmal ein Stück schneller, wenn man mit byte, statt int32 arbeitet? Oder wird in aktuellen CPU-ALUs das eh alles auf 32Bit bzw. 64Bit erweitert?

PPS: Frohes Fest schonmal :)
So genau kann man das nicht sagen. Kommt halt immer darauf an, was man GENAU macht. Pauschalaussagen kannst du da nie treffen. Ein Modulo ist schon deutlich langsamer als eine normale Addition oder Multiplikation. Je nachdem was du aber genau machst, ist es aber dennoch langsamer, wenn du es ohne Modulo machst.

Erstens optimieren die Compiler sowieso den Code, es sei denn Du programmierst in Assembler. Und außerdem sollte der Befehl evtl. sogar direkt in Hardware (CPU-Befehl) funktionieren.
Das ist aber eine SEHR gewagte Pauschalaussage...

Kurze Gegenfrage, macht es einen Unterschied, ob ich:

x=y/2.0

mache, oder

x=y*0.5

?

Denk mal drüber nach, dann wirst du sehen, dass die Sache mit Modulo auch nicht so einfach ist.


In Rechensystemen ist Modulo so einer der grundlegendsten Rechenbefehle. Viele Sachen laufen indirekt über den Modulo, da musst/kannst du nichts optimieren. Was genau müsste ich aber nochmal in meinem Info-Skript nachschauen... gerade bin ich dazu aber zu faul. Wie schon gesagt wurde wird eh alles durch den Compiler nochmal optimiert, es sei denn, du schreibst das alles direkt im Assembler. Lange Rechenzeit braucht der Modulo jedenfalls nicht.
Ach und die Division ist das nicht? :ugly:

Trotzdem ist die Division deutlich langsamer als ne Addition. Deswegen ist die Umwandlung von Divisionen in Multiplikationen ja auch eine der grundlegenden Optimierungen, die ein guter Programmierer direkt beim programmieren macht. Über so was denkst du mit der Zeit gar nicht mehr nach.

Das gleiche bei StructsOfArrays oder ArrayOfStructs

Da hilft dir auch nicht wirklich nen Compiler. Auf der CPU noch relativ, aber eben nicht in allen Fällen. Zudem erkennt man solche Sachen selbst mit Profiling nur recht schwer, kann einen aber doch einiges an Performance bringen.

Derartige Optimierungen sind aber ziemlich zweischneidig und "gefährlich", da man apriori NIE weiß, wieviel es bringt, und ob es im Einzelfall halt nicht doch von der Regel abweicht. Daher ist das Profiling ja auch so wichtig, wenn man mal fertig ist mit dem programmieren. Man kann aber eben doch noch das eine oder andere raus holen durch derartige Erfahrungen.

Ist halt wie in der reinen Mathe auch mit dem lösen von Gleichungen "durch genaues hinsehen" :D Also auf gut Deutsch "Raten auf Grundlage von Erfahrung"

Also etwas wie Modulo nachzubauen ist sicher nicht schneller wie die Standardimplementierung - das wird ja sowieso oft gebraucht (zumindest ich brauchs oft) und selbst in Mikrocontrollern gibts keine Probleme damit ;-)

Demnach schöne Weihnachten und viel Spaß beim Programmieren! :daumen:
Wie gesagt, kommt immer auf den Kontext, also auf den genauen Algorithmus drauf an, den man implementieren will. Je nachdem kann man nämlich gewisse Eigenschaften des Problems nutzen, womit man das Problem einfacher macht und ohne Modulo aus kommt. Am Ende hilft da aber nur eine Komplexitätsanalyse um eine sichere Aussage zu treffen.

Hat die reine Länge des ASM-Codes denn eigentlich so erstmal nichts zu bedeuten, sondern ist nur ein Anhaltspunkt für die Laufzeit? Sprich wenn ich 100 "NOP"s (oder wie diese Leerzyklen heißen) habe und 99 "MOVE"s kann es ja trotzdem sein, dass ein MOVE mehr Takte braucht, als ein "NOP" ... wenn das denn überhaupt stimmt; Rechnerarchitektur ist schon wieder ein Semester her :ugly:

Aber das mit der Disassembly hab ich mir vorhin auch mal grob angeschaut und die Schleife ist bei mir auch wesentlich länger.
Naja, kommt auch immer drauf an, wieviele Schleifendurchläufe du brauchst, und natürlich auch, ob sich an anderen Stellen im Code dadurch was vereinfacht oder verkompliziert.

Kurz um als Zusammenfassung:
Mach ein Profiling deines Programms, und schau WO genau du die meiste Rechenzeit verbrauchst. Im Optimalfall sind das nur einige wenige Zeilen, die für den größten Teil der Laufzeit verantwortlich sind, und um genau die kümmerst du dich.

Wenn das nicht der Fall ist, ist entweder dein Algorithmus nicht sonderlich gut, oder das Problem nicht gutartig, und damit schwer zu optimieren.

PS:
Aus einer Codezeile kann man dir kaum sagen, was schneller ist am Ende.

Wenns wirklich nur um die Modulooperation an und für sich ist, dann wird die Verwendung von Modulo als Funktion schon schneller sein, als dein Nachbau. Ich bezweifle aber, das es dir wirklich nur darum geht..
 
TE
fadade

fadade

BIOS-Overclocker(in)
Moin,

First: :wow: thx für die ausführliche Antwort (um diese Uhrzeit noch^^)

Also dass man wo es geht Multiplikationen statt Divisionen nehmen sollte, habe ich mir auch schon angewöhnt - bzw. Shift-L/R bei Ganzzahlen.


Um mal den Sinn hinter der Sache zu klären:
Ich sitze momentan an einem Algorithmus für dreidimensionale Oberflächendarstellung in dynamischen Detailstufen, sowas wie Level Of Detail halt. Mein Prof sagte mir, dass Nachbarspeicherung da im Prinzip unumgänglich ist. Also habe ich mir verschiedene geometrische Formen angesehen, die die gewünschten Oberflächen gut darstellen und vor allem flüssig bei Ansichtsveränderungen.
Also ein 3D-Modell wird ganz normal mit Punkten und den dazugehörigen Dreiecken geladen und von mir mit einer anderen "Gruppierung" der Dreiecke versehen. Naja, da sollte ich vielelicht nicht so ins Detail gehen.
Jedenfalls haben meine "Gruppen" (Dreiecke, 5-Ecke, 6-Ecke .... 8-Ecke) eine bestimmte Anzahl von Nachbarn und Kindergruppen, wenn man sie unterteilt (tesseliert). Basierend auf meinen Festlegungen sind z.B. die Kinder 0 und 1 von 0,1,2,3 eines Dreiecks immer an der Kante 0 bzw. gerichtet zum Nachbarn 0, die Kinder 1,2 an Kante 1, Kinder 2,0 an Kante 2 und wieder von vorne.
Also wenn ich die beiden Kinder für Kante n brauche, suche ich mir Kind n und Kind (n+1) MOD 3 heraus.

------> Da war auch schon der Modulo :)
Analog dazu habe ich das mit anderen Vielecken und der Suche nach den Eckpunkten und anderen Daten gestaltet.
Da ich für einen Aktualisierungsschritt teils extrem viele dieser Operationen machen muss hat mich halt mal interessiert, ob Modulo da zur Bremse wird bei den kleinen Zahlen.
Allerdings bin ich noch nicht so weit, dass ich wirklich sagen kann, ob das überhaupt ins Gewicht fällt; momentan friemel ich mir eher einen mit einfach verketteten Listen zurecht, die entsprechend langsam sind :ugly:

Darüber hinaus habe ich schon an eine andere "Hashfunktion" gedacht um z.B. die Kinder an Kante n zu suchen, aber die funktioniert dann wieder nicht, wenn ich mal in einer Schleife hochzähle und ich auf einmal über dem Definitionsbereich der Hashfunktion bin ... da hilft Modulo halt, indem er da mit Restklassen immer im Definitionsbereich bleibt.

Um mal kurz den Sinn dahinter erwähnt zu haben, um diese Uhrzeit weiß ich allerdings nicht, ob man noch versteht was ich so von mir gebe :D
 

Skysnake

Lötkolbengott/-göttin
Ich glaub ich kann das schon ganz gut nachvollziehen, was du da machen willst. Was ich da aber im Moment lese an deinen Ideen lässt mich aber ein bischen zweifeln, ob du dir wirklich schon tiefergehende Überlegungen dazu gemacht hast, wie du das Problem "geschickt" lösen kannst. Das Problem ist ja wirklich ganz interessant, aber auch nicht ganz einfach. Muss ja performant sein, sonst interessierts keine Sau.

Hast du eigentlich mal ne Vorlesung "Algorithmen und Datenstrukturen" gehört? Wenn nicht, dann kann ich dir NUR empfehlen das schnellstmöglich nach zu holen. Wenn du derartige Probleme angehst, dann brauchst du vor allem einen guten Algorithmus und eine dazu passende Datenstruktur, bzw. umgekehrt. Die von mir genannte Komplexitätsanalyse ist da ein sehr gutes Hilfsmittel, um sich an zu schauen, ob der von dir erdachte Algorthmus überhaupt Sinn macht, oder eben nicht. Bei solchen Sachen hast du ja, wie schon gesagt immer das Problem, das es eben performant sein muss, ansonsten interessiert es keine Sau, und das macht es nicht gerade einfach...

Eine Vorlesung "Rechnerarchitektur" wäre wohl auch nicht das schlechteste, was dir noch passieren könnte, wenn du noch keine gehört hast. Btw. Bachelor oder Masterarbeit?

Eine ganz WICHTIGE Frage, die du dir stellen solltest ist auch, ob du einmal Objekte erstellst, und dann nur noch aus dem Speicher eben diese Vorlagen abrufst, oder ob du diese Umsetzung nur einmalig machst, und dann eben abspeicherst. Je nachdem wirst du wahrscheinlich auch komplett andere Datenstrukturen wählen.

Mich hat es z.B. SEHR verwundert, das du verkettete Listen verwendest. Mir ist nicht klar, wie du diese genau verwendest und wie du Sie aufbaust, aber verkettete Listen erlauben eben keinen wahlweisen zugriff! Sie sind also sehr schlecht, wenn deine Zugriffe weit auseinander liegen. Verkette Listen sind eigentlich nur bei genau einer Sache wirklich richtig gut, und das ist als FIFO/LIFO und sonst, wenn du sehr viel einfügen und entfernen musst, aber selbst da gibts mit dynamischen Arrays und akkumulierter Effizienz effiziente Algorthmen mit Arrays. Bäume sind noch etwas, was man gut mit Listen abbilden kann. Ansonsten siehts aber eher schlecht aus. Und genau DIE Frage musst du dir halt stellen. Mache ich über die gesamte Laufzeit viele Einfüge/Entfernen Operationen oder nicht?

Bei Visualisierung würde ich eher sagen, dass du das einmalig machst, und dann immer nur wiederverwendest, also im Speicher hälst. Das spricht eigentlich dafür, dass du eher nur liest als das du ständig einfügst und entfernst.

Du solltest dir also überlegen, ob du dein Problem auf Arrays mappen kannst. Die erlauben halt einen wahlfreien Zugriff.

Einen Punkt, den du ja schon richtig angesprochen hast, sind Hashfunktionen. Die erlauben halt sowohl schnelles einfügen/entfernen als auch wahlfreien Zugriff. Das Problem ist halt, dass du eine gescheite Hashfunktion brauchst, ansonsten ist das Ganze fürn Poppes. Im Netz gibt es ein gutes Paper zur "optimalen Hashfunktion". Da wird ein Algorithmus vorgestellt, mit dm man sehr schnell eine optimale Hashfunktion berechnen kann. Das würde ich dir mal empfehlen. Wenn du die Ergebnisse sehr oft wiederverwendest, wovon ich ausgehe, amortisiert sich der Aufwand ja relativ schnell.

Und da kommen wir zu noch einem wichtigen Punkt. Du solltest schnellst möglich klären, ob Speicherverbrauch für dich ein relevantes Thema ist oder eben nicht. Wenn nicht, dann halt einfach alles im Speicher. Wenn ja, dann viel Spaß bei der Entscheidung, was raus kann, und was nicht. :devil:

Allgemein noch ein Punkt zu deiner Frage!
Gewöhn dir an, bei derart simplen Fragen einfach kurz ein minimales C/C++ (oder what ever was du nutzt) zu schreiben und das Problem einfach zu profilen!

Das liefert dir GENAU Ergebnisse.

Ich weiß jetzt nicht mehr, ob ich mich richtig erinnere, aber ich meine mich zu erinnern, das Modulo SEHR viel langsamer ist als die anderen mathematischen Operationen. Also selbst langsamer als Division, wobei ich mir da wirklich nicht mehr sicher bin. Ich würde halt genau obig genanntes als nächstes machen, aber ich denke das ist eine gute Übung für dich ;)

Du solltest dir auch überlegen, ob du wirklich Modulo brauchst oder nicht! So wie sich das für mich anhört, hast du nur eine SEHR begrenzte Auswahl an Möglichkeiten. Ein Lookuptable in Form einer Hashtabelle wäre da durchaus auch eine Möglichkeit das zu lösen mit Hilfe von eventuell OR/XOR usw.

Mach dir halt mal wirklich gendanken, was du da machen willst, und mach dann eben die Komplextätsanalyse, bzw wenns schnell gehen soll einfache Laufzeitmessungen. Um die wirst du eh nicht rum kommen.

Cacheing wird für dich wohl auch ein Problem sein, um das du dir Gedanken machen solltest.

Multithreading kannst du wohl SEHR trivial lösen, indem du einfach mehrere Objekte nutzt. Ich hoffe doch, dass du nicht nur jeweils ein Objekt hast, das halt SEHR groß ist. Wenn doch, musst du halt geschickt segmentieren, ist aber auch kein unüberwindbares Problem.
 
TE
fadade

fadade

BIOS-Overclocker(in)
Eine Vorlesung "Rechnerarchitektur" wäre wohl auch nicht das schlechteste, was dir noch passieren könnte, wenn du noch keine gehört hast. Btw. Bachelor oder Masterarbeit?
Weder noch^^
Die Bachelor-Arbeit ist noch etwas entfernt, aber fände ich super, wenn das bei mir in eine solche Richtung gehen könnte :)

Ich habe mir zwar schon zahlreiche Diplom-/Bachelor-/Master-Arbeiten zu dem Thema angesehen und durchgearbeitet, aber dort werden nur die Grundlegenden Dreieck betrachtet. Sprich die tatsächlich vorliegenden und vorgegebenen Dreiecke des Modells. Ich arbeite aber mit Gruppen von Dreiecken! Der Unterschied ist zwar nicht so groß, aber ein Hauptproblem gibts trotzdem (wird weiter unten erwähnt).

Also wie gesagt, ich habe ein Modell und "lege" da meine eigene Struktur drauf. Je nach Wunsch kann nun die Detailstufe erhöht werden, sprich das Objekt wird tesseliert und die tesselierten Dreiecke werden wieder als Basis für meine Level of Detail-Struktur verwendet. (Also grob gesagt: niedrige Detailstufe = 1 Dreieck, wobei dieses auch gleich meine Struktur ist --> höhere Detailstufe 2 oder 4 Kinder-Dreiecke und die sind auch gleichzeitig die Struktur der Kinder für meine Elternstruktur (-> 1 Dreieck)).
Momentan bin ich bei dem Versuch das ganze mit 6-Ecken als Struktur zu machen. Also über die vorgegebene Geometrie des Modells lege ich ein Gitter aus 6-Eck-Strukturen (die ja alle jeweils 6 Dreiecke vereinen).
Seeehr tiefgehende Gedanken habe ich mir da auch noch nicht gemacht. Ich wollte erst einmal etwas machen, was funktioniert, sodass ich mich in die Themtik einarbeite und dann erstens sehen kann, dass das überhaupt geht (wird wohl jetzt nicht unmöglich sein :D) und zweitens auf dem Ergebnis basierend entscheiden kann, ob ob ich das verfeinere oder ob der eingeschlagene Weg doch eher Richtung Sackgasse führt.

Bei der Erhöhung der Detailstufe kann ich nun das naheste 6-Eck suchen - bzw. das am höchsten priorisierte - und mich dort auf eine angemessene Detailebene "runterarbeiten".
Soweit so gut. Alle 6-Ecke werden in die einfach verkettete Liste eingetragen um sie als zum Rendern markiert zu speichern. Da reicht m.M.n. so eine gammelige Liste, da ich später dort nur einmal durchlaufen muss und mir von jeder vorliegenden Struktur die Render-Daten einmal holen muss - suchen o.ä. ist da nicht weiter nötig.
Allerdings entstehen zwangsläufig Risse in der gerenderten Oberfläche bei einem Übergang von einer Struktur zu deren Kinderstrukturen, da die Dreiecksauflösung dort ja mindestens doppelt so groß ist. Und mein Hauptproblem besteht momentan darin diese Risse zu schließen. Dazu muss ich halt über Nachbarsuche und Interpolation zwischen mehreren Ebenen an den Rändern jeweils "Fülldreiecke" erzeugen, die die Risse schließen.
Das reine Heraussuchen der Render-Daten ist kein Problem und auch schon lange echtzeitfähig, aber wenn ich jetzt zwischen zwei Strukturen noch die Risse an den Kanten schließen soll, kommt die Nachbarssuche ins Spiel und 1. bricht mir dann die Performance ein und 2. funktioniert das eh noch nicht :D
Also da sitze ich momentan noch dran; dass alle gruppierten Dreiecke intern von jeder Instanz gleich ausgerichtet betrachtet werden und ich so immer direkt weiß, dass Nachbar[3] eines Kindes[4] auch gleich der nachbar[2] des Kindes[1] vom übergeordneten Nachbarn[4] ist ......... so in der Art jedenfalls :schief:
Die normalisierte Ausrichtung der einzelnen Dreiecke in einer Gruppierung zwingt mich eben dazu für jedes Dreieck einen Ausrichtungsoffset zu speichern, den ich bei den Nachbar-/Kind-/Eckpunkt-/Kanten-/Eltern-Suchen immer mit einbeziehe. Der wird einfach draufaddiert und dort nutze ich dann die Modulofunktion, dass mein Kind[2 + (Offset=2)] = Kind[4] auch wieder mein Kind[1] ist.

Dass ich nun erfrage, ob es dafür eine bessere Variante als Modulo gibt hängt einfach damit zusammen, dass ich das gleich von Anfang an möglichst "gut" machen wollte und ggf. vereinfacht das ja auch einiges.

Möglicherweise hast du recht, dass die Anwendung einer Hashtable noch recht performant ist, sodass folgendes gemacht wird:
Code:
byte GetID(byte position, byte offset)
{
     //a)
     return ((byte) (position + offset) % [Anzahl Kanten/Eltern/Kinder/...]);

     //bzw. b)
     return  hashtable[position+offset]; //vorberechneter Wert für pos+offs % Kanten/Kinder/eltern/punkte/......
}
Allderings muss ich dann auch je nachdem wie komplex ich das gestalte (ob absichtlich oder unabsichtlich sei mal dahin gestellt :ugly: ) einige Hashtables nutzen und aufpassen, dass keine falschen Aufrufe geschen!
Hmm.... ist ja eigentlich nur mal kurz 4 oder 5 statische Arrays für die jeweiligen Gruppierungsklassen erzeugen und immer aufrufen ...

Das könnte ich ja eigentlich gleich mal umsetzen. Keine Ahnung warum ich da nicht auch schon drauf gekommen bin :huh:

In der Phase vom konkreten Performance-Profiling bin ich allerdings noch nicht, und weiß auch nicht, ob das (erstmal) so nötig ist. RAM, VRAM, etc. sind mir momentan noch ziemlich egal und wie ich meine Daten anordne, damit das Caching performant ist weiß ich eh nicht^^
ArrayOfStructs und StructOfArrays habe ich bisher auch nur einmal flüchtig gehört. Hat es damit etwas tiefsinnigeres auf sich?

(Danke schonmal bis hierhin für deine weichenstellenden Antworten :daumen: )
 
Zuletzt bearbeitet:

Skysnake

Lötkolbengott/-göttin
Gerade auf GPUs macht es einen Unterschied bzgl prefetching.

Du musst ja immer bedenken, dass du auf CPUs ganze Cachelines lädst, und auf GPUs halt immer in Bänken denken musst.

SOA ist da halt meistens performanter, weil du immer sequenziell zugreifen kannst, bzw. eben automatisch die Daten direkt mit lädst, die du eh gleich braubst.

Das ist bei AOS nicht wirklich gegeben, weil du halt sehr sehr sehr oft dann Daten mit lädst, die du eigentlich gar nicht brauchst.

Kurz um, du erhöhst halt im Allgemeinen deine Datenlokalität.
 
TE
fadade

fadade

BIOS-Overclocker(in)
So kleine Rückmeldung:

Die Verwendung einer Lookup-Tabelle hat das ganze doch schon spürbar beschleunigt! :)
Irgendwie hatte ich da echt nen Brett vorm Kopf ... wahrscheinlich weil
Code:
array[ a + b % c]
einfach kürzer und intuitiver als
Code:
array[lookup[a+b]] //wobei lookup[x] = x % c
ist ^^

Nun könnte man sich als Erweiterung noch Gedanken darüber machen, ob es in Ordnung ist die ganzen Nachbarschaftsbeziehungen und so mit Zahlen vom Typ byte zu realisieren, oder ob man lieber int32 nimmt; könnte ja sein, dass man als Spezialist weiß, dass aktuelle 32bit/64bit-CPUs mit eben 32/64 bit großen Daten besser klarkommen, aber ich denke das ist mir 1.) nicht soo wichtig und 2.) steigt die Datenmenge dann doch schon um einiges an, da ich pro Dreieck/Patch/Struktur Offsets für die Kinder und Nachbarn habe, wobei eine Einheit jeweils auf > 2 Offsets jeweils für Nachbarn und Kinder kommt.


Das mit AoS/SoA ist dann ja auch (noch) nicht relevant, da diese Daten momentan noch komplett und ausschließlich mit der CPU in Kontakt geraten. Für das Rendering ordne ich das alles eh nochmal um um Redundanzen auf 0 abzusenken und transportiere das getrennt voneinander zur GPU.
 

Skysnake

Lötkolbengott/-göttin
Du solltest immer dran denken, dass du bei kleineren Datentypen eben mehr Werte pro Cacheline hast, und damit auch wiederum mehr Werte im Cache haben kannst. Nimm also bitte immer nur genau so viel wie du wirklich brauchst.

Du kannst das aber natürlich auch über ein Define und einen eigenen Datentype regeln, oder aber mit Prototypen/überladen.

PS:
Schön das mein Tip so hilfreich war :D
 
Oben Unten