Performance de carte contre starmap?

Question

J'essayais de faire une comparaison pure-python (sans dépendances externes) de deux séquences. Ma première solution était:

list(map(operator.eq, seq1, seq2)) 

Je trouve starmap fonction de itertools, qui semblait assez semblable à moi. Mais il s'est avéré être 37% plus rapide sur mon ordinateur dans le pire des cas. Comme il n'a pas été évident pour moi, je l'ai mesuré le temps nécessaire pour récupérer 1 élément d'un générateur (ne sais pas si cette façon est correcte):

from operator import eq 
from itertools import starmap 

seq1 = [1,2,3]*10000 
seq2 = [1,2,3]*10000 
seq2[-1] = 5 

gen1 = map(eq, seq1, seq2)) 
gen2 = starmap(eq, zip(seq1, seq2)) 

%timeit -n1000 -r10 next(gen1) 
%timeit -n1000 -r10 next(gen2) 

271 ns ± 1.26 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each) 
208 ns ± 1.72 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each) 

Dans la récupération des éléments de la deuxième solution est 24% plus performante . Après cela, ils produisent tous deux les mêmes résultats pour list. Mais quelque part, nous gagnons de plus de 13% dans le temps:

%timeit list(map(eq, seq1, seq2)) 
%timeit list(starmap(eq, zip(seq1, seq2))) 

5.24 ms ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
3.34 ms ± 84.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

Je ne sais pas comment creuser plus profondément dans le profilage d'un tel code imbriqué? Donc ma question est pourquoi le premier générateur est-il plus rapide à récupérer et d'où nous gagnons 13% de plus dans la fonction list?

EDIT: Ma première intention était d'effectuer la comparaison élément par élément au lieu de all, de sorte que la fonction all a été remplacé par list. Ce remplacement n'affecte pas le rapport de synchronisation.

CPython 3.6.2 sur Windows 10 (64 bits)

Answer 1

Il y a plusieurs facteurs qui contribuent (en même temps) à la différence de performance observée:

• zip réutilise le retour tuple si elle a un compte de référence de 1 lorsque la prochaine __next__ appel est fait.
• map génère un nouveautuple qui est transmis à la «fonction mappée» à chaque appel __next__. En fait, il ne créera probablement pas un nouveau tuple à partir de zéro car Python maintient un stockage pour les tuples inutilisés. Mais dans ce cas map doit trouver un tuple inutilisé de la bonne taille.
• starmap vérifie si l'élément suivant dans le itérable est de type tuple et si oui, il le transmet simplement.
• L'appel d'une fonction C à partir du code C avec PyObject_Call ne créera pas un nouveau tuple transmis à l'appelé.

Alors starmap avec zip n'utilisera un tuple encore et encore qui est passé à operator.eq réduisant ainsi grandement la fonction d'appel en tête. D'autre part, map va créer un nouveau tuple (ou remplir un tableau C à partir de CPython 3.6) chaque fois que operator.eq est appelée. Donc, quelle est la différence de vitesse est juste la surcharge de la création de tuple.

Au lieu de lier au code source, je vais vous donner un code Cython qui peut être utilisé pour vérifier:

In [1]: %load_ext cython 

In [2]: %%cython 
    ...: 
    ...: from cpython.ref cimport Py_DECREF 
    ...: 
    ...: cpdef func(zipper): 
    ...:  a = next(zipper) 
    ...:  print('a', a) 
    ...:  Py_DECREF(a) 
    ...:  b = next(zipper) 
    ...:  print('a', a) 

In [3]: func(zip([1, 2], [1, 2])) 
a (1, 1) 
a (2, 2) 

Oui, tuple s ne sont pas vraiment immuable, un Py_DECREF simple a été suffisante pour " astuce "zip en croyant que personne d'autre ne détient une référence au tuple retourné!

Quant à la "tuple-pass-thru":

In [4]: %%cython 
    ...: 
    ...: def func_inner(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(*args): 
    ...:  print(id(args)) 
    ...:  func_inner(*args) 

In [5]: func(1, 2) 
1404350461320 
1404350461320 

Ainsi, le tuple est passé à travers (juste parce que ceux-ci sont définis comme des fonctions C!) Cela ne se produit pas pour les fonctions pures Python:

In [6]: def func_inner(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(*args): 
    ...:  print(id(args)) 
    ...:  func_inner(*args) 
    ...: 

In [7]: func(1, 2) 
1404350436488 
1404352833800 

Notez que cela ne se produit également pas si la fonction appelée n'est pas une fonction C, même si elle est appelée à partir d'une fonction C:

In [8]: %%cython 
    ...: 
    ...: def func_inner_c(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(inner, *args): 
    ...:  print(id(args)) 
    ...:  inner(*args) 
    ...: 

In [9]: def func_inner_py(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: 

In [10]: func(func_inner_py, 1, 2) 
1404350471944 
1404353010184 

In [11]: func(func_inner_c, 1, 2) 
1404344354824 
1404344354824 

Donc, il y a beaucoup de « coïncidences » menant au point que starmap avec zip est plus rapide que d'appeler map avec de multiples arguments lorsque la fonction appelée est une fonction C ...

Answer 2

Une différence que je peux remarquer est la façon dont map récupère les articles des iterables. Les deux map et zip créent un tuple d'itérateurs de chaque itérable passé. Maintenant zip maintient un result tuple en interne qui est rempli chaque fois que le prochain est appelé et d'autre part, map creates a new array^* à chaque appel suivant et le libère.

---

* _{Comme indiqué par MSeifert jusqu'à 3.5.4 map_next utilisé pour allouer un nouveau chaque tuple Python. Cela a changé dans 3.6 et jusqu'à 5 itérations C pile est utilisée et pour tout ce qui est plus grand que ce tas est utilisé. PR connexes: Issue #27809: map_next() uses fast call et Add _PY_FASTCALL_SMALL_STACK constant | Problème: https://bugs.python.org/issue27809}