Performancegewinn bei double zu float

[starcow]

Tach Zusammen :-)

Ich arbeite in meinem Kollisionsprogramm bei Fliesskommazahlen überall mit double.
Jetzt frag ich mich, ob - und wenn ja, in welcher Grössenordung ein Performance-Sprung zu erwarten wäre, wenn ich konsequent auf float umstellen würde.
Lässt sich dazu pauschal was sagen?

Gruss starcow

[Schrompf]

Pauschal sicher nicht. Praktisch glaube ich, dass Du kaum einen Unterschied messen können wirst.

Instructions: die CPU kann nach meinem Wissen double praktisch genauso schnell verrechnen wie float.

Vektorisierung: float hat nur die halbe Anzahl Bits, und es gibt mehr SSE / AVX-Instructions dafür als für Double. Aber da Du wahrscheinlich nichts von Hand vektorisiert hast, musst Du dem Compiler vertrauen. Und der erkennt mit Mühe SSE-Gelegenheiten für 3xfloat-Vektoren. Ob er für Double überhaupt sucht, weiß ich nicht mal.

Speicherbandbreite: floats sind nur halb so groß. Wenn Dein Algorithmus also daran hängt, große Massen von Zahlen mit simplen Berechnungen zu verarbeiten, könnte es was nützen. Bezweifle ich aber. Das müssten wirklich Hunderte Millionen an einfachen Berechnungen xmal die Sekunde sein, damit Du in die Nähe der Speicherbandbreite kommst.

[Krishty]

Pauschal lässt sich nichts sagen, das hat Schrompf gut zusammengefasst. Aber was uns wirklich vom Hocker hauen würde:

1. ersetz mal alle doubles durch ein eigenes using starcow_float = double;
2. so weit, dass du nur durch Umschalten dieses usings aussuchen kannst, ob du mit float oder double kompilierst
3. dann miss mit beiden die Leistung und poste hier

