Welche Optimierungsstufe (g++) verwenden Sie beim Vergleich zweier verschiedener in C++ geschriebener Algorithmen?

Question

Ich habe zwei Algorithmen in C++ geschrieben. Soweit ich weiß, ist es üblich, sie mit
-O0 -NDEBUG (g++) beim Vergleich der Leistung der beiden Algorithmen (asymptotisch sind sie gleich).
Aber ich denke, die Optimierungsebene ist unfair zu einem von ihnen, weil es STL in jedem Fall verwendet. Das Programm, das ein einfaches Array verwendet, übertrifft den STL-lastigen Algorithmus um den Faktor 5, wenn es mit der Option -O0 kompiliert wird. Aber der Leistungsunterschied ist nicht viel anders, wenn ich sie mit -O2 -NDEBUG kompiliere.

Gibt es eine Möglichkeit, das Beste aus STL herauszuholen (ich bekomme starke Leistungseinbußen in der vector [] Operator) in der Optimierungsebene -O0?

Welche Optimierungsstufe (und möglicherweise Variablen wie -NDEBUG) verwenden Sie beim Vergleich zweier Algorithmen?

Es wäre auch eine große Hilfe, wenn jemand etwas über den Trend in der akademischen Forschung zum Vergleich der Leistung von in C++ geschriebenen Algorithmen sagen könnte.

---

Ok, um das Problem der Optimierungsebene zu isolieren, verwende ich jetzt einen Algorithmus, aber zwei verschiedene Implementierungen.

Ich habe eine der Funktionen mit rohen Zeigern (int und boolean) in std::vector und std::vector geändert... Mit -O0 -NDEBUG sind die Leistungen 5,46s(raw pointer) und 11,1s(std::vector). Und mit -O2 -NDEBUG sind die Leistungen 2,02s (roher Zeiger) und 2,21s (std::vector). Derselbe Algorithmus, eine Implementierung verwendet 4/5 dynamische Arrays von int und boolean. Die andere verwendet stattdessen std::vector und std::vector. In jedem anderen Fall sind sie gleich

Sie können sehen, dass std::vector in -O0 mit doppelt so schnellen Zeigern übertroffen wird. Bei -O2 sind sie fast gleich schnell.

Aber ich bin wirklich verwirrt, weil in akademischen Bereichen, wenn sie die Ergebnisse von Algorithmen in Laufzeit veröffentlichen, kompilieren sie die Programme mit -O0.

Gibt es einige Compiler-Optionen, die ich vermisse?

Answer 1

Das hängt davon ab, was Sie optimieren wollen.

Velocidad

Ich empfehle die Verwendung von -O2 -NDEBUG -ftree-vectorize und wenn Ihr Code speziell für die Ausführung auf x86 oder x86_64 konzipiert ist, fügen Sie -msse2 . So erhalten Sie eine grobe Vorstellung davon, wie es mit GIMPLE funktionieren wird.

Tamaño

Ich glaube, Sie sollten Folgendes verwenden -Os -fno-rtti -fno-exceptions -fomit-frame-pointer . Dadurch wird die Größe der ausführbaren Datei bis zu einem gewissen Grad minimiert (C++ vorausgesetzt).

---

In beiden Fällen ist die Geschwindigkeit des Algorithmus nicht vom Compiler abhängig, aber ein Compiler kann das Verhalten des Codes drastisch verändern, wenn er es "beweisen" kann.

GCC erkennt "gewöhnlichen" Code wie handcodierten min() y max() und verwandelt sie in einen SSE-Befehl (auf x86/x86_64 und wenn -msse gesetzt ist) oder verwendet cmov, wenn i686 verfügbar ist (SSE hat höhere Priorität). GCC nimmt sich auch die Freiheit, Schleifen neu zu ordnen, Funktionen abzurollen und zu inlinen, wenn er das möchte, und entfernt sogar nutzlosen Code.

Was Ihre letzte Bearbeitung betrifft:

Sie können sehen, dass bei -O0 std::vector mit doppelt so schnellen Zeigern übertroffen wird Zeigern. Bei -O2 sind sie fast gleich sind.

Das liegt daran, dass std::vector hat immer noch Code, der Ausnahmen auslöst und rtti verwenden kann. Versuchen Sie einen Vergleich mit -O2 -NDEBUG -ftree-vectorize -fno-rtti -fno-exceptions -fomit-frame-pointer und Sie werden sehen, dass std::vector etwas besser sein wird als Ihr Code. GCC weiß, was "eingebaute" Typen sind und wie man sie ausnutzen kann im praktischen Einsatz und wird dies auch gerne tun - so wie sie weiß, was memset() y memcpy() und wie man sie entsprechend optimiert, wenn die Kopiergröße bekannt ist.

