Haypo le 3 mars 2008 à 21:28

2008-03-03T21:28:59Z

← Version précédente		Version du 3 mars 2008 à 21:28
Ligne 1 :		Ligne 1 :
		+	<div style="float: right; margin-bottom: 1ex; text-align: right;">
		+	'''Â« ''Premature optimization is the root of all evil'' Â» â€” Donald Knuth'''
		+	</div>
	[[CatÃ©gorie:Programmation]] [[CatÃ©gorie:Logiciel libre]]		[[CatÃ©gorie:Programmation]] [[CatÃ©gorie:Logiciel libre]]
	{{Retour\|Programmation\|Retour aux articles de programmation}}		{{Retour\|Programmation\|Retour aux articles de programmation}}

Haypo: /* Toujours plus loin */

2006-12-31T17:20:15Z

Toujours plus loin

Nouvelle page

[[CatÃ©gorie:Programmation]] [[CatÃ©gorie:Logiciel libre]]
{{Retour|Programmation|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.

== 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

== 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)

=== 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.
* Voir le '''[http://hachoir.org/browser/hachoir-core/trunk/hachoir_core/benchmark.py code source de la classe Benchmark]'''

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.

=== 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)
<nowiki>return ''.join(text)</nowiki>

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.

== 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) :

* [http://oprofile.sourceforge.net/ oprofile] : ne nÃ©cessite pas de recompilation
* [http://www.gnu.org/software/binutils/ gprof] : nÃ©cessite une recompilation
* [http://docs.python.org/lib/profile.html Modules python profiler et hotshot] : simple Ã mettre en Å“uvre

== Cas pratique : optimisation d'urwid en UTF-8 ==

=== 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()

=== 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%).

=== 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.

=== 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

=== 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).

Optimisation - Historique des versions

Haypo le 3 mars 2008 à 21:28

Haypo: /* Toujours plus loin */