Heute lese ich Code mit Hilfe einer Nachschlagetabelle anstelle von if-else, um zwei summierte uint8-Werte zu erfassen. Die Karte ist i in i={0...255} und 255 in i={256...511} . Ich fragte mich, wie groß der Gewinn davon sein könnte, und versuchte es herauszufinden, mit gprof,
mit dem unten angehängten Code. Jetzt ohne das -O2-Flag gprof sagt, dass lookup () wie 45% und ifelse () wie 48% der Ausführungszeit dauert. Bei -O2 sind es 56% für lookup () und 43% für ifelse (). Aber ist dieser Benchmark wirklich korrekt? Vielleicht ist viel Code weg optimiert da dst nie gelesen wird?
%Vor%Aktualisierter Code:
%Vor% Nun, da src als std::vector<uint8_t> deklariert ist, ist src[i] nie größer als 255 , was der höchstmögliche Wert für eine 8-Bit-Ganzzahl ohne Vorzeichen ist.
Daher rate ich, dass der Compiler die Überprüfung optimiert. Was bleibt, ist nur die Boilerplate-Schleife, so dass der Benchmark bedeutungslos ist.
Vorausgesetzt, die Überprüfung war nicht bedeutungslos (d. h. gegen 64 statt gegen 255), wird das Ergebnis der "Optimierung" vermutlich stark maschinenabhängig sein. Die Verzweigungsvorhersage kann (abhängig von den Eingabedaten) eine gute Arbeit bei der Verringerung der Kosten der Verzweigung leisten. Die Nachschlagetabelle benötigt andererseits (wiederum abhängig von den Eingangsdaten) wahlfreien Speicherzugriff und verdirbt den Cache ...
Abgesehen von der Sache, die Alexander schon gesagt hat:
Nachschlagetabellen können die Leistung drastisch verbessern . Dies wird jedoch durch die Zeit ausgeglichen, die zum Erstellen der Nachschlagetabelle an erster Stelle benötigt wird. Normalerweise würden Sie dies separat benchmarken.
Es ist noch zu beachten, dass die Nachschlagetabelle Platz im Cache benötigt und daher zu Cache-Misses führen kann, wenn sie groß ist. Wenn genügend Cache-Fehler auftreten, ist die if -Methode schneller als die Nachschlagetabelle.
Schließlich ist gprof sehr gut, um Engpässe zu identifizieren. Aber ich würde es nicht für Benchmarks verwenden. Verwenden Sie stattdessen eine Zeitfunktion. gprof verwendet Sampling, das streng genommen der verbrauchten Zeit zugeordnet werden kann, aber hier weniger genau ist.
Die Behandlung des Arrays lookup ist unterbrochen. Diese Zeile:
ist um eins deaktiviert, Sie möchten lookup[512]; , da Sie mit dem Index 511 zu rechnen scheinen (der auf das 512. Element zugreift). Natürlich, wie Alexander darauf hingewiesen hat, ist es sowieso egal, da uint8_t bedeutet, dass Sie keinen Index von etwas über 255 haben können.
Wie es ist, dieser Code:
%Vor%indexiert außerhalb der Grenzen und schreibt 255 in einen mehr oder weniger zufällig ausgewählten Speicherort.
Sie messen auch die Zeit für die Initialisierung der Nachschlagetabelle, und dies ist möglicherweise nicht das, was Sie wollen. Wenn die Tabelle nur einmal im Produktionscode initialisiert, aber mehrmals verwendet wird, sollten Sie die Initialisierung nicht messen.
Beide Ansätze scheinen ziemlich merkwürdig. Brauchen Sie diese Optimierung wirklich? Wenn ja, würde ich die Verwendung von Vektoren in Frage stellen und stattdessen C-Arrays in Betracht ziehen!
Der "iffelse" -Ansatz scheint offensichtlicher. Ich bezweifle, dass es merklich langsamer / schneller als die Nachschlagetabelle ist, es sei denn, Sie rufen diese Milliarden Male an.
Persönlich würde ich wahrscheinlich nur den src-Vektor klonen, dann darüber iterieren und die Werte fixieren (250 hier verwenden, weil 255 keinen Sinn ergibt, wie erwähnt):
%Vor%Abhängig davon, wie das Klonen tatsächlich vom Compiler durchgeführt und optimiert wird (z. B. kann es eine Blockspeicherkopie machen), könnte dies tatsächlich marginal schneller sein. Es ist sicherlich sauberer und leichter zu verstehen.
Manchmal ist der Compiler schlau genug, um einfache Profiling-Tests zu optimieren. Wenn dies der Fall ist, haben Sie den Trick, den Compiler nicht zu optimieren. Die Verwendung eines viel größeren Wiederholungswerts kann Ihnen auch helfen, bessere Ergebnisse zu erzielen oder Ihnen zu sagen, ob etwas weg optimiert wird.
Nachschlagetabellen können schneller als verkettet sein, wenn / elseifs, aber in diesem Fall würde ich mit nur einem Vergleich nicht viel Unterschied erwarten. Zum Beispiel, wenn Sie 10, 100, 1000 ... Vergleiche hatten, sollte die Nachschlagetabelle im Allgemeinen gewinnen.
Eine mögliche schmutzige kleine C-Lösung (von meinem Kopf und ungetestet / unkompiliert, enthält also wahrscheinlich Fehler):
%Vor%Es würde mich interessieren, wie das aussieht. (Wiederum kann es von der Implementierung von memcpy abhängen, da es nur schneller ist, wenn große Speicherkopien effizienter sind als Byte-für-Byte-Kopien).
Abhängig von der Spezifikation Ihres Chips (d. h. 8-Bit- oder 16-Bit-Registergrößen) kann der Single-Byte-Zugriff schneller sein als der Double-Byte-Zugriff. Wenn dies der Fall ist, könnte der obige Code auch neu geschrieben werden, um dst als ein Array von unit8_t zu behandeln. Dann würde es nur jedes zweite Byte untersuchen und wenn es nicht Null ist, setze es auf 0 und das folgende Byte * auf 0xFF.
(* oder vorheriges Byte, je nach Endian)
Tags und Links optimization c++ performance