Warum ist dieses C++ Programm so unglaublich schnell?

Question

Ich habe einen kleinen Benchmark geschrieben, um die Leistung verschiedener Interpreter/Compiler für Python, Ruby, JavaScript und C++ zu vergleichen. Wie erwartet, stellt sich heraus, dass (optimiertes) C++ die Skriptsprachen übertrifft, aber der Faktor, mit dem es dies tut, ist unglaublich hoch.

Die Ergebnisse sind:

sven@jet:~/tmp/js$ time node bla.js    # * JavaScript with node * 
0 

real 0m1.222s 
user 0m1.190s 
sys 0m0.015s 
sven@jet:~/tmp/js$ time ruby foo.rb    # * Ruby * 
0 

real 0m52.428s 
user 0m52.395s 
sys 0m0.028s 
sven@jet:~/tmp/js$ time python blub.py   # * Python with CPython * 
0 

real 1m16.480s 
user 1m16.371s 
sys 0m0.080s 

sven@jet:~/tmp/js$ time pypy blub.py    # * Python with PyPy * 
0 

real 0m4.707s 
user 0m4.579s 
sys 0m0.028s 

sven@jet:~/tmp/js$ time ./cpp_non_optimized 1000 1000000 # * C++ with -O0 (gcc) * 
0 

real 0m1.702s 
user 0m1.699s 
sys 0m0.002s 
sven@jet:~/tmp/js$ time ./cpp_optimized 1000 1000000  # * C++ with -O3 (gcc) * 
0 

real 0m0.003s # (!!!) <---------------------------------- WHY? 
user 0m0.002s 
sys 0m0.002s 

Ich frage mich, ob jemand eine Erklärung dafür, warum die optimierte C++ Code über drei Größenordnungen schneller als alles andere.

Der C++ - Benchmark verwendet Befehlszeilenparameter, um zu verhindern, dass das Ergebnis zur Kompilierzeit vorberechnet wird.

Unten habe ich die Quellcodes für die verschiedenen Sprachbenchmarks platziert, die semantisch äquivalent sein sollten. Außerdem habe ich den Assembler-Code für die optimierte C++ - Compiler-Ausgabe (mit gcc) zur Verfügung gestellt. Wenn man sich die optimierte Assembly ansieht, scheint es, dass der Compiler die beiden Loops im Benchmark zu einem einzigen zusammengeführt hat, aber trotzdem gibt es noch eine Schleife!

JavaScript:

var s = 0; 
var outer = 1000; 
var inner = 1000000; 

for (var i = 0; i < outer; ++i) { 
    for (var j = 0; j < inner; ++j) { 
     ++s; 
    } 
    s -= inner; 
} 
console.log(s); 

Python:

s = 0 
outer = 1000 
inner = 1000000 

for _ in xrange(outer): 
    for _ in xrange(inner): 
     s += 1 
    s -= inner 
print s 

Rubin:

s = 0 
outer = 1000 
inner = 1000000 

outer_end = outer - 1 
inner_end = inner - 1 

for i in 0..outer_end 
    for j in 0..inner_end 
    s = s + 1 
    end 
    s = s - inner 
end 
puts s 

C++ :

#include <iostream> 
#include <cstdlib> 
#include <cstdint> 

int main(int argc, char* argv[]) { 
    uint32_t s = 0; 
    uint32_t outer = atoi(argv[1]); 
    uint32_t inner = atoi(argv[2]); 
    for (uint32_t i = 0; i < outer; ++i) { 
    for (uint32_t j = 0; j < inner; ++j) 
     ++s; 
    s -= inner; 
    } 
    std::cout << s << std::endl; 
    return 0; 
} 

Assembly (wenn ES O3 -std = C++ 0x den oben C++ Code mit gcc kompilieren):

.file "bar.cpp" 
    .section .text.startup,"ax",@progbits 
    .p2align 4,,15 
    .globl main 
    .type main, @function 
main: 
.LFB1266: 
    .cfi_startproc 
    pushq %r12 
    .cfi_def_cfa_offset 16 
    .cfi_offset 12, -16 
    movl $10, %edx 
    movq %rsi, %r12 
    pushq %rbp 
    .cfi_def_cfa_offset 24 
    .cfi_offset 6, -24 
    pushq %rbx 
    .cfi_def_cfa_offset 32 
    .cfi_offset 3, -32 
    movq 8(%rsi), %rdi 
    xorl %esi, %esi 
    call strtol 
    movq 16(%r12), %rdi 
    movq %rax, %rbp 
    xorl %esi, %esi 
    movl $10, %edx 
    call strtol 
    testl %ebp, %ebp 
    je .L6 
    movl %ebp, %ebx 
    xorl %eax, %eax 
    xorl %edx, %edx 
    .p2align 4,,10 
    .p2align 3 
.L3:        # <--- Here is the loop 
    addl $1, %eax    # <--- 
    cmpl %eax, %ebx   # <--- 
    ja .L3      # <--- 
.L2: 
    movl %edx, %esi 
    movl $_ZSt4cout, %edi 
    call _ZNSo9_M_insertImEERSoT_ 
    movq %rax, %rdi 
    call _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ 
    popq %rbx 
    .cfi_remember_state 
    .cfi_def_cfa_offset 24 
    popq %rbp 
    .cfi_def_cfa_offset 16 
    xorl %eax, %eax 
    popq %r12 
    .cfi_def_cfa_offset 8 
    ret 
