Pregunta ¿Por qué este programa en C ++ es increíblemente rápido?


Escribí un pequeño punto de referencia para comparar el rendimiento de diferentes intérpretes / compiladores para Python, Ruby, JavaScript y C ++. Como era de esperar, resulta que C ++ (optimizado) supera a los lenguajes de scripting, pero el factor por el cual lo hace es increíblemente alto.

Los resultados son:

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

Me pregunto si alguien puede dar una explicación de por qué el código optimizado de C ++ es más de tres órdenes de magnitud más rápido que todo lo demás.

El benchmark C ++ usa parámetros de línea de comando para evitar el pre-cálculo del resultado en tiempo de compilación.

A continuación, coloqué los códigos fuente para los diferentes puntos de referencia del idioma, que deben ser semánticamente equivalentes. Además, proporcioné el código ensamblador para la salida optimizada del compilador C ++ (usando gcc). Al observar el ensamblaje optimizado, parece que el compilador fusionó los dos bucles en el punto de referencia en uno solo, pero aún así, ¡todavía hay un ciclo!

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

Pitón:

s = 0
outer = 1000
inner = 1000000

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

Rubí:

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

Ensamblado (al compilar el código C ++ anterior con 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

74
2017-07-18 15:55


origen


Respuestas:


El optimizador ha resuelto que el ciclo interno junto con la línea subsiguiente no funciona, y lo eliminó. Desafortunadamente, no ha logrado eliminar el bucle externo también.

Tenga en cuenta que el ejemplo de node.js es más rápido que el ejemplo de C ++ no optimizado, lo que indica que V8 (el compilador JIT del nodo) ha logrado eliminar al menos uno de los bucles. Sin embargo, su optimización tiene algunos gastos generales, ya que (como cualquier compilador JIT) debe equilibrar las oportunidades de optimización y la re-optimización guiada por perfiles, en comparación con el costo de hacerlo.


101
2017-07-18 16:11



No hice un análisis completo del ensamblaje, pero parece que se desenrolló el lazo interno y descubrí que, junto con la resta del interior, es un nudo.

El ensamblaje solo parece hacer el lazo externo que solo incrementa un contador hasta que se alcanza el exterior. Incluso podría haber optimizado eso, pero parece que no lo hizo.


21
2017-07-18 16:04



¿Hay alguna manera de almacenar en caché el código compilado JIT después de que lo optimice, o tiene que volver a optimizar el código cada vez que se ejecuta el programa?

Si estuviera escribiendo en Python, intentaría reducir el tamaño del código para obtener una vista "general" de lo que estaba haciendo el código. Como intentar escribir esto (mucho más fácil de leer IMO):

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

o incluso s = sum(inner - inner for _ in xrange(outer))


6
2017-07-18 19:49



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

El bucle interno es equivalente a "s + = inner; j = inner;" que un buen compilador de optimización puede hacer. Como la variable j se ha ido después del ciclo, todo el código es equivalente a

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

Nuevamente, un buen compilador de optimización puede eliminar los dos cambios en s, luego eliminar la variable i, y no queda nada en absoluto. Parece que eso es lo que sucedió.

Ahora depende de usted decidir con qué frecuencia ocurre una optimización como esta, y si se trata de un beneficio real.


2
2017-07-20 12:13



A pesar de que los bucles tienen muchas iteraciones, los programas probablemente todavía no tengan una ejecución prolongada suficiente como para escapar de la sobrecarga de los tiempos de inicio del intérprete / JVM / shell / etc. En algunos entornos, estos pueden variar enormemente; en algunos casos, * tos * Java * tos * tarda varios segundos antes de que llegue a estar cerca de su código real.

Idealmente, medirías la ejecución dentro de cada fragmento de código. Puede ser complicado hacer esto con precisión en todos los idiomas, pero incluso imprimir el tiempo del reloj en tics antes y después sería mejor que usar time, y haría el trabajo ya que probablemente no te preocupes por el tiempo súper preciso aquí.

(Supongo que esto no se relaciona con por qué el ejemplo de C ++ es mucho más rápido, pero podría explicar parte de la variabilidad en los otros resultados :)).


2
2017-07-22 23:50