int-Operatoren! = und == beim Vergleich mit Null

75

Ich habe festgestellt, dass! = Und == nicht die schnellsten Methoden zum Testen auf Null oder Nicht-Null sind.

bool nonZero1 = integer != 0;
xor eax, eax
test ecx, ecx
setne al

bool nonZero2 = integer < 0 || integer > 0;
test ecx, ecx
setne al

bool zero1 = integer == 0;
xor eax, eax
test ecx, ecx
sete al

bool zero2 = !(integer < 0 || integer > 0);
test ecx, ecx
sete al

Compiler: VC ++ 11 Optimierungsflags: / O2 / GL / LTCG

Dies ist die Assembly-Ausgabe für x86-32. Die zweiten Versionen beider Vergleiche waren sowohl auf x86-32 als auch auf x86-64 ~ 12% schneller. Auf x86-64 waren die Anweisungen jedoch identisch (die ersten Versionen sahen genauso aus wie die zweiten Versionen), aber die zweiten Versionen waren immer noch schneller.

  1. Warum generiert der Compiler die schnellere Version auf x86-32 nicht?
  2. Warum sind die zweiten Versionen auf x86-64 noch schneller, wenn die Assembly-Ausgabe identisch ist?

EDIT: Ich habe Benchmarking-Code hinzugefügt. NULL: 1544 ms, 1358 ms NON_ZERO: 1544 ms, 1358 ms http://pastebin.com/m7ZSUrcP oder http://anonymouse.org/cgi-bin/anon-www.cgi/http://pastebin.com/m7ZSUrcP

Hinweis: Es ist wahrscheinlich unpraktisch, diese Funktionen zu finden, wenn sie in einer einzelnen Quelldatei kompiliert werden, da main.asm ziemlich groß ist. Ich hatte null1, null2, nonZero1, nonZero2 in einer separaten Quelldatei.

EDIT2: Könnte jemand, auf dem sowohl VC ++ 11 als auch VC ++ 2010 installiert sind, den Benchmarking-Code ausführen und die Timings veröffentlichen? Es könnte tatsächlich ein Fehler in VC ++ 11 sein.

c++ performance assembly machine-code NFRCR
quelle
11
Würden Sie das vollständige Programm bereitstellen, mit dem Sie die Leistung bewerten?
James McNellis
Wie garantiert es also, dass der Rest von eax Null ist, wenn nur das xor übersprungen wird?
Harold
1
Woher kommen die xorAnweisungen? Sie sehen für den Test nicht relevant aus, daher sollte er Teil des umgebenden Codes sein.
Mark Ransom
2
Was passiert, wenn Sie die Reihenfolge ändern? Der Compiler ist klug genug zu wissen, dass er vor dem ersten Test xor: ed hat und dass das für den nächsten gültig bleibt ...eax
Andreas Magnusson
2
NFRCR, haben Sie das wirklich als linearen Code bewertet? Ich nahm an, Sie haben sie gerade zusammengeklebt, um die Größe des Pfostens gering zu halten.
Harold

Antworten:

19

BEARBEITEN: Die Versammlungsliste von OP für meinen Code wurde angezeigt. Ich bezweifle, dass dies jetzt sogar ein allgemeiner Fehler bei VS2011 ist . Dies kann einfach ein Sonderfallfehler für den OP-Code sein. Ich habe den Code von OP so wie er ist mit clang 3.2, gcc 4.6.2 und VS2010 ausgeführt und in allen Fällen lagen die maximalen Unterschiede bei ~ 1%.

Kompilieren Sie einfach die Quellen mit geeigneten Änderungen an meiner ne.cDatei und den /O2und /GL-Flaggen. Hier ist die Quelle

int ne1(int n) {
 return n != 0;
 }

 int ne2(int n) {
 return n < 0 || n > 0;
 }

 int ne3(int n) {
 return !(n == 0);
 }

int main() { int p = ne1(rand()), q = ne2(rand()), r = ne3(rand());}

und die entsprechende Baugruppe:

    ; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.30319.01 

    TITLE   D:\llvm_workspace\tests\ne.c
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB OLDNAMES

EXTRN   @__security_check_cookie@4:PROC
EXTRN   _rand:PROC
PUBLIC  _ne3
; Function compile flags: /Ogtpy
;   COMDAT _ne3
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne3    PROC                        ; COMDAT
; File d:\llvm_workspace\tests\ne.c
; Line 11
    xor eax, eax
    cmp DWORD PTR _n$[esp-4], eax
    setne   al
; Line 12
    ret 0
_ne3    ENDP
_TEXT   ENDS
PUBLIC  _ne2
; Function compile flags: /Ogtpy
;   COMDAT _ne2
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne2    PROC                        ; COMDAT
; Line 7
    xor eax, eax
    cmp eax, DWORD PTR _n$[esp-4]
    sbb eax, eax
    neg eax
; Line 8
    ret 0
_ne2    ENDP
_TEXT   ENDS
PUBLIC  _ne1
; Function compile flags: /Ogtpy
;   COMDAT _ne1
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne1    PROC                        ; COMDAT
; Line 3
    xor eax, eax
    cmp DWORD PTR _n$[esp-4], eax
    setne   al
; Line 4
    ret 0
_ne1    ENDP
_TEXT   ENDS
PUBLIC  _main
; Function compile flags: /Ogtpy
;   COMDAT _main
_TEXT   SEGMENT
_main   PROC                        ; COMDAT
; Line 14
    call    _rand
    call    _rand
    call    _rand
    xor eax, eax
    ret 0
_main   ENDP
_TEXT   ENDS
END

ne2()die verwendet <, >und ||Betreiber ist deutlich teurer. ne1()und ne3()die die Operatoren ==und !=verwenden, sind terser und äquivalent.

Visual Studio 2011 befindet sich in der Beta . Ich würde dies als Fehler betrachten. Meine Tests mit zwei anderen Compilern, nämlich gcc 4.6.2 und clang 3.2 , mit dem O2Optimierungsschalter ergaben für alle drei Tests (die ich hatte) auf meiner Windows 7-Box genau die gleiche Baugruppe. Hier ist eine Zusammenfassung:

$ cat ne.c

#include <stdbool.h>
bool ne1(int n) {
    return n != 0;
}

bool ne2(int n) {
    return n < 0 || n > 0;
}

bool ne3(int n) {
    return !(n != 0);
}

int main() {}

ergibt mit gcc:

_ne1:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    testl   %eax, %eax
    setne   %al
    ret
    .cfi_endproc
LFE0:
    .p2align 2,,3
    .globl  _ne2
    .def    _ne2;   .scl    2;  .type   32; .endef
_ne2:
LFB1:
    .cfi_startproc
    movl    4(%esp), %edx
    testl   %edx, %edx
    setne   %al
    ret
    .cfi_endproc
LFE1:
    .p2align 2,,3
    .globl  _ne3
    .def    _ne3;   .scl    2;  .type   32; .endef
_ne3:
LFB2:
    .cfi_startproc
    movl    4(%esp), %ecx
    testl   %ecx, %ecx
    sete    %al
    ret
    .cfi_endproc
LFE2:
    .def    ___main;    .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 2,,3
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
LFB3:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    andl    $-16, %esp
    call    ___main
    xorl    %eax, %eax
    leave
    .cfi_restore 5
    .cfi_def_cfa 4, 4
    ret
    .cfi_endproc
LFE3:

und mit klirren: 

    .def     _ne1;
    .scl    2;
    .type   32;
    .endef
    .text
    .globl  _ne1
    .align  16, 0x90
_ne1:
    cmpl    $0, 4(%esp)
    setne   %al
    movzbl  %al, %eax
    ret

    .def     _ne2;
    .scl    2;
    .type   32;
    .endef
    .globl  _ne2
    .align  16, 0x90
_ne2:
    cmpl    $0, 4(%esp)
    setne   %al
    movzbl  %al, %eax
    ret

    .def     _ne3;
    .scl    2;
    .type   32;
    .endef
    .globl  _ne3
    .align  16, 0x90
_ne3:
    cmpl    $0, 4(%esp)
    sete    %al
    movzbl  %al, %eax
    ret

    .def     _main;
    .scl    2;
    .type   32;
    .endef
    .globl  _main
    .align  16, 0x90
_main:
    pushl   %ebp
    movl    %esp, %ebp
    calll   ___main
    xorl    %eax, %eax
    popl    %ebp
    ret

