Optimisation
Un article de Haypo.
« Premature optimization is the root of all evil » — Donald Knuth
Retour aux articles de programmation
L'optimisation d'un programme est une tâche très complexe contrairemenet à ce qu'on pourrait penser à première vue. Cet article détaille les points cruciaux à observer lorsqu'on veut optimiser un programme.
Sommaire |
[modifier] N'optimiser que ce quand c'est vraiment nécessaire
Il faut éviter :
- d'optimiser trop tôt :
- avant que le programme ne soit plainement fonctionnel
- avant d'avoir chercher plusieurs façons d'avoir au même but mais avec des algorithmes différents
- les micro-optimisations : optimisation faisant gagner moins de 5% de performance
- une optimisation rendant le code obscure / illisible
[modifier] Outil de mesure
Optimiser sans outil de mesure n'a aucun sens. Il 'faut absoluement pouvoir mesurer le temps d'exécution (voir également l'empreinte mémoire) pour pouvoir comparer deux algorithmes. Voici quelques outils de mesure :
- Instruction machine RDTSC des processeurs Pentium : voir l'article Fréquence_du_processeur, précision : fréquence du processeur (donc d'une précision optimale)
- Fonction clock() de la libc, précision : CLOCKS_PER_SEC Hertz (NdR: est-ce vraiment cette fréquence là?)
- Fonction time.time() en Python, précision : ??? (dépend de l'implémentation de Python)
[modifier] Python : classe Benchmark
Pour comparer deux fonctions simples, Python offre le module timeit. Mais j'ai développé ma propre classe Benchmark pour rendre cette tâche encore plus simple.
Paramètres de cette classe (du plus important au moins important) :
- Nombre d'itération minimum (défaut: 5)
- Temps d'exécution maximum recommandé (limite le nombre d'itérations) (défaut: 5 secondes)
- Nombre d'itération maximum (paramètre très peu utile en fait)
On peut également demander à afficher la progression de la mesure (avec rafraichissement 4 fois par seconde), désactiver le ramasse miette (garbage collector), etc.
Le gros avantage de cette classe est qu'elle calcule elle-même le bon nombre d'itérations à faire. Elle calcule également le temps minimum, maximum, moyen et total.
[modifier] Exemple d'utilisation de Benchmark
Code pour comparer deux fonctions :
from benchmark import Benchmark
def funcA():
text = ""
for index in xrange(1000):
text += str(index)
return text
def funcB():
text = []
for index in xrange(1000):
text += str(index)
return ''.join(text)
b = Benchmark(max_time=1.0)
b.run(funcA)
b.run(funcB)
Résultat :
Run benchmark: 935 calls (estimate: 999.58 ms) Benchmark: best=967.03 usec average=1.00 ms worst=10.63 ms total=940.08 ms Run benchmark: 613 calls (estimate: 998.50 ms) Benchmark: best=1.49 ms average=1.57 ms worst=11.02 ms total=960.96 ms
967 µsec contre 1490 µsec, la fonction funcA() est donc plus rapide.
[modifier] Trouver la partie à optimiser
Une tâche très importante et qui amène sur de fausses pistes si elle est faite à la va-vite : trouver la partie précise à optimiser. En général, un programme passe 90% de son temps dans 10% du code. Il faut optimiser ces 10% et surtout ne pas perdre de temps sur les autres 90% qui sont rarement utilisés.
De toute manière, quand on optimise une partie peu gourmande en ressource, on "voit" facilement avec un outil de mesure que ça ne change rien (moins de 5% de gain) aux performances.
Trouver la portion de code qui consomme le maximum de ressource processeur peut être faite facilement avec un profiler. Voici un petite liste (loin d'être exhaustive) :
- oprofile : ne nécessite pas de recompilation
- gprof : nécessite une recompilation
- Modules python profiler et hotshot : simple à mettre en œuvre
[modifier] Cas pratique : optimisation d'urwid en UTF-8
[modifier] Trouver le code à optimiser
urwid est une bibliothèque permettant de concevoir facilement des interfaces en mode texte. La version 0.9.7 souffre de lenteur lorqu'on l'utilise dans un terminal avec le charset UTF-8. Lançons un profileur (modules Python hotshot et stat) pour voir quel est le code à optimiser :
2099491 function calls (2099179 primitive calls) in 8.134 CPU seconds
Ordered by: internal time, call count
List reduced from 247 to 50 due to restriction <50>
ncalls tottime percall cumtime percall filename:lineno(function)
9685 3.546 0.000 6.717 0.001 util.py:557(calc_width)
982880 1.606 0.000 1.606 0.000 utable.py:79(decode_one)
983865 1.598 0.000 1.598 0.000 utable.py:69(get_width)
1786 0.243 0.000 0.243 0.000 canvas.py:366(arange)
76 0.214 0.003 0.334 0.004 curses_display.py:484(draw_screen)
2090 0.133 0.000 6.900 0.003 canvas.py:37(__init__)
1786 0.086 0.000 0.952 0.001 canvas.py:354(apply_text_layout)
21090 0.048 0.000 0.048 0.000 util.py:869(rle_len)
3760 0.046 0.000 0.193 0.000 urwid_ui.py:252(_get)
(...)
Informations importantes :
- Temps total d'exécution : 8.1 secondes
- Fonctions consommant le plus de temps processeur : calc_width(), decode_one(), get_width()
Il faut donc se concentrer sur ces 3 fonctions :
- decode_one() extrait le premire caractère Unicode d'une chaîne UTF-8
- get_width() calcule la largeur à l'écran d'un caractère Unicode
- calc_width() calcule la largeur à l'écran d'une chaîne de caractère et utilise decode_one() et get_width()
[modifier] Fausse piste
Au début, j'étais parti sur une mauvaise piste : chercher à optimiser decode_one() ou get_width(), travail long, laborieux et surtout qui n'avait aucun impact sur les performances (gain entre 1 et 2%).
[modifier] Unicode or not Unicode: that is the question
En lisant le code plus attentivement, j'ai compris qu'urwid acceptait soit des chaînes encodées soit en Unicode soit dans un autre charset (ex: UTF-8). En bref, le classe Canvas n'acceptait que des châines non-Unicode en entrée: il fallait convertir de l'Unicode en UTF-8 si besoin. Alors qu'elle reconvertissait en Unicode quelques instants plus tard... Mais surtout d'une manière complexe et coûteuse.
J'ai alors fait en sorte qu'urwid conserve les chaînes en Unicode le plus longtemps possible : j'ai stocké les chaînes deux fois dans Canvas : encodées en UTF-8 et en Unicode.
Les résultats sont très encourageants :
- Urwid normal : 7.8 sec
- En conservant les chaînes Unicode : 4.1 sec
Le programme est donc deux fois plus rapide (100% plus rapide). Ceci montre qu'on a touché la corde sensible d'urwid.
[modifier] Toujours plus loin
En discutant avec Julien, il m'a suggéré de cacher widths : tableau contenant le résultat des appels à calc_width() pour chaque Canvas. Effectivement, j'avais stockés les chaînes Unicode pour accélérer le calcul de widths mais en fait il suffisait de stocker widths. Ce qui évitait en plus de recalculer widths plus tard.
Nouveau résultats :
- Urwid normal : 7.8 sec
- En stockant widths : 2.7 sec
[modifier] Tentons autre chose
En prenant du recul, j'ai réalisé que tout tournait autour de la fonction calc_width()... ce qui est d'ailleurs clair en regardant les résultats du profiler. Quand on n'arrive plus à améliorer l'algorithme d'une fonction, une bonne idée est de précalculer ou cacher les résultats.
Fonction « naïve » pour cacher les résultats :
def calc_width( text, start_offs, end_offs ):
key = hash( (text, start_offs) )
if key not in calc_width.cache:
calc_width.cache[key] = _calc_width(text, start_offs, end_offs)
return calc_width.cache[key]
calc_width.cache = {}
(il faut renommer la vraie fonction calc_width() en _calc_width())
En utilisant juste cette fonction, les résultats sont impressionants :
- Urwid normal : 7,8 sec
- Avec le cache : 2,1 sec
Nous sommes donc passés de 7,8 secondes à 4,1 secondes, puis 2,7 et finalement 2,1. Le plus drôle étant que finalement, cette dernière fonction est la plus courte (changement minimum d'urwid).
