Skip to content

Latest commit

 

History

History
746 lines (555 loc) · 23.8 KB

b06t02.md

File metadata and controls

746 lines (555 loc) · 23.8 KB
Raw

Python de alto rendimiento

Python se pensó para ocultar los detalles de implementación del lenguaje y que el desarrollador pudiera centrarse en los aspectos prácticos de la resolución de problemas.

Desafortunadamente, la abstracción está reñida con el rendimiento y los mecanismos que empleamos para mantener un diseño modular, reutilizable y cohesionado, pero sin acoplamiento o dependencias fuertes, añaden una sobrecarga que puede ser evidente en ciertas situaciones. Al fin y al cabo los procesadores se diseñaron para optimizar la ejecución de código ensamblador, no Python.

Los optimizadores de código de los lenguajes compilados hacen precisamente esto: eliminan la abstracción y acoplan los subsistemas del lenguaje tomando decisiones que suelen intercambiar especio por velocidad.

Afortunadamente para nosotros, la compilación no es el único recurso. La naturaleza del problema puede arrojar pistas de mejores estrategias para resolver el mismo, sin tener que descender al mundo de los lenguajes compilados.

Caracterización de aplicaciones (profiling)

Para poder optimizar un problema, primero debemos caracterizarlo. Existen algunas herramientas en el ecosistema Python para realizar este análisis y el propio Python incluye el módulo cProfiler para este fin.

  1. Crea un fichero profiling.py y añade el siguiente listado:

    import time

def improvable():
    for i in range(10000000):
        _ = i**2
    time.sleep(2)

def not_improvable():
    time.sleep(1)

def main():
    not_improvable()
    improvable()

if __name__ == '__main__':
    main()

  2. Ahora, desde una línea de comandos, ejecuta:

    $ python -m cProfile profiling.py

    El resultado tendrá una pinta similar a:

    $ python -m cProfile profiling.py
         8 function calls in 6.117 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    6.117    6.117 profiling.py:1(<module>)
        1    0.000    0.000    6.117    6.117 profiling.py:11(main)
        1    3.108    3.108    5.112    5.112 profiling.py:3(improvable)
        1    0.000    0.000    1.004    1.004 profiling.py:8(not_improvable)
        1    0.000    0.000    6.117    6.117 {built-in method builtins.exec}
        2    3.008    1.504    3.008    1.504 {built-in method time.sleep}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

    Donde existe una fila por cada función involucrada en la ejecución y los campos significan:

    • ncalls es el número de llamadas a la función.
    • tottime es el tiempo total pasado en esa función, sin contar el tiempo pasado en las sub-llamadas.
    • percall es la media de tiempo total por llamada.
    • cumtime es el tiempo total empleado en esa función, incluyendo sub-llamadas.
    • percall es la media del tiempo acumulado por llamada.
    • filename:lineno(function) indica dónde se produce la inversión de tiempo.

  3. El módulo cPython permite grabar exportar esta información:

    $ python -m cProfile -o data.prof profiling.py

    Y utilizar SnakeViz o tuna para visualizar el resultado:

    $ pip install tuna snakeviz
$ snakeviz data.prof

    Cuidado, porque en las interfaces gráficas puede darse una interpretación distinta a los mismos nombre. La mayoría llama "tiempo total" al tiempo invertido por una función y las sub-llamadas. Cuando esto pasa, el tiempo empleado sólo en la función se suele llamar "tiempo local" o se marca de alguna forma.

Los gráficos de llamas son útiles porque permiten visualizar fracciones de tiempo. En lenguajes interpretados, la mayor parte del fondo de las gráficas son llamadas a las funciones de la biblioteca estándar, muchas de ellas nativas y, por tanto, "inmejorables".

Conviene primero buscar las funciones que consumen más tiempo acumulado y, de entre ellas, comenzar por las que emplean más tiempo en sí mismas.

La ley de Amdahl

La ley de Amdahl dice:

La mejora en la latencia de un sistema está limitada por la porción de tiempo en que no obtenemos ninguna ganancia.

La ley de Amdahl se expresa matemáticamente como 1/(1 - p) donde p es la fracción de tiempo en la que podemos aplicar la mejora.

Por ejemplo, supón que caracterizamos un software y descubrimos que el 80% del tiempo lo empleamos en una función fácilmente paralelizable. Cuestión de arrojar más núcleos al problema. Lo que dice la ley de Amdahl es que la mejora en velocidad está limitada por ese 20% en el que no podemos aplicar la mejora. En particular, la mejora no puede ser superior a 1/(1 - 0.8) = 5. O lo que es lo mismo, el sistema nunca será más de 5 veces más rápido.

