Pourquoi ce programme C ++ est-il si incroyablement rapide?

Question

J'ai écrit un petit benchmark pour comparer les performances de différents interpréteurs et compilateurs pour Python, Ruby, JavaScript et C++. Comme prévu, il s'avère que (optimisé) C++ bat les langages de script, mais le facteur par lequel il le fait est incroyablement élevé.

Les résultats sont les suivants:

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

Je me demande si quelqu'un peut fournir une explication de pourquoi le C++ optimisé le code est plus de trois ordres de grandeur plus rapide que tout le reste.

Le C++ de référence utilise des paramètres de ligne de commande afin de prévenir la pré-calculer le résultat au moment de la compilation.

Ci-dessous, j'ai placé les codes sources pour les différents niveaux de compétence linguistique, qui devrait être sémantiquement équivalentes. Aussi, je fournis le code assembleur pour l'optimisation du compilateur C++ de sortie (à l'aide de gcc). Lors de la recherche à l'optimisation de l'assemblée, il semble que le compilateur a fusionné les deux boucles dans la référence à une seule, mais néanmoins, il reste une boucle!

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

Ruby:

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;
}

De l'assemblée (lors de la compilation ci-dessus du code C++ avec gcc -S -O3-std=c++0x):

    .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

L'optimiseur a travaillé sur l'intérieur de la boucle et la ligne est un no-op, et à l'éliminer. Malheureusement, il n'a pas réussi à éliminer la boucle externe.

Notez que l'node.js exemple est plus rapide que la unoptimized exemple C++, indiquant que la V8 (nœud du compilateur JIT) a réussi à éliminer au moins une des boucles. Cependant, son optimisation a une surcharge, comme (comme n'importe quel compilateur JIT), il doit mettre en balance les possibilités pour l'optimisation et de profil-guidée de la ré-optimisation contre le coût de le faire.

Answer 2

Je n’ai fait une analyse complète de l’Assemblée, mais on dirait qu’il a fait en boucle déroulement de la boucle interne et compris qu’avec la soustraction d’intérieur c’est un nop.

L’Assemblée seulement semble faire la boucle externe qui n’incrémente un compteur jusqu'à ce que l’extérieur soit atteinte. Il pourrait même avoir optimisé qui loin, mais il semble qu’il n’a pas le faire.

Answer 3

<blockquote> <p><em>Y at-il un moyen pour mettre en cache le JIT code compilé après qu’il l’optimise, ou faut-il ré-optimiser le code chaque fois que le programme est exécuté ?</em></p> <p>Si je devais écrire en Python je voudrais essayer de réduire le code vers le bas en taille pour obtenir une vue de « frais généraux » de ce que le code a été fait. Comme essayer d’écrire ceci (beaucoup plus facile de lire l’OMI) :</p><pre><code></code></pre><p>ou même<code></code></p></blockquote>

Answer 4

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

La boucle interne est équivalent à "s += interne; j = interne;" qu'une bonne optimisation du compilateur peut faire. Puisque la variable j est allée au bout de la boucle, l'ensemble du code est équivalent à

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

Encore une fois, une bonne optimisation du compilateur peut supprimer les deux modifications à s, puis de supprimer la variable i, et il n'y a rien que ce soit. Il semble que c'est ce qui s'est passé.

Maintenant c'est à vous de décider comment souvent une optimisation comme ce qui se passe, et si c'est une réelle vie.

Answer 5

Même si les boucles ont beaucoup d'itérations, les programmes probablement encore ne sont pas de longue durée d'exécution suffisant pour échapper à la surcharge de l'interprète/JVM/shell/etc.'s temps de démarrage. Dans certains environnements, il peut s'agir massivement, dans certains cas, *toux*Java*tousse* prendre plusieurs secondes avant qu'il arrive n'importe où près de votre code.

L'idéal serait de temps de l'exécution à l'intérieur de chaque morceau de code. Il peut être difficile de le faire avec précision dans toutes les langues, mais même l'impression de l'heure de l'horloge dans les tiques avant et après serait mieux que d'utiliser time, et devrait faire le travail puisque vous avez probablement ne sont pas concernés avec un super moment précis ici.

(Je suppose que ce n'est pas vraiment lié à pourquoi l'exemple C++ est beaucoup plus rapide, mais elle pourrait expliquer en partie la variabilité dans les résultats. :) ).