logo le blog invivoo blanc

À la vitesse du Python

20 février 2018 | Python

1 – Contexte

Python est un langage compilé en bytecode dont le bytecode sera ensuite interprété. Si l’interpréteur est très efficace et que la plupart des bibliothèques sont écrites en C, il n’en reste pas moins que beaucoup d’opérations peuvent être plus lentes que si elles avaient compilé comme le C. Voici un petit benchmark qui met en concurrence différents langages avec comme référence le C.

On constate que Python peut être jusqu’à 100 fois plus lent que le C. De bons choix techniques et l’utilisation d’outils comme le profileur sont susceptibles d’éviter les écueils de performance…

Ne perdons cependant pas de vue que la majorité des contre-performances sont souvent dues à de mauvais choix algorithmiques ou à des conteneurs inadaptés aux besoins… Bien réfléchir à son besoin, à la volumétrie actuelle ou à venir peut fortement diriger le développeur vers des choix techniques et algorithmiques différents.

2 – Estimer les performances

La première chose à savoir est comment estimer le temps passé dans un traitement. Je vais vous proposer 3 méthodes différentes.

2.1 – La méthode « Old School »

Cette méthode était déjà utilisée en 1972 par Brian Kernighan : on utilise une horloge… Employée dans de nombreux langages cette méthode a des limites notamment dans des applications multi-threadées. Mais elle reste simple à mettre en œuvre. En voici un exemple :

« sample1.csv » est un fichier CSV de 39Mb et le temps constaté est de 1.33s sur mon PC. Cela permet de constater que l’appel de read_csv prend un certain temps mais ne permet pas de savoir quelle ligne à l’intérieur de la fonction est la plus coûteuse. Cela donne une estimation mais insuffisante pour optimiser le code.

2.2 – timeit

timeit est un module qui permet de mesurer le temps à évaluer un nombre défini d’appels à un code contenu dans une chaîne de caractères. Cela permet de mesurer même pour des portions très rapide en agissant sur la valeur de ‘number’. Voici un exemple d’utilisation :

On peut aussi l’utiliser depuis la ligne de commande de python :

python3 -m timeit '"-".join(str(n) for n in range(100))'

2.3 – Profiling

Pour mesurer les performances plus finement, l’outil adéquat est le profileur de code. On peut le lancer en ligne de commande via la ligne suivante :

python -m cProfile [-o output_file] [-s sort_order] myscript.py

 

Le rapport fournit présente plusieurs champs intéressants :

  • ncalls : le nombre d’appels de la fonction
  • tottime : founit le temps total en secondes passé dans la fonction en excluant les sous-fonctions
  • percall : est égal à tottime/ncalls
  • cumtime : est le temps passé dans la fonction et les sous-fonctions
  • filename :lineno(function) : donne l’information sur la fonction testée ainsi que sa position (fichier + numéro de ligne)

Reprenons l’exemple « Old School » et testons la commande et voyons ce que nous retourne la commande sans les options ‘-o’ et ‘-s’ :

Voir le résultat
consumed time = 1.443044 s

