Ich habe zwei Versionen der Suche durch ein int-Array für einen bestimmten Wert.
Die erste Version ist die direkte Version
%Vor%Die zweite Version sollte schneller sein. Das übergebene Array muss ein Element größer als im vorherigen Fall sein. Sagen Sie für ein Array mit 5 Werten, ordnen Sie sechs Ints zu und machen Sie dann das folgende
%Vor%Diese Version sollte schneller sein - Sie müssen die Array-Grenzen nicht bei jeder Iteration durch Arr überprüfen.
Jetzt das "Problem". Wenn diese Funktionen 100 KB-Mal in einem Array von 100 KB-Elementen in Debug ausgeführt werden, ist die zweite Version etwa 2x schneller. In Release ist die erste Version jedoch ca. 6000x schneller. Und die Frage ist warum.
Ein Programm, das dies demonstriert, finden Sie unter Ссылка
Jede Einsicht wird sehr geschätzt. Daniel
Hier sind meine Ergebnisse mit DevStudio 2005:
Debuggen:
Freigabe:
Es ist sehr wichtig, dass dies über die Befehlszeile und nicht über DevStudio ausgeführt wird. DevStudio wirkt sich auf die Leistung der App aus.
Der einzige Weg zu wissen, was wirklich passiert, ist der Assembler-Code. Hier ist der Assembler, der in der Version generiert wurde: -
%Vor%Beachten Sie, dass der Compiler den ArrLen-Parameter entfernt und durch eine Konstante ersetzt hat! Es hat es auch als Funktion behalten.
Das hat der Compiler mit der anderen Funktion (FindWithBlock) gemacht: -
%Vor% Hier wurde die Funktion eingezeichnet. Der lea esp,[esp] ist nur ein 7-Byte-NOP, um den nächsten Befehl auszurichten. Der Code überprüft Index 0 separat zu allen anderen Indizes, aber die Hauptschleife ist definitiv enger als die FindWithoutBlock-Version.
Hmmm. Hier ist der Code, der FindWithoutBlock aufruft: -
%Vor%Aha! Die FindWitoutBlock-Funktion wird nur einmal aufgerufen! Der Compiler hat erkannt, dass die Funktion jedes Mal den gleichen Wert zurückgibt und sie für einen einzelnen Aufruf optimiert hat. In FindWithBlock kann der Compiler die gleiche Annahme nicht machen, weil Sie vor der Suche in das Array schreiben, daher ist das Array (potenziell) für jeden Aufruf anders.
Um dies zu testen, fügen Sie das Schlüsselwort volatile wie folgt hinzu: -
Dadurch laufen beide Versionen in ähnlicher Zeit (6.040). Da der Speicherzugriff ein großer Engpass ist, haben die komplexeren Tests von FindWithoutBlock keinen Einfluss auf die Gesamtgeschwindigkeit.
Erstens, ewwwwww ekelhaft C Müll. std::find und Iteratoren?
Aber zweitens ist der Optimierer des Compilers so geschrieben, dass er die erste Form erkennt - nicht die zweite. Es kann zum Beispiel inline, entrollt oder vektorisiert sein, während die zweite nicht sein kann.
Betrachte im allgemeinen Fall das Cache-Problem. Sie berühren das Ende des Arrays und gehen dann zum Anfang - dies könnte ein Cache-Miss sein. Aber im ersten Block gehst du fröhlich nur sequentiell durch das Array - mehr Cache kohärent.
Dies ist eher ein erweiterter Kommentar als eine Antwort. Skizz hat die Frage bereits mit " Aha beantwortet! Die Funktion FindWithoutBlock wird nur einmal aufgerufen! "
Testtreiber
Normalerweise tendiere ich dazu, den Code für den Testtreiber und den Testartikel in separaten Dateien zu speichern. Zum einen werden Sie den Testfahrer nicht liefern. Zum anderen kann der Optimierer durch die Kombination wie gewohnt die Dinge tun, die Sie wirklich nicht tun möchten, z. B. die Funktion einmal anstatt 100.000 mal aufrufen. Wenn Sie sie trennen, können Sie verschiedene Optimierungsstufen für den Treiber und den Testartikel verwenden. Ich neige dazu, den Treiber unoptimiert zu kompilieren, so dass die Schleife, die 100K mal dasselbe tut, 100K mal ausgeführt wird. Der Testartikel hingegen wird mit der für die Veröffentlichung erwarteten Optimierung zusammengestellt.
Verwendung von getchar ()
Es ist normalerweise eine schlechte Idee, beim Testen der CPU-Auslastung einen I / O innerhalb der Testschleife zu verwenden. Ihr Testcode ruft getchar auf, wenn sich das gefundene Element nicht im Array befindet. [Rest der fehlerhaften Analyse wurde entfernt.] Update: Ihr Testcode ruft getchar when auf Das zu findende Objekt befindet sich im Array. Obwohl Ihr Testcode sicherstellt, dass das Objekt nicht gefunden wird (und daher getchar nicht aufgerufen wird), ist es trotzdem keine gute Idee, diesen Anruf zu haben. Tun Sie stattdessen etwas schnell und gutartig.
C gegen C ++
Ihr Code sieht eher wie C ± statt C ++ aus. Sie verwenden malloc anstatt new , Sie mischen C und C ++ - E / A, und Sie verwenden nicht die C ++ - Bibliothek wie std::find . Dies ist typisch für jemanden, der von C nach C ++ wechselt. Es ist gut, Dinge wie std::find zu beachten. Dadurch können Sie Ihre FindWithoutBlock -Funktion vollständig eliminieren.
Vorzeitige Optimierung
Der einzige Grund, diese FindWithBlock -Formulierung zu verwenden, ist, dass diese Suche ein Flaschenhals ist. Ist das wirklich ein Flaschenhals? Die FindWithoutBlock -Formulierung (und noch besser, std::find ) ist wohl ein besserer Weg, da Sie das Array nicht ändern müssen und daher das Array-Argument als const markiert werden kann. Das Array kann nicht mit FindWithBlock als solches markiert werden, weil Sie das Array ändern.
Ich beobachte, dass im ersten Fall der Compiler zur Laufzeit die Größe der Schleife kennt (z.B. & lt; ArrLen). Im zweiten Fall kann der Compiler das nicht wissen.
Die erste for .. Schleife enthält zwei Bedingungen für jede Iteration, während die zweite for Schleife eine Iteration pro Schleife enthält. Bei einer großen Anzahl von Iterationen sollte dieser Unterschied auftreten, da zwischen der zweiten Bedingung und dem Iteratorinkrement eine RAW-Abhängigkeit besteht. Aber ich denke immer noch nicht, dass die Beschleunigung so hoch sein sollte.
Im ersten Beispiel werden bei jeder Iteration zwei Bedingungen überprüft: i < ArrLen und Arr[i] == Val . Im zweiten Beispiel gibt es nur eine Bedingung zu überprüfen. Deshalb ist die erste Schleife doppelt so langsam.
Ich kann das gleiche Verhalten nicht mit GCC beobachten: Die erste Schleife ist noch langsamer.
Mit -O0 :
Mit -O3 :
Ich nehme an, dass der Compiler irgendwie abgeleitet hat, dass es kein SearchVal im Array gibt und daher gibt es keinen Grund, eine Funktion aufzurufen, die danach sucht.
Ihr Compiler ist schlau.
Wenn Sie die Seite LLVM Try Out verwenden, erhalten Sie folgende generierte IR:
%Vor% Der einzige Unterschied ist das Vorhandensein des Attributs readonly für die erste Funktion:
Auf der Seite Sprachreferenz :
readonly
Dieses Attribut zeigt an, dass die Funktion nicht über Zeigerargumente (einschließlich byval-Argumente) schreibt oder anderweitig irgendeinen Zustand (z. B. Speicher, Steuerregister usw.) ändert, der für Funktionen des Aufrufers sichtbar ist. Es kann Zeigerargumente de-referenzieren und den Status lesen, der in dem Aufrufer festgelegt werden kann. Eine readonly-Funktion gibt immer denselben Wert zurück (oder gibt eine Ausnahme identisch zurück), wenn sie mit demselben Satz von Argumenten und dem globalen Status aufgerufen wird. Es kann keine Ausnahme durch Aufruf der C ++ - Exception-Wowing-Methoden auflösen.
Dies bedeutet, dass der Optimierer möglicherweise erkennt, dass die Funktion immer die gleiche Berechnung (für eine gegebene Schleife) zurückgibt und sie außerhalb der Schleife aufhebt.
Tags und Links c++ performance