Sam & Max » slicing http://sametmax.com Du code, du cul Sat, 07 Nov 2015 10:56:13 +0000 en-US hourly 1 http://wordpress.org/?v=4.1 Les slices, c’est rapide et c’est beau 19 http://sametmax.com/les-slices-cest-rapide-et-cest-beau/ http://sametmax.com/les-slices-cest-rapide-et-cest-beau/#comments Thu, 16 Apr 2015 08:35:46 +0000 http://sametmax.com/?p=16085 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 array sert à é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.
]]>
http://sametmax.com/les-slices-cest-rapide-et-cest-beau/feed/ 19
Connaissez vous l’objet slice en Python ? 11 http://sametmax.com/connaissez-vous-lobjet-slice-en-python/ http://sametmax.com/connaissez-vous-lobjet-slice-en-python/#comments Tue, 27 Aug 2013 07:56:08 +0000 http://sametmax.com/?p=7218 slice en Python ? What the actual fucking fuck ?]]> Python, le langage sans fond. Arriverai-je à n’avoir plus jamais d’article à écrire un jour ?

Tenez, hier, j’étais en train de lire un blog sur le Web, le bourrelet paresseusement calé entre mon dossier et la table, quand soudain, boum !

Je tombe sur ça :

>>> slice
<type 'slice'>

Aucun import. Rien.

Attend, il y a un type built-in slice en Python ? What the actual fucking fuck ?

Alors je testouille un truc, y croyant vaguement :

>>> lst = ['a', 'b', 'c', 'd']
>>> lst[1:3]
[u'b', u'c']
>>> lst[slice(1,3)]
[u'b', u'c']

Donc plutôt que de se trimbaler avec des tuples de valeurs dont il faudra tester ou imposer la taille. Plutôt que d’attendre en paramètre uniquement des entiers positionnels ou forcer le passage de None, on peut aussi tout simplement passer un slice à vos fonctions qui font du slicing.

Ça veut dire des objets slices en valeurs par défaut.

Ça veut dire des objets slices dans les mapping, les iterables, etc.

Un seul regret :

>>> from itertools import islice
>>> islice(lst, slice)
Traceback (most recent call last):
  File "<ipython-input-5-7eb2c7533070>", line 1, in <module>
    islice(lst, slice(1,3))
ValueError: Stop argument for islice() must be None or an integer: 0 <= x <= maxint.

Et ça c’est vraiment con.

]]>
http://sametmax.com/connaissez-vous-lobjet-slice-en-python/feed/ 11