Frage Warum kann der C ++ - Compiler "if (test) - foo" nicht auf "foo - = test" optimieren?


Ich habe eine Funktion, die für eine gegebene Ganzzahl die nächste Potenz von zwei findet. Wenn die Ganzzahl eine Zweierpotenz ist, gibt sie die Potenz zurück.

Ziemlich einfach:

char nextpow2if(int a)
{
    char foo = char(32 - __builtin_clz(a));
    bool ispow2 = !(a & a-1);
    if (ispow2) --foo;
    return foo;
}

Nach dem Kompilieren mit gcc 6 mit -O2, nach der Überprüfung der generierten Assembly, sehe ich jedoch, dass dies mit scheinbar nutzlosen Anweisungen kompiliert wird cmovne nach der Berechnung von foo-1. Noch schlimmer mit gcc5 und älter bekomme ich einen tatsächlichen jne verzweigen Sie in den Code.

Der schnellere Weg, dies zu kompilieren, wäre, als ob ich die folgende Funktion geschrieben hätte:

char nextpow2sub(int a)
{
    char foo = char(32 - __builtin_clz(a));
    bool ispow2 = !(a & a-1);
    return foo - ispow2;
}

Dieser Code wird von allen Compilern korrekt zu der kürzesten (und schnellsten) möglichen Assembly mit a kompiliert sete und Subtraktion für den Bool.

Warum kann der Compiler den ersten nicht optimieren? Dies scheint ein wirklich leicht zu identifizierender Fall zu sein. Warum kompiliert gcc 5 und älter dies zu einem tatsächlichen jne Ast? Gibt es einen Grenzfall zwischen den beiden Versionen, den ich nicht sehen kann, der dazu führen könnte, dass sie sich anders verhalten?

PS: Live-Demo Hier

Edit: Ich habe die Leistung mit gcc 6 nicht getestet, aber mit gcc 5 ist letzteres etwa zwei mal schneller (zumindest in einem synthetischen Performanz-Test). Das hat mich dazu gebracht, diese Frage zu stellen.


6
2017-11-16 10:27


Ursprung


Antworten:


Ich glaube, der Grund dafür könnte sein bool wird typischerweise in einem Byte gespeichert. Daher kann der Compiler den aktuellen Speicher möglicherweise nicht sicher annehmen genau gleich 1. Der true/false check vergleicht wahrscheinlich nur gegen null. Subtraktion könnte jedoch eine andere Geschichte mit Nebenwirkungen sein.

Sehen Beispielcode auf Ideone:

#include <iostream>
using namespace std;

union charBool
{
    unsigned char aChar;
    bool aBool;
};

int main() 
{
    charBool var;
    charBool* varMemory = &var;

    var.aBool = 65;
    std::cout << "a boolean = " << var.aBool << std::endl;
    std::cout << "a char = " << var.aChar << std::endl;
    std::cout << "varMemory = " << (*(reinterpret_cast<unsigned char*>(varMemory))) << std::endl;

    var.aChar = 98;   // note: Ideone C++ compiler resolves this to zero, hence bit0 seems to be the only checked
    std::cout << "a boolean = " << var.aBool << std::endl;
    std::cout << "a char = " << var.aChar << std::endl;
    std::cout << "varMemory = " << (*(reinterpret_cast<unsigned char*>(varMemory))) << std::endl;

    return 0;
}

Das ergibt:

a boolean = 1
a char = 
varMemory = 
a boolean = 0
a char = b
varMemory = b

(Hinweis: die ersten zwei Zeichen sind nicht druckbar)


0
2017-11-16 10:46



Nun, der Compiler könnte diese Optimierung in diesem speziellen Fall durchführen, ohne den Standard zu verletzen. Aber bedenken Sie den folgenden etwas anderen Fall:

char nextpow2sub(int a)
{
    char foo = char(32 - __builtin_clz(a));
    bool ispow2 = !(a & a-1);
    return foo - (5 * ispow2);
}

char nextpow2if(int a)
{
    char foo = char(32 - __builtin_clz(a));
    bool ispow2 = !(a & a-1);
    if (ispow2) foo = foo - 5;
    return foo;
}

Die einzige Änderung, die ich hier vorgenommen habe, ist, dass ich Subtrahieren um 5 statt 1 subtrahieren. Wenn Sie mit gcc 6.x kompilieren und vergleichen, sehen Sie, dass der generierte Binärcode für beide Funktionen die gleiche Größe hat. Ich erwarte auch, dass beide mehr oder weniger die gleiche Leistung haben.

Dies zeigt, dass der Optimierungsalgorithmus, den der Compiler verwendet hat, für den allgemeinen Fall entworfen wurde. Das heißt, selbst für den Fall der Subtraktion um 1 erwarte ich (unter Verwendung von gcc 6.x), dass es einen kleinen Leistungsunterschied bei jedem modernen Prozessor gibt, der Parallelität auf Befehlsebene und Registerumbenennung unterstützt.

Dieser Code wird von allen Compilern korrekt zu den kürzesten (und   schnellste) mögliche Montage mit a sete und Subtraktion für die bool.

Woher wussten Sie, dass dies der kürzeste und schnellste Code ist? Ja, es ist kürzer und schneller, aber haben Sie den Beweis, dass dies der kürzeste und schnellste ist? Auch können Sie eine solche Aussage nicht geben, ohne eine bestimmte Architektur und Mikroarchitektur anzugeben.


0
2017-11-23 07:06