… in meiner Physik-Engine habe ich noch zu viel handgeschriebenes SSE-Zeug, um das komplett austauschbar zu machen :(

[starcow]

Danke für die gute Erklärung Schrompf! Nur eine Sache erschliesst sich mir irgendwie nicht intuitiv: Wenn double genauer ist, dann brauche ich doch auch mehr Zeit, um diese zusätzlichen Stellen einer Zahl bei einer mathematischen Operation zu berechnen. Grob hätte ich geschätzt, dass ich für 12 Stellen nach dem Komma doppelt so lange rechnen muss, wie für 6 Stellen nach dem Komma. Aber das scheint nicht der Fall zu sein...?

Pauschal lässt sich nichts sagen, das hat Schrompf gut zusammengefasst. Aber was uns wirklich vom Hocker hauen würde:

1. ersetz mal alle doubles durch ein eigenes using starcow_float = double;
2. so weit, dass du nur durch Umschalten dieses usings aussuchen kannst, ob du mit float oder double kompilierst
3. dann miss mit beiden die Leistung und poste hier

… in meiner Physik-Engine habe ich noch zu viel handgeschriebenes SSE-Zeug, um das komplett austauschbar zu machen :(

Achso! :-D Sehr gut! Das macht natürlich Sinn! Danke Krishty
Ich meine sowas ähnliches mal gsehen zu haben, wo dies mittels "typedef" realisiert wurde. Was ist den der Unterschied zu deiner Methode mittels "using"? Ich kenne using eigentlich nur im Zusammenhang mit den "namespaces"...
Und eine andere Frage in diesem Kontext:
In meinem Code weise ich ja oft den Variablen konkrete Werte zu. Wenn ich dann aber mit dieser Technik auf "float" umstelle, müsste ich ja bei jeder Zahlenkonstanten noch ein "f" dranhängen. Ist es nicht so, dass der Compiler eine Dezimalzahl ohne das Postfix "f" als double Konstante interpretiert und dann zuerst einen cast nach float ausführen müsste, wenn ich "umschalte"? Oder lässt sich auch das irgendwie dynamisch gestalten?

Gruss starcow

[Schrompf]

Das geht so, denke ich. Ne 4.3 lässt sich eh nicht exakt darstellen, der Fehler verschiebt sich bei double nur 10 Stellen nach hinten. Wenn's kompliziert sein soll, schreibst Du jede Initialisierung als Konstruktor: auto zahl = starcow_float(3.6)

Und die Rechenzeit ist nicht von der Anzahl der Stellen abhängig. Die heutigen Chips haben dafür kaskadierende Gatter, deren Namen mir gerade nicht einfällt. Die eigentliche Ausführung der allermeisten Ops geht in einem Takt, egal ob 32bit, 64bit oder 256bit. Natürlich ist die ganze Vor- und Nachbereitung kompliziert und wegen dem Pipelining kann man nicht mehr von "ein Takt" sprechen. Intel gibt zu seinen Instructions immer Throughput (wieviele Berechnungen pro Takt) und Latency (nach wievielen Takten kann das Ergebnis einer Berechnung als Eingabe einer neuen Berechnung benutzt werden). Für skalare Fließkomma- oder Integer-Ops, egal ob 32 oder 64bit, ist der Throughput üblicherweise 2, und die Latenz ist für die allermeisten Mathe-Ops 3 bis 4 Takte.

[Krishty]

Danke für die gute Erklärung Schrompf! Nur eine Sache erschliesst sich mir irgendwie nicht intuitiv: Wenn double genauer ist, dann brauche ich doch auch mehr Zeit, um diese zusätzlichen Stellen einer Zahl bei einer mathematischen Operation zu berechnen. Grob hätte ich geschätzt, dass ich für 12 Stellen nach dem Komma doppelt so lange rechnen muss, wie für 6 Stellen nach dem Komma. Aber das scheint nicht der Fall zu sein...?

Bei einfachen Operationen (Addition, Multiplikation, Bitweises) wird das durch Transistordichte völlig ausgeglichen. In den SSE-Registern liegen 128 Bit Daten, die einmal als Addition von 4× float verkabelt sind oder als Addition von 2× double. Du jagst Strom durch und am anderen Ende liegt das Ergebnis an. Beides dauert vier Takte.

Komplexe Operationen, die gewissermaßen Schleifen erfordern (Division, Quadratwurzel) sind tatsächlich langsamer: 13 gegen 18 Takte. Die sollten aber selten sein (und durch Out-of-Order kaschierbar).

Was ist den der Unterschied zu deiner Methode mittels "using"?

Keiner; ist nur einfacher lesbar. Wurde vor ein paar Jahren in den C++-Standard aufgenommen. Nimm ruhig typedef, falls du dich damit wohler fühlst.

Und eine andere Frage in diesem Kontext:
In meinem Code weise ich ja oft den Variablen konkrete Werte zu. Wenn ich dann aber mit dieser Technik auf "float" umstelle, müsste ich ja bei jeder Zahlenkonstanten noch ein "f" dranhängen. Ist es nicht so, dass der Compiler eine Dezimalzahl ohne das Postfix "f" als double Konstante interpretiert und dann zuerst einen cast nach float ausführen müsste, wenn ich "umschalte"? Oder lässt sich auch das irgendwie dynamisch gestalten?

Ja, die Konstanten sind tatsächlich ein Problem. Ich würde beim Ausprobieren alle Konstanten so lassen, wie sie sind, und die Warnungen ignorieren. Falls es ernst wird, würde ich mit allen Literalen so etwas machen:

Code: Alles auswählen

constexpr starcow_float make_starcow_float(double literal) {
	return static_cast<starcow_float>(literal);
}

auto a = make_starcow_float(3.1); // wird float oder double, je nach typedef

Edit: Ups, Schrompf war schneller

Natürlich ist die ganze Vor- und Nachbereitung kompliziert

Ich habe letztens gelernt, dass ein L1-Hit drei Takte benötigt. Also der Zugriff auf einen Wert, der bereits im schnellsten Cache liegt. Drei Takte. Außerdem limitiert im L1 die Anzahl der Lese- und Schreiboperationen, nicht die Größe. Man kann also nicht genug betonen, wie wichtig es ist, alles in Registern zu halten und nötigenfalls halt sechzehn chars in einem Rutsch zu laden und im Register zu extrahieren statt einzeln drauf zuzugreifen (bestenfalls nutzt man natürlich SIMD).

[Alexander Kornrumpf]

Ich warte schon auf die Verfilmung unter dem Titel "A starcow_float is born". Mit Lady Gaga als float, Bradley Cooper als double und Til Schweiger als static_cast.

Sorry, keine Ahnung wo das jetzt herkam aber ich finde den bezeichner starcow_float einfach hilariös.

[Krishty]

lol

Hätte auch was von einer Queer Story. Muss erst rausfinden, ob es sich eher als double oder float identifiziert.

[Schrompf]

Hihihi. Sein Gefühl als zufriedener Float in einer stabilen Multiplikation gerät ins Wanken, als er den neuen Kollegen kennenlernt, der offensiv als Double lebt.

[edit] Ich hab übrigens was von 9 bis 10 Takten für einen erfolgreichen Level1-Cache-Hit im Kopf. Aber das ist immer noch gerade mal die halbe Pipelinelänge, also grob die Strafe für einen Mispredicted Jump. Die moderne CPU-Welt ist kompliziert.

[Krishty]

P.S.: Bei sin(), cos(), tan() und ihren Inversen sind die double-Versionen übrigens viel, viel, viel langsamer als die float-Versionen.

Ich habe hier gerade Code, der für einen Winkel als double feststellt, in welchem Quadranten er sich befindet – und der ist so lang und verschachtelt, da könnte man stattdessen auch ein ganzes Atari-Spiel samt Grafiken unterbringen.

Hauptgrund ist, dass man Mathematik ohne Rundungsfehler braucht. Bei float kann man meist einfach auf double umsteigen und hat seine zusätzliche Genauigkeit. Bei double bleibt nur Mathematik mit großen Integern und direktes Arbeiten auf den Komponenten der Gleitkommazahl, und das … boah.

[starcow]

Sehr gut! Wieder so einiges gelernt! Vielen Dank euch! :-)
Da sowieso einige Refactoring-Augaben anstehen, werde ich versuchen, den Vorschlag gleich in diesem Zug umzusetzen.
Vielleicht noch eine Frage in diesem Kontext (Performance) - auch wenn das vielleicht etwas ins OT abdriftet:
Bis jetzt hab ich nur eine einzige Klasse, die sich um die Kollisionsaufgaben kümmert - meine CLS_Circle Klasse.
Bislang hat das auch sehr gut funktioniert. Nur habe ich jetzt, für den Fall, dass das Objekt (der Kreis) ein Geschoss ist, neue Methoden hinzugefügt. Methoden für die Berechnung der elastischen Kollision. Für reine Charakteren bräuchte es eigentlich diese Methoden nicht, da diese das Modell der inelastischen Kollision verwenden. Dafür hat dann die Kreis-Instanz eines Charakters wiederum Variablen, die ein Geschoss nicht bräuchte.
Ich vermute, dass es jetzt wohl im sinnvollsten wäre, eine Basis-Klasse zu erstellen und von dieser abzuleiten (?).
Allerdings komme ich - wenn ich das ganze konsequenz durchdenke - auf mehrere Vererbungen.

Code: Alles auswählen

                                Kollisions-Objekt
                          /                         \
                     Linien                       Kreise
                                            /                      \
                                        statisch              dynamisch (beweglich)
                                                  /                                  \
                                                 /                                    \
                                           elastisch                               inelastisch
                                           /      \                                  /         \
                                    steuerbar    nicht-steuerbar              steuerbar     nicht-steuerbar

Ich hab keine Erfahrungen damit, wie weit solche Vererbungen sinnvoll sind - und vorallem, ob sie sich negativ auf die Performance auswirken können.
Ist das ganze, so in dieser Form übertrieben?

Gruss starcow

[Schrompf]

Definitiv. Erstens: wenn Du Performance willst, nimmst Du keine virtuellen Funktionen. Zweitens: wenn die Ableitungsbeziehungen Dir zu kompliziert erscheinen, ist das ein Hinweis, dass Ableitungen ein ungeeignetes Stilmittel für dieses Problem sind. Statisch und Dynamisch ist z.b. eine Unterscheidung, die man als "Kollisionsreaktion" abstrahieren könnte. Und das ist keine Ableitung, sondern ein Parameter eines Physikkörpers. Irgendwann willst Du auch mal nen kantigen Stein aus Linien durch die Gegend werfen. Also würde ich auch nicht zwischen "Linien" und "Kreise" unterscheiden, sondern allgemein das Zeitverhalten / die Kollisionsreaktion von der Kollisionsform trennen. Steuerbar / Nicht-Steuerbar ist ne Frage, wer welche Kräfte auf das Objekt ausübt. Auch das ist keine Ableitung, sondern ein Thema außerhalb der Physik. Eine Spieldesign-Entscheidung quasi, keine Code-Entscheidung.

Schmeiß also die ganzen Ableitungen weg und mach Folgendes:

Physikkörper: hat eine Kollisionsform und ein Verhalten bei Kollision
Kollisionsform: Einen Satz an Liniensegmenten und Kreisen, oder halt simpel "entweder ein Kreis oder ein Satz Linien"
Kollisionsreaktion: Masse bzw. bool "unbeweglich", der halt die Formeln mit Masse == Unendlich betritt. Du siehst natürlich sofort, dass Du nicht mit Masse unendlich rechnen kannst. Aber Du siehst auch sofort, was z.b. beim elastischen Stoß passiert, wenn Du die Masse eines Teilnehmers immer größer werden lässt. So macht man unbewegliche Physikkörper.
Steuerung: Du übst Kräfte auf einen Physikkörper aus. Bei "unbeweglich" würde die Masse -> unendlich dafür sorgen, dass jede Kraft ne Wirkung von 0 hat.

Und das sind drei separate Konzepte, die Du eigentlich mischen und kombinieren kannst, wie Du es brauchst. Das ist ein Hinweis, dass "Ableitung" als Lösungsmittel ungeeignet ist.

[Spiele Programmierer]

Ich stimme Schrompf auf jeden Fall darin zu, dass soviele Unterklassen total übertrieben wären. Momentan hast du ja nur einen Kreis, allerding ist es bereits jetzt so, dass der Code von "steuerbar" für die beiden Unterklassen vermutlich viele Gemeinsamkeiten besitzt. Nachdem du später wahrscheinlich steuerbare Rechtecke und Dreiecke hinzufügen willst, wird es immer mehr Überschneidungen zwischen der Funktionalität geben. Um das zu verhindern bräuchte man dann Mehrfachvererbung die wahrscheinlich auch noch virtuell sein muss und deine Performance ist endgültig ruiniert.

Was ich allerdings noch zu Schrompf ergänzen will ist, dass ich in diesem Fall einen guten Anwendungsfall für datenorientiertes Design erwarte. Besonders katastrophal für die Performance wäre es, die verschiedenen Objekttypen einzeln zu alloziieren und über den Heap zu verteilen. Ich würde stattdessen empfehlen die Objekte ohne indirektion direkt in einem großen Array abspeichern oder, noch besser, du verzichtest auf "Kollisions-Objekte" vollständig und machst lieber mehrere Arrays für Position, Größe, Objektform, Elastizität usw. Das verbessert die Cache-Ausnutzung weiter und erlaubt es dir später SIMD besser einzusetzen.

Ich weiß nicht genau wie welche Logik du für die Objekte implementieren willst, aber ich denke, für den ersten Teil der Verarbeitung wirst du vermutlich eine Datenstruktur haben, die dabei hilft, potentielle Kollisionen zu erkennen (z.B. ein einfaches 2D-Gitter). Für die optimale Performance bietet es sich hier an, die damit aufkommenden Kollisionspaare nach der notwendig Verarbeitung sortieren. z.B. kannst du hier Liste für Kreis - Kreis, eine für Kreis - Rechteck und eine für Rechteck - Rechteck Kollisionen anlegen und dann im zweiten schritt ohne virtuelle Methoden und Verzweigungen diese Listen durchgehen (sogar mit SIMD!). Wahlweise kannst du auf die tatsächlichen Kolisionen jetzt danach z.B. nach Elastizität ordnen, um dann wieder ohne Verzweigungen bezüglich Elastizitäts unterschiedliche Methoden auf die Kollisionspaare anzuwenden.
Und dann brauchst du vermutlich noch einen zweiten Verarbeitungspass, der einmal über alle Objekte iteriert, um z.B. die Kräfte anzuwenden und Geschwindigkeiten aufzuaddieren.

[Walker]

Ich habe das für ein größeres 3D Projekt mal getestet. float vs double (soweit das ging). Von der reinen Speed ist da nichts an Vorteil zu "messen". Einzig die Bandbreite der Daten ist kleiner. Da wir diese Daten mittlerweile auch anderweitig nutzen (WebGL) werden einige Dinge auf float umgestellt weil das für den View ausreichend ist.

[Krishty]

Ich hatte bei einem großen Voxelprojekt tatsächlich große Gewinne durch die Umstellung von double auf float, aber meine Aufzeichnungen darüber sind weg. Deshalb weiß ich nicht mehr, wie viel, und ob das Projekt durch Rechenleistung oder Speicherbandbreite limitiert wurde. Die Änderung war aber jedenfalls spürbar.

[joeydee]

(Zum Offtopic-Thema)

dass ich in diesem Fall einen guten Anwendungsfall für datenorientiertes Design erwarte. [...] mehrere Arrays [jeweils] für Position, Größe, Objektform, [...]

Dem stimme ich erstmal zu. Auch unter dem Namen ECS (Entity-Component-System) geläufig. Damit löst man das Vererbungsproblem, holt sich aber eine Reihe neuer Designprobleme an Bord ;)
Es ist ein bischen wie "Ich will alle meine Fotos sortieren" - einmal mittels Ordnern auf Festplatte (==Objektorientiert mit fester Hierarchie), einmal mit Tags und Datenbankabfragen (==Datenorientiert).
Willst du erstmal überschaubare Projekte machen, die *wirklich laufen*: Mache erstmal eine einzige Klasse, die möglichst alles beinhaltet, manches läuft dann eben leer. Ist Overhead, aber läuft. Unsere Rechner sind schnell und die Lüfter leise, da wird vieles verziehen, für Experimentalprojekte ohne Vermarktung sowieso. Trenne dann im laufenden oder nächsten Projekt nach gewonnener Erfahrung und Notwendigkeit, statt zu versuchen ein OO-Design vorher rein theoretisch zu entwickeln und dann in der Realität irgendwie damit klarzukommen.
Willst du hoch hinaus skalieren, ständig etliche neue Features einbauen und diese beliebig kombinieren können ohne viel Overhead zu produzieren ("Lootboxen sind keine Spieler, haben aber trotzdem ein eigenes Inventar", "Bäume können dank eines neuen Zauberspruchs nun sprechen wie NPCs, aber nicht die Position ändern"), schau dir ECS an.
Eine kleine Simulation wie das Look-and-Feel dazu im Code wäre kann man sich schnell mit Standardcontainern zusammenbauen.
Aber fang besser ein neues Thema dazu an.

[starcow]

Vielen Dank euch allen für eure guten Ratschläge und Erklärungen! Erst jetzt bin ich dazu gekommen, mich wieder meinem Herzensprojekt anzunehmen und weiter zu basteln (wäre doch blos mehr Zeit vorhanden :-/ ). Ich werde versuchen all die schlauen Ideen aufzugreifen und in die Neustrukturierung einfliessen zu lassen. Ich muss aber zugeben, dass ich nicht alles restlos verstanden habe - meine aber zumindest die Stossrichtung der einzelnen Ansätze zu erkennen.
Für neue Fragen werde ich dann wohl besser einen frischen Thread eröffnen...

Gruss und schönen Abend
starcow