C++Guns – RoboBlog

23.04.2018

C++ Guns: branch free min() with Conditional Move CMOVcc

Filed under: Allgemein — Tags: — Thomas @ 18:04

In der Regel wird die min() Funktion mittels Verzweigung implementiert. Ohne zusätzliche Optimierung führt dies zu einem Sprung im Code und damit zu Branchs Mispredicts. Dies ist gerade beim HPC Code ziemlich schlecht, da im Fall einer falscher Sprungvorhersage die CPU Pipeline wieder zurückgesetzt werden muss.

Es gibt aber Alternativen: Conditional Move CPU Instruktionen. Je nach Bedingung wird ein Wert in ein anderes Register kopiert, oder eben nicht. Da steckt kein Sprung im Code dahinter, das wird alles auf CPU Ebene realisiert. So wird dieser C++ Code zu folgendem Assember ersetzt:

int func(int x, int y) {
    int a = y;
    if(x < y) {
        a = x;
    }
    return a;
}
func(int, int):
  cmp esi, edi        x < y ?
  mov eax, edi        a = y
  cmovle eax, esi     Wenn x<y dann a = x
  ret                 return a

Es ist aber garnicht nötig so komplizierten C++ Code, oder gar inline Assember zu schreiben, der Compiler erkennt das Muster automatisch. So führt die Benutzung von std::min(x,y) zu exakt dem selben Assember Code.

Das ganze Funktioniert bei meinen Tests mit Optimierung O1 und O2, aber nicht mehr mit O3. Da bei dieser Optimierung wohl zuviel Schleifen Optimierungs Magie zum Einsatz kommt. Die verantwortlichen Flags müssten -fif-conversion -fif-conversion2 sein, welche bei jeder Optimierungsstufe aktiv sein.

-fif-conversion

Attempt to transform conditional jumps into branch-less equivalents. This includes use of conditional moves, min, max, set flags and abs instructions, and some tricks doable by standard arithmetics. The use of conditional execution on chips where it is available is controlled by -fif-conversion2.

Enabled at levels -O, -O2, -O3, -Os.
-fif-conversion2

Use conditional execution (where available) to transform conditional jumps into branch-less equivalents.

Enabled at levels -O, -O2, -O3, -Os.

Selbstverständlich funktioniert das auch für Floatingpoint Typen, da reich auch eine einzelne Assembler Anweisung: std::min(x,y)

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress