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:

  1. 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.

  2. 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.SVC y linear_model.LogisticRegression (envoltorios para liblinear y libsvm).

  3. 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.ElasticNet y linear_model.SGDClassifier por ejemplo.

  4. 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.

  5. 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

Ver documentación joblib

Un simple truco algorítmico: reinicios en caliente

Ver la entrada del glosario para warm_start