Also gibt es einen if-else-Zweig in meinem Programm mit etwa 30 if-else-Anweisungen. Dieser Teil läuft mehr als 100 Mal pro Sekunde, also sah ich es als eine Gelegenheit, zu optimieren, und machte es binäre Suche mit einem Funktionszeigerarray (praktisch eine ausgeglichene Baumkarte), anstatt lineare if-else Bedingungsprüfungen durchzuführen. Aber es lief langsamer um 70% der vorherigen Geschwindigkeit.
Ich habe ein einfaches Benchmark-Programm erstellt, um das Problem zu testen, und es ergab auch ein ähnliches Ergebnis, dass der if-else-Teil sowohl mit als auch ohne Compiler-Optimierung schneller läuft.
Ich habe auch die Anzahl der durchgeführten Vergleiche gezählt, und wie erwartet, hat derjenige, der die binäre Suche durchführt, ungefähr die Hälfte der Vergleiche gemacht, als der einfache if-else-Zweig. Aber es lief immer noch 20 ~ 30% langsamer.
Ich möchte wissen, wo all meine Rechenzeit verschwendet wird und warum das lineare if-else schneller läuft als die logarithmische binäre Suche?
%Vor%mögliche Ausgabe:
%Vor% Sie sollten sich die generierten Anweisungen ansehen ( gcc -S source.c ), aber im Allgemeinen kommt es auf diese drei an:
Wenn Sie nur 8 verschiedene Zweige haben, führen Sie durchschnittlich 4 Prüfungen durch (unter Annahme von gleich wahrscheinlichen Fällen, sonst könnte es sogar noch schneller gehen).
Wenn Sie es zu einer binären Suche machen, wird log (8) == 3 überprüft, aber diese Prüfungen sind viel komplexer, was dazu führt, dass insgesamt mehr Code ausgeführt wird.
Also, wenn Ihr N nicht zu Hunderten ist, macht es wahrscheinlich keinen Sinn, dies zu tun. Sie könnten Profiling durchführen, um den tatsächlichen Wert für N zu finden.
Im Falle einer linearen Suche ist jede Bedingung in 1/N cases wahr, was bedeutet, dass der Compiler und der Verzweigungsprädiktor keine Verzweigung annehmen und dann nur einmal wiederherstellen können. Bei einer binären Suche wird die Pipeline wahrscheinlich einmal in jeder Schicht gelöscht. Und für N & lt; 1024, 1/log(N) Wahrscheinlichkeit einer Fehlvorhersage schadet tatsächlich der Leistung.
Wenn Sie einen Zeiger auf eine Funktion ausführen, müssen Sie sie aus dem Speicher holen, dann müssen Sie Ihre Funktion in den Befehlscache laden, dann führen Sie die Aufrufanweisung, die Funktion setup und return aus. Sie können keine Inline-Funktionen aufrufen, die über einen Zeiger aufgerufen werden, dh es gibt mehrere zusätzliche Anweisungen sowie Speicherzugriff und Verschieben von Objekten in den Cache. Es summiert sich ziemlich schnell.
Alles in allem ist dies nur für ein großes N sinnvoll, und Sie sollten immer ein Profil erstellen, bevor Sie diese Optimierungen anwenden.
Verwenden Sie eine switch-Anweisung.
Compiler sind schlau. Sie werden den effizientesten Code für Ihre speziellen Werte produzieren. Sie werden sogar eine binäre Suche (mit Inline-Code) durchführen, wenn dies als effizienter erachtet wird.
Und als großer Vorteil ist der Code lesbar und erfordert nicht, dass Sie an einem halben Dutzend Stellen Änderungen vornehmen, um einen neuen Fall hinzuzufügen.
PS. Offensichtlich ist dein Code eine gute Lernerfahrung. Jetzt hast du es gelernt, also mach es nicht noch einmal: -)
Tags und Links optimization c binary-search linear-search