Geschwindigkeit von C++-Operatoren/ einfacher Mathematik

Question

Ich arbeite an einer Physik-Engine und bin der Meinung, dass es hilfreich wäre, ein besseres Verständnis für die Geschwindigkeits- und Leistungseffekte bei der Durchführung vieler einfacher oder komplexer mathematischer Operationen zu haben.

1. Ein großer Teil einer Physik-Engine besteht darin, unnötige Berechnungen zu eliminieren, aber Ab wann sind die Berechnungen so klein, dass eine vergleichende Prüfung nicht mehr notwendig ist?

   • z.B.: Prüfung, ob sich zwei Liniensegmente schneiden. Sollte geprüft werden, ob sie sich nahe beieinander befinden, bevor man direkt zur einfachen Berechnung übergeht, oder würde die zusätzliche Operation den Prozess auf Dauer verlangsamen?

2. Wie viel Zeit benötigen die verschiedenen mathematischen Berechnungen?

   • z.B.: (3+8) vs (5x4) vs (log(8)) usw.

3. Wie lange dauern die Ungleichheitskontrollen?

   • z.B.: >, <, =

Answer 1

1. Sie werden ein Profil erstellen müssen.

2. Grundlegende Operationen, wie Additionen oder Multiplikationen, sollten nur eine asm Anweisungen.

   EDIT: Wie in den Kommentaren erwähnt, können Multiplikationen, obwohl sie eine asm-Anweisung benötigen, zu Mikroanweisungen erweitert werden.

   Logarithmen brauchen länger.

3. Auch eine asm Anweisung.

Wenn Sie Ihren Code nicht profilieren, können Sie nicht feststellen, wo Ihre Engpässe liegen.

Solange Sie mathematische Operationen nicht millionenfach aufrufen (und wahrscheinlich auch dann nicht), führt eine gute Wahl der Algorithmen oder eine andere Optimierung auf höherer Ebene zu einem größeren Geschwindigkeitsgewinn als die Optimierung der kleinen Dinge.

Sie sollten Code schreiben, der leicht zu lesen und leicht zu ändern ist, und erst wenn Sie mit der Leistung nicht zufrieden sind, sollten Sie mit der Optimierung beginnen - zuerst auf hoher Ebene und erst danach auf niedriger Ebene.

Sie können auch die dynamische Programmierung oder das Caching ausprobieren.

Answer 2

Nun, das hängt von Ihrer Hardware ab. Sehr schöne Tabellen mit Befehlslatenz sind http://www.agner.org/optimize/instruction_tables.pdf

1. Es hängt stark vom Code ab. Vergessen Sie auch nicht, dass es nicht nur von den Berechnungen abhängt, sondern auch davon, wie gut die Vergleichsergebnisse vorhergesagt werden können.

2. Im Allgemeinen ist die Addition/Subtraktion sehr schnell, die Multiplikation von Floats ist etwas langsamer. Die Division von Fließkommazahlen ist ziemlich langsam (wenn Sie durch eine Konstante c dividieren müssen, ist es oft besser, 1/c vorzuberechnen und damit zu multiplizieren). Die Bibliotheksfunktionen sind normalerweise (ich wage zu behaupten: immer) langsamer als einfache Operatoren, es sei denn, der Compiler entscheidet sich für SSE. Zum Beispiel können sqrt() und 1/sqrt() mit einer SSE-Anweisung berechnet werden.

3. Von etwa einem Zyklus bis zu mehreren Dutzend Zyklen. Die aktuellen Prozessoren führen die Vorhersage nach Bedingungen durch. Wenn die Vorhersage richtig ist, wird sie schnell sein. Wenn die Vorhersage jedoch falsch ist, muss der Prozessor alle vorgeladenen Anweisungen wegwerfen (IIRC Sandy Bridge lädt bis zu 30 Anweisungen vor) und mit der Verarbeitung neuer Anweisungen beginnen.