Answer 2

Die Compiler-Optimierungen ändern normalerweise nicht die Komplexitätsreihenfolge eines Algorithmus, sondern nur die Konstante und den linearen Skalierungsfaktor. Compiler sind ziemlich schlau, aber sie sind nicht que schlau.

Werden Sie Ihren Code für die Veröffentlichung nur mit -O0 kompilieren? Wahrscheinlich nicht. Sie können genauso gut die Leistung der Algorithmen vergleichen, wenn sie mit den Kompilierungsflags kompiliert werden, die Sie tatsächlich zu verwenden beabsichtigen.

Answer 3

Sie haben zwei Algorithmen implementiert in C++. Wenn Sie die relative Leistung der beiden Implementierungen vergleichen wollen, sollten Sie die Optimierungsstufe verwenden, die Sie in Ihrem Endprodukt verwenden werden. Für mich ist das -O3 .

Wenn man die Komplexität eines Algorithmus analysieren will, dann ist das eher ein Analyseproblem, bei dem man die Gesamtzahl der Operationen betrachtet, die für verschiedene Größen und Eigenschaften der Eingaben durchgeführt werden müssen.

Als Entwickler, der Code schreibt, bei dem die Leistung eine Rolle spielt, sollten Sie sich über das Spektrum der Optimierungen im Klaren sein, die ein Compiler auf Ihren Code anwenden kann und wahrscheinlich auch wird. Wenn Sie nicht optimieren, benachteiligen Sie Code, der zwar klar geschrieben, aber so konzipiert ist, dass er leicht optimiert werden kann, gegenüber Code, der bereits "mikro-optimiert" ist.

Answer 4

Ich sehe keinen Grund, sie nicht beide bei O2 zu kompilieren und laufen zu lassen. Es sei denn, Sie machen das als rein akademische Übung (und selbst wenn Sie das täten, ist es sehr unwahrscheinlich, dass die Optimierungen grundlegende Änderungen in den Eigenschaften des Algorithmus bewirken würden - obwohl ich mich freuen würde, wenn GCC anfinge, O(N)-Quellcode in O(lgN)-Assembler zu verwandeln), dann wollen Sie Informationen, die mit denen übereinstimmen, die Sie erhalten würden, wenn Sie das endgültige Programm tatsächlich ausführen. Sie werden das Programm höchstwahrscheinlich nicht mit O0-Optimierungen herausgeben, also wollen Sie die Algorithmen nicht unter O0-Optimierungen vergleichen.

Answer 5

Bei einem solchen Vergleich geht es weniger um Fairness als um die Gewinnung nützlicher Informationen. Sie sollten die Optimierungsstufe verwenden, die Sie planen, wenn/falls der Code in Produktion geht. Wenn Sie im Grunde nur Forschung betreiben, also Sie nicht persönlich planen, es in der Produktion einzusetzen, müssen Sie die etwas schwierigere Aufgabe bewältigen, zu erraten, was jemand, der es in der Produktion einsetzen würde, wahrscheinlich tun würde.

Realistisch betrachtet, selbst wenn Sie sich mit der Entwicklung und nicht mit der Forschung befassen, müssen Sie ohnehin ein wenig davon in Kauf nehmen - es ist fast unmöglich vorherzusagen, welche Optimierungsstufe Sie letztendlich mit diesem speziellen Code verwenden werden.

Ich persönlich verwende normalerweise -O2 mit gcc. Meine allgemeine Faustregel ist, die niedrigste Optimierungsstufe zu verwenden, die das automatische Inlining aktiviert. Ich schreibe einen Großteil meines Codes in der Erwartung, dass kleine Funktionen vom Compiler inlined werden -- und schreibe den Code speziell, um dabei zu helfen (z.B. verwende ich oft Funktoren anstelle von Funktionen). Wenn der Compiler nicht so eingestellt ist, dass er Code für diese Inline-Funktionen erzeugt, erhalten Sie nicht das, was ich wirklich beabsichtigt habe. Die Leistung des Codes, wenn er auf diese Weise kompiliert wird, bedeutet nicht wirklich etwas - ich würde sicherlich nicht Ich habe nicht vor, es jemals wirklich auf diese Weise zu benutzen.