La mémoization est une forme de mise en cache, elle consiste à cacher le résultat d’une fonction afin que les appels successifs avec des paramètres identiques utilisent le cache plutôt que de calculer à nouveau les données.
En gros:
>>> fonction_super_lente(True, '127.0.0.1') # calcule >>> fonction_super_lente(True, '127.0.0.1') # ne calcule pas, retourne le cache >>> fonction_super_lente(True, '192.168.0.1') # calcule car les paramètres sont différents |
En Python on peut le faire de plusieurs manières, malgré ce que prétend la philosophie du langage.
La version avec dico externe
resultats = {} def fonction_super_lente(le_faire, sur_quoi): if not (le_faire, sur_quoi) in resultats: resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici return resultats[(le_faire, sur_quoi)] |
Cela marche parceque resultats est gardé dans une closure et donc accessible dans la fonction. Comme il est défini avant, et que les dictionnaires sont mutables, on a toujours la même référence au même dico à chaque appel. On a juste a vérifier qu’un résultat pour ces param existent (les tuples peuvent être des clés de dictionnaires), et si non, on remplit le cache.
Avantages:
- c’est facile à comprendre;
- on peut manipuler le cache depuis l’extérieur.
Inconvénient:
- le namespace du module est pollué;
- on risque d’importer le cache par erreur.
La version avec paramètre additionel
def fonction_super_lente(le_faire, sur_quoi, _resultats={}): if not (le_faire, sur_quoi) in resultats: _resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici return _resultats[(le_faire, sur_quoi)] |
Même chose que précédement, mais la différence est que le cache est stocké dans un paramètre. Cela marche car les paramètres sont initialisés à la déclaration en Python, et une seule fois.
Notez le underscore devant le nom de paramètre qui est une convention pour désigner un paramètre qui ne fait pas partie de l’API publique.
Avantages:
- c’est encore pas trop dur à comprendre;
- le namespace est clean.
Inconvénient:
- la signature de la fonction possède un argument artificiel.
La version avec attribut
def fonction_super_lente(le_faire, sur_quoi): resultats = getattr(function_super_lente, '_resultats', {}) if not (le_faire, sur_quoi) in resultats: resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici function_super_lente._resultats = resultats return resultats[(le_faire, sur_quoi)] |
Cela marche car les fonctions en Python sont des objets. On peut leur rajouter des attributs à la volées comme pour n’importe quel objet :-)
Notez l’usage du troisième paramètre de getattr() qui nous permet d’avoir une valeur par défaut même si l’attribut n’existe pas encore.
Avantages:
- pas de polution du namespace ni de la signature.
Inconvénient:
- votre collègue va surement vous demander: WTF ?
La version avec décorateur
Il existe pas mal de versions de décorateurs de mémoization disponibles sur le Net. Ca s’utilise généralement comme ça :
from malib import memoized @memoized def fonction_super_lente(le_faire, sur_quoi): return # le truc normalement |
Avantages:
- y a pas plus propre;
- y a pas plus facile.
Inconvénient:
- une dépendance de plus;
- chaque implémentation possède une caractéristique (souvent une limite): il faut donc comprendre des codes parfois complexes pour les utiliser en toute tranquilité d’esprit.
Petit rappel
Cette technique, de par sa nature, implique de tout stocker en mémoire vive. Donc attention à votre RAM, et vérifiez bien que ça vaut le coup d’échanger la charge CPU contre celle de vos barettes. Ensuite, le bénéfice est d’autant plus grand que le code tourne longtemps. Si c’est un script lancé de nombreuses fois, avec quelques appels à la fonction, le gain est faible: entre chaque initialisation de la VM Python, le cache disparait. Dans ce cas il vaut mieux se tourner vers une solution telle que Redis.
Le cas typique d’usage pertinent est celui d’un daemon faisant des appels à une API WEB: en cachant les résultats, vous économisez une requête HTTP.
Plug éhonté: pour faire du mémoizing avec persistence sur disque (utile en environement multiprocessus ou pour garder la persistence d’une session Python à l’autre): joblib
C’est très sympas ce truc. Ca stoque les infos dans quel format ? Comment ça gère l’accès concurrent ?
Sur python 3 il y a aussi le décorateur lru_cache
Si vous voulez voir un comparatif de caches: récit d’un panouillage avec memoize
J’ai testé pour vous :
* memoize avec dict;
* memoize avec un dict à taille fixe mimine 1.0;
* repoze.lru (LRU) cache à taille fixe et éventuellement à temps d’expiration;
* beaker.cache (fait tout mémoire, disk, memcached, taille fixe…)
À le problème d’un mémoize c’est que si on rappelle la fonction souvent on peut pas vider le cache donc repoze.lru propose un fournisseur de cache nommé que l’on peut vider, qui a mon grand dam n’est pas documenté.
Si vous voulez le beurre l’argent du beurre, et marier la crémière je conseille beaker.cache.
Excellent article. Le benchmarking est toujours un exercice trollesque, mais c’est très bien traité.
Le commentaire de Marius Gedminas à lui tout seul est important.
Ça raconte surtout comment je m’ai fail comme le noob que je suis.
Avant d’optimiser, faut bien mesurer le gain que l’on souhaite, et faire gaffe aux propriétés des fonctions que l’on cache.
Sinon, j’insiste beaker.cache c’est la solution costard, cravatte, canne et monocle. Ai je précisé que comme repoze.lru c’est thread safe? La seule différence entre repoze.lru et beaker.cache c’est pour beaker il y avait pas besoin de soumettre un patch pour qu’elle soit complète.
Ouahou, j’ai toujours fait ce genre de truc manuellement, sans penser que y’en a qui y aurait réfléchi dessus avec un vrai cerveau.
Penser à remplacer le “if” par un “if not” dans la version avec attribut. Sinon y’a pas que votre collègue qui va vous demander WTF, y’a l’interpréteur python aussi.
À part ça, les tampons, c’est top feng shui, mais des fois ça cache le texte. Peut-être que vous vous en êtes aperçus et que vous préférez le laisser comme ça, parce que ça fait artiste.
“Ouuaaaiis t’vois, l’important, c’est pas les caractères, mec. C’est ce qu’ils veulent dire au fond d’eux mêmes, t’vois.”
non justement je viens juste de régler l’opacity :)
Là ils devraient permettre de voir correctement ce qu’il y a dessous.
Ayant une vision supermanesque j’avais complètement oublié que les mortels que vous êtes ne pouvaient voir ce qui était écrit en dessous de ces merveilleux petits tampounets…
Pensez à faire un F5
Une question maître !
Lorsque tu dis “les paramètres sont initialisés à la déclaration en Python, et une seule fois“, cela est-il vrai aussi dans ce cas là ?
J’ai mis en place ce système pour le module MSS, et il s’avère que ça a plombé le bousin.
Par contre, en déclarant
resultatsjuste avant la fonction, j’ai pu constater une amélioration flagrante.Sinon, merci pour l’article ;)
@Tiger: Pas dans ton cas, puisque tu repasses un nouveau dictionnaire à chaque appel de fonction. Dans ta ligne tu ne déclare pas la fonction, tu l’utilises !
En déclarant le dictionnaire avant, tu utilises bien toujours le même et ça marche.
Tu devrais avoir un truc plutôt comme ça:
Au passage, depuis python3.2 il y a un cache dans la lib standard: functools.lru_cache. Dans quelques années ça sera être un standard, qui sait ? En attendant une version compatible pour python < 3.2 est là: http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/
@kontre : Ah ok, merci pour les explications :)