Rendimiento en diferentes métodos de vectorización en números.

Quería probar el rendimiento del código de vectorización en python:

import timeit import numpy as np def func1(): x = np.arange(1000) sum = np.sum(x*2) return sum def func2(): sum = 0 for i in xrange(1000): sum += i*2 return sum def func3(): sum = 0 for i in xrange(0,1000,4): x = np.arange(i,i+4,1) sum += np.sum(x*2) return sum print timeit.timeit(func1, number = 1000) print timeit.timeit(func2, number = 1000) print timeit.timeit(func3, number = 1000) 

El código da la siguiente salida:

 0.0105729103088 0.069864988327 0.983253955841 

La diferencia de rendimiento en la primera y segunda funciones no son sorprendentes. Pero me sorprendió que la tercera función sea significativamente más lenta que las otras funciones.

Estoy mucho más familiarizado con el código de vectorización en C que en Python y la tercera función es más parecida a C: ejecutar un bucle for y procesar 4 números en una instrucción en cada bucle. A mi entender, numpy llama a una función C y luego vectoriza el código en C. Entonces, si este es el caso, mi código también está pasando 4 números para numpy cada uno a la vez. El código no debería funcionar mejor cuando paso más números a la vez. Entonces, ¿por qué es mucho más lento? ¿Es debido a la sobrecarga en llamar a una función numpy?

