Cómo optimizar para velocidad¶
A continuación se ofrecen algunas directrices prácticas para ayudarte a escribir un código eficiente para el proyecto scikit-learn.
Nota
Aunque siempre es útil perfilar tu código para comprobar los supuestos de rendimiento, también es muy recomendable revisar la literatura para asegurarse de que el algoritmo implementado es el más avanzado para la tarea antes de invertir en una costosa optimización de la implementación.
Una y otra vez, las horas de esfuerzo invertidas en la optimización de complicados detalles de implementación se han vuelto irrelevantes por el posterior descubrimiento de simples trucos algorítmicos, o por el uso de otro algoritmo que sea más adecuado para el problema.
La sección Un simple truco algorítmico: reinicios en caliente ofrece un ejemplo de este tipo de trucos.
¿Python, Cython o C/C++?¶
En general, el proyecto scikit-learn enfatiza la legibilidad del código fuente para facilitar a los usuarios del proyecto la inmersión en el código fuente para entender cómo se comporta el algoritmo en sus datos, pero también para facilitar el mantenimiento (por parte de los desarrolladores).
Cuando se implementa un nuevo algoritmo se recomienda empezar a implementarlo en Python usando Numpy y Scipy teniendo cuidado de evitar el código de bucles usando los modismos vectorizados de esas bibliotecas. En la práctica esto significa intentar reemplazar cualquier bucle for anidado por llamadas a métodos de arreglos Numpy equivalentes. El objetivo es evitar que la CPU pierda tiempo en el intérprete de Python en lugar de hacer cálculos para ajustar tu modelo estadístico. En general, es una buena idea tener en cuenta los tips de rendimiento de NumPy y SciPy: https://scipy.github.io/old-wiki/pages/PerformanceTips
Sin embargo, a veces un algoritmo no puede ser expresado eficientemente en un simple código Numpy vectorizado. En este caso, la estrategia recomendada es la siguiente:
Perfila la implementación en Python para encontrar el principal cuello de botella y aislarlo en una función dedicada a nivel de módulo. Esta función se reimplementará como un módulo de extensión compilado.
Si existe una implementación BSD o MIT C/C++ bien mantenida del mismo algoritmo que no sea demasiado grande, puedes escribir un envoltorio (wrapper) de Cython para él e incluir una copia del código fuente de la biblioteca en el árbol fuente de scikit-learn: esta estrategia se utiliza para las clases
svm.LinearSVC,svm.SVCylinear_model.LogisticRegression(envoltorios para liblinear y libsvm).De lo contrario, escribe una versión optimizada de tu función de Python usando Cython directamente. Esta estrategia se utiliza para las clases
linear_model.ElasticNetylinear_model.SGDClassifierpor ejemplo.Cambia la versión de Python de la función en las pruebas y úsala para comprobar que los resultados de la extensión compilada sean consistentes con la versión de Python gold standard y fácil de depurar.
Una vez que el código está optimizado (no es un simple cuello de botella detectable mediante el perfilado), comprueba si es posible tener un paralelismo de grano grueso que sea susceptible de multiprocesamiento utilizando la clase
joblib.Parallel.
Al utilizar Cython, usar cualquiera
python setup.py build_ext -i
python setup.py install
para generar archivos C. Eres responsable de añadir las extensiones .c/.cpp junto con los parámetros de compilación en cada submódulo setup.py.
Los archivos generados en C/C++ están embebidos en los paquetes estables distribuidos. El objetivo es hacer posible la instalación de la versión estable de scikit-learn en cualquier máquina con Python, Numpy, Scipy y compilador C/C++.
Perfilar el código Python¶
Para perfilar el código Python recomendamos escribir un script que cargue y prepare tus datos y luego utilizar el perfilador integrado de IPython para explorar interactivamente la parte relevante para el código.
Supongamos que queremos perfilar el módulo de Factorización Matricial No Negativa (Non Negative Matrix Factorization) de scikit-learn. Vamos a configurar una nueva sesión de IPython y cargar el conjunto de datos de dígitos y como en el ejemplo Reconocimiento de dígitos escritos a mano:
In [1]: from sklearn.decomposition import NMF
In [2]: from sklearn.datasets import load_digits
In [3]: X, _ = load_digits(return_X_y=True)
Antes de iniciar la sesión de perfilado y realizar iteraciones de optimización tentativas, es importante medir el tiempo total de ejecución de la función que queremos optimizar sin ningún tipo de sobrecarga del perfilador y guardarlo en algún lugar para su posterior consulta:
In [4]: %timeit NMF(n_components=16, tol=1e-2).fit(X)
1 loops, best of 3: 1.7 s per loop
Para ver el perfil de rendimiento general utilizando el comando magic %prun:
In [5]: %prun -l nmf.py NMF(n_components=16, tol=1e-2).fit(X)
14496 function calls in 1.682 CPU seconds
Ordered by: internal time
List reduced from 90 to 9 due to restriction <'nmf.py'>
ncalls tottime percall cumtime percall filename:lineno(function)
36 0.609 0.017 1.499 0.042 nmf.py:151(_nls_subproblem)
1263 0.157 0.000 0.157 0.000 nmf.py:18(_pos)
1 0.053 0.053 1.681 1.681 nmf.py:352(fit_transform)
673 0.008 0.000 0.057 0.000 nmf.py:28(norm)
1 0.006 0.006 0.047 0.047 nmf.py:42(_initialize_nmf)
36 0.001 0.000 0.010 0.000 nmf.py:36(_sparseness)
30 0.001 0.000 0.001 0.000 nmf.py:23(_neg)
1 0.000 0.000 0.000 0.000 nmf.py:337(__init__)
1 0.000 0.000 1.681 1.681 nmf.py:461(fit)
La columna tottime es la más interesante: da el tiempo total de ejecución del código de una función determinada, ignorando el tiempo de ejecución de las subfunciones. El tiempo total real (código local + llamadas a subfunciones) viene dado por la columna cumtime.
Ten en cuenta el uso de -l nmf.py que restringe la salida a las líneas que contienen la cadena «nmf.py». Esto es útil para echar un vistazo rápido al punto de acceso del módulo de Python nmf en sí mismo, ignorando cualquier otra cosa.
Aquí está el principio de la salida del mismo comando sin el filtro -l nmf.py:
In [5] %prun NMF(n_components=16, tol=1e-2).fit(X)
16159 function calls in 1.840 CPU seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
2833 0.653 0.000 0.653 0.000 {numpy.core._dotblas.dot}
46 0.651 0.014 1.636 0.036 nmf.py:151(_nls_subproblem)
1397 0.171 0.000 0.171 0.000 nmf.py:18(_pos)
2780 0.167 0.000 0.167 0.000 {method 'sum' of 'numpy.ndarray' objects}
1 0.064 0.064 1.840 1.840 nmf.py:352(fit_transform)
1542 0.043 0.000 0.043 0.000 {method 'flatten' of 'numpy.ndarray' objects}
337 0.019 0.000 0.019 0.000 {method 'all' of 'numpy.ndarray' objects}
2734 0.011 0.000 0.181 0.000 fromnumeric.py:1185(sum)
2 0.010 0.005 0.010 0.005 {numpy.linalg.lapack_lite.dgesdd}
748 0.009 0.000 0.065 0.000 nmf.py:28(norm)
...
Los resultados anteriores muestran que la ejecución está dominada en gran medida por las operaciones de productos punto (delegadas a blas). Por lo tanto, probablemente no se puede esperar una gran ganancia reescribiendo este código en Cython o C/C++: en este caso, de los 1.7s de tiempo total de ejecución, se gastan casi 0.7s en código compilado que podemos considerar óptimo. Reescribiendo el resto del código Python y suponiendo que pudiéramos lograr un aumento del 1000% en esta porción (lo que es muy improbable dada la poca profundidad de los bucles de Python), no ganaríamos más de una velocidad global 2.4 veces superior.
Por lo tanto, las mejoras importantes sólo pueden lograrse mediante mejoras algorítmicas en este ejemplo en particular (por ejemplo, tratando de encontrar operaciones que sean a la vez costosas e inútiles para evitar su cálculo entonces, en lugar de tratar de optimizar su implementación).
Sin embargo, sigue siendo interesante comprobar lo que ocurre dentro de la función _nls_subproblem, que es el punto de acceso si sólo tenemos en cuenta el código de Python: requiere alrededor del 100% del tiempo acumulado del módulo. Para entender mejor el perfil de esta función específica, instalemos line_profiler y conectémoslo a IPython:
pip install line_profiler
En IPython 0.13+, primero crea un perfil de configuración:
ipython profile create
Luego registra la extensión line_profiler en ~/.ipython/profile_default/ipython_config.py:
c.TerminalIPythonApp.extensions.append('line_profiler')
c.InteractiveShellApp.extensions.append('line_profiler')
Esto registrará el comando magic %lprun en la aplicación de terminal de IPython y en los otros frontends como qtconsole y notebook.
Ahora reinicia IPython y usemos este nuevo juguete:
In [1]: from sklearn.datasets import load_digits
In [2]: from sklearn.decomposition import NMF
... : from sklearn.decomposition._nmf import _nls_subproblem
In [3]: X, _ = load_digits(return_X_y=True)
In [4]: %lprun -f _nls_subproblem NMF(n_components=16, tol=1e-2).fit(X)
Timer unit: 1e-06 s
File: sklearn/decomposition/nmf.py
Function: _nls_subproblem at line 137
Total time: 1.73153 s
Line # Hits Time Per Hit % Time Line Contents
==============================================================
137 def _nls_subproblem(V, W, H_init, tol, max_iter):
138 """Non-negative least square solver
...
170 """
171 48 5863 122.1 0.3 if (H_init < 0).any():
172 raise ValueError("Negative values in H_init passed to NLS solver.")
173
174 48 139 2.9 0.0 H = H_init
175 48 112141 2336.3 5.8 WtV = np.dot(W.T, V)
176 48 16144 336.3 0.8 WtW = np.dot(W.T, W)
177
178 # values justified in the paper
179 48 144 3.0 0.0 alpha = 1
180 48 113 2.4 0.0 beta = 0.1
181 638 1880 2.9 0.1 for n_iter in range(1, max_iter + 1):
182 638 195133 305.9 10.2 grad = np.dot(WtW, H) - WtV
183 638 495761 777.1 25.9 proj_gradient = norm(grad[np.logical_or(grad < 0, H > 0)])
184 638 2449 3.8 0.1 if proj_gradient < tol:
185 48 130 2.7 0.0 break
186
187 1474 4474 3.0 0.2 for inner_iter in range(1, 20):
188 1474 83833 56.9 4.4 Hn = H - alpha * grad
189 # Hn = np.where(Hn > 0, Hn, 0)
190 1474 194239 131.8 10.1 Hn = _pos(Hn)
191 1474 48858 33.1 2.5 d = Hn - H
192 1474 150407 102.0 7.8 gradd = np.sum(grad * d)
193 1474 515390 349.7 26.9 dQd = np.sum(np.dot(WtW, d) * d)
...
Si se observan los valores más altos de la columna % Time es realmente fácil señalar las expresiones más costosas que merecerían atención adicional.
Perfilar el uso de memoria¶
Puedes analizar en detalle el uso de memoria de cualquier código Python con la ayuda de memory_profiler. Primero, instala la última versión:
pip install -U memory_profiler
Luego, configura los magics de forma similar a line_profiler.
En IPython 0.11+, primero crea un perfil de configuración:
ipython profile create
Luego registra la extensión en ~/.ipython/profile_default/ipython_config.py junto al perfilador de línea:
c.TerminalIPythonApp.extensions.append('memory_profiler')
c.InteractiveShellApp.extensions.append('memory_profiler')
Esto registrará los comandos magic %memit y %mprun en la aplicación de terminal de IPython y en los otros frontends como qtconsole y notebook.
%mprun es útil para examinar, línea por línea, el uso de memoria de las funciones clave de tu programa. Es muy similar a %lprun, discutido en la sección anterior. Por ejemplo, desde el directorio examples de memory_profiler:
In [1] from example import my_func
In [2] %mprun -f my_func my_func()
Filename: example.py
Line # Mem usage Increment Line Contents
==============================================
3 @profile
4 5.97 MB 0.00 MB def my_func():
5 13.61 MB 7.64 MB a = [1] * (10 ** 6)
6 166.20 MB 152.59 MB b = [2] * (2 * 10 ** 7)
7 13.61 MB -152.59 MB del b
8 13.61 MB 0.00 MB return a
Otro magic útil que define memory_profiler es %memit, que es análogo a %timeit. Se puede utilizar de la siguiente manera:
In [1]: import numpy as np
In [2]: %memit np.zeros(1e7)
maximum of 3: 76.402344 MB per loop
Para más detalles, consulta las cadenas de documentación de los magics, utilizando %memit? y %mprun?.
Tips de rendimiento para el desarrollador Cython¶
Si el perfilado del código Python revela que la sobrecarga del intérprete Python es mayor en un orden de magnitud o más que el coste del cálculo numérico real (por ejemplo, bucles for sobre componentes vectoriales, evaluación anidada de expresiones condicionales, aritmética escalar…), probablemente sea adecuado extraer la parte hotspot del código como una función independiente en un archivo .pyx, añadir declaraciones de tipos estáticos y luego utilizar Cython para generar un programa en C adecuado para ser compilado como un módulo de extensión Python.
La documentación oficial disponible en http://docs.cython.org/ contiene un tutorial y un manual de referencia para desarrollar dicho módulo. A continuación sólo destacaremos un par de trucos que hemos encontrado importantes en la práctica en el código base de cython existente en el proyecto scikit-learn.
TODO: informe html, declaraciones de tipo, comprobaciones de límites, comprobaciones de división por cero, alineación de memoria, llamadas directas a blas…
Utilizando OpenMP¶
Como scikit-learn puede ser construido sin OpenMP, es necesario proteger cada llamada directa a OpenMP. Esto se puede hacer usando la siguiente sintaxis:
# importing OpenMP
IF SKLEARN_OPENMP_PARALLELISM_ENABLED:
cimport openmp
# calling OpenMP
IF SKLEARN_OPENMP_PARALLELISM_ENABLED:
max_threads = openmp.omp_get_max_threads()
ELSE:
max_threads = 1
Nota
La protección del bucle paralelo, prange, ya la hace cython.
Perfilar las extensiones compiladas¶
Cuando se trabaja con extensiones compiladas (escritas en C/C++ con un envoltorio o directamente como extensión de Cython), el perfilador de Python predeterminado es inútil: necesitamos una herramienta dedicada para introspeccionar lo que está sucediendo dentro de la propia extensión compilada.
Utilizando yep y gperftools¶
El perfilado fácil sin opciones especiales de compilación utiliza yep:
Utilizando gprof¶
Para perfilar las extensiones de Python compiladas se puede utilizar gprof después de haber recompilado el proyecto con gcc -pg y utilizando la variante python-dbg del intérprete en debian / ubuntu: sin embargo, este enfoque requiere tener también numpy y scipy recompilados con -pg, lo que es bastante complicado de conseguir.
Afortunadamente, existen dos perfiladores alternativos que no requieren que se recompile todo.
Utilizando valgrind / callgrind / kcachegrind¶
kcachegrind¶
Se puede utilizar yep para crear un informe de perfilado. kcachegrind proporciona un entorno gráfico para visualizar este informe:
# Run yep to profile some python script
python -m yep -c my_file.py
# open my_file.py.callgrin with kcachegrind
kcachegrind my_file.py.prof
Nota
yep puede ser ejecutado con el argumento --lines o -l para compilar un informe de perfilado “línea por línea”.
Paralelismo multinúcleo utilizando joblib.Parallel¶
Un simple truco algorítmico: reinicios en caliente¶
Ver la entrada del glosario para warm_start