python - ¿Por qué numpy.any es tan lento en grandes matrices?

arrays performance

Question

Estoy buscando la manera más eficiente de determinar si una matriz grande contiene al menos un valor distinto de cero. A primera vista, np.any parece ser la herramienta obvia para el trabajo, pero parece inesperadamente lenta en arreglos grandes.

Considera este caso extremo:

first = np.zeros(1E3,dtype=np.bool)
last = np.zeros(1E3,dtype=np.bool)

first[0] = True
last[-1] = True

# test 1
%timeit np.any(first)
>>> 100000 loops, best of 3: 6.36 us per loop

# test 2
%timeit np.any(last)
>>> 100000 loops, best of 3: 6.95 us per loop

Por lo menos, np.any parece estar haciendo algo vagamente sensato aquí: si el valor distinto de cero es el primero en la matriz, no debería haber necesidad de considerar ninguna otra antes de regresar a True , por lo que esperaría que la prueba 1 fuera ligeramente más rápida que prueba 2.

Sin embargo, ¿qué sucede cuando hacemos las matrices mucho más grandes?

first = np.zeros(1E9,dtype=np.bool)
last = np.zeros(1E9,dtype=np.bool)

first[0] = True
last[-1] = True

# test 3
%timeit np.any(first)
>>> 10 loops, best of 3: 21.6 ms per loop

# test 4
%timeit np.any(last)
>>> 1 loops, best of 3: 739 ms per loop

Como se esperaba, la prueba 4 es bastante más lenta que la prueba 3. Sin embargo, en la prueba 3 np.any , np.any deberían tener que verificar first el valor de un elemento individual para saber que contiene al menos un valor distinto de cero. ¿Por qué, entonces, la prueba 3 es mucho más lenta que la prueba 1?

Editar 1:

Estoy usando una versión de desarrollo de Numpy (1.8.0.dev-e11cd9b), pero obtengo los mismos resultados de sincronización usando Numpy 1.7.1. Estoy ejecutando Linux de 64 bits, Python 2.7.4. Mi sistema está básicamente inactivo (estoy ejecutando una sesión de IPython, un navegador y un editor de texto), y definitivamente no estoy llegando al intercambio. También repliqué el resultado en otra máquina ejecutando Numpy 1.7.1.

Editar 2:

Usando Numpy 1.6.2 obtengo tiempos de ~ 1.85us para las pruebas 1 y 3, así que como dice jorgeca parece haber habido alguna regresión de rendimiento entre Numpy 1.6.2 y 1.7.1 1.7.0 en este sentido.

Editar 3:

Siguiendo el ejemplo de JF Sebastian y jorgeca, he hecho más benchmarking utilizando np.all en una matriz de ceros, que debería ser equivalente a llamar a np.any en una matriz donde el primer elemento es uno.

Secuencia de comandos de prueba:

import timeit
import numpy as np
print ''Numpy v%s'' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(10):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool)" %(10**ii)
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

Resultados:

Numpy v1.6.2
Array size: 1E0, 1000000 loops, best of 3: 1.738 us/loop
Array size: 1E1, 1000000 loops, best of 3: 1.845 us/loop
Array size: 1E2, 1000000 loops, best of 3: 1.862 us/loop
Array size: 1E3, 1000000 loops, best of 3: 1.858 us/loop
Array size: 1E4, 1000000 loops, best of 3: 1.864 us/loop
Array size: 1E5, 1000000 loops, best of 3: 1.882 us/loop
Array size: 1E6, 1000000 loops, best of 3: 1.866 us/loop
Array size: 1E7, 1000000 loops, best of 3: 1.853 us/loop
Array size: 1E8, 1000000 loops, best of 3: 1.860 us/loop
Array size: 1E9, 1000000 loops, best of 3: 1.854 us/loop

Numpy v1.7.0
Array size: 1E0, 100000 loops, best of 3: 5.881 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.831 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.924 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.864 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.997 us/loop
Array size: 1E5, 100000 loops, best of 3: 6.979 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.196 us/loop
Array size: 1E7, 10000 loops, best of 3: 116.162 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.112 ms/loop
Array size: 1E9, 100 loops, best of 3: 11.061 ms/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.216 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.257 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.318 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.247 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.492 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.406 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.426 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.946 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.102 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.987 ms/loop

Numpy v1.8.0.dev-e11cd9b
Array size: 1E0, 100000 loops, best of 3: 6.357 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.399 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.425 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.397 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.596 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.569 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.445 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.109 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.094 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.840 ms/loop

Editar 4:

Siguiendo el comentario de Seberg, probé la misma prueba con una matriz np.float32 lugar de np.bool . En este caso, Numpy 1.6.2 también muestra una desaceleración a medida que aumenta el tamaño de las matrices:

Numpy v1.6.2
Array size: 1E0, 100000 loops, best of 3: 3.503 us/loop
Array size: 1E1, 100000 loops, best of 3: 3.597 us/loop
Array size: 1E2, 100000 loops, best of 3: 3.742 us/loop
Array size: 1E3, 100000 loops, best of 3: 4.745 us/loop
Array size: 1E4, 100000 loops, best of 3: 14.533 us/loop
Array size: 1E5, 10000 loops, best of 3: 112.463 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.101 ms/loop
Array size: 1E7, 100 loops, best of 3: 11.724 ms/loop
Array size: 1E8, 10 loops, best of 3: 116.924 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.168 s/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.548 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.546 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.804 us/loop
Array size: 1E3, 100000 loops, best of 3: 7.784 us/loop
Array size: 1E4, 100000 loops, best of 3: 17.946 us/loop
Array size: 1E5, 10000 loops, best of 3: 117.235 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.096 ms/loop
Array size: 1E7, 100 loops, best of 3: 12.328 ms/loop
Array size: 1E8, 10 loops, best of 3: 118.431 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.172 s/loop

¿Por qué debería suceder esto? Al igual que con el caso booleano, np.all solo debería tener que verificar el primer elemento antes de volver, por lo que los tiempos deberían ser constantes con el tamaño de la matriz.

Answer 1

Como se ha adivinado en los comentarios, puedo confirmar que el procesamiento de la matriz se realiza en fragmentos. Primero, le mostraré dónde están las cosas en el código y luego le mostraré cómo puede cambiar el tamaño del fragmento y el efecto que tiene en su punto de referencia.

Dónde encontrar el procesamiento de reducción en los archivos fuente Numpy

np.all (x) es lo mismo que x.all (). all () realmente llama a np.core.umath.logical_and.reduce (x).

Si quieres profundizar en la fuente numpy, intentaré guiarte para encontrar que se usa un tamaño de buffer / fragmento. La carpeta con todo el código que veremos es numpy / core / src / umath /.

PyUFunc_Reduce () en ufunc_object.c es la función C que maneja el reducir. En PyUFunc_Reduce (), el tamaño del trozo o del búfer se encuentra al buscar el valor para reducir en algún diccionario global a través de la función PyUFunc_GetPyValues ​​() (ufunc_object.c). En mi máquina y compilando desde la rama de desarrollo, el tamaño del fragmento es 8192. Se llama a PyUFunc_ReduceWrapper () en reduction.c para configurar el iterador (con una zancada igual al tamaño del fragmento) y llama a la función de bucle pasante que es reduce_loop () en ufunc_object.c.

reduce_loop () básicamente usa el iterador y llama a otra función innerloop () para cada fragmento. La función innerloop se encuentra en loops.c.src. Para una matriz booleana y nuestro caso de todos / logical_and, la función de bucle interno apropiada es BOOL_logical_and. Puede encontrar la función correcta buscando BOOLEAN LOOPS y luego es la segunda función que aparece debajo (es difícil de encontrar debido a la programación similar a una plantilla que se usa aquí). Allí encontrará que en realidad se está haciendo un cortocircuito por cada fragmento.

Cómo cambiar el tamaño del búfer utilizado en ufunciones (y por lo tanto en cualquier / todos)

Puede obtener el tamaño de fragmento / búfer con np.getbuffersize (). Para mí, eso devuelve 8192 sin configurar manualmente lo que coincide con lo que encontré al imprimir el tamaño del búfer en el código. Puede usar np.setbuffersize () para cambiar el tamaño del fragmento.

Resultados utilizando un tamaño de búfer más grande

Cambié tu código de referencia a lo siguiente:

import timeit
import numpy as np
print ''Numpy v%s'' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(9):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool); np.setbufsize(%d)" %(10**ii, max(8192, min(10**ii, 10**7)))
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

A Numpy no le gusta que el tamaño del búfer sea demasiado pequeño o demasiado grande, así que me aseguré de que no fuera más pequeño que 8192 o mayor que 1E7 porque a Numpy no le gustaba un tamaño de búfer de 1E8. De lo contrario, estaba configurando el tamaño del búfer al tamaño de la matriz que se está procesando. Solo subí a 1E8 porque mi máquina solo tiene 4 GB de memoria en este momento. Aquí están los resultados:

Numpy v1.8.0.dev-2a5c2c8
Array size: 1E0, 100000 loops, best of 3: 5.351 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.390 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.366 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.360 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.433 us/loop
Array size: 1E5, 100000 loops, best of 3: 5.400 us/loop
Array size: 1E6, 100000 loops, best of 3: 5.397 us/loop
Array size: 1E7, 100000 loops, best of 3: 5.381 us/loop
Array size: 1E8, 100000 loops, best of 3: 6.126 us/loop

Hay un pequeño repunte en el último momento debido a que hay varios fragmentos procesados ​​debido a las limitaciones de tamaño del tamaño del búfer.