Geschwindigkeit C++ - Code
-
LionAM schrieb:
Also, es ist VC++ 6.0 Standard. Ich weiß,
dass das nicht der schnellste Compiler ist,
er unterstützt auch keine Code-Optimierung.
Allerding hab ich das ganze auch unter gcc
compiliert - mit Optimierungen - was keinen
Geschwindigkeitsvorteil brachte.
Genauso war es aber auch bei dem VC++ 2005
Express, ich konnte keinen Geschwindigkeitsvorteil
feststellendas muss ein kurioser code sein.
zu /EHsc:
cl : Command line error D8016 : '/EHs' and
'/clr' command-line options are incompatible
was ist /clr? /EHsc scheint ja mit Exceptions
zusammenzuhängen, ich hab es ausgeschaltet,
es gibt bei mir im moment sowieso keine...dann ist das kein native win32 projekt.
Wie man SSE aktiviert, weiß ich leider nicht,
da hab ich keine Option gefunden.menü Project -> Properties
dann unter Configuration Properties -> C/C++ -> Code Generation -> Enable Enhanced Instrruction Set (bzw. /arch:SSE2 in der commandozeile)ich weiß nicht, ob da noch so viel im Quellcode
zu optimieren geht...wir auch nicht, solange wir den code nicht gesehen haben
-
Du verwendest sicher kein SIMD bei deiner Vektorberechnung, stimmt's?
->Auf jeden Fall SIMD verwenden!
-
Hallo. Danke erstmal für die Antworten.
Der /clr-Compiler-Switch vermasselt mal wieder
die SSE2-Auswahl... - wie kann ich den abschalten?
Heißt ja irgend wie common language runtime
compilation - aber ich finde die Einstellung nicht.
zu camper: Es ist momentan eine Windows-Konsolen-
Anwendung, soll aber portabel bleiben und später
in ein QT-Projekt eingebunden werden.Ein paar Beispiele:
CTriangle* tri = new CTriangle[100000]; // std::vector<CTriangle> tri(100000); // std::vector<CTriangle>::iterator aktTri; int i, j; for (i = 0; i < 100000; i++) { tri[i].SetValue(CPoint3d(1,2,0),CPoint3d(2,3,0),CPoint3d(4,1,0)); } int time = GetTickCount(); double t; CVector3d p; CRay ray(CVector3d(2,2.9,0), CVector3d(0,0,1)); for (j = 0; j < 100; j++) { aktTri = tri.begin(); for (i = 0; i < 100000; i++) { bool hit = tri[i].HitBy(ray); // aktTri->HitBy(ray); // ++aktTri; } } time = GetTickCount() - time; cout << time << "\n"; delete[] tri; }Das Ausführen dauert (momentan) etwa 6.8 s.
Lasse ich das die Variable t (die nie verwendet
wird) weg, dauert es 400 ms länger.
Nehme ich statt dem dynamischen Array einen
vector, erhalte ich 6.3 s Ausführzeit.
Mit einem globalen statischen Array gehts in
6 Sekunden usw.
Die CTriangle-Klasse ist inzwischen auf 424 Byte
angewachsen. Interessanterweise scheint dies eine
"magische Zahl" zu sein (vgl. Atomschale oder
Atomkern - da spricht der Physiker
Wenn ich dummy-doubles in die Klasse einfüge,
wird die Ausführung lagsamer (~150 ms je
Variable) - eine entfernen bringt einen Einbruch
um 700 ms (!)
Alex
-
bei diesen objektgrößen ist denkbar es denkbar, dass du mit cache problemen zu kämpfen hast. im zweifel ist es hier besser, mal das gesamte projekt in seiner jetzigen form verfügbar zu machen, damit wir damit spielen können. codeoptimierung beginnt man ja am besten auf einer möglichst hohen abstraktionsebene. in dem gezeigten ausschnitt steckt ja außerdem einiges an zusätzlichen code, wie konstruktoren/destruktoren, HitRay etc.
die /clr option findest du unter Configuration Properties -> General -> Common Language Runtime Support
edit: das beschriebene laufzeitverhalten beweist eigentlich, dass keine optimierung stattgefunden hat. PODs, die nicht initialisiert und genutzt werden sind so ziemlich das erste was eliminiert wird.
-
LionAM schrieb:
Das Ausführen dauert (momentan) etwa 6.8 s.
Lasse ich das die Variable t (die nie verwendet
wird) weg, dauert es 400 ms länger.
Nehme ich statt dem dynamischen Array einen
vector, erhalte ich 6.3 s Ausführzeit.Der iterator entspricht einem pointer und es geht einfach schneller mit nem Pointer auf ein element zuzugreifen, als über den arrayindex.
-
Hallo nochmal!
Danke für den Tip mit /clr - das auszuschalten hat
wirklich 20% Geschwindigkeitsgewinn gebracht, jetzt
ist der von VC2005 generierte Code etwas schneller
als die anderen (ich musste die von VC generierte
Datei "Assembly Info" auskommentieren).
Der Geschwindigkeitsgewinn durch Einschalten von
SSE2 war aber quasi 0...Zu dem Iterator: allein die Existenz verlagsamt unter
VC6 die Ausführung, die Verwendung hat keinen
Geschwindigkeitsvorteil...Zu der Klasse: die ist deswegen so groß, weil ich wie
schon oben erwähnt alles zwischenspeichere, was ich
bei der Berechnung später verwende.Ich habe allerdings bei VC2005 einen großen Teil meiner
Vorberechnung entfernt - die Klasse hat noch 344 Byte.
Interessanterweise hatte das nur minimalen Einfluss auf
die Geschwindigkeit (<10%). Selbst die Wurzelberechnung,
die unter VC6 einen deutlichen Einfluss hatte, war kaum
merkbar...
Den Algorithmus wollte ich noch nicht preis geben,
ich habe nur mal die Operationen gezählt:
12-18 Multiplikationen (=4-6 Skalarprodukte), 1 Division,
9-13 Additionen, 1 Subtraktion, 5 Zuweisungen (double),
einmal ==, 1-3 mal <
Welcher Algorithmus zur Bestimmung, ob ein Strahl ein Dreieck
trifft, wäre effizienter? Also ich hab im Internet keinen
gefunden. Man muss ja bedenken, dass ein Vektorprodukt
ja schon 6 Multiplikationen entspricht...Alex
-
LionAM schrieb:
Zu dem Iterator: allein die Existenz verlagsamt unter
VC6 die Ausführung, die Verwendung hat keinen
Geschwindigkeitsvorteil...und weil vc6 (standard) nicht optimiert (sowenig wie vc2005, solange du ihm nichts anderes sagst), ist das nicht ungewöhnlich.
Welcher Algorithmus zur Bestimmung, ob ein Strahl ein Dreieck
trifft, wäre effizienter?keine ahnung. ohne mich damit beschäftigt zu haben, fällt mir auf anhieb ein algorithmus ein, der 1-3 vektorprodukte, 1-3 skalarprofukte und 1-3 vergleiche (mit 0) enthält, ein. das wären dann wohl 27 skalaren multiplikationen und 15 skalare additionen/subtraktionen. ob das besser ist? das kann man wohl nur im direkten vergleich beurteilen. es kommt ja auch darauf an, wie oft ein treffer tatsächlich eintritt. bei einem miss verrringert sich ja die anzahl der operationen entsprechend.
Man muss ja bedenken, dass ein Vektorprodukt
ja schon 6 Multiplikationen entspricht...die verwendung von vektorbefehlen der cpu kann hier ggf. sehr helfen. das ist dann allerdings nicht mehr mit standard c++ machbar.
eine weitere maßnahme könnte die verringerung der genauigkeit sein. für einen raytracer ist das möglicherweise im allgemeinen inakzeptabel; für einen hittest könnte es aber auch dort angebracht sein.
-
und weil vc6 (standard) nicht optimiert (sowenig wie vc2005, solange du ihm nichts anderes sagst),
Wichtig: VC2005 EE ist ein optimierender Compiler. Nicht das beim LionAM der falsche Eindruck entstünde, er müsse eine Kaufversion besorgen. Optimierung muß (wie von dir gesagt) eingeschaltet sein.
Bemühe mal die MSDN um heraus zu finden, wie man SSE2, MMX usw. nutzen kann.
Vielleicht hilft das hier weiter:
http://msdn2.microsoft.com/en-us/library/26td21ds.aspx
-
Der hier erwähnte GCC optimiert auch erst dann, wenn man ihm das sagt. -O2 oder -O3 müssen schon angegeben werden.
-
camper schrieb:
keine ahnung. ohne mich damit beschäftigt zu haben, fällt mir auf anhieb ein algorithmus ein, der 1-3 vektorprodukte, 1-3 skalarprofukte und 1-3 vergleiche (mit 0) enthält, ein. das wären dann wohl 27 skalaren multiplikationen und 15 skalare additionen/subtraktionen. ob das besser ist? das kann man wohl nur im direkten vergleich beurteilen. es kommt ja auch darauf an, wie oft ein treffer tatsächlich eintritt. bei einem miss verrringert sich ja die anzahl der operationen entsprechend.
Das klingt sehr danach, als ob bei dir getestet wird, ob ein
Punkt in der Ebene des Dreiecks innerhalb desselben liegt.
Der Punkt muss ja aber erst berechnet werden... (irgendwie fehlt
mir bei dir der Offset) - das ist bei mir schon drin.
Ob der Punkt drin liegt, ist bei mir mit 1-3 Skalarprodukten
und Vergleichen raus... (kein Vektorprodukt)Weil anscheinend einige anscheinend etwas anderes Vermuten:
sowohl bei gcc als auch bei VC2005 habe ich natürlich die Optimierungen
engeschaltet (und, was bisher nicht erwähnt wurde, als Release
compiliert).Ich werd mich aber erst mal nicht länger mit dem Optimieren
aufhalten, sondern erst mal weiterprogrammieren. Da wird sich
noch einiges in der Klasse (und im Hauptprogramm sowieso) ändern.
Da macht es jetzt noch nicht so viel Sinn, da weiterzuoptimieren.Alex
-
LionAM schrieb:
camper schrieb:
keine ahnung. ohne mich damit beschäftigt zu haben, fällt mir auf anhieb ein algorithmus ein, der 1-3 vektorprodukte, 1-3 skalarprofukte und 1-3 vergleiche (mit 0) enthält, ein. das wären dann wohl 27 skalaren multiplikationen und 15 skalare additionen/subtraktionen. ob das besser ist? das kann man wohl nur im direkten vergleich beurteilen. es kommt ja auch darauf an, wie oft ein treffer tatsächlich eintritt. bei einem miss verrringert sich ja die anzahl der operationen entsprechend.
Das klingt sehr danach, als ob bei dir getestet wird, ob ein
Punkt in der Ebene des Dreiecks innerhalb desselben liegt.
Der Punkt muss ja aber erst berechnet werden... (irgendwie fehlt
mir bei dir der Offset) - das ist bei mir schon drin.
Ob der Punkt drin liegt, ist bei mir mit 1-3 Skalarprodukten
und Vergleichen raus... (kein Vektorprodukt)den schnittpunkt ermittele ich nicht. die idee ist die:
nehmen wir das orientierte dreieck ABC, der strahl sei durch den ursprung P und einen weiteren punkt Q definiert (z.b. einfach Q = P + v, falls du nur einen richtungsvektor hast, der abstand PQ ist jedenfalls egal).
dann ist PABC ein tetraeder (ob der degenerierte fall, wenn P in der ebene von ABC liegt, gesondert behandelt werden muss, müsste noch überlegt werden).
jetzt müssen wir nur schauen, in welchen halbräumen der punkt Q bezüglich der ebenen ABP, BCP und CAP liegt. jeder einzelne test (jeweils ein vektor-und skalarprodukt) kann dazu führen, das ein dreieck aussortiert wird (im schnitt würde ich 50% im ersten, 25% im zweiten und 25% im dritten test erwarten, wenn der strahl das dreieck nicht trifft - also im schnitt 1.75 tests je dreieck). da wir hier hier nur multiplikation und addition arbeiten, ist die fehlerfortpflanzung kein thema und man kann das ganze ohne weiteres mit relativ geringer genauigkeit berechnen lassen, ohne viele fehler zu machen.edit: wir brauchen am anfang noch ein skalarprodukt zwischen dem normalenvektor des dreiecks (sicherlich schonmal irgendwann vorausberechnet) und AP (oder BP,CP), um das vorzeichen in jedem test richtig interpretieren zu können. damit lässt sich der degenerierte fall auch ohne zusätzlichen aufwand aussortieren (in diesem fall wäre das skalarprodukt ja 0)