Ich habe kürzlich einen Code für ein Forschungsprojekt geschrieben, an dem ich arbeite, wo Effizienz sehr wichtig ist. Ich habe darüber nachgedacht, einige der regulären Methoden, in denen ich Dinge mache, zu entfernen und stattdessen bitweise XORs zu verwenden. Was ich mich wundere ist, ob dies einen Unterschied machen wird (wenn ich diese Operation mache, sagen wir mehrere Millionen Mal) oder ob es dasselbe ist, nachdem ich 03 in g ++ benutzt habe.
Die zwei Beispiele, die Ihnen einfallen:
Ich hatte eine Instanz, wo (ich arbeite mit rein positiven Ints) Ich musste n zu n-1 ändern, wenn n ungerade war oder n zu (n + 1) wenn n gerade war. Ich dachte, ich hätte ein paar Optionen:
%Vor%oder
%Vor%Schließlich:
%Vor%Alle Methoden machen eindeutig dasselbe, aber mein Gefühl war, dass der dritte der effizienteste wäre.
Das nächste Beispiel ist allgemeiner gehalten. Sagen wir, ich vergleiche zwei positive ganze Zahlen, wird eine davon besser als die anderen funktionieren. Oder wird der Unterschied wirklich nicht auffallen, auch wenn ich diese Operation mehrere Millionen Male mache:
%Vor%Wird der Compiler in all diesen Fällen die gleiche Operation ausführen? Ich bin nur neugierig, ob es eine Instanz gibt, in der ich bitweise Operationen verwenden sollte und nicht dem Compiler traue, die Arbeit für mich zu erledigen.
Korrigiert: In korrekter Angabe des Problems.
Es ist einfach genug zu überprüfen, feuern Sie einfach Ihren Disassembler. Schau es dir an:
f.c:
%Vor%Erstellen und disassemblieren:
%Vor% Es sieht so aus, als ob f1() etwas kürzer ist, ob das in der Realität zählt oder nicht, liegt an einem Benchmarking.
Ich musste n zu n-1 ändern, wenn n gerade war oder n zu (n + 1), wenn n ungerade war.
In diesem Fall ist n = n ^ 1 unabhängig von der Effizienz falsch .
Für Ihren zweiten Fall ist == genauso effizient (wenn nicht noch so) wie alle anderen.
Wenn es um die Optimierung geht, sollten Sie es im Allgemeinen selbst bewerten . Wenn eine mögliche Optimierung kein Benchmarking wert ist, lohnt es sich nicht wirklich.
Ich stimme den meisten Antworten hier nicht zu, weshalb ich mich immer noch auf eine Frage von 2010 beziehe: -)
XOR ist praktisch der schnellste Vorgang, den eine CPU ausführen kann, und der gute Teil ist, dass alle CPUs es unterstützen. Der Grund dafür ist ziemlich einfach: Ein XOR-Gatter kann mit nur 4 NAND-Gattern oder 5 NOR-Gattern erstellt werden - was bedeutet, dass es einfach ist, mit der Struktur Ihres Siliziums zu erstellen. Nicht überraschend, alle CPUs, die ich kenne, können Ihre XOR-Operation in 1 Uhr Tick (oder sogar weniger) ausführen.
Wenn Sie ein XOR für mehrere Elemente in einem Array ausführen müssen, unterstützen moderne x64-CPUs auch XORs für mehrere Elemente gleichzeitig, wie z. die SIMD-Anweisungen auf Intel.
Die alternative Lösung, die Sie wählen, verwendet das if-then-else. Es stimmt, die meisten Compiler sind in der Lage, diese einfache Sache zu verstehen ... aber warum sollten Sie irgendwelche Risiken eingehen und was ist die Konsequenz?
Die Konsequenz Ihres Compilers, es nicht herauszufinden, sind Verzweigungsvorhersagefehler. Ein einzelner Verzweigungsvorhersagefehler wird leicht 17 Takt-Ticks dauern. Wenn Sie einen Blick auf die Ausführungsgeschwindigkeit von Prozessoranweisungen werfen, werden Sie feststellen, dass Verzweigungen für Ihre Leistung ziemlich schlecht sind, besonders wenn Sie mit zufälligen Daten arbeiten.
Beachten Sie, dass dies auch bedeutet, dass, wenn Sie Ihren Test falsch konstruieren, die Daten Ihre Leistungsmessungen durcheinander bringen.
Also zum Schluss: erst denken, dann programmieren, dann profilieren - nicht umgekehrt. Und verwende XOR.
Über den einzigen Weg, um sicher zu wissen, ist zu testen. Ich würde zustimmen müssen, dass es einen ziemlich cleveren Compiler braucht, um so effizient wie möglich zu produzieren für:
%Vor% wie für n ^= 1; , aber ich habe vor kurzem nichts Ähnliches überprüft, um es mit Sicherheit zu sagen.
Was Ihre zweite Frage anbelangt, bezweifle ich, dass es einen Unterschied macht - ein Gleichheitsvergleich wird für jede dieser Methoden schnell enden. Wenn Sie Geschwindigkeit wollen, ist die Hauptsache zu vermeiden, überhaupt einen Zweig zu haben - z. etwas wie:
%Vor% kann wie folgt geschrieben werden: c += d * (a==b); . Wenn man sich die Assembler-Sprache anschaut, sieht die zweite oft ein wenig chaotisch aus (mit hässlichem Crust, um das Ergebnis des Vergleichs von den Flags in ein normales Register zu bekommen), aber immer noch besser, wenn man Verzweigungen vermeidet.
Edit: Zumindest die Compiler, die ich praktisch habe (gcc & amp; MSVC), erzeugen kein cmov für if , aber sie erzeugen sete für * (a==b) . Ich habe den Code auf etwas Testbares erweitert.
Edit2: Da Potatoswatter eine andere Möglichkeit bitweise und statt der Multiplikation aufbaute, beschloss ich, das zusammen mit den anderen zu testen. Hier ist der Code mit dem hinzugefügt:
%Vor%Nun der wirklich interessante Teil: Die Ergebnisse für die dritte Version sind durchaus interessant. Für MS VC ++ erhalten wir ungefähr, was die meisten von uns wahrscheinlich erwarten würden:
%Vor% Die Verwendung von & anstelle von * führt zu einer deutlichen Verbesserung - fast ist eine Verbesserung, da * mehr als if ergibt. Mit gcc ist das Ergebnis allerdings ein bisschen anders:
In diesem Fall liegt der Code mit if viel näher an der Geschwindigkeit des Codes mit * , aber der Code mit & ist langsamer als jeder - ein Los Langsamer! Falls es jemanden interessiert, fand ich das überraschend genug, dass ich ein paar mal mit verschiedenen Flags neu kompiliert habe, ein paar mal mit jedem neu durchgelaufen bin, und das Ergebnis war völlig konsistent - der Code mit & war konsequent deutlich langsamer.
Das schlechte Ergebnis mit der dritten Version des mit gcc kompilierten Codes bringt uns zurück zu dem, was ich gesagt habe, um mit [zu beginnen und diese Änderung zu beenden]:
Wie ich schon sagte, "der einzige Weg, um sicher zu sein, ist zu testen" - aber zumindest in diesem begrenzten Test schlägt die Multiplikation konsistent die if . Möglicherweise gibt es eine einige Kombination aus Compiler, Compilerflags, CPU, Datenmuster, Iterationszählung usw., die die if über die Multiplikation favorisiert - es gibt keine Frage, dass der Unterschied klein genug ist Ein Test, der in die andere Richtung geht, ist absolut glaubwürdig. Trotzdem glaube ich, dass es eine Technik ist, die es zu wissen lohnt. Für Mainstream-Compiler und CPUs scheint es einigermaßen effektiv zu sein (obwohl es bei MSVC sicherlich hilfreicher ist als bei gcc).
[Wiederaufnahme von edit2:] Das Ergebnis mit gcc mit & demonstriert den Grad, in dem 1) Mikrooptimierungen compilerspezifisch sein können und 2) wie viel unterschiedliche reale Ergebnisse von den Erwartungen sein können.
Ist n^=1 schneller als if ( n%2 ) --n; else ++n; ? Ja. Ich würde nicht erwarten, dass ein Compiler das optimiert. Da die bitweise Operation so viel prägnanter ist, könnte es sich lohnen, sich mit XOR vertraut zu machen und vielleicht einen Kommentar zu dieser Codezeile hinzuzufügen.
Wenn es für die Funktionalität Ihres Programms entscheidend ist, könnte es auch als Portabilitätsproblem betrachtet werden: Wenn Sie Ihren Compiler testen und es schnell geht, würden Sie wahrscheinlich eine Überraschung erleben, wenn Sie einen anderen Compiler ausprobieren. Normalerweise ist dies kein Problem für algebraische Optimierungen.
Ist x^y schneller als x==y ? Nein, Dinge auf Umwegen zu tun, ist im Allgemeinen nicht gut.
Ein guter Compiler optimiert n%2 , aber Sie können immer die produzierte Assembly überprüfen. Wenn Sie Divisionen sehen, starten Sie die Optimierung selbst, da divide so langsam wie möglich ist.
Sie sollten Ihrem Compiler vertrauen. gcc / ++ ist das Produkt jahrelanger Entwicklung und ist in der Lage, alle Optimierungen durchzuführen, an die Sie wahrscheinlich denken. Und wenn Sie anfangen, herumzuspielen, werden Sie wahrscheinlich daran arbeiten, Ihren Code zu optimieren.
n ^= 1 und n1==n2 sind wahrscheinlich die besten, die Sie tun können, aber wirklich, wenn Sie nach maximaler Effizienz suchen, achten Sie nicht auf den Code auf der Suche nach kleinen Dingen wie das.
Hier ist ein Beispiel, wie Sie die Leistung wirklich optimieren können.
Erwarten Sie nicht, dass Low-Level-Optimierungen viel helfen, bis die Stichprobe bewiesen hat, dass sie sich dort konzentrieren sollten.
Tags und Links c++ performance bitwise-operators