Micro-Optimierung einer C++ Vergleichsfunktion

Question

Ich habe eine Compare() Funktion, die wie folgt aussieht:

inline bool Compare(bool greater, int p1, int p2) { 
    if (greater) return p1>=p2; 
    else return p1<=p2; 
} 

I Verzweigung zu optimieren entschied zu vermeiden:

inline bool Compare2(bool greater, int p1, int p2) { 
    bool ret[2] = {p1<=p2,p1>=p2}; 
    return ret[greater]; 
} 

ich dann, indem Sie diese getestet:

Die Ergebnisse:

Compare(): 3.14ns avg 
Compare2(): 1.61ns avg 

Ich würde sagen, Fall geschlossen, vermeiden Verzweigung FTW. Aber für die Vollständigkeit, ersetzte ich

a[i] = rand()%2; 

mit:

a[i] = true; 

und bekam genau die gleiche Messung von ~ 3.14ns. Vermutlich gibt es dann keine Verzweigung, und der Compiler schreibt tatsächlich Compare() um, um die if Anweisung zu vermeiden. Aber warum ist Compare2() schneller?

Leider bin ich Assembler-Analphabet, sonst hätte ich versucht, das selbst zu beantworten.

EDIT: Im Folgenden finden Sie einige Montage:

_Z7Comparebii: 
.LFB4: 
    .cfi_startproc 
    .cfi_personality 0x3,__gxx_personality_v0 
    pushq %rbp 
    .cfi_def_cfa_offset 16 
    movq %rsp, %rbp 
    .cfi_offset 6, -16 
    .cfi_def_cfa_register 6 
    movl %edi, %eax 
    movl %esi, -8(%rbp) 
    movl %edx, -12(%rbp) 
    movb %al, -4(%rbp) 
    cmpb $0, -4(%rbp) 
    je  .L2 
    movl -8(%rbp), %eax 
    cmpl -12(%rbp), %eax 
    setge %al 
    jmp  .L3 
.L2: 
    movl -8(%rbp), %eax 
    cmpl -12(%rbp), %eax 
    setle %al 
.L3: 
    leave 
    ret 
    .cfi_endproc 
.LFE4: 
    .size _Z7Comparebii, .-_Z7Comparebii 
    .section  .text._Z8Compare2bii,"axG",@progbits,_Z8Compare2bii,comdat 
    .weak _Z8Compare2bii 
    .type _Z8Compare2bii, @function 
_Z8Compare2bii: 
.LFB5: 
    .cfi_startproc 
    .cfi_personality 0x3,__gxx_personality_v0 
    pushq %rbp 
    .cfi_def_cfa_offset 16 
    movq %rsp, %rbp 
    .cfi_offset 6, -16 
    .cfi_def_cfa_register 6 
    movl %edi, %eax 
    movl %esi, -24(%rbp) 
    movl %edx, -28(%rbp) 
    movb %al, -20(%rbp) 
    movw $0, -16(%rbp) 
    movl -24(%rbp), %eax 
    cmpl -28(%rbp), %eax 
    setle %al 
    movb %al, -16(%rbp) 
    movl -24(%rbp), %eax 
    cmpl -28(%rbp), %eax 
    setge %al 
    movb %al, -15(%rbp) 
    movzbl -20(%rbp), %eax 
    cltq 
    movzbl -16(%rbp,%rax), %eax 
    leave 
    ret 
    .cfi_endproc 
.LFE5: 
    .size _Z8Compare2bii, .-_Z8Compare2bii 
    .text 

nun der eigentliche Code, der den Test verwenden könnte inlined Versionen der oben genannten zwei Funktionen erfüllt, so besteht die Möglichkeit, das der falsche sein könnte Code zu analysieren. Mit diesem gesagt, sehe ich einen jmp Befehl in Compare(), also denke ich, dass es bedeutet, dass es sich verzweigt. Wenn ja, denke ich, diese Frage wird: Warum verbessert der Zweig Prädiktor nicht die Leistung von Compare(), wenn ich a[i] von rand()%2 zu true (oder false für diese Angelegenheit) ändern?

EDIT2: Ich ersetzt "Verzweigung Vorhersage" mit "Verzweigung", um meine Post sinnvoller zu machen.

Answer 1

Ich glaube, ich die meisten dieser herausgefunden.

Als ich die Assembly für die Funktionen in meinem OP-Bearbeitung veröffentlicht, habe ich festgestellt, dass die Inline-Version möglicherweise anders sein. Ich hatte den Timing-Code nicht untersucht oder gepostet, weil es haariger war, und weil ich dachte, dass sich der Inlining-Prozess nicht ändern würde, unabhängig davon, ob die Verzweigung in Compare() stattfindet oder nicht.

Wenn ich die Funktion und wiederholte meine Messungen-un inlined ich die folgenden Ergebnisse erhielt:

Compare(): 7.18ns avg 
Compare2(): 3.15ns avg 

Dann, als ich a[i]=rand()%2 mit a[i]=false ersetzt, bekam ich folgendes:

Compare(): 2.59ns avg 
Compare2(): 3.16ns avg 

Dies zeigt den Vorteil der Verzweigungsvorhersage. Die Tatsache, dass die Substitution a[i] keine Verbesserung ergab, zeigt ursprünglich, dass das Inlining den Zweig entfernt hat.

Also das letzte Stück des Geheimnisses ist, warum die inline Compare2() übertrifft die inline Compare(). Ich nehme an, ich könnte die Assembly für den Timing-Code buchen. Es scheint plausibel genug zu sein, dass eine gewisse Eigenart, wie Funktionen inline werden, dazu führen könnte, also bin ich damit zufrieden, meine Untersuchung hier zu beenden. Ich werde Compare() durch Compare2() in meiner Anwendung ersetzen.

