## Les performances en Python par <!-- .slide: data-background="static/background.jpg" --> Julien Palard <julien@palard.fr> https://mdk.fr

## Bien choisir sa structure de donnée C'est bien choisir l'algorihtme qu'on va utiliser.

## Comparaison asymptotique Les notations les plus utilisées : ```text O(1) Constant O(log n) Logarithmique O(n) Linéaire O(n log n) « Linéarithmique » O(n²) Quadratique O(2ⁿ) Exponentielle O(n!) Factorielle ``` notes: Il faut les grapher pour s'en rendre compte : cf. examples/big.o.py

## Comparaison asymptotique Exemples.

## O(1) ```python def get_item(a_list: list, an_idx): return a_list[an_idx] ``` ou ```python def is_in(a_set: set, a_value): return a_value in a_set ``` notes: Peu importe la taille de la liste, accéder à un élément prend le même temps.

## O(log n) Attention c'est toujours en base deux. Exemple typique : chercher dans un annuaire. notes: Un annuaire deux fois plus gros ne vous demandera pas deux fois plus de temps mais peut-être une opération de plus.

## O(log n) ```python def index(a_list, a_value): """Locate the leftmost value exactly equal to a_value.""" begin, end = 0, len(a_list) while begin < end: # Search in a_list[begin:end] middle = (end + begin) // 2 if a_value > a_list[middle]: begin = middle + 1 else: end = middle if (a_list and begin != len(a_list) and a_list[begin] == a_value): return begin raise ValueError ```

## O(n) ```python def dumb_index(a_list, a_value): """Locate the leftmost value exactly equal to a_value.""" for i, value in enumerate(a_list): if value == a_value: return i raise ValueError ```

## O(n log n) C'est `n` fois un `log n`, par exemple rayer `n` personnes dans un annuaire. Typique d'algorithmes de tris.

## Les mesures de complexité - De temps (CPU consommé). - D'espace (mémoire consommée). - Dans le meilleur des cas. - Dans le pire des cas. - Dans le cas moyen. - Amorti. - ...

## Les mesures de complexité Il n'est pas forcément nécessaire d'apprendre par cœur toutes les complexités de chaque opération. Pas toute suite.

## Les bases Mais comprendre la complexité de quelques structures élémentaires permet d'éviter les « erreurs de débutants ».

## Rappel des unités de temps - 1 milliseconde (1 ms) c'est un millième de seconde. - 1 microseconde (1 μs) c'est un millionième de seconde. - 1 nanoseconde (1 ns) c'est un milliardième de seconde.

## Rappel des unités de temps - milli c'est `10 ** -3`, c'est `0.001`. - micro c'est `10 ** -6`, c'est `0.000_001`. - nano c'est `10 ** -9`, c'est `0.000_000_001`.

## Le cas typique ```shell $ python -m pyperf timeit --setup \ > 'container = list(range(10_000_000))' \ > '10_000_001 in container' Mean +- std dev: 56.6 ms +- 3.0 ms $ python -m pyperf timeit --setup \ > 'container = set(range(10_000_000))' \ > '10_000_001 in container' Mean +- std dev: 11.9 ns +- 0.5 ns ``` Pourquoi une si grande différence !? notes: C'est l'heure du live coding !

## À vous ! Simulez un tas de sable, moi je joue avec la conjecture de Syracuse. Ne vous souciez pas des perfs, on s'en occupera. notes: Leur laisser ~15mn. voir: https://git.afpy.org/mdk/fast-abelian-sandpile/

## Simulateur de tas de sable Rédigez une fonction nommée `apply_gravity`, acceptant un `array numpy` à deux dimensions : - chaque valeur de l’array est un entier représentant le nombre de grains de sables empilés verticalement à cet endroit. - une colonne de 4 grains de sable ou plus s’effondre sous l’effet de la gravité : un grain part au nord, un autre au sud, un à l’est, et un à l’ouest.

## Exemple ```python >>> import numpy as np >>> area = np.zeros((5, 5), dtype=np.uint32) >>> area[2, 2] = 16 # Une colonne de 16 grains au milieu >>> apply_gravity(area) >>> print(area) # La colonne de 16 grains s’est effondrée [[0 0 1 0 0] [0 2 1 2 0] [1 1 0 1 1] [0 2 1 2 0] [0 0 1 0 0]] ```

## Les outils notes: Je mesure mes perfs, puis ils mesurent leurs perfs.

## `pyperf command` ```shell $ pyperf command python collatz.py 100 ..................... command: Mean +- std dev: 8.88 ms +- 0.21 ms $ pyperf command python collatz.py 200 ..................... command: Mean +- std dev: 27.0 ms +- 1.1 ms $ pyperf command python collatz.py 300 ..................... command: Mean +- std dev: 294 ms +- 11 ms ```

## Petite parenthèse Mais attention, démarrer un processus Python n'est pas gratuit : ```shell $ pyperf command python -c pass ..................... command: Mean +- std dev: 8.48 ms +- 0.30 ms ``` notes: N'essayez pas de retenir les chiffres, retenez les faits.

## Petite parenthèse Et puis il peut dépendre de la version de Python, des options de compilation, ... : ```shell $ pyperf command ~/.local/bin/python3.10 -c pass ..................... command: Mean +- std dev: 37.6 ms +- 0.6 ms $ pyperf command /usr/bin/python3.10 -c pass ..................... command: Mean +- std dev: 14.4 ms +- 0.4 ms ``` notes: Leur parler de `--enable-optimizations` (PGO).

## `pyperf timeit` Il existe aussi `timeit` dans la stdlib, mais je préfère `pyperf timeit` : ```shell $ pyperf timeit --setup \ > 'from collatz import next_flight' \ > 'next_flight(200)' Mean +- std dev: 20.4 ms +- 0.5 ms $ pyperf timeit --setup \ > 'from collatz import next_flight' \ > 'next_flight(300)' Mean +- std dev: 310 ms +- 6 ms ```

## Les outils — À vous ! Effectuez quelques mesures sur votre implémentation. Tentez d'en déterminer la complexité en fonction du nombre de grains. Explorez les limites de vos implémentations.

## Profilage `pyperf` c'est bien pour mesurer, comparer. Le profilage peut nous aider à trouver la fonction coupable.

## cProfile, exemple ```python import sys from itertools import count def collatz(n): if n % 2 == 0: return n // 2 else: return n * 3 + 1 def flight_duration(n): if n == 1: return 0 return 1 + flight_duration(collatz(n)) def next_flight(duration): for i in count(1): if flight_duration(i) > duration: return i def main(): n = next_flight(int(sys.argv[1])) print(f"Found a flight of {flight_duration(n)} starting at {n}.") if __name__ == '__main__': main() ```

## cProfile, exemple Sortons cProfile : ```shell $ python -m cProfile --sort cumulative collatz.py 300 > 300 Found a flight of 307 starting at 26623. 5055546 function calls (2541088 primitive calls) in 0.978 seconds Ordered by: cumulative time ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.978 0.978 {built-in method builtins.exec} 1 0.000 0.000 0.978 0.978 collatz.py:1(<module>) 1 0.000 0.000 0.978 0.978 collatz.py:24(main) 1 0.005 0.005 0.978 0.978 collatz.py:18(next_flight) 2541082/26624 0.756 0.000 0.974 0.000 collatz.py:12(flight_duration) 2514458 0.217 0.000 0.217 0.000 collatz.py:5(collatz) 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} ```

## cProfile, exemple Cachons les résultats de `flight_duration` : ```python @cache def flight_duration(n): if n == 1: return 0 return 1 + flight_duration(collatz(n)) ```

## cProfile, exemple On mesure toujours : ```shell $ pyperf timeit --setup \ > 'from collatz import next_flight' \ > 'next_flight(300)' Mean +- std dev: 310 ms +- 6 ms $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms ```

## cProfile, exemple Et on repasse dans cProfile voir ce qu'on peut améliorer : ```shell $ python -m cProfile --sort cumulative \ > collatz_cache.py 300 Found a flight of 307 starting at 26623. 115092 function calls (69079 primitive calls) in 0.036 seconds Ordered by: cumulative time ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.036 0.036 {built-in method builtins.exec} 1 0.000 0.000 0.036 0.036 <module> 1 0.000 0.000 0.036 0.036 main 1 0.007 0.007 0.036 0.036 next_flight 57534/11521 0.022 0.000 0.029 0.000 flight_duration 57533 0.007 0.000 0.007 0.000 collatz 1 0.000 0.000 0.000 0.000 functools.py:651(cache) 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 functools.py:518(decorating_function) 1 0.000 0.000 0.000 0.000 functools.py:35(update_wrapper) 1 0.000 0.000 0.000 0.000 functools.py:479(lru_cache) 7 0.000 0.000 0.000 0.000 {built-in method builtins.getattr} 5 0.000 0.000 0.000 0.000 {built-in method builtins.setattr} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 1 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance} 1 0.000 0.000 0.000 0.000 {method 'update' of 'dict' objects} 1 0.000 0.000 0.000 0.000 {built-in method builtins.callable} ```

## Snakeviz ```shell $ python -m pip install snakeviz $ python -m cProfile -o collatz.prof collatz_cache.py 300 $ python -m snakeviz collatz.prof ```

## Snakeviz 

## Scalene ```shell $ python -m pip install scalene $ scalene collatz_cache.py 400 ```

## Scalene 

## line_profiler ```shell $ python -m pip install line_profiler $ python -m kernprof --view --prof-mod \ > collatz_cache.py --line-by-line \ > collatz_cache.py 300 Found a flight of 307 starting at 26623. Wrote profile results to collatz_cache.py.lprof Timer unit: 1e-06 s Total time: 0.0157484 s File: examples/collatz_cache.py Function: collatz at line 6 Line # Hits Time Per Hit % Time Line Contents ============================================================== 6 def collatz(n): 7 57533 7147.1 0.1 45.4 if n % 2 == 0: 8 36476 4459.1 0.1 28.3 return n // 2 9 else: 10 21057 4142.1 0.2 26.3 return n * 3 + 1 Total time: 0.142476 s File: examples/collatz_cache.py Function: flight_duration at line 13 Line # Hits Time Per Hit % Time Line Contents ============================================================== 13 @cache 14 def flight_duration(n): 15 57534 6066.5 0.1 4.3 if n == 1: 16 1 0.1 0.1 0.0 return 0 17 57533 136409.4 2.4 95.7 return 1 + flight_duration(collatz(n)) Total time: 0.214208 s File: examples/collatz_cache.py Function: next_flight at line 20 Line # Hits Time Per Hit % Time Line Contents ============================================================== 20 def next_flight(duration): 21 26623 3011.2 0.1 1.4 for i in count(1): 22 26623 211195.8 7.9 98.6 if flight_duration(i) > duration: 23 1 0.9 0.9 0.0 return i Total time: 0.219884 s File: examples/collatz_cache.py Function: main at line 25 Line # Hits Time Per Hit % Time Line Contents ============================================================== 25 def main(): 26 1 219859.8 219859.8 100.0 n = next_flight(int(sys.argv[1])) 27 1 23.9 23.9 0.0 print(f"Found a flight of {flight_duration(n)} starting at {n}.") ```

## py-spy ```shell $ pip install py-spy py-spy> Sampling process 100 times a second. Press Control-C to exit. Found a flight of 307 starting at 26623. py-spy> Stopped sampling because process exited py-spy> Wrote flamegraph data to 'output/py-spy.svg'. Samples: 2 Errors: 0 ```

## py-spy 

## Aussi - https://github.com/gaogaotiantian/viztracer - https://github.com/joerick/pyinstrument - https://github.com/benfred/py-spy - https://github.com/sumerc/yappi - https://github.com/vmprof/vmprof-python - https://github.com/bloomberg/memray - https://github.com/pythonprofilers/memory_profiler

## Profilage — À vous ! Profilez votre implémentation et tentez quelques améliorations.

## Cython Cython est un dialecte de Python transpilable en C.

## Cython démo Sans modifier le code : ```bash $ pip install cython $ cythonize --inplace -3 examples/collatz_cython.py ```

## Cython démo ``` $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup 'from collatz_cython \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 7.45 ms +- 0.27 ms ```

## Cython démo En annotant le fichier on permet à cython d'utiliser des types natifs. Et ainsi réduire les aller-retour coûteux entre le C et Python.

## Cython annotate ```shell $ cython -3 --annotate collatz_annotated.py ``` 

## Cython démo En annotant le code : ```bash $ cythonize --inplace examples/collatz_annotated.py ```

## Cython démo ``` $ pyperf timeit --setup 'from collatz_cython \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 7.45 ms +- 0.27 ms $ pyperf timeit --setup 'from collatz_annota \ > ted import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 6.71 ms +- 0.21 ms ```

## Cython — À vous !

## Numba Numba est un `JIT` : « Just In Time compiler ». ```python from itertools import count from numba import njit @njit def flight_duration(n): if n == 1: return 0 if n % 2 == 0: return 1 + flight_duration(n // 2) else: return 1 + flight_duration(n * 3 + 1) def next_flight(duration): for i in count(1): if flight_duration(i) > duration: return i ```

## Numba démo ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup \ > 'from collatz_numba import next_flight' \ > 'next_flight(300)' Mean +- std dev: 12.2 ms +- 0.4 ms ```

## numba — À vous !

## pypy pypy est un interpréteur Python écrit en Python. ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ .venvpypy/bin/pypy3 -m pyperf timeit --setup 'from \ > collatz_cache import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 6.34 ms +- 0.68 ms ```