Además, la razón por la que se me ocurrió la tercera función en primer lugar es porque me preocupa el rendimiento de la gran cantidad de memoria func1 a x en func1 .

    ¿Es mi preocupación válida? ¿Por qué y cómo puedo mejorarlo o por qué no?

    Gracias por adelantado.

    Editar:

    En aras de la curiosidad, aunque anula mi propósito original de crear la tercera versión, he examinado la sugerencia de roganjosh y he intentado la siguiente edición.

     def func3(): sum = 0 x = np.arange(0,1000) for i in xrange(0,1000,4): sum += np.sum(x[i:i+4]*2) return sum 

    La salida:

     0.0104308128357 0.0630609989166 0.748773813248 

    Hay una mejora, pero todavía una gran brecha en comparación con las otras funciones.

    ¿Es porque x[i:i+4] todavía crea una nueva matriz?

    Edición 2:

    He modificado el código nuevamente de acuerdo con la sugerencia de Daniel.

     def func1(): x = np.arange(1000) x *= 2 return x.sum() def func3(): sum = 0 x = np.arange(0,1000) for i in xrange(0,1000,4): x[i:i+4] *= 2 sum += x[i:i+4].sum() return sum 

    La salida:

     0.00824999809265 0.0660569667816 0.598328828812 

    Hay otra aceleración. Por lo tanto, la statement de arrays numpy es definitivamente un problema. Ahora en func3 solo debe haber una statement de array, pero el tiempo sigue siendo mucho más lento. ¿Es debido a la sobrecarga de llamar arrays numpy?

    Parece que está más interesado en la diferencia entre su función 3 en comparación con los enfoques de NumPy puro (función 1) y Python (función 2). La respuesta es bastante simple (especialmente si nos fijamos en la función 4):

    • Las funciones NumPy tienen un factor “enorme” constante.

    Por lo general, se necesitan varios miles de elementos para obtener el régimen en el que el tiempo de ejecución de np.sum realmente depende del número de elementos de la matriz. Usando IPython y matplotlib (el gráfico se encuentra al final de la respuesta) puede verificar fácilmente la dependencia del tiempo de ejecución:

     import numpy as np n = [] timing_sum1 = [] timing_sum2 = [] for i in range(1, 25): num = 2**i arr = np.arange(num) print(num) time1 = %timeit -o arr.sum() # calling the method time2 = %timeit -o np.sum(arr) # calling the function n.append(num) timing_sum1.append(time1) timing_sum2.append(time2) 

    Los resultados para np.sum (acortados) son bastante interesantes:

     4 22.6 µs ± 297 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 16 25.1 µs ± 1.08 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 64 25.3 µs ± 1.58 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 256 24.1 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 1024 24.6 µs ± 221 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 4096 27.6 µs ± 147 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 16384 40.6 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 65536 91.2 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 262144 394 µs ± 8.09 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 1048576 1.24 ms ± 4.38 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 4194304 4.71 ms ± 22.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 16777216 18.6 ms ± 280 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

    Parece que el factor constante es aproximadamente 20 20µs en mi computadora) y se necesita una matriz con 16384 mil elementos para duplicar ese tiempo. Así que el tiempo para la función 3 y 4 son en su mayoría multiplicativos de tiempo del factor constante.

    En la función 3 incluyes el factor constante 2 veces, una vez con np.sum y una vez con np.arange . En este caso, un arange es bastante barato porque cada matriz es del mismo tamaño, por lo que NumPy y Python y su sistema operativo probablemente reutilicen la memoria de la matriz de la última iteración. Sin embargo, incluso eso lleva tiempo (aproximadamente 2µs para arreglos muy pequeños en mi computadora).

    Más generalmente: para identificar cuellos de botella, ¡siempre debe perfilar las funciones!

    Muestro los resultados para las funciones con perfilador de línea . Por lo tanto, modifiqué las funciones un poco para que solo hagan una operación por línea:

     import numpy as np def func1(): x = np.arange(1000) x = x*2 return np.sum(x) def func2(): sum_ = 0 for i in range(1000): tmp = i*2 sum_ += tmp return sum_ def func3(): sum_ = 0 for i in range(0, 1000, 4): # I'm using python3, so "range" is like "xrange"! x = np.arange(i, i + 4, 1) x = x * 2 tmp = np.sum(x) sum_ += tmp return sum_ def func4(): sum_ = 0 x = np.arange(1000) for i in range(0, 1000, 4): y = x[i:i + 4] y = y * 2 tmp = np.sum(y) sum_ += tmp return sum_ 

    Resultados:

     %load_ext line_profiler %lprun -f func1 func1() Line # Hits Time Per Hit % Time Line Contents ============================================================== 4 def func1(): 5 1 62 62.0 23.8 x = np.arange(1000) 6 1 65 65.0 24.9 x = x*2 7 1 134 134.0 51.3 return np.sum(x) %lprun -f func2 func2() Line # Hits Time Per Hit % Time Line Contents ============================================================== 9 def func2(): 10 1 7 7.0 0.1 sum_ = 0 11 1001 2523 2.5 30.9 for i in range(1000): 12 1000 2819 2.8 34.5 tmp = i*2 13 1000 2819 2.8 34.5 sum_ += tmp 14 1 3 3.0 0.0 return sum_ %lprun -f func3 func3() Line # Hits Time Per Hit % Time Line Contents ============================================================== 16 def func3(): 17 1 7 7.0 0.0 sum_ = 0 18 251 909 3.6 2.9 for i in range(0, 1000, 4): 19 250 6527 26.1 21.2 x = np.arange(i, i + 4, 1) 20 250 5615 22.5 18.2 x = x * 2 21 250 16053 64.2 52.1 tmp = np.sum(x) 22 250 1720 6.9 5.6 sum_ += tmp 23 1 3 3.0 0.0 return sum_ %lprun -f func4 func4() Line # Hits Time Per Hit % Time Line Contents ============================================================== 25 def func4(): 26 1 7 7.0 0.0 sum_ = 0 27 1 49 49.0 0.2 x = np.arange(1000) 28 251 892 3.6 3.4 for i in range(0, 1000, 4): 29 250 2177 8.7 8.3 y = x[i:i + 4] 30 250 5431 21.7 20.7 y = y * 2 31 250 15990 64.0 60.9 tmp = np.sum(y) 32 250 1686 6.7 6.4 sum_ += tmp 33 1 3 3.0 0.0 return sum_ 

    No voy a entrar en los detalles de los resultados, pero como puede ver, np.sum es definitivamente el cuello de botella en func3 y func4 . Ya adiviné que np.sum es el cuello de botella antes de escribir la respuesta, pero estos perfiles de línea en realidad verifican que se trata del cuello de botella.

    Lo que lleva a un hecho muy importante al usar NumPy:

    • ¡Sepa cuándo usarlo! Las matrices pequeñas no valen la pena (en su mayoría).
    • Conozca las funciones NumPy y solo úselos. Ya usan (si están disponibles) banderas de optimización del comstackdor para desenrollar los bucles.

    Si realmente crees que alguna parte es demasiado lenta, entonces puedes usar:

    • NumPy’s C API y procesa la matriz con C (puede ser muy fácil con Cython, pero también puedes hacerlo manualmente)
    • Numba (basado en LLVM).

    Pero en general, es probable que no pueda vencer a NumPy para arreglos de tamaño moderado (varios miles de entradas y más).


    Visualización de los tiempos:

     %matplotlib notebook import matplotlib.pyplot as plt # Average time per sum-call fig = plt.figure(1) ax = plt.subplot(111) ax.plot(n, [time.average for time in timing_sum1], label='arr.sum()', c='red') ax.plot(n, [time.average for time in timing_sum2], label='np.sum(arr)', c='blue') ax.set_xscale('log') ax.set_yscale('log') ax.set_xlabel('elements') ax.set_ylabel('time it takes to sum them [seconds]') ax.grid(which='both') ax.legend() # Average time per element fig = plt.figure(1) ax = plt.subplot(111) ax.plot(n, [time.average / num for num, time in zip(n, timing_sum1)], label='arr.sum()', c='red') ax.plot(n, [time.average / num for num, time in zip(n, timing_sum2)], label='np.sum(arr)', c='blue') ax.set_xscale('log') ax.set_yscale('log') ax.set_xlabel('elements') ax.set_ylabel('time per element [seconds / element]') ax.grid(which='both') ax.legend() 

    Las plots son log-log, creo que fue la mejor manera de visualizar los datos, dado que se extienden a varios órdenes de magnitud (solo espero que todavía sea comprensible).

    La primera gráfica muestra cuánto tiempo se tarda en hacer la sum :

    introduzca la descripción de la imagen aquí

    La segunda gráfica muestra el tiempo promedio que se tarda en hacer la sum dividida por el número de elementos en la matriz. Esta es solo otra forma de interpretar los datos:

    introduzca la descripción de la imagen aquí

    Según las pruebas (que se muestran a continuación), parece que está superado por la sobrecarga funcional de la llamada. Junto con la capacidad vectorizada de las funciones / herramientas NumPy, tenemos que proporcionarle suficientes datos para su procesamiento. Con func3 , le damos solo 4 elementos por llamada a np.sum .

    Vamos a investigar la sobrecarga por llamada para np.sum . Aquí está np.sum comenzando con la sum de ninguno, un elemento y en adelante:

     In [90]: a = np.array([]) In [91]: %timeit np.sum(a) 1000000 loops, best of 3: 1.6 µs per loop In [61]: a = np.array([0]) In [62]: %timeit np.sum(a) 1000000 loops, best of 3: 1.66 µs per loop In [63]: a = np.random.randint(0,9,(100)) In [64]: %timeit np.sum(a) 100000 loops, best of 3: 1.79 µs per loop In [65]: a = np.random.randint(0,9,(1000)) In [66]: %timeit np.sum(a) 100000 loops, best of 3: 2.25 µs per loop In [67]: a = np.random.randint(0,9,(10000)) In [68]: %timeit np.sum(a) 100000 loops, best of 3: 7.27 µs per loop 

    y así.

    Por lo tanto, incurriríamos en un mínimo de alrededor de 1.6 u-sec por llamada a np.sum en la configuración del sistema para estas pruebas.

    Veamos cómo se realiza la adición escalar con el operador de sum –

     In [98]: def add_nums(a,b): ...: return a+b ...: In [99]: %timeit add_nums(2,3) 10000000 loops, best of 3: 71.5 ns per loop 

    Esto es aproximadamente 25x más rápido que la sobrecarga por llamada para np.sum .

    La siguiente idea obvia es probar para ver cómo funciona func3 con más datos np.sum en np.sum .

    func3 modificada (la versión que usa la segmentación) para tener un tamaño de datos variable para la sum por iteración:

     def func3(scale_factor = 4): sum1 = 0 x = np.arange(0,1000) for i in xrange(0,1000,scale_factor): sum1 += np.sum(x[i:i+scale_factor]*2) return sum1 

    Comenzando con un scale_factor = 4 tal como se usa originalmente

     In [83]: %timeit func1() 100000 loops, best of 3: 5.39 µs per loop In [84]: %timeit func2() 10000 loops, best of 3: 39.8 µs per loop In [85]: %timeit func3(scale_factor = 4) 1000 loops, best of 3: 741 µs per loop 

    Sí, func3 es lento.

    Ahora, vamos a dar más datos por llamada a np.sum es decir, boost scale_factor

     In [86]: %timeit func3(scale_factor = 8) 1000 loops, best of 3: 376 µs per loop In [87]: %timeit func3(scale_factor = 20) 10000 loops, best of 3: 152 µs per loop In [88]: %timeit func3(scale_factor = 100) 10000 loops, best of 3: 33.5 µs per loop 

    y así sucesivamente hasta que alimentemos todos los datos a np.sum para el límite máximo de rendimiento con np.sum y la sobrecarga de llamadas mínima.

    En primer lugar, nadie escribiría la tercera variante en C, porque el comstackdor debería hacer las optimizaciones necesarias.

    Así que toma el primero, tienes dos creaciones de matrices numpy (arange y * 2) y una sum. La creación de objetos complejos como una gran cantidad de matrices toma tiempo, pero cada operación de vector se escribe en código C y muy rápido.

    El segundo solo utiliza operaciones de Python primitivas (aproximadamente 3000, iteración, multipicación y sum), que están escritas en C y muy rápido.

    La tercera variante crea aproximadamente 2 * 250 matrices numpy (una operación comparativamente lenta), lo que lleva a una velocidad de ejecución 100 veces más lenta en comparación con solo crear 2 matrices numpy.

    Si tiene inquietudes con respecto al uso de la memoria, debe usar operaciones en línea, que solo crean una matriz:

     x = np.arange(1000) x *= 2 return x.sum() 

    Si aún tiene que usar demasiada memoria, divida sus operaciones en trozos lo más grandes posible.