La mejora real del sistema se calcula en base a la mejora local, según la expresión S = 1/((1 - p) + p/s) donde S es la mejora global (global speedup) y p vuelve a ser la fracción del tiempo donde podemos aplicar la mejora local s (local speedup).

Paralelismo y multiprocesamiento

¿Permite Python ejecución paralela?

La respuesta rápida es no. Sin embargo podemos ser algo más transigentes y plantearnos otra pregunta, más general:

¿Permite Python ejecución concurrente?

En este caso la respuesta es sí. La diferencia entre paralelismo y concurrencia es sutil aunque relevante. La concurrencia se produce cuando más de una tarea progresa al mismo tiempo, sin esperar las unas a la finalización de las otras. El paralelismo se produce cuando dos tareas se ejecutan al mismo tiempo.

Python soporta múltiples tareas (threads) pero sólo una de ellas puede estar ejecutándose a la vez en el intérprete. Quien posee la ejecución en cada momento, se dice que está en posesión del GIL. Sin embargo, Python interrumpirá las tareas automáticamente y bajo ciertas condiciones para dejar que otras tareas progresen antes de que la actual termine.

Ojo, es el intérprete de Python el que no puede ejecutar más de una tarea al mismo tiempo. Si la ejecución ha salido fuera del intérprete (a una llamada del sistema nativo en C, por ejemplo), esta restricción no aplica y la ejecución depende del sistema.

Concurrencia multi-hilo

  1. Reemplaza el código de profiling.py (o crea un fichero nuevo) con este otro:

    from urllib import request

def get(url):
    response = request.urlopen(url)
    print(f'Body at {url}:\n {response.read()}')

def main():
    urls = [
        'https://raw.githubusercontent.com/python/cpython/master/README.rst',
        'https://raw.githubusercontent.com/rust-lang/rust/master/README.md',
        'https://raw.githubusercontent.com/ruby/ruby/master/README.md'] * 80

    list(map(get, urls))

if __name__ == '__main__':
    main()

    Caracterízalo y visualiza los resultados. ¿Qué observas?

  2. Ahora cambia el código para que utilice hilos:

    from urllib import request
from concurrent.futures import ThreadPoolExecutor

def get(url):
    response = request.urlopen(url)
    print(f'Body at {url}:\n {response.read()}')

def main():
    urls = [
        'https://raw.githubusercontent.com/python/cpython/master/README.rst',
        'https://raw.githubusercontent.com/rust-lang/rust/master/README.md',
        'https://raw.githubusercontent.com/ruby/ruby/master/README.md'] * 80

    with ThreadPoolExecutor(max_workers=5) as executor:
        executor.map(get, urls)

if __name__ == '__main__':
    main()

    Caracterízalo en un fichero de salida distinto y visualiza los resultados. Compáralos con los de antes.

Paralelismo multiproceso

  1. Considera el siguiente código:

    from datetime import datetime
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    start = datetime.now()
    for number, prime in zip(PRIMES, map(is_prime, PRIMES)):
        print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

  2. Ahora considera su versión multi-hilo:

    from datetime import datetime
from concurrent.futures import ThreadPoolExecutor
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    start = datetime.now()
    with ThreadPoolExecutor(max_workers=2) as executor:
        for number, prime in zip(PRIMES, executor.map(is_prime, PRIMES)):
            print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

    Caracterízala y observa las diferencias. ¿Qué ha pasado?

  3. Ahora prueba con la siguiente versión multiproceso:

    from datetime import datetime
from concurrent.futures import ProcessPoolExecutor
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    start = datetime.now()
    with ProcessPoolExecutor(max_workers=2) as executor:
        for number, prime in zip(PRIMES, executor.map(is_prime, PRIMES)):
            print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

    No intentes caracterizarlo, no funcionará. Es una de las limitaciones de cProfile: no funciona con mutiprocesamiento.

  4. Ve aumentando el parámetro processes desde 2 hasta que no notes ninguna mejora. ¿Por qué deja de haber mejora? Compara este número con el número de núcleos de tu ordenador.

¿Cuándo usar paralelismo y cuándo usar concurrencia?

En general, tendrás que distinguir si tus programas están constreñidos por la CPU o por la entrada y salida. Estas situaciones se conocen respectivamente como CPU Bound e I/O Bound.