.L6: 
    .cfi_restore_state 
    xorl %edx, %edx 
    jmp .L2 
    .cfi_endproc 
.LFE1266: 
    .size main, .-main 
    .p2align 4,,15 
    .type _GLOBAL__sub_I_main, @function 
_GLOBAL__sub_I_main: 
.LFB1420: 
    .cfi_startproc 
    subq $8, %rsp 
    .cfi_def_cfa_offset 16 
    movl $_ZStL8__ioinit, %edi 
    call _ZNSt8ios_base4InitC1Ev 
    movl $__dso_handle, %edx 
    movl $_ZStL8__ioinit, %esi 
    movl $_ZNSt8ios_base4InitD1Ev, %edi 
    addq $8, %rsp 
    .cfi_def_cfa_offset 8 
    jmp __cxa_atexit 
    .cfi_endproc 
.LFE1420: 
    .size _GLOBAL__sub_I_main, .-_GLOBAL__sub_I_main 
    .section .init_array,"aw" 
    .align 8 
    .quad _GLOBAL__sub_I_main 
    .local _ZStL8__ioinit 
    .comm _ZStL8__ioinit,1,1 
    .hidden __dso_handle 
    .ident "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2" 
    .section .note.GNU-stack,"",@progbits 

Answer 1

Der Optimierer hat herausgefunden, dass die innere Schleife zusammen mit der nachfolgenden Zeile ein No-Op ist, und beseitigt es. Leider ist es auch nicht gelungen, die äußere Schleife zu eliminieren.

Beachten Sie, dass das node.js-Beispiel schneller als das nicht optimierte C++ - Beispiel ist und angibt, dass V8 (Knoten-JIT-Compiler) mindestens eine der Schleifen eliminiert hat. Seine Optimierung hat jedoch einige Gemeinkosten, da (wie bei jedem JIT-Compiler) die Möglichkeiten zur Optimierung und profilgesteuerten Neuoptimierung gegen die Kosten ausgewogen sein müssen.

Answer 2

habe ich eine vollständige Analyse der nicht tun die Versammlung, aber es sieht aus, als ob es Schleifenabrollen der inneren Schleife und herausgefunden hat, dass zusammen mit der Subtraktion von innerem es ein nop ist.

Die Baugruppe scheint nur die äußere Schleife zu tun, die nur einen Zähler erhöht, bis der äußere erreicht ist. Es könnte sogar das weg optimiert haben, aber es scheint, dass es das nicht getan hat.

Answer 3

Gibt es eine Möglichkeit, den JIT-kompilierten Code zu speichern, nachdem er optimiert wurde, oder muss er den Code jedes Mal neu optimieren, wenn das Programm ausgeführt wird?

Wenn ich in Python zu schreiben wäre, würde ich versuchen, den Code unten in der Größe zu reduzieren, um eine „Overhead“ Ansicht zu bekommen, was der Code tut. Wie versuchen Sie dies schriftlich (viel einfacher IMO zu lesen):

for i in range(outer): 
    innerS = sum(1 for _ in xrange(inner)) 
    s += innerS 
    s -= innerS 

oder sogar s = sum(inner - inner for _ in xrange(outer))

Answer 4

for (uint32_t i = 0; i < outer; ++i) { 
    for (uint32_t j = 0; j < inner; ++j) 
     ++s; 
    s -= inner; 
} 

Die innere Schleife entspricht "s + = Innen; j = innere," was eine gute Optimierung Compiler kann. Da die Variable j nach der Schleife weg ist, ist der gesamte Code entspricht

for (uint32_t i = 0; i < outer; ++i) { 
    s += inner; 
    s -= inner; 
} 

Auch hier kann eine gute optimierenden Compiler die beiden Änderungen s entfernen, dann entfernen Sie die Variable i, und es gibt nichts, was auch immer links. Es scheint, dass das passiert ist.

Nun liegt es an Ihnen zu entscheiden, wie oft eine solche Optimierung stattfindet und ob es sich um einen wirklichen Nutzen handelt.

Answer 5

Obwohl die Schleifen viele Wiederholungen haben, sind die Programme wahrscheinlich immer noch nicht lange genug, um dem Overhead der Startzeiten von Interpreter/JVM/Shell/etc. zu entgehen. In einigen Umgebungen können diese massiv variieren - in einigen Fällen * hust * Java * hust * dauert einige Sekunden, bevor es in die Nähe Ihres tatsächlichen Codes kommt.

Idealerweise würden Sie die Ausführung in jedem Codeabschnitt zeitlich festlegen. Es mag schwierig sein, dies in allen Sprachen genau zu machen, aber sogar das Ausgeben der Uhrzeit in Ticks davor und danach wäre besser als die Verwendung von time und würde den Job erledigen, da Sie hier wahrscheinlich nicht auf ein supergenaues Timing achten müssen.

(Ich denke, das bezieht sich nicht wirklich darauf, warum das C++ - Beispiel so viel schneller ist - aber es könnte einige der Variabilität in den anderen Ergebnissen erklären. :)).