Python vs CPP: ¿Por qué la diferencia en velocidad es tan grande?

c++ performance

Question

def main():
    i = 2
    sum = 1
    while i < 100000:
        j = 2
        while j < i:
            if i%j == 0:
                sum += 1
                break
            j += 1
        i += 1

    print(sum)


if __name__ == "__main__":
    main()

#include<iostream>

using namespace std;

int main() {
    int sum = 1;
    for (int i=2; i<100000; i++) {
        for (int j=2; j<i; j++) {
            if (i%j == 0) {
                sum++;
                break;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

C ++

Ejecutar con: g++ -std=c++11 x.cpp -ox && time ./x

Tiempo: ./x 1.36s user 0.00s system 99% cpu 1.376 total

Pitón

Ejecutar con: python x.py

Tiempo: python x.py 32.10s user 0.21s system 98% cpu 32.854 total

¿Alguien puede explicar la gran diferencia entre el tiempo que llevan los 2 programas? ¿Y qué se puede hacer para acelerar Python One?

Answer 1

Aquí hay un ejemplo simple de la diferencia:

i++ en C ++ compila hasta (en máquinas x86-64) una simple instrucción de inc REGISTER . Toma una fracción de un ciclo para ejecutar.

i += 1 en Python se puede desmontar con el módulo dis través de dis.dis(''i += 1'') que nos informa que el dis.dis(''i += 1'') involucrado es:

  1           0 LOAD_NAME                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_NAME               0 (i)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE

Pruébalo en línea!

Técnicamente, todas las instrucciones que terminan en _NAME convierten en _FAST en una función (desensamblamos una declaración aislada, por lo que se comportó de forma ligeramente diferente), y el LOAD_CONST (None) / RETURN_VALUE no existirá para la expresión en una función real (el la función tiene que hacerlo, pero no para cada expresión), pero lo suficientemente cerca. En la práctica, el código de bytes real dentro de una función sería más parecido a:

  1           0 LOAD_FAST                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_FAST               0 (i)

Cada una de esas instrucciones requiere una ejecución a través de una instrucción switch o un goto calculado (dependiendo de cómo se compiló CPython), cargar la siguiente instrucción y actualizar la información de posición del código (también implica verificar repetidamente para asegurarse de que ningún otro hilo solicite el GIL ) LOAD_FAST instrucciones LOAD_FAST y LOAD_CONST implican una búsqueda de matriz C y un ajuste de recuento de referencia (un solo ajuste de recuento de referencia solo es equivalente al i++ de antes, excepto que tiene que cambiar la memoria, no un registro, por lo que es más lento). STORE_FAST manera similar implica una búsqueda de matriz C, ajuste de recuento de referencia (para disminuir el valor existente) y, a menudo, liberar memoria (si el decref eliminó la última referencia al valor). INPLACE_ADD tiene que buscar dinámicamente y llamar a un puntero de función para realizar la adición (y lo hace a través de unas pocas capas de indirección de función en primer lugar), que a su vez tiene que extraer el valor C subyacente de cada Python int para hacer el trabajo ( y si los números son lo suficientemente grandes, esto implica matemática basada en matrices, que se vuelve fea), (generalmente) crea un nuevo objeto int Python y también realiza más ajustes de recuento de referencias.

Básicamente, para obtener el equivalente de lo que C / C ++ hace en una sola instrucción de ensamblaje barata contra un registro, Python tuvo que realizar (estimar) media docena de llamadas a funciones (incluyendo una a través de un puntero de función), docenas de búsquedas de memoria, un más o menos una docena de ajustes de recuento de referencias, etc. Francamente, lo más sorprendente es que Python solo tarda ~ 24 veces más que C ++.

Notaré que el costo relativo aquí es más alto para operaciones matemáticas simples; cuanto más trabajo haga un solo bytecode, menos importa la sobrecarga del intérprete. Desafortunadamente para este caso, su código no es más que matemática simple, por lo que Python (al menos, CPython) es el peor aquí.

En cuanto a acelerarlo, las reglas principales son:

1. Escriba el código Python, no el código C. Mantiene manualmente sus contadores, cuando el range de Python podría hacer el trabajo por usted (y guardar muchas instrucciones de código de bytes individuales). Como mencioné, son las operaciones más simples y baratas donde la sobrecarga del intérprete es más alta, pero esas operaciones son normalmente cosas que en realidad no necesita hacer mucho, porque generalmente hay una mejor manera de hacerlo (por ejemplo, for bucles for encima del range en lugar de bucles while con ajuste manual del contador).
2. Para operaciones matemáticas en masa, use módulos de extensión que puedan hacer el trabajo en masa, por ejemplo, numpy . Toda esa sobrecarga para una sola adición es mala; pagarlo por 1000 adiciones es bastante trivial.
3. Pruebe con intérpretes alternativos (p. Ej., PyPy)
4. Use Cython para compilar C ++ a partir de su código Python (requiere agregar declaraciones cdef apropiadas)
5. Use ctypes para llamar a las bibliotecas C existentes y / o escriba extensiones de Python C sin formato (cuando Cython no puede manejar lo que desea)

Aparte de eso, solo tiene que aceptar que los idiomas interpretados con tipeo dinámico siempre tendrán una sobrecarga que no tendrá un lenguaje compilado estáticamente tipado.

Para abordar el punto # 1, una versión Pythonic de su código se vería así:

def main():
    sum = 1
    for i in range(2, 100000):
        for j in range(2, i):
            if i%j == 0:
                sum += 1
                break

    print(sum)

if __name__ == "__main__":
    main()

Incluso podría reemplazar el bucle interno con:

    sum += any(i % j == 0 for j in range(2, i))

aunque es poco probable que produzca beneficios de rendimiento, solo un poco de simplificación de código. Los beneficios de rendimiento provienen del uso del range , que agrupa todas las matemáticas básicas de incremento y prueba en una sola función dedicada, reduciendo significativamente la sobrecarga.

Para demostrar la diferencia en la complejidad del código de bytes, considere una función que no hace nada más que ejecutar un ciclo con while y un contador manual o for y range :

def whileloop(n):
    i = 0
    while i < n:
        i += 1

def forloop(n):
    for i in range(n):
        pass

Desmontar cada función muestra:

  3           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (i)

  4           4 SETUP_LOOP              20 (to 26)
        >>    6 LOAD_FAST                1 (i)
              8 LOAD_FAST                0 (n)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       24

  5          14 LOAD_FAST                1 (i)
             16 LOAD_CONST               2 (1)
             18 INPLACE_ADD
             20 STORE_FAST               1 (i)
             22 JUMP_ABSOLUTE            6
        >>   24 POP_BLOCK
        >>   26 LOAD_CONST               0 (None)
             28 RETURN_VALUE

para whileloop y:

  8           0 SETUP_LOOP              16 (to 18)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 4 (to 16)
             12 STORE_FAST               1 (i)

  9          14 JUMP_ABSOLUTE           10
        >>   16 POP_BLOCK
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

Pruébalo en línea!

para forloop . El cuerpo del bucle (el material ejecutado una vez por pasada, incluida la prueba de la condición de terminación) durante el while ejecuta desde LOAD_FAST después de SETUP_LOOP hasta JUMP_ABSOLUTE , que abarca nueve instrucciones por bucle; para for , se ejecuta desde FOR_ITER hasta JUMP_ABSOLUTE , abarcando solo tres instrucciones. Dado que el trabajo realizado para todas estas instrucciones es bastante trivial, es fácil ver cómo la sobrecarga del bucle en sí sería significativamente mayor para el contador administrado manualmente con un bucle while.

Answer 2

Estás calculando algo así como los números no primos hasta algunos n . Hacerlo con un tamiz es mucho más rápido:

def count_primes(n):
    count = 0
    w = [False]*n
    for m in range(2,n):
        if not w[m]:
            w[m*m::m] = [True] * ((n+m-m*m-1)//m)
            count+=1
    return count

print(99999 - sieve(100000))

Esto se ejecuta en milisegundos, incluso con python.

Answer 3

[SO]: Python vs CPP: ¿Por qué la diferencia de velocidad es tan grande? (La respuesta de @ ShadowRanger) explica muy bien el por qué (justificación que ocurre detrás de escena). Aquí hay algunos intentos que he hecho en pasos (incrementales).

1. Preparar:

   SO , herramientas y otra información.

   [cfati@cfati-5510-0:/cygdrive/e/Work/Dev//q057044727]> ~/sopr.sh
   *** Set shorter prompt to better fit when pasted in  (or other) pages ***
   
   [prompt]> uname -a
   CYGWIN_NT-10.0 cfati-5510-0 3.0.7(0.338/5/3) 2019-04-30 18:08 x86_64 Cygwin
   [prompt]>
   [prompt]> python3 -c "import sys;print(/"Python {0:s} {1:d}bit on {2:s}/".format(/" /".join(item.strip() for item in sys.version.split(/"/n/")), 64 if sys.maxsize > 0x100000000 else 32, sys.platform))"
   Python 3.6.8 (default, Feb 14 2019, 22:09:48) [GCC 7.4.0] 64bit on cygwin
   [prompt]>
   [prompt]> g++ --version | grep g++
   g++ (GCC) 7.4.0
   [prompt]>
   [prompt]> ls
   dll0.cpp  dll1.cpp  main.cpp  script00.py  script01.py  script02.py  script03.py  script04.py

2. C ++ (0):

   Divida el código en 2 archivos (más adelante verá por qué).

   dll0.cpp :

   #include <iostream>
   
   #if defined(_WIN32)
   #  define DLL_EXPORT_API __declspec(dllexport)
   #else
   #  define DLL_EXPORT_API
   #endif
   
   
   using std::cout;
   using std::endl;
   
   
   DLL_EXPORT_API int func() {
       int non_primes = 1;
       for (int i = 2; i < 100000; i++) {
           for (int j = 2; j < i; j++) {
               if (i % j == 0) {
                   non_primes++;
                   break;
               }
           }
       }
       cout << non_primes << endl;
       return 0;
   }

   main.cpp :

   #include "dll0.cpp"
   
   
   int main() {
       return func();
   }

   Salida :

   [prompt]> g++ -std=c++11 main.cpp -o main0
   [prompt]>
   [prompt]> time ./main0
   90407
   
   real    0m1.384s
   user    0m1.359s
   sys     0m0.000s

3. script00.py :

   Su guión original (con pequeñas correcciones).

   #!/usr/bin/env python3
   
   
   def main():
       non_primes = 1
       i = 2
       while i < 100000:
           j = 2
           while j < i:
               if i % j == 0:
                   non_primes += 1
                   break
               j += 1
           i += 1
       print(non_primes)
   
   
   if __name__ == "__main__":
       main()

   Salida :

   [prompt]> time python3 script00.py
   90407
   
   real    0m53.738s
   user    0m53.703s
   sys     0m0.031s

4. script01.py :

   Reemplazó los bucles while (ineficientes) por for (usando el rango ).

   #!/usr/bin/env python3
   
   
   def main():
       non_primes = 1
       for i in range(2, 100000):
           for j in range(2, i):
               if i % j == 0:
                   non_primes += 1
                   break
       print(non_primes)
   
   
   if __name__ == "__main__":
       main()

   Salida :

   [prompt]> time python3 script01.py
   90407
   
   real    0m34.142s
   user    0m34.124s
   sys     0m0.000s

5. script02.py :

   Utilice la prueba de igualdad de estilo Python 0 .

   #!/usr/bin/env python3
   
   
   def main():
       non_primes = 1
       for i in range(2, 100000):
           for j in range(2, i):
               if not i % j:
                   non_primes += 1
                   break
       print(non_primes)
   
   
   if __name__ == "__main__":
       main()

   Salida :

   [prompt]> time python3 script02.py
   90407
   
   real    0m28.440s
   user    0m28.406s
   sys     0m0.031s

6. script03.py :

   Específico para este caso . La búsqueda de divisores es altamente ineficiente. Se itera hasta el número en sí (cuando en realidad solo debe ir a su raíz cuadrada ), generando muchas operaciones inútiles que profundizan la brecha de rendimiento entre los 2 idiomas.

   #!/usr/bin/env python3
   
   from math import sqrt
   
   
   def main():
       non_primes = 1
       for i in range(2, 100000):
           for j in range(2, int(sqrt(i) + 1)):
               if not i % j:
                   non_primes += 1
                   break
       print(non_primes)
   
   
   if __name__ == "__main__":
       main()

   Salida :

   [prompt]> time python3 script03.py
   90407
   
   real    0m0.291s
   user    0m0.265s
   sys     0m0.015s

   Como se ve, una enorme diferencia ( casi 100 veces más rápido ) que la versión anterior, e incluso mejor que el código C (original).

7. C ++ (1):

   El paso anterior funcionaba con el algoritmo mismo. Cambie también la variante de C ++ , de lo contrario la comparación sería injusta.

   dll1.cpp :

   #include <iostream>
   #include <math.h>
   
   #if defined(_WIN32)
   #  define DLL_EXPORT_API __declspec(dllexport)
   #else
   #  define DLL_EXPORT_API
   #endif
   
   
   using std::cout;
   using std::endl;
   
   
   #if defined(__cplusplus)
   extern "C" {
   #endif
   
   DLL_EXPORT_API int func() {
       int non_primes = 1;
       for (int i = 2; i < 100000; i++) {
           for (int j = 2; j < static_cast<int>(sqrt(i) + 1); j++) {
               if (i % j == 0) {
                   non_primes++;
                   break;
               }
           }
       }
       cout << non_primes << endl;
       return 0;
   }
   
   #if defined(__cplusplus)
   }
   #endif

   main.cpp debe (obviamente) modificarse en consecuencia ( #include "dll1.cpp" ).

   Salida :

   [prompt]> g++ -std=c++11 main.cpp -o main1
   [prompt]>
   [prompt]> time ./main1
   90407
   
   real    0m0.279s
   user    0m0.250s
   sys     0m0.030s

8. Llame al código C ++ (interfaz C ) desde Python a través de [Python 3.Docs]: ctypes - Una biblioteca de funciones foráneas para Python :

   Utiliza el código C ++ del paso anterior.

   script04.py :

   #!/usr/bin/env python3
   
   import ctypes
   
   
   def main():
       dll = ctypes.CDLL("./dll1.so")
       func = dll.func
       func.argtypes = []
       func.restype = ctypes.c_int
       func()
   
   
   if __name__ == "__main__":
       main()

   Salida :

   [prompt]> g++ -std=c++11 -fPIC -shared dll1.cpp -o dll1.so
   [prompt]>
   [prompt]> time python3 script04.py
   90407
   
   real    0m0.327s
   user    0m0.281s
   sys     0m0.031s

Conclusiones (extraídas de los ejemplos anteriores):

• Ejecuté cada paso 3 veces, y coloqué aquí el resultado medio. Sin embargo, una prueba con resultados significativos debe ejecutarse varios miles de veces y debe calcularse un promedio. Además, el hecho de que estoy usando Cygwin podría interferir con los resultados

• Escribiendo código ic de Python , mejoró el rendimiento casi 2 veces ( # 4. , # 5. )

• Al escribir un algoritmo eficiente, se redujo la diferencia entre los 2 idiomas casi a 0 ( # 6. Vs. # 7. ), Y el código Python (puro) parece ejecutarse más rápido que el # 8. .
  Sin embargo, no te dejes engañar por estos hechos. Como se demostró, si el número de operaciones aumenta (y no necesariamente debido a la ineficiencia), C ++ funcionará mucho más rápido.
  Puede verificar esto aplicando el paso 8. a dll0.cpp