## mypyc mypyc est un compilateur qui s'appuie sur les annotationes de type mypy : ```python import sys from functools import cache from itertools import count def collatz(n: int) -> int: if n % 2 == 0: return n // 2 else: return n * 3 + 1 @cache def flight_duration(n: int) -> int: if n == 1: return 0 return 1 + flight_duration(collatz(n)) def next_flight(duration: int) -> int: for i in count(1): if flight_duration(i) > duration: return i return -1 ```

## mypyc demo ```shell $ pip install mypy $ mypyc collatz_mypy.py running build_ext Disabling color, you really want to install colorlog. copying build/lib.linux-x86_64-cpython-311/collatz_mypy.cpython-311-x86_64-linux-gnu.so -> ```

## mypyc demo ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup 'from collatz_mypy i \ > mport next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 7.95 ms +- 0.50 ms ```

## mypyc — À vous !

## Pythran pythran est un compilateur pour du code scientifique : ```python from itertools import count #pythran export capsule collatz(uint64) def collatz(n): if n % 2 == 0: return n // 2 else: return n * 3 + 1 #pythran export capsule flight_duration(uint64, uint64:uint64 dict) def flight_duration(n, cache): if n in cache: return cache[n] result = 1 + flight_duration(collatz(n), cache) cache[n] = result return result #pythran export next_flight(uint64) def next_flight(duration): cache = {1: 0} for i in count(1): new_duration = flight_duration(i, cache) if new_duration > duration: return i ```

## Pythran demo ```shell $ pip install pythran $ pythran examples/collatz_pythran.py ```

## Pythran demo ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup \ > 'from collatz_pythran import next_flight' \ > 'next_flight(300)' Mean +- std dev: 2.86 ms +- 0.10 ms ```

## pythran — À vous !

## Nuitka Aussi un compilateur, aussi utilisable pour distribuer une application. ```shell $ pip install nuitka $ python -m nuitka --module collatz_nuitka.py ``` ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup 'from collatz_nuitka \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 8.62 ms +- 0.39 ms ```

## Voir aussi - JAX

## Hand crafted C ```c // Compile with: // cc -c -fPIC my_collatz.c -o libcollatz.so #include <string.h> static long collatz(long n) { if (n % 2 == 0) return n / 2; else return n * 3 + 1; } #define CACHE_SIZE 1024 static long cache[CACHE_SIZE]; void clear_cache(void) { memset(cache, 0, CACHE_SIZE * sizeof(long)); } static long flight_duration(long n) { long result; if (n == 1) return 0; if (n < 1024 && cache[n] != 0) return cache[n]; result = 1 + flight_duration(collatz(n)); if (n < 1024) cache[n] = result; return result; } long next_flight(long duration) { long new_duration; for (long i = 1; ; ++i) { new_duration = flight_duration(i); if (new_duration > duration) return i; } } ``` Mais comment l'utiliser ?

## Avec Cython ```cpython cdef extern from "collatz.c": cpdef long next_flight(long n) cpdef void clear_cache() ```

## Avec Cython ```shell $ cythonize -i examples/collatz_cython_to_c.pyx ```

## Avec Cython ```shell $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup \ > 'from collatz_cython_to_c import next_flight' \ > 'next_flight(300)' Mean +- std dev: 1.25 ms +- 0.04 ms ```

## Hand crafted rust ```rust // rustimport:pyo3 use std::sync::Mutex; use pyo3::prelude::*; fn collatz(n: u64) -> u64 { if n % 2 == 0 { n / 2 } else { n * 3 + 1 } } fn flight_duration(n: u64) -> u64 { static cache: Mutex<[u64;1024]> = Mutex::new([0; 1024]); if n == 1 { return 0; } if n < 1024 && cache.lock().unwrap()[n as usize] != 0 { return cache.lock().unwrap()[n as usize]; } let result = 1 + flight_duration(collatz(n)); if n < 1024 { cache.lock().unwrap()[n as usize] = result; } result } #[pyfunction] fn next_flight(duration: u64) -> u64 { let mut new_duration: u64; let mut i = 1; loop { new_duration = flight_duration(i); if new_duration > duration { return i; } i += 1; } } ```

## with rustimport ```bash $ pip install rustimport ```

## with rustimport ```bash $ pyperf timeit --setup 'from collatz_cache \ > import next_flight, flight_duration' \ > 'flight_duration.cache_clear(); next_flight(300)' Mean +- std dev: 12.0 ms +- 0.4 ms $ pyperf timeit --setup 'import rustimport.import_hoo \ > k; import rustimport.settings; rustimport.settings.compile_ \ > release_binaries = True; from collatz_rs import ne \ > xt_flight' 'next_flight(300)' Mean +- std dev: 1.02 ms +- 0.03 ms ```