Si tu aplicación es I/O Bound pasará más tiempo fuera del intérprete de Python que dentro. En este caso, cualquiera de las aproximaciones es válida aunque la concurrencia es más ligera y no implica al sistema operativo.

Si tu aplicación es CPU Bound, entonces pasará más tiempo en el intérprete de Python que fuera. Es lo que pasa con los algoritmos matemáticos de solución de problemas algebráicos o de cálculo. En este caso tienes que llevarte la gestión de la multitarea al sistema operativo con multiprocesamiento porque el intérprete sólo permitirá a un hilo operar al mismo tiempo.

Compiladores "al vuelo" (JIT compilers): Numba

Antes de problar con paralelización, sobre todo si nuestro código es de tipo "operaciones", convendría probar Numba, una biblioteca que implementa un compilador "al vuelo" compatible con la implementación de referencia, CPython.

Sencillamente importa el decorador jit y aplícalo a tu función crítica (Numba viene incluído en Anaconda, así que puedes usarlo desde el entorno virtual base que instalaste en el tema anterior):

from numba import jit
from datetime import datetime
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]

@jit(nopython=True)
def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    start = datetime.now()
    for number, prime in zip(PRIMES, map(is_prime, PRIMES)):
        print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

El parámetro nopython=True se pasa para que el compilador produzca un código más rápido, sin volver a la ejecución Python, en caso de que no consiguiera compilar el código. Es como indicar "sólo código nativo".

En el mundo real, la verdad es que Numba está muy limitado en cuanto a compatibilidad con Python. El código optimizable por Numba no es muy pythonico, podríamos decir. Si usas Numba, evita el uso de generadores y listas de listas; si necesitas listas anidadas, considera usar los ndarray de NumPy

Numba es además capaz de paralelizar código automáticamente, compilar para SIMD e, incluso, ¡para GPUs!

Intérpretes más rápidos: PyPy

Otra alternativa es utilizar una implementación de Python más rápida, como PyPy. PyPy es, actualmente, compatible con Python 3.6 y una de sus desventajas es, precisamente, que suele ir una versión por detrás del intérprete oficial y que no todo el software compatible con CPython, lo es también con PyPy.

No obstante, si puedes permitirte ir una versión por detrás y resulta que no utilizas nada incompatible con el intérprete, la ganancia vale la pena, aunque es similar a la de Numba.

  1. Abre una consola y usa pyenv para instalar la última versión de PyPy:

    $ pyenv install pypy3.6-7.1.0

  2. Restaura la versión mono-hilo del comprobador de primos:

    from datetime import datetime
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    start = datetime.now()
    for number, prime in zip(PRIMES, map(is_prime, PRIMES)):
        print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

  3. Lanza el script desde una terminal:

    $ python profiling.py

  4. Ahora instala y activa la última versión de pypy con pyenv:

    $ pyenv install pypy3.6-7.1.0
$ pyenv shell pypy3.6-7.1.0

  5. Lanza de nuevo el script, una vez activado pypy:

    $ python profiling.py

PyPy está escrito en RPython, una versión especial de Python que puede compilarse a código específico de la plataforma. Y lo que es más, todo una cadena de herramientas (toolchain) para la creación de intérpretes super-rápidos de lenguajes dinámicos.

Extensiones nativas

Como su propio nombre indica, CPython está escrito en C, y es compatible con más código C, siempre y cuando siga ciertos convenios. Las extensiones son módulos escritos en C y luego compilados, nombrados como modulo.so o modulo.pyd, en Windows. El sistema de importación de Python permite la carga de módulos .so/.pyd sin que tengamos que intervenir:

```python
import modulo
```

Una forma de escribir extensiones es en C directamente. Otra forma es usar Cython: un lenguaje transpilado, distinto de Python, que es además un superconjunto de Python. En particular, Cython permite la anotación de código Python con tipos de C.

Cython está disponible con Anaconda y también es instalable a través de pip:

$ pip install cython

  1. Crea una carpeta primes y dentro, dos ficheros: primality_test.py y primer.pyx (fíjate en la extensión .pyx del segundo módulo).

  2. En primality_test.py pon la parte del código mono-hilo que hace uso de la función is_prime:

    import pyximport
pyximport.install()

from profilingnative import is_prime

from datetime import datetime


PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]


