Ist die `if`-Anweisung vor Modulo- und vor Assign-Operationen redundant?

Betrachten Sie den nächsten Code:

unsigned idx;
//.. some work with idx
if( idx >= idx_max )
    idx %= idx_max;

Könnte auf nur die zweite Zeile vereinfacht werden:

idx %= idx_max;

und wird das gleiche Ergebnis erzielen.

Mehrmals traf ich den nächsten Code:

unsigned x;
//... some work with x
if( x!=0 )
  x=0;

Könnte vereinfacht werden

x=0;

Die Fragen:

• Gibt es einen Sinn zu verwenden if und warum? Besonders mit dem ARM Thumb-Befehlssatz.
• Könnten diese ifs weggelassen werden?
• Welche Optimierung macht Compiler?

Wenn Sie verstehen möchten, was der Compiler tut, müssen Sie nur eine Assembly aufrufen. Ich empfehle diese Seite (ich habe bereits Code aus der Frage eingegeben)): https://godbolt.org/g/FwZZOb.

Das erste Beispiel ist interessanter.

int div(unsigned int num, unsigned int num2) {
    if( num >= num2 ) return num % num2;
    return num;
}

int div2(unsigned int num, unsigned int num2) {
    return num % num2;
}

Erzeugt:

div(unsigned int, unsigned int):          # @div(unsigned int, unsigned int)
        mov     eax, edi
        cmp     eax, esi
        jb      .LBB0_2
        xor     edx, edx
        div     esi
        mov     eax, edx
.LBB0_2:
        ret

div2(unsigned int, unsigned int):         # @div2(unsigned int, unsigned int)
        xor     edx, edx
        mov     eax, edi
        div     esi
        mov     eax, edx
        ret

Grundsätzlich wird der Compiler nicht Optimieren Sie den Zweig weg, aus ganz bestimmten und logischen Gründen. Wenn die ganzzahlige Division ungefähr die gleichen Kosten wie der Vergleich hätte, wäre die Verzweigung ziemlich sinnlos. Aber ganzzahlige Division (welcher Modul normalerweise zusammen mit durchgeführt wird) ist tatsächlich sehr teuer: http://www.agner.org/optimize/instruction_tables.pdf. Die Zahlen variieren stark je nach Architektur und ganzzahliger Größe, aber es kann sich typischerweise um eine Latenz von 15 bis fast 100 Zyklen handeln.

Indem Sie vor der Ausführung des Moduls eine Verzweigung nehmen, können Sie sich tatsächlich viel Arbeit ersparen. Beachten Sie jedoch: Der Compiler wandelt den Code ohne Verzweigung auch nicht in eine Verzweigung auf Assembly-Ebene um. Das liegt daran, dass der Zweig auch eine Kehrseite hat: Wenn der Modulus am Ende trotzdem notwendig ist, haben Sie nur ein bisschen Zeit verschwendet.

Es gibt keine Möglichkeit, eine vernünftige Entscheidung über die richtige Optimierung zu treffen, ohne die relative Häufigkeit zu kennen idx < idx_max wird wahr sein. Daher entscheiden sich die Compiler (gcc und clang tun dasselbe) dafür, den Code auf relativ transparente Weise abzubilden, und überlassen diese Wahl den Entwicklern.

Dieser Zweig könnte also eine sehr vernünftige Wahl gewesen sein.

Der zweite Zweig sollte völlig sinnlos sein, weil Vergleich und Zuordnung sind zu vergleichbaren Kosten. Allerdings können Sie in dem Link sehen, dass Compiler diese Optimierung immer noch nicht durchführen, wenn sie einen Verweis auf die Variable haben. Wenn der Wert eine lokale Variable ist (wie in Ihrem demonstrierten Code), optimiert der Compiler die Verzweigung weg.

Alles in allem ist das erste Stück Code vielleicht eine vernünftige Optimierung, das zweite wahrscheinlich nur ein müder Programmierer.

Es gibt eine Reihe von Situationen, in denen das Schreiben einer Variablen mit einem Wert, den sie bereits enthält, möglicherweise langsamer ist als das Lesen, das Herausfinden, dass der gewünschte Wert bereits enthalten ist, und das Überspringen des Schreibens. Einige Systeme verfügen über einen Prozessor-Cache, der alle Schreibanforderungen sofort an den Speicher sendet. Während solche Designs heute nicht mehr alltäglich sind, waren sie früher recht verbreitet, da sie einen erheblichen Bruchteil der Leistungssteigerung bieten können, die ein vollständiges Lese-/Schreib-Caching bieten kann, jedoch zu einem kleinen Bruchteil der Kosten.

