python - ¿Por qué log2 y log1p son mucho más rápidos que log and log10?

performance numpy

Question

Mientras jugaba con esta pregunta, me di cuenta de algo que no podía explicar en relación con el rendimiento relativo de np.log2 , np.log y np.log10 :

In [1]: %%timeit x = np.random.rand(100000)
   ....: np.log2(x)
   ....: 
1000 loops, best of 3: 1.31 ms per loop

In [2]: %%timeit x = np.random.rand(100000)
np.log(x)
   ....: 
100 loops, best of 3: 3.64 ms per loop

In [3]: %%timeit x = np.random.rand(100000)
np.log10(x)
   ....: 
100 loops, best of 3: 3.93 ms per loop

np.log2 es aproximadamente 3 veces más rápido que np.log y np.log10 . Quizás incluso más contraintuitivamente, np.log1p(x) , que calcula ln (x + 1) , está a la par con np.log2 :

In [4]: %%timeit x = np.random.rand(100000)
np.log1p(x)
   ....: 
1000 loops, best of 3: 1.46 ms per loop

Obtuve tiempos casi idénticos en numpy v1.10.1 y v1.8.2.

¿Existe una explicación intuitiva para estas discrepancias en el rendimiento en tiempo de ejecución?

Answer 1

(Probablemente debería ser un comentario pero será demasiado largo ...)

Para hacer esto más interesante, en 2018 en una máquina con Windows 10 de 64 bits, los resultados se invierten.

Predeterminado Anaconda

Python 3.6.3 |Anaconda, Inc.| (default, Oct 15 2017, 03:27:45) [MSC v.1900 64 bit (AMD64)]
Type ''copyright'', ''credits'' or ''license'' for more information
IPython 6.1.0 -- An enhanced Interactive Python. Type ''?'' for help.

In [1]: import numpy as np; np.random.seed(0); x = np.random.rand(100000)
   ...: %timeit np.log2(x)
   ...: %timeit np.log1p(x)
   ...: %timeit np.log(x)
   ...: %timeit np.log10(x)
   ...:
1.48 ms ± 18 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
1.33 ms ± 36.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
840 µs ± 7.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
894 µs ± 2.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Intel Python

Python 3.6.3 |Intel Corporation| (default, Oct 17 2017, 23:26:12) [MSC v.1900 64 bit (AMD64)]
Type ''copyright'', ''credits'' or ''license'' for more information
IPython 6.1.0 -- An enhanced Interactive Python. Type ''?'' for help.

In [1]: import numpy as np; np.random.seed(0); x = np.random.rand(100000)
   ...: %timeit np.log2(x)
   ...: %timeit np.log1p(x)
   ...: %timeit np.log(x)
   ...: %timeit np.log10(x)
   ...:
1.01 ms ± 2.57 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
236 µs ± 6.08 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
161 µs ± 1.77 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
171 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 2

Descargo de responsabilidad: No soy ni una fuente creíble ni oficial.

Estoy casi seguro de que cualquier implementación de log en la función base e puede realizarse tan rápido como la función log2, porque para convertir una a la otra se necesita una única división por una constante. Esto es, por supuesto, suponiendo que una operación de división única es una pequeña fracción de los otros cálculos; lo que en implementaciones precisas de logaritmos es cierto.

En la mayoría de los casos, numpy usa math.h de glibc , verá la misma diferencia en C / C ++ si usa math.h / cmath.h . En los comentarios, algunas personas observan las mismas velocidades para np.log y np.log2 ; Sospecho que esto puede provenir de diferentes construcciones / plataformas.

Puede encontrar el código fuente bien comentado para las dos funciones en los archivos e_log.c , e_log2.c , e_logf.c , e_log2f.c en los e_log2f.c dbl-64/ y flt-32/ de este repositorio de GitHub .

Para la doble precisión, en glibc , la función de log está implementando un algoritmo completamente diferente (comparado con el log ) de IBM desde ~ 2001, que se incluyó en su biblioteca libultim . Mientras que log2 es de Sun Microsystems desde ~ 1993. Con solo mirar el código, se pueden ver dos aproximaciones diferentes que se están implementando. En contraste, para una precisión simple, tanto las funciones log como log2 son las mismas aparte de la división por ln2 en el caso log2 , por lo tanto, la misma velocidad.

Para obtener más información sobre los algoritmos subyacentes, las alternativas y las discusiones sobre las que se incluirán en glibc en el futuro, consulte here .

Answer 3

Encontré su pregunta extremadamente interesante, así que pasé unas horas haciendo un poco de investigación; Creo que he encontrado una explicación para la diferencia de rendimiento que se aplica a los enteros (gracias a Matteo Italia por su nota). No está claro cómo se puede extender ese razonamiento a los flotadores:

Las computadoras utilizan la base 2: de acuerdo con los artículos vinculados en la referencia, el cálculo de log2 es un proceso de 4 ciclos de procesamiento; el de log10 requiere multiplicar log2 (val) por 1 / log2 (10), lo que agrega otros 5 ciclos.

Encontrar log2 es una cuestión de encontrar el índice del bit menos significativo de un valor . (video a los 23 minutos aproximadamente).

hacks de bits: Encuentre la base de registros de enteros 10 de un entero

hacks de bits: busque la base de registro 2 de un entero de N bits en O (lg (N))

La base de registro de enteros 10 se calcula utilizando primero una de las técnicas anteriores para encontrar la base de registro 2. Mediante la relación log10 (v) = log2 (v) / log2 (10), necesitamos multiplicarlo por 1 / log2 ( 10), que es aproximadamente 1233/4096, o 1233 seguido de un cambio a la derecha de 12. Es necesario agregar uno porque IntegerLogBase2 se redondea hacia abajo. Finalmente, como el valor t es solo una aproximación que puede estar desactivada en uno, el valor exacto se encuentra restando el resultado de v <PowersOf10 [t].

Este método requiere 6 operaciones más que IntegerLogBase2. Se puede acelerar (en máquinas con acceso rápido a la memoria) modificando el método de búsqueda en tabla del log base 2 anterior para que las entradas contengan lo que se calcula para t (es decir, agregar previamente, -mulitply y -shift). Hacer esto requeriría un total de solo 9 operaciones para encontrar el log base 10, suponiendo que se usaron 4 tablas (una para cada byte de v).

Es de destacar: el uso de las técnicas de búsqueda y cambio de bits de DeBruijn para calcular log2 en este video del MIT: Lec 2 | MIT 6.172 Ingeniería de rendimiento de sistemas de software, otoño de 2010 (video en la marca del minuto 36 en adelante).

Es de destacar que esta publicación de que muestra un método para realizar cálculos log2 eficientes realmente es multiplataforma con C ++

Advertencia: no he comprobado el código fuente numpy para verificar que efectivamente implementa técnicas similares, pero sería sorprendente que no lo hiciera. De hecho, a partir de los comentarios en la publicación del OP, Fermion Portal ha verificado:

En realidad, numpy usa math.h de glibc, verá la misma diferencia en C / C ++ si usa math.h / cmath.h. Puede encontrar el código fuente bien comentado para las dos funciones, por ejemplo, ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… y ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… - Portal de Fermion [9]

Answer 4

Esto es solo una nota, pero más largo que un comentario. Aparentemente esto tiene que ver con su instalación particular:

import numpy as np
import numexpr as ne
x = np.random.rand(100000)

Obtengo los mismos tiempos con numpy 1.10 de conda y una versión compilada con icc:

%timeit np.log2(x)
1000 loops, best of 3: 1.24 ms per loop

%timeit np.log(x)
1000 loops, best of 3: 1.28 ms per loop

Pensé que podría tener algo que ver con agarrar el paquete MKL VML, pero parece que eso es un no:

%timeit ne.evaluate(''log(x)'')
1000 loops, best of 3: 218 µs per loop

Parece que su instalación numpy está tomando su implementación log / log2 desde dos lugares diferentes, lo que es extraño.