def main():
    start = datetime.now()

    for number, prime in zip(PRIMES, map(is_prime, PRIMES)):
        print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

    Fíjate en las dos primeras líneas del fichero. El modulo pyximport permite cargar módulos .pyx. La utilidad compila el módulo en tiempo de importación y luego lo importa como una extensión nativa de Python.

  3. En el módulo primes.pyx deja el código mono-hilo de la implementación:

    import math

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

  4. Ejecuta el módulo primality_test.py desde una terminal (asegúrate de que se trata del intérprete de referencia):

    $ python primality_test.py

  5. Transforma ahora el código de primer.pyx, enriqueciéndolo con anotaciones en Cython:

    import math

def is_prime(long int n):
    if n % 2 == 0:
        return False

    cdef long int sqrt_n = math.floor(math.sqrt(n))
    cdef long int i
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

    Lo único que has hecho es anotar los tipos de las variables que intervienen en el algoritmo sqrt_n, i y n. Para anotar las variables se utiliza la palabra clave cdef (de "C definition") y los mismos tipos que se usarían en C.

En situaciones del mundo real, no todo es tan sencillo. El tipado de los distintos objetos es una habilidad en sí misma y conviene estar muy familiarizacon con el sistema de tipos de Cython.

Para el manejo de listas, es conveniente usar el módulo array, que proporciona, de manera nativa, una implementación compacta de listas homogéneas, a lo ndarray de NumPy, aunque menos sofisticada. De hecho, también es perfectamente posible y recomendable utilizar los ndarray de NumPy.

Compilando la extensión

El compilador de Cython traduce a C. Se debe usar un compilador de C para generar la extensión.

  1. En la carpeta primer, crea un fichero setup.py y en su interior escribe:

    from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules = cythonize("primes.pyx")
)

  2. Ahora, desde una terminal, ejecuta:

    $ python setup.py build_ext --inplace

    El resultado de la ejecución es el fichero primes.c con el código traducido y un fichero primes.<plataforma>.so. Este es el fichero que cargará Python.

  3. Modifica primality_test.py y elimina las dos primeras líneas, que quede:

    from profilingnative import is_prime

from datetime import datetime


PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419]


def main():
    start = datetime.now()

    for number, prime in zip(PRIMES, map(is_prime, PRIMES)):
        print('%d is prime: %s' % (number, prime))

    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

  4. Ejecuta el programa desde la terminal:

    $ python primality_test.py

Multiplicación de matrices

Crea ahora una nueva carpeta matrix y añade a un archivo mul_matrices.py el siguiente código para la multiplicación de matrices (asume que las matrices son cuadradas):

from datetime import datetime

def mul(a, b):
    size = len(a)
    result = [[0 for _ in range(size)] for _ in range(size)]
    for a_row_index, row in enumerate(a):
        for b_col_index in range(size):
            col = (b[r][b_col_index] for r in range(size))
            item = sum(va * vb for va, vb in zip(row, col))
            result[a_row_index][b_col_index] = item

    return result


def main():
    SIZE = 200
    a = [[i for i in range(SIZE)] for _ in range(SIZE)]
    b = [[i for i in range(SIZE)] for _ in range(SIZE)]
    start = datetime.now()
    print(mul(a, b))
    print('Elapsed time:', datetime.now() - start)

if __name__ == '__main__':
    main()

Utiliza las distintas técnicas que has aprendido para mejorar el tiempo de la función. Como estrategia general, trata de seguir este plan:

Primero prueba la opción más sencilla: cambia a PyPy y mira cómo se comporta el código sin cambiar nada. Apunta los tiempos típicos de cada optimización que pruebes.

Ahora vuelve a CPython y prueba a simplificar el código. Trata de eliminar cuantas más abstracciones puedas, mejor. Esto quiere decir que elimines los generadores, más allá del range(x) (aunque si puedes eliminar este, hazlo también). Toma nota del tiempo típico.

Seguidamente, prueba a utilizar Numba. Es posible que tengas problemas al tratar de usar listas de listas. Si es tu caso, prueba a usar el decorador njit en combinación con los ndarray de NumPy.

Finalmente, prueba la opción de la extensión nativa. Mueve el código de mul() a un módulo .pyx e impórtalo desde el fichero principal. No te olvides de importar pyximport y llamar a su método install().

Comienza tipando los índices con los que recorres las listas para ver si hay cambios. Cuando se te acaben los índices, pasa a las listas, que habrás de cambiar por ndarray de NumPy. Los ndarrays se tipan con la sintáxis cdef int[:, :], para un array de enteros de 2 dimensiones o cdef int[:], para un array de enteros unidimensional.

¡Suerte!