Danke für die vielen hilfreichen Kommentare.

EDIT: Ich sollte hinzufügen, dass der wahrscheinliche Grund, dass Compare2 schlägt alle anderen ist, dass der Prozessor beide Vergleiche parallel durchführen kann. Das war die Intuition, die mich dazu brachte, die Funktion so zu schreiben, wie ich es tat. Alle anderen Varianten benötigen im Wesentlichen zwei logisch serielle Operationen.

Answer 2

Wie wäre es damit ...

inline bool Compare3(bool greater, int p1, int p2) 
{ 
    return (!greater != !(p1 <= p2)) | (p1 == p2); 
} 

oder

inline bool Compare4(bool greater, int p1, int p2) 
{ 
    return (greater^(p1 <= p2)) | (p1 == p2); 
} 

Answer 3

Ich schrieb eine C++ - Bibliothek namens Celero entworfen, um nur solche Optimierungen und Alternativen zu testen. (Shameless Eigenwerbung: https://github.com/DigitalInBlue/Celero)

Ich lief Ihre Fälle mit dem folgenden Code:

class StackOverflowFixture : public celero::TestFixture 
{ 
    public: 
    StackOverflowFixture() 
    { 
    } 

    inline bool NoOp(bool greater, int p1, int p2) 
    { 
     return true; 
    } 

    inline bool Compare(bool greater, int p1, int p2) 
    { 
     if(greater == true) 
     { 
     return p1>=p2; 
     } 

     return p1<=p2; 
    } 

    inline bool Compare2(bool greater, int p1, int p2) 
    { 
     bool ret[2] = {p1<=p2,p1>=p2}; 
     return ret[greater]; 
    } 

    inline bool Compare3(bool greater, int p1, int p2) 
    { 
     return (!greater != !(p1 <= p2)) | (p1 == p2); 
    } 

    inline bool Compare4(bool greater, int p1, int p2) 
    { 
     return (greater^(p1 <= p2)) | (p1 == p2); 
    } 
}; 

BASELINE_F(StackOverflow, Baseline, StackOverflowFixture, 100, 5000000) 
{ 
    celero::DoNotOptimizeAway(NoOp(rand()%2, rand(), rand())); 
} 

BENCHMARK_F(StackOverflow, Compare, StackOverflowFixture, 100, 5000000) 
{ 
    celero::DoNotOptimizeAway(Compare(rand()%2, rand(), rand())); 
} 

BENCHMARK_F(StackOverflow, Compare2, StackOverflowFixture, 100, 5000000) 
{ 
    celero::DoNotOptimizeAway(Compare2(rand()%2, rand(), rand())); 
} 

BENCHMARK_F(StackOverflow, Compare3, StackOverflowFixture, 100, 5000000) 
{ 
    celero::DoNotOptimizeAway(Compare3(rand()%2, rand(), rand())); 
} 

BENCHMARK_F(StackOverflow, Compare4, StackOverflowFixture, 100, 5000000) 
{ 
    celero::DoNotOptimizeAway(Compare4(rand()%2, rand(), rand())); 
} 

Die Ergebnisse unten:

[==========] 
[ CELERO ] 
[==========] 
[ STAGE ] Baselining 
[==========] 
[ RUN  ] StackOverflow.Baseline -- 100 samples, 5000000 calls per run. 
[  DONE ] StackOverflow.Baseline (0.690499 sec) [5000000 calls in 690499 usec] [0.138100 us/call] [7241140.103027 calls/sec] 
[==========] 
[ STAGE ] Benchmarking 
[==========] 
[ RUN  ] StackOverflow.Compare -- 100 samples, 5000000 calls per run. 
[  DONE ] StackOverflow.Compare (0.782818 sec) [5000000 calls in 782818 usec] [0.156564 us/call] [6387180.672902 calls/sec] 
[ BASELINE ] StackOverflow.Compare 1.133699 
[ RUN  ] StackOverflow.Compare2 -- 100 samples, 5000000 calls per run. 
[  DONE ] StackOverflow.Compare2 (0.700767 sec) [5000000 calls in 700767 usec] [0.140153 us/call] [7135039.178500 calls/sec] 
[ BASELINE ] StackOverflow.Compare2 1.014870 
[ RUN  ] StackOverflow.Compare3 -- 100 samples, 5000000 calls per run. 
[  DONE ] StackOverflow.Compare3 (0.709471 sec) [5000000 calls in 709471 usec] [0.141894 us/call] [7047504.408214 calls/sec] 
[ BASELINE ] StackOverflow.Compare3 1.027476 
[ RUN  ] StackOverflow.Compare4 -- 100 samples, 5000000 calls per run. 
[  DONE ] StackOverflow.Compare4 (0.712940 sec) [5000000 calls in 712940 usec] [0.142588 us/call] [7013212.893091 calls/sec] 
[ BASELINE ] StackOverflow.Compare4 1.032500 
[==========] 
[ COMPLETE ] 
[==========] 

dieser Test gegeben, es sieht aus wie Compare2 ist die beste Option für diese Mikrooptimierung.

EDIT:

Compare2 Versammlung (Der beste Fall):

cmp r8d, r9d 
movzx eax, dl 
setle BYTE PTR ret$[rsp] 
cmp r8d, r9d 
setge BYTE PTR ret$[rsp+1] 
movzx eax, BYTE PTR ret$[rsp+rax] 

Vergleich3 Assembly (Die nächstbesten Fall):

xor r11d, r11d 
cmp r8d, r9d 
mov r10d, r11d 
setg r10b 
test dl, dl 
mov ecx, r11d 
sete cl 
mov eax, r11d 
cmp ecx, r10d 
setne al 
cmp r8d, r9d 
sete r11b 
or eax, r11d