Si vous faites de l’analyse de gros jeux de données en Python, vous vous êtes vite rendu compte que c’est là que le langage montre sa lenteur.
Les boucles pour manipuler des arrays d’entiers, qui prennent quelque nanosecondes en C, prennent des microsecondes en Python. C’est pour ça que les scientifiques utilisent SciPy et les analystes Pandas, qui sont tous deux basés sur la lib C Numpy bien enrobée dans du joli Python.
Parfois néanmoins, garder le code en pur Python est un objectif, comme dans le cas du projet mss, un screenshotter qui ne souhaites avoir une extension compilée attachée à la patte.
Or la manipulation d’images, ça bouffe des grosses matrices de pixels, et l’auteur nous a posé une jolie colle sur IndexError : ayant un array de pixels en notation BGR (Blue, Green Red), comment le transposer en RGB de manière performante ?
Sa proposition était :
pixels = range(300) # je réduis le nombre de pixel pour le benchmark buffer_len = len(pixels) def version1(): for idx in range(0, buffer_len - 2, 3): pixels[idx + 2], pixels[idx] = pixels[idx], pixels[idx + 2] |
J’ai tenté :
from array import array xrange = getattr(__builtins__, 'xrange', range) def version2(): def to_rgb(pixels, buffer_len): for i in xrange(0, buffer_len - 2, 3): yield pixels[i + 2] yield pixels[i + 1] yield pixels[i] return array('H', to_rgb(pixels, buffer_len)) |
Mais mesurer révèle que cette solution est au final bien plus lente que celle de l’auteur :
import timeit print(timeit.timeit('version1()', setup='from __main__ import version1')) #16.9543120861 print(timeit.timeit('version2()', setup='from __main__ import version2')) #42.7808477879 |
C’est bubulle qui va nous pondre une solution originale, élégante, mais surtout 5 fois plus rapide, ce qui est complètement inattendu :
def version3(): pixels[2:buffer_len:3], pixels[0:buffer_len:3] = pixels[0:buffer_len:3], pixels[2:buffer_len:3] |
Il utilise 3 astuces en une :
- Le swap de variable par unpacking: a, b = b, a. On sait que c’est plus rapide que deux assignation car Python saute la version intermédiaire.
- Le slicing avec pas (l[debut:fin:pas]), et il parcours donc son array de 3 en 3. Super malin ! Non seulement je n’y aurais jamais pensé, mais en prime j’aurais imaginé que créer deux nouveaux arrays à partir du premier serait lent.
- L’assignation de slices. Oui, on peut faire l[3:5] = [‘a’, ‘b’] en Python.
Le gain de perf est assez bluffant :
print(timeit.timeit('version3()', setup='from __main__ import version3')) #1.84227705002 |
Pourquoi est-ce aussi rapide ? Je ne peux que faire des suppositions.
Je pense que faisant cette opération sans boucler explicitement, une bonne partie reste dans l’implémentation en C sous-jacente. On évite notamment pas mal d’appels à __getitem__ et __setitem__ qui sont toujours coûteux en Python.
Par curiosité, j’ai lancé le même test sur pypy :
0.359977960587 15.5387830734 0.750488996506 |
On voit l’effet de la compilation JIT puisque la boucle explicite redevient plus performante.
Mais du coup je me pose une question : pourquoi ma version, qui utilise une boucle explicite également, reste autant à la traine ?
Puis j’ai réalisé : l’array stock des entier C, mais quand on les sort, il faut les rewrapper dans des entiers Python. Donc ma boucle se tape cette conversion à chaque tour, et ça bouffe.
Je vire l’array :
def version4(): def to_rgb(pixels, buffer_len): for i in xrange(0, buffer_len - 2, 3): yield pixels[i + 2] yield pixels[i + 1] yield pixels[i] return list(to_rgb(pixels, buffer_len)) |
Et pouf, le temps devient plus raisonnable.
Avec CPython : 1.84687900543
Avec Pypy : 0.274104118347
Sur CPython, la vitesse est du même ordre de grandeur que la version avec les slices.
Sur PyPy, la version est 2X plus rapide que les slices, est 25% plus rapide que la version originale.
Moralités :
- Les slices, c’est rapide. Et beau.
- Bien connaitre ses structures de données. Utiliser la mauvaise vous tue les perfs, et
arraysert à économiser de la place en mémoire, pas à gagner du CPU. - Pypy, ça trace, mais le gain de perf peut se déplacer d’un algo à l’autre.
Merci pour l’analyse. Tu peux expliquer ce que ton troisième point (“L’assignation de slices. Oui, on peut faire l[3:5] = [‘a’, ‘b’] en Python.”) a de surprenant/novateur/original? je ne vois pas la différence avec l’unpacking (bouh bouh).
T’aurais pu mettre le profil de en lien, il mérite bien ça =D
Je crois qu’il manque l’utilisation de array dans la version 2
(parce que je vois pas vraiment de diff avec la version4 :) )
Alors déjà que recevoir un commentaire de Sam comme “Putain mais c’est brillant.” avec cette verve si caractéristique, j’en avais les yeux qui s’humectent. Je n’ose pas dire où se déplace mon humidité corporelle de me voir ainsi cité dans un article sur sametmax…
J’ai plus le réflexe de travailler avec Numpy où l’utilisation des slices est assez naturelle et je suis moi-même surpris qu’on puisse transférer ce type d’approche avec un certain succès.
Au final, ton benchmark suggère que la version 4 est bonne sur le temps d’exécution tout en évitant des listes temporaires, je pense que c’est elle qu’il faut privilégier.
@Furankun
D’une certaine manière, tu démontres la cohérence de Python :) On aurait tout à fait raison de voir l’assignation par slice comme équivalente à l’unpacking.
En pratique, il y a une vrai différence dans l’implémentation puisque
l[3:5] = [‘a’, ‘b’]est en fait interprété commel.setitem(slice(3, 5), ['a', 'b']). Mais on s’en fout de l’implémentation tant qu’on peut écrire facilement du code expressif et synthétique.@bubulle:
“si à 50 ans t’es pas sourcé dans un article chez sam et max, t’as raté ta vie” :)
@Furankun: dans son exemple, il a un pas, donc le slicing prend en compte le pas. C’est ça qui est funky.
@mgautierfr: bien vu.
“il parcours donc sont array”
Ouh mon dieu ;-)
Dans le genre optimisation surprise, y’a ça qui est vraiment très très intéressant : https://www.python.org/doc/essays/list2str/
@Charles: tu n’as rien vu.
J’ai encore appris quelque chose aujourd’hui grâce à vous et Bubulle du coup merci !! :)
Juste un truc que j’ai pas capté, quand tu dis qu’il y a une conversion de type entre C et python pour les integer dans un array ça veut dire quoi ? Je pensais que python était basé sur C et que du coup il utilisait les même valeurs en mémoire pour stocker un int ? (Message de gros noob numéro 4529)
“Mais mesurer révèle que”, c’est pas plutôt “Mes mesures révèlent que” ?
On s’en fout des fautes, on est trop excités :D
(merci pour les précisions)
@betepoilue: les entiers Python sont bien écrits en C, mais sont des objets complexes. Alors qu’en C, définir un entier long peut se faire un simple “signed double var = “, faire un entier long en Python utilise une struture bien plus complexe :
Le module array est un module Python un peu particulier, qui permet de stocker ses valeurs sous la forme qu’on utiliserait en C. Mais quand on sort une valeur de l’array, il faut de nouveau l’enrober dans une structure complexe.
Alors pour le coup, j’ai voulu tester avec Pandas une autre solution:
import pandas as pd
def version5():
df = pd.DataFrame(pd.np.array(pixels).reshape(100, 3))
df = df[[0, 2, 1]]
return df.stack().tolist()
Mais timeit met un temps infini et je dois killer le test oO. Si quelqu’un sait pourquoi, ça m’interesse
Si on a pas le code timeit derrière ni tes données en pixels, ça va être dur.
@Sam j’ai pris les mêmes que toi
pas doué le gars avec les tags…
@sam pardon je n’ai pas pu répondre plus tôt !! Merci beaucoup pour l’explication complète et le code, je ne savais pas du tout que les types en python fonctionnaient de cette manière. Ça a l’air super intéréssant en tout cas, je vais regarder ça et du côté d’array du coup. Merci !!
J’array donc je suis !