Code wie der obige kann auch in einigen Multi-CPU-Situationen relevant sein. Die häufigste derartige Situation wäre, wenn Code, der gleichzeitig auf zwei oder mehr CPU-Kernen ausgeführt wird, wiederholt auf die Variable trifft. In einem Mehrkern-Caching-System mit einem starken Speichermodell muss ein Kern, der eine Variable schreiben möchte, zuerst mit anderen Kernen verhandeln, um den exklusiven Besitz der Cache-Zeile zu erwerben, die sie enthält, und muss dann erneut verhandeln, um diese Kontrolle beim nächsten Mal aufzugeben jeder andere Kern möchte es lesen oder schreiben. Solche Operationen können sehr teuer sein, und die Kosten müssen getragen werden, selbst wenn jeder Schreibvorgang einfach den Wert speichert, den der Speicher bereits gehalten hat. Wenn der Speicherort jedoch Null wird und nie wieder beschrieben wird, können beide Kerne die Cache-Zeile gleichzeitig für einen nicht-exklusiven Nur-Lese-Zugriff halten und müssen nie weiter dafür verhandeln.

In fast allen Situationen, in denen mehrere CPUs auf eine Variable treffen könnten, sollte die Variable zumindest deklariert werden volatile. Die einzige Ausnahme, die hier anwendbar sein könnte, wäre in Fällen, in denen alle Schreibvorgänge in eine Variable nach dem Start von erfolgen main() speichert den gleichen Wert, und der Code würde sich korrekt verhalten, unabhängig davon, ob ein Speicher einer CPU in einer anderen sichtbar war oder nicht. Wenn das mehrmalige Ausführen einer Operation verschwenderisch, aber ansonsten harmlos wäre und der Zweck der Variablen darin besteht, anzugeben, ob sie ausgeführt werden muss, können viele Implementierungen möglicherweise besseren Code ohne die generieren volatile Qualifizierer als mit, vorausgesetzt, dass sie nicht versuchen, die Effizienz zu verbessern, indem sie das Schreiben bedingungslos machen.

Übrigens, wenn auf das Objekt über einen Zeiger zugegriffen würde, gäbe es einen weiteren möglichen Grund für den obigen Code: Wenn eine Funktion so konzipiert ist, dass sie entweder a akzeptiert const Objekt, bei dem ein bestimmtes Feld Null ist, oder ein Nicht-const Objekt, für das dieses Feld auf Null gesetzt sein sollte, ist möglicherweise Code wie der obige erforderlich, um in beiden Fällen ein definiertes Verhalten sicherzustellen.

In Bezug auf den ersten Codeblock: Dies ist eine Mikrooptimierung basierend auf den Empfehlungen von Chandler Carruth für Clang (weitere Informationen finden Sie hier), es gilt jedoch nicht unbedingt, dass es sich um eine gültige Mikrooptimierung in dieser Form handelt (mit if eher als ternär) oder auf einem beliebigen Compiler.

Modulo ist eine relativ teure Operation. Wenn der Code häufig ausgeführt wird und eine starke statistische Neigung zu der einen oder anderen Seite der Bedingung besteht, reduziert die Verzweigungsvorhersage der CPU (bei einer modernen CPU) die Kosten der Verzweigungsanweisung erheblich .

Es scheint mir eine schlechte Idee zu sein, das if dort zu verwenden.

Sie haben Recht. Ob oder nicht idx >= idx_maxwird es danach unter idx_max sein idx %= idx_max. Wenn idx < idx_maxes bleibt unverändert, ob dem if gefolgt wird oder nicht.

Während Sie vielleicht denken, dass das Verzweigen um das Modulo herum Zeit sparen könnte, würde ich sagen, dass der wahre Schuldige darin besteht, dass moderne CPUs beim Verfolgen von Verzweigungen ihre Pipeline zurücksetzen müssen, und das kostet relativ viel Zeit. Besser keiner Verzweigung folgen müssen, als eine ganzzahlige Modulo-Operation, die ungefähr so ​​viel Zeit kostet wie eine ganzzahlige Division.

BEARBEITEN: Es stellt sich heraus, dass der Modul im Vergleich zum Zweig ziemlich langsam ist, wie von anderen hier vorgeschlagen. Hier ist ein Typ, der genau diese Frage untersucht: CppCon 2015: Chandler Carruth “Tuning von C++: Benchmarks und CPUs und Compiler! Oh mein Gott!” (vorgeschlagen in einer anderen SO-Frage, die mit einer anderen Antwort auf diese Frage verknüpft ist).

Dieser Typ schreibt Compiler und dachte, es wäre ohne den Zweig schneller; aber seine Benchmarks haben ihm das Gegenteil bewiesen. Selbst wenn der Zweig nur zu 20 % der Zeit belegt war, wurde er schneller getestet.

Ein weiterer Grund, das if nicht zu haben: Eine Codezeile weniger, die gewartet werden muss, und jemand anderes muss herausfinden, was es bedeutet. Der Typ im obigen Link hat tatsächlich ein “schnelleres Modul” -Makro erstellt. IMHO ist diese oder eine Inline-Funktion der richtige Weg für leistungskritische Anwendungen, da Ihr Code ohne die Verzweigung viel verständlicher ist, aber genauso schnell ausgeführt wird.

Schließlich plant der Typ im obigen Video, diese Optimierung Compiler-Autoren bekannt zu machen. Daher wird das if wahrscheinlich für Sie hinzugefügt, wenn nicht im Code. Daher wird nur der Mod allein ausreichen, wenn dies geschieht.