Mein Vorschlag wäre, dies als Fehler bei Microsoft Connect einzureichen .

Hinweis: Ich habe sie als C-Quelle kompiliert, da ich nicht glaube, dass die Verwendung des entsprechenden C ++ - Compilers hier wesentliche Änderungen bewirken würde.

dirkgently
quelle
1
Ihr neuer Test ist durcheinander, der Compiler hat eine konstante Weitergabe durchgeführt, da er n = 10immer ermittelt hat . Darüber hinaus wurden die Funktionsaufrufe vollständig eliminiert, da das Ergebnis nicht verwendet wurde und keine Nebenwirkungen auftreten.
Ben Voigt
1
@dirkgently: Wenn es um Optimierungsfragen geht, ist der Kontext alles.
Ben Voigt
7
Es ist kein Fehler! Wie kann es ein Fehler sein, wenn sich der kompilierte Code so verhält, wie er sollte? Es zeigt, dass der Optimierer Verbesserungspotenzial aufweist, aber jeder Optimierer bietet Verbesserungspotenzial. (Das ist übrigens ein Satz.)
TonyK
1
Visual C ++ - Fehler können in Microsoft Connect gemeldet werden .
James McNellis
1
Es lohnt sich auch, dies mit dem heute veröffentlichten Visual C ++ 2012 RC zu testen .
James McNellis
122

Dies ist eine großartige Frage, aber ich denke, Sie sind der Abhängigkeitsanalyse des Compilers zum Opfer gefallen.

Der Compiler muss die hohen Bits nur eaxeinmal löschen, und sie bleiben für die zweite Version gelöscht. Die zweite Version müsste den Preis dafür zahlen, xor eax, eaxaußer dass die Compiler-Analyse bewiesen hat, dass sie von der ersten Version gelöscht wurde.

Die zweite Version kann "schummeln", indem sie die Arbeit des Compilers in der ersten Version nutzt.

Wie messen Sie die Zeiten? Ist es "(Version eins, gefolgt von Version zwei) in einer Schleife" oder "(Version eins in einer Schleife) gefolgt von (Version zwei in einer Schleife)"?

Führen Sie nicht beide Tests im selben Programm durch (kompilieren Sie stattdessen für jede Version neu). Wenn Sie dies tun, testen Sie sowohl "Version A zuerst" als auch "Version B zuerst" und prüfen Sie, ob derjenige, der zuerst kommt, eine Strafe zahlt.

Illustration des Betrugs:

timer1.start();
double x1 = 2 * sqrt(n + 37 * y + exp(z));
timer1.stop();
timer2.start();
double x2 = 31 * sqrt(n + 37 * y + exp(z));
timer2.stop();

Wenn die timer2Dauer kleiner als die timer1Dauer ist, schließen wir nicht, dass das Multiplizieren mit 31 schneller ist als das Multiplizieren mit 2. Stattdessen stellen wir fest, dass der Compiler eine allgemeine Analyse des Unterausdrucks durchgeführt hat und der Code wie folgt lautet:

timer1.start();
double common = sqrt(n + 37 * y + exp(z));
double x1 = 2 * common;
timer1.stop();
timer2.start();
double x2 = 31 * common;
timer2.stop();

Und das einzige, was bewiesen ist, ist, dass das Multiplizieren mit 31 schneller ist als das Rechnen common. Was überhaupt nicht überrascht - die Multiplikation ist weitaus schneller als sqrtund exp.

Ben Voigt
quelle
Benchmarking-Code hinzugefügt. Ich habe Benchmark1 und Benchmark2 getrennt ausgeführt, die gleichen Ergebnisse. Der einzige Unterschied ist der erste Benchmark, der ausgeführt wird, sich dann "erwärmt" und etwas langsamer ist.
NFRCR
Dies hat nichts damit zu tun, aber würde ein Compiler eine Multiplikation mit 31 zu a nicht optimieren (common << 5) - common?
Matt
3
@Matt: Nicht für die Gleitkomma-Multiplikation wäre es nicht;) Für die Ganzzahl-Multiplikation, ja, ich denke, die meisten Compiler kennen diesen Trick, aber je nach Architektur kann er schneller sein oder auch nicht. IMUL by two wird mit ziemlicher Sicherheit in eine Linksverschiebung umgewandelt.
Ben Voigt