Das heißt, wenn Sie einen Code haben, bei dem eine Bedingung die meiste Zeit erfüllt ist, wird er schnell sein. Ähnlich verhält es sich mit einem Code, bei dem die Bedingung die meiste Zeit nicht erfüllt ist: Er ist schnell. Einfache alternierende Bedingungen (TFTFTF ) sind normalerweise auch schnell.

Answer 3

Was die Punkte 2 und 3 betrifft, so kann ich Sie auf die Handbuch zur Optimierung von Intel® 64- und IA-32-Architekturen . In Anhang C werden die Latenzzeiten und der Durchsatz verschiedener Anweisungen dargestellt. Wenn Sie den Assemblercode nicht von Hand codieren, wird Ihr Compiler jedoch seine eigenen Optimierungen anwenden, so dass es schwierig wäre, diese Informationen direkt zu verwenden.

Noch wichtiger ist, dass Sie SIMD verwenden können, um Ihren Code zu vektorisieren und Berechnungen parallel durchzuführen. Auch die Speicherleistung kann ein Engpass sein, wenn Ihr Speicherlayout nicht ideal ist. Das Dokument, das ich verlinkt habe, enthält Kapitel zu beiden Themen.

Wie @Ph0en1x jedoch sagte, wäre der erste Schritt die Auswahl (oder das Schreiben) eines effizienten Algorithmus, der für Ihr Problem geeignet ist. Erst dann sollten Sie sich Gedanken über Optimierungen auf niedriger Ebene machen.

Wie für 1, in einem allgemeinen Fall würde ich sagen, dass, wenn Ihr Algorithmus funktioniert in einer Weise, dass es einige einstellbare Schwellenwerte für, wenn bestimmte Tests ausführen, könnten Sie einige Profilerstellung und drucken Sie eine Performance-Graph einer Art, und bestimmen Sie die optimalen Werte für diese Schwellenwerte.

Answer 4

1. Dies hängt von dem Szenario ab, das Sie zu simulieren versuchen. Wie viele Objekte gibt es und wie nah sind sie beieinander? Sind sie gebündelt oder gleichmäßig verteilt? Bewegen sich Ihre Objekte viel oder sind sie statisch? Sie werden Tests durchführen müssen. Mögliche Datenstrukturen zur schnellen Überprüfung der Nähe sind kd-Bäume o ortsabhängige Hashes (es kann auch andere geben). Ich bin mir nicht sicher, ob diese für Ihre Anwendung geeignet sind. Sie müssen prüfen, ob die Pflege der Datenstruktur und die Kosten für das Nachschlagen für Sie in Ordnung sind.
2. Sie werden Tests durchführen müssen. Prüfen Sie, ob Sie die Vektorisierung oder ob Sie sogar einige der Berechnungen auf einem Grafikprozessor durchführen können, indem Sie CUDA oder so ähnlich.
3. Dasselbe wie oben - Sie müssen testen.

Answer 5

Ungleichheitsprüfungen, Inkrementieren, Dekrementieren, Bitverschiebungen, Addition und Subtraktion können im Allgemeinen als sehr billig angesehen werden. Multiplikation und Division sind im Allgemeinen etwas teurer. Komplexe mathematische Operationen wie Logarithmen sind viel teurer.

Führen Sie einen Benchmark auf Ihrer Plattform durch, um sicherzugehen. Seien Sie vorsichtig beim Benchmarking mit künstlichen Tests mit engen Schleifen - das führt oft zu irreführenden Ergebnissen. Versuchen Sie, Benchmarking mit möglichst realistischem Code durchzuführen. Idealerweise erstellen Sie ein Profil des tatsächlichen Codes unter realistischen Bedingungen.

Was die Optimierungen für Dinge wie Linienüberschneidungen angeht, so hängt dies vom Datensatz ab. Wenn Sie viele Prüfungen durchführen und die meisten Ihrer Zeilen kurz sind, kann es sich lohnen, eine kurze Prüfung durchzuführen, um Fälle auszuschließen, in denen sich die X- oder Y-Bereiche nicht überschneiden.