12 KiB
Les performances en Python
par
Julien Palard julien@palard.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 :
O(1) Constant
O(log n) Logarithmique
O(n) Linéaire
O(n log n) Parfois appelée « linéarithmique »
O(n²) Quadratique
O(nᶜ) Polynomiale
O(cⁿ) Exponentielle
O(n!) Factorielle
notes:
Il faut les grapher pour s'en rendre compte : cf. examples/big.o.py
Comparaison asymptotique
Exemples.
O(1)
def get_item(a_list: list, an_idx):
return a_list[an_idx]
ou
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)
#!sed -n '/def index/,/raise ValueError/p' examples/find_in_list.py
O(n)
#!sed -n '/def dumb_index/,/raise ValueError/p' examples/find_in_list.py
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 retenir par cœur 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'est0.001
. - micro c'est
10 ** -6
, c'est0.000_001
. - nano c'est
10 ** -9
, c'est0.000_000_001
.
Le cas typique
#!cache python -m pyperf timeit --setup 'container = list(range(10_000_000))' '10_000_001 in container'
#!cache python -m pyperf timeit --setup 'container = set(range(10_000_000))' '10_000_001 in container'
Pourquoi une si grande différence !?
notes:
C'est l'heure du live coding !
À vous !
Simulez un tas de sable, moi je calcule le nombre l'or.
Ne vous souciez pas des perfs, on s'en occupera.
notes:
Leur laisser ~15mn.
voir sandpile.py
Les outils
notes:
Je mesure mes perfs, puis ils mesurent leurs perfs.
pyperf command
#!cache pyperf command python examples/phi1.py 3
#!cache pyperf command python examples/phi1.py 6
#!cache pyperf command python examples/phi1.py 9
Petite parenthèse
Mais attention, démarrer un processus Python n'est pas gratuit :
#!cache pyperf command python -c pass
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, ... :
$ 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
:
#!cache pyperf timeit --setup 'from examples.phi1 import approx_phi_up_to' 'approx_phi_up_to(3)'
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
#!sed -n '/def fib/,/return approx/p' examples/phi1.py
cProfile, exemple
Sortons cProfile :
$ python -m cProfile --sort cumulative phi1.py 10
...
#!cache python -m cProfile --sort cumulative examples/phi1.py 10 | sed -n '/fib\|function calls/{s/ \+/ /g;s/^ *//;p}'
...
C'est donc fib
la coupable :
- C'est ~100% du temps (
cumtime
). - C'est ~100% des appels de fonctions.
cProfile, exemple
Cachons les résultats de fib
:
#!sed -n '/import cache/,/return fib/p' examples/phi2.py
cProfile, exemple
Et on repasse dans cProfile !
$ python -m cProfile --sort cumulative phi2.py 10
...
#!cache python -m cProfile --sort cumulative examples/phi2.py 10 | sed -n '/fib\|function calls/{s/ \+/ /g;s/^ *//;p}'
...
C'est mieux !
cProfile, exemple
On essaye d'aller plus loin ?
#!cache python -m cProfile --sort cumulative examples/phi2.py 2000 | head -n 3 | sed 's/^ *//g;s/seconds/s/g'
Ça tient, mais peut-on faire mieux ?
cProfile, exemple
Divisons par 10 le nombre d'appels, on réduira mécaniquement par 10 le temps d'exécution ?
#!sed -n '/def approx_phi_up_to/,/return step1/p' examples/phi3.py
cProfile, exemple
#!cache python -m cProfile --sort cumulative examples/phi3.py 2000 | head -n 3 | sed 's/^ *//g;s/seconds/s/g'
cProfile, exemple
En cachant approx_phi
?
#!sed -n '10,/return step1/p' examples/phi4.py
notes:
Notez l'astuce pour que le step2
d'un
tour soit le step1
du suivant...
cProfile, exemple
$ python -m cProfile --sort cumulative examples/phi4.py 2000
RecursionError
!? En effet, en avançant par si grands pas, le cache
de fib
n'est pas chaud, et il peut vite devoir descendre
profondément en récursion...
cProfile, exemple
Il est temps de sortir une implémentation de fib
plus robuste, basée
sur l'algorithme « matrix exponentiation » :
#!sed -n '/def fib/,/return fib/p' examples/phi5.py
cProfile, exemple
#!cache python -m cProfile --sort cumulative examples/phi5.py 2000 | head -n 3 | sed 's/^ *//g;s/seconds/s/g'
notes:
Mieux.
Snakeviz
$ python -m pip install snakeviz
$ python -m cProfile -o phi5.prof phi5.py 2000
$ python -m snakeviz phi5.prof
#!if [ ! -f .cache/phi5.prof ]; then python -m cProfile -o .cache/phi5.prof examples/phi5.py 2000 >/dev/null 2>&1; fi #!if [ ! -f output/phi5-snakeviz.png ]; then python -m snakeviz -s .cache/phi5.prof & TOKILL=$!; sleep 1; cutycapt --min-width=1024 --delay=500 --url=file://$(pwd)/.cache/phi5.prof --out=output/phi5-snakeviz.png ; kill $TOKILL; fi
Snakeviz
Scalene
$ python -m pip install scalene
$ scalene phi5.py 100000
#!if [ ! -f output/phi5.html ]; then ( cd examples; scalene phi5.py 100000 --html --outfile ../output/phi5.html --cli >&2 ); fi #!if [ ! -f output/phi5-scalene.png ]; then cutycapt --min-width=1024 --delay=100 --url=file://$(pwd)/output/phi5.html --out=output/phi5-scalene.png; fi
Scalene
line_profiler
$ python -m pip install line_profiler
#!cache python -m kernprof --view --prof-mod examples/phi5.py --line-by-line examples/phi5.py 100000
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 :
$ pip install cython
$ cythonize --inplace examples/phi5cython.py
#!cythonize --inplace examples/phi5cython.py
Cython démo
#!cache pyperf timeit --setup 'from examples.phi5 import approx_phi_up_to' 'approx_phi_up_to(100_000)'
#!cache pyperf timeit --setup 'from examples.phi5cython import approx_phi_up_to' 'approx_phi_up_to(100_000)'
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
#!cache cython --annotate examples/phi5cython.py
#!if ! [ -f output/phi5cython.png ] ; then cutycapt --min-width=1024 --delay=500 --url=file://$(pwd)/examples/phi5cython.html --out=output/phi5cython.png; fi
Cython — À vous !
Numba
Numba est un JIT
: « Just In Time compiler ».
#!
#!cat examples/collatz_length_numba.py
Numba démo
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'from examples.collatz_length_numba import collatz_length' 'collatz_length(837799)'
numba — À vous !
pypy
pypy est un interpréteur Python écrit en Python.
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pypy3 -m pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
mypyc
mypyc est un compilateur qui s'appuie sur les annotationes de type mypy :
#!cat examples/collatz_length_mypy.py
mypyc demo
$ pip install mypy
#!cd examples; mypyc collatz_length_mypy.py
$ mypyc collatz_length_mypy.py
mypyc demo
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'from examples.collatz_length_mypy import collatz_length' 'collatz_length(837799)' 2>/dev/null
mypyc — À vous !
Pythran
pythran est un compilateur pour du code scientifique :
#!cat examples/collatz_length_pythran.py
Pythran demo
$ pip install pythran
$ pythran examples/collatz_length_pythran.py
#!if ! [ -f examples/collatz_length_pythran.*.so ]; then cd examples; pythran collatz_length_pythran.py; fi
Pythran demo
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'from examples.collatz_length_pythran import collatz_length' 'collatz_length(837799)'
pythran — À vous !
Nuitka
Aussi un compilateur, aussi utilisable pour distribuer une application.
$ pip install nuitka
$ python -m nuitka --module collatz_length_nuitka.py
#!if ! [ -f examples/collatz_length_nuitka.*.so ]; then (cd examples/; python -m nuitka --module collatz_length_nuitka.py >/dev/null); fi
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'from examples.collatz_length_nuitka import collatz_length' 'collatz_length(837799)'
Hand crafted C
#!sed -n '/int collatz_length/,$p' examples/my_collatz_length.c
Mais comment l'utiliser ?
Avec Cython
#!cat examples/collatz_length_cython_to_c.pyx
$ cythonize -i examples/collatz_length_cython_to_c.pyx
#!if ! [ -f examples/collatz_length_cython_to_c.*.so ] ; then cythonize -i examples/collatz_length_cython_to_c.pyx; fi
Avec Cython
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'from examples.collatz_length_cython_to_c import collatz_length' 'collatz_length(837799)'
Hand crafted rust
#!sed -n '/pyfunction/,$p' examples/collatz_length_rs.rs
with rustimport
$ pip install rustimport
with rustimport
#!cache pyperf timeit --setup 'from examples.collatz_length import collatz_length' 'collatz_length(837799)'
#!cache pyperf timeit --setup 'import rustimport.import_hook; import rustimport.settings; rustimport.settings.compile_release_binaries = True; from examples.collatz_length_rs import collatz_length' 'collatz_length(837799)'