3010586 function calls (3010575 primitive calls) in 1.445 seconds
Ordered by: standard name
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:103(release)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:143(__init__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:147(__enter__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:151(__exit__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:176(cb)
5/1    0.000    0.000    0.001    0.001 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
23    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:222(_verbose_message)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:232(_requires_builtin_wrapper)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:307(__init__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:311(__enter__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:318(__exit__)
12    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:321(<genexpr>)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:35(_new_module)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:369(__init__)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:403(cached)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:416(parent)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:424(has_location)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:433(spec_from_loader)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:504(_init_module_attrs)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:564(module_from_spec)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:58(__init__)
3/1    0.000    0.000    0.001    0.001 <frozen importlib._bootstrap>:651(_load_unlocked)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:707(find_spec)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:728(create_module)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:736(exec_module)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:753(is_package)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:78(acquire)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:780(find_spec)
5    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:843(__enter__)
5    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:847(__exit__)
3    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:870(_find_spec)
3/1    0.000    0.000    0.001    0.001 <frozen importlib._bootstrap>:936(_find_and_load_unlocked)
3/1    0.000    0.000    0.001    0.001 <frozen importlib._bootstrap>:966(_find_and_load)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:997(_handle_fromlist)
5    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:1080(_path_importer_cache)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:1117(_get_spec)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:1149(find_spec)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:1228(_get_spec)
4    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:1233(find_spec)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:263(cache_from_source)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:361(_get_cached)
4    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:37(_relax_case)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:393(_check_name_wrapper)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:430(_validate_bytecode_header)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:485(_compile_bytecode)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:52(_r_long)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:524(spec_from_file_location)
20    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:57(_path_join)
20    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:59(<listcomp>)
2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:63(_path_split)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:669(create_module)
1    0.000    0.000    0.001    0.001 <frozen importlib._bootstrap_external>:672(exec_module)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:743(get_code)
6    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:75(_path_stat)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:800(__init__)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:825(get_filename)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:830(get_data)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:840(path_stats)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:85(_path_is_mode_type)
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap_external>:94(_path_isfile)
1    0.000    0.000    0.000    0.000 _bootlocale.py:11(getpreferredencoding)
1    0.000    0.000    0.000    0.000 codecs.py:259(__init__)
1    0.535    0.535    1.444    1.444 consumed_time_clock.py:11(read_csv)
1    0.000    0.000    1.445    1.445 consumed_time_clock.py:6(<module>)
6    0.000    0.000    0.000    0.000 cp1252.py:18(encode)
4879    0.003    0.000    0.065    0.000 cp1252.py:22(decode)
1    0.000    0.000    0.000    0.000 datetime.py:1023(time)
2    0.000    0.000    0.000    0.000 datetime.py:1048(__new__)
1    0.000    0.000    0.000    0.000 datetime.py:1360(datetime)
3    0.000    0.000    0.000    0.000 datetime.py:1368(__new__)
1    0.000    0.000    0.000    0.000 datetime.py:1949(timezone)
3    0.000    0.000    0.000    0.000 datetime.py:1972(_create)
35    0.000    0.000    0.000    0.000 datetime.py:261(_check_int_field)
5    0.000    0.000    0.000    0.000 datetime.py:278(_check_date_fields)
5    0.000    0.000    0.000    0.000 datetime.py:291(_check_time_fields)
5    0.000    0.000    0.000    0.000 datetime.py:308(_check_tzinfo_arg)
1    0.000    0.000    0.000    0.000 datetime.py:336(timedelta)
9    0.000    0.000    0.000    0.000 datetime.py:355(__new__)
3    0.000    0.000    0.000    0.000 datetime.py:40(_days_before_year)
5    0.000    0.000    0.000    0.000 datetime.py:45(_days_in_month)
1    0.000    0.000    0.001    0.001 datetime.py:5(<module>)
1    0.000    0.000    0.000    0.000 datetime.py:530(__neg__)
1    0.000    0.000    0.000    0.000 datetime.py:658(date)
2    0.000    0.000    0.000    0.000 datetime.py:688(__new__)
1    0.000    0.000    0.000    0.000 datetime.py:953(tzinfo)
19    0.000    0.000    0.000    0.000 {built-in method __new__ of type object at 0x0000000058B4B3F0}
4879    0.062    0.000    0.062    0.000 {built-in method _codecs.charmap_decode}
6    0.000    0.000    0.000    0.000 {built-in method _codecs.charmap_encode}
1    0.000    0.000    0.000    0.000 {built-in method _imp._fix_co_filename}
11    0.000    0.000    0.000    0.000 {built-in method _imp.acquire_lock}
2    0.000    0.000    0.000    0.000 {built-in method _imp.create_builtin}
2    0.000    0.000    0.000    0.000 {built-in method _imp.exec_builtin}
3    0.000    0.000    0.000    0.000 {built-in method _imp.is_builtin}
1    0.000    0.000    0.000    0.000 {built-in method _imp.is_frozen}
11    0.000    0.000    0.000    0.000 {built-in method _imp.release_lock}
1    0.000    0.000    0.000    0.000 {built-in method _locale._getdefaultlocale}
6    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
6    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
6    0.000    0.000    0.000    0.000 {built-in method builtins.__build_class__}
72    0.000    0.000    0.000    0.000 {built-in method builtins.abs}
3    0.000    0.000    0.000    0.000 {built-in method builtins.any}
45    0.000    0.000    0.000    0.000 {built-in method builtins.divmod}
2/1    0.000    0.000    1.445    1.445 {built-in method builtins.exec}
14    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}
16    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
164    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
4    0.000    0.000    0.000    0.000 {built-in method builtins.len}
1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
9    0.000    0.000    0.000    0.000 {built-in method builtins.round}
2    0.000    0.000    0.000    0.000 {built-in method from_bytes}
1    0.000    0.000    0.000    0.000 {built-in method io.open}
1    0.000    0.000    0.000    0.000 {built-in method marshal.loads}
2    0.000    0.000    0.000    0.000 {built-in method now}
3    0.000    0.000    0.000    0.000 {built-in method nt.fspath}
2    0.000    0.000    0.000    0.000 {built-in method nt.getcwd}
6    0.000    0.000    0.000    0.000 {built-in method nt.stat}
1000012    0.071    0.000    0.071    0.000 {method 'append' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
1    0.000    0.000    0.000    0.000 {method 'endswith' of 'str' objects}
6    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
22    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
1    0.000    0.000    0.000    0.000 {method 'read' of '_io.FileIO' objects}
12    0.000    0.000    0.000    0.000 {method 'rpartition' of 'str' objects}
2    0.000    0.000    0.000    0.000 {method 'rsplit' of 'str' objects}
1000042    0.072    0.000    0.072    0.000 {method 'rstrip' of 'str' objects}
1000000    0.701    0.000    0.701    0.000 {method 'split' of 'str' objects}
1    0.000    0.000    0.000    0.000 {method 'total_seconds' of 'datetime.timedelta' objects}

Il se trouve que Spyder fournit un outil interactif rendant la lecture du profileur plus simple : dont voici le résultat :

3 – Attention aux modules

Les modules Python sont une force de ce langage car c’est l’écosystème des modules qui fait la popularité du langage… Malheureusement un mauvais usage de ceux-ci peut engendrer des contre-performances. Nous allons tester différents usages afin de comprendre qu’est ce qui est efficace et qu’est ce qui ne l’est pas.

3.1 – L’import local

Partons de cet exemple : Nous allons utiliser le profileur intégré à Spyder pour mesurer les temps passés :   On constate qu’un appel à build consomme 6.95s et que 10000001 appels à f prennent 3.53s.

3.2 – L’import global

Modifions l’exemple précédent pour rendre global l’import de math :   En utilisant le profileur de Spyder, nous obtenons :   Nous gagnons 1.04s grâce à cette action : il est donc préférable d’importer les modules dans l’espace global dès lors que l’on doit appeler un grand nombre de fois la fonction…

3.3 – from math import cos

En utilisant « from math import cos » nous allons charger uniquement la fonction cos dans l’espace global, ce qui nous donnera le code suivant : Nous obtenons avec le profileur : Nous obtenons un gain faible (0.31s) mais non-négligeable quand répété à de nombreuses reprises.

3.4 – Conclusion

L’interpréteur Python est géré avec des dictionnaires. Il y a deux dictionnaires principaux retournés par les fonctions suivantes : globals() et locals(). globals() fournit le dictionnaire des définitions globales et locals() retourne le dictionnaire des définitions locales. Ils se présentent sous la forme (nom_de_la_définition, valeur_associée). Quand on exécute math.cos, l’interpréteur cherche dans le dictionnaire local la définition de math, s’il ne le trouve pas il va chercher dans le dictionnaire global. Une fois trouvé, math se présente sous la forme d’un dictionnaire qui contient la définition de la fonction cos (cosinus). Lorsque l’on fait « from math import cos » on importe dans l’espace global cos en faisant une seule recherche dans le dictionnaire math au lieu de le faire une fois par appel à math.cos.

4 – Boucles vs générateurs

Tentons d’améliorer la boucle (celle de la fonction build) de notre exemple pour améliorer les performances.

4.1 – Eliminez les points…

Comme expliquer dans la conclusion, tout est dictionnaire (même les objets Python sont des dictionnaires) et appeler result.append consiste en la liste des opérations suivantes :

  • chercher result dans le dictionnaire locals()
  • chercher append dans result
  • invoquer la fonction trouvée

On peut améliorer cela de la manière suivante : Nous donnant les performances suivantes :   9 centièmes de secondes semble un gain faible mais répéter à de nombreuses reprises cette amélioration peut engendrer des gains plus importants. Par contre, malheureusement, si la bloc interne de la boucle était important (trop de lignes), cette optimisation pourrait nuire à la lisibilité.

4.2 – Eliminer l’inutile

La déclaration « x=step*i » ne sert qu’à l’appel de f. Mais « x= » crée une entrée dans le dictionnaire local puis « f(x) » recherche x dans ce dictionnaire… Ce sont des opérations qui peuvent être éliminées : donnant les temps suivants :       Encore 0.03s de gagner… 😊

4.3 – Générateur de séquence

En utilisant la génération de la séquence sous une forme compacte on obtient un code plus optimisé : Nous avons gagné 1.32s. 😊

5 – Récursivité et performances

Les fonctions récursives sont rarement performantes d’autant plus si one refait plein de fois le même calcul… Prenons l’exemple de la suite de Fibonacci qui est la référence des suites récursives lentes à calculer… Le code est simple : Et le profileur nous retourne les informations suivantes : Et le profileur nous retourne le rapport suivant :

fib n’est désormais appelé que 35 fois, et d’un temps en secondes nous passons en microsecondes… Mais attention, la mise en cache passe par du stockage et donc une augmentation de la mémoire consommée : si maxsize n’est pas utilisé on peut se mettre à consommer toute la mémoire disponible. De plus on ne peut pas réinitialiser le cache facilement : il reste présent aussi longtemps que le module (contenant la fonction) est chargé en mémoire…

 

6 – Les chaînes de caractères

Mes 19 années d’expériences m’ont permis d’être souvent mis face à des opérations sur les chaînes de caractères dont le coût d’exécution avait été largement sous-estimé et ce quel que soit le langage utilisé… Les langages proposent souvent des API simples à utiliser (std ::string en C++ par exemple) dont l’implémentation interne est trop souvent inconnue au développeur… Et la puissance des machines d’aujourd’hui ne force pas le développeur à être attentif à ses outils ☹… Nous allons partir d’un besoin simple : je souhaite générer une table de calculs. Un fichier CSV (utilisant le ‘;’ comme séparateur de colonnes) contenant 4 colonnes et un million de lignes. Pour chaque ligne, je souhaite stocker (i, x=pi * i / 1000000, cos(x), sin(x) ) . Voici une façon (pas la meilleure, certes, mais c’est pour le besoin pédagogique) d’écrire ce fichier : Le profileur nous retourne le rapport suivant :

6.1 – Formatage plutôt que concaténation ?

Les chaînes de caractères sont non-modifiables et donc faire « text+= ‘;’ » crée un nouvel objet chaîne qui contient la valeur de text auquel on rajoute la nouvelle valeur ‘;’… Python 3.x propose une fonction de formatage (§ https://docs.python.org/3.4/library/string.html) globalement efficace et offrant de nombreuses fonctionnalités utiles… Essayons ce code : {0!s} signifie que l’on prend le 1er paramètre du tuple et qu’on le convertit en appelant la fonction str… En exécutant ce code, on obtient le rapport suivant : On passe de 6s à 5.49s environ… Voilà un petit gain, non?

6.2 – join?

L’API des chaînes en Python propose 2 fonctions très utiles au quotidien : string.split et string.join… Nous allons tester join afin de réussir à améliorer les performances. Grâce à la fonction format on crée immédiatement la chaîne dans values pour gagner du temps puis on remplace la boucle d’écriture dans le fichier par un join. On obtient alors : Nous passons à 4.39s donc un gain de 1.1s (20% de gain !!!). Le défaut de la méthode est que nous avons créé tout le fichier en mémoire avant de l’écrire sur le disque. Pour information, la bibliothèque pandas propose une méthode d’écriture des fichiers CSV plus efficace dès lors que l’on travaille avec des tableaux numpy

7 – numba

La distribution Anaconda fournit un package intéressant dès lors que l’on souhaite faire du calcul : numba. Celui-ci permet de compiler le bytecode Python à la volée vers du code machine comme le fait .NET ou Java… Cela permet d’obtenir des gains intéressants. Je vais juste vous présenter un petit exemple extrêmement basique pour vous montrer le gain. Par contre numba méritera un article complet car il y a beaucoup de paramètres que le développeur peut vouloir utiliser afin d’améliorer les performances et il y a, malheureusement, des limitations… Voici un petit exemple qui reprend la suite de Fibonacci avec le même algorithme mais via 2 fonctions distinctes : une sera interprétée en Python et l’autre compilée à la volée. On déclenche la compilation à la volée via le décorateur @jit. Dans notre cas, le profileur nous indique que : fib_seq est pratiquement dix  fois plus lent que fib_seq_numba (la version compilée à la volée).