Interprétation vs pénalité de répartition dynamique en Python

Question

J'ai regardé Brandon Rhodes parler de Cython - "Le jour de l'EXE est sur nous". Brandon mentionne à 09:30 que pour un court morceau de code spécifique, l'interprétation de saut a donné une accélération de 40%, tandis que sauter l'allocation et l'expédition a donné 574% d'accélération (10:10).

Ma question est - comment est-ce mesuré pour un morceau de code spécifique? Faut-il extraire manuellement les commandes c sous-jacentes et ensuite les faire tourner?

Ceci est une observation très intéressante, mais comment puis-je recréer l'expérience?

Answer 1

Jetons un coup d'oeil à cette fonction python:

def py_fun(i,N,step): 
    res=0.0 
    while i<N: 
     res+=i 
     i+=step 
    return res 

et utiliser ipython-magique temps:

In [11]: %timeit py_fun(0.0,1.0e5,1.0) 
10 loops, best of 3: 25.4 ms per loop 

L'interprète sera en cours d'exécution à travers le bytecode résultant et l'interpréter. Cependant, nous avons pu découper l'interprète à l'aide cython pour/cythonizing le même code:

%load_ext Cython 
%%cython 
def cy_fun(i,N,step): 
    res=0.0 
    while i<N: 
     res+=i 
     i+=step 
    return res 

Nous obtenons une place de vitesse de 50% pour elle:

In [13]: %timeit cy_fun(0.0,1.0e5,1.0) 
100 loops, best of 3: 10.9 ms per loop 

Quand nous regardons dans le produit c-code, nous voyons que les bonnes fonctions sont appelées directement, sans la nécessité d'être interprété/appelant ceval, ici après dépouillant le code boilerplate:

static PyObject *__pyx_pf_4test_cy_fun(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_i, PyObject *__pyx_v_N, PyObject *__pyx_v_step) { 
    ... 
    while (1) { 
    __pyx_t_1 = PyObject_RichCompare(__pyx_v_i, __pyx_v_N, Py_LT); 
    ... 
    __pyx_t_2 = __Pyx_PyObject_IsTrue(__pyx_t_1); 
    ... 
    if (!__pyx_t_2) break; 
    ... 
    __pyx_t_1 = PyNumber_InPlaceAdd(__pyx_v_res, __pyx_v_i); 
    ... 
    __pyx_t_1 = PyNumber_InPlaceAdd(__pyx_v_i, __pyx_v_step); 
    } 
    ... 
    return __pyx_r; 
} 

Cependant, ce c La fonction ython gère les objets python et non les flottants de type c, donc dans la fonction PyNumber_InPlaceAdd il est nécessaire de comprendre, ce que sont réellement ces objets (entier, flottant, autre chose?) et d'envoyer cet appel aux bonnes fonctions qui feraient le travail.

Avec l'aide de cython on peut aussi éliminer la nécessité de cette expédition et d'appeler directement la multiplication des flotteurs:

%%cython 
def c_fun(double i,double N, double step): 
     cdef double res=0.0 
     while i<N: 
     res+=i 
     i+=step 
     return res 

Dans cette version, i, N, step et res doubles c style et plus d'objets python. Donc, il n'y en a besoin plus d'appeler dispatch-fonctions comme PyNumber_InPlaceAdd mais nous pouvons appeler directement + -operator pour double:

static PyObject *__pyx_pf_4test_c_fun(CYTHON_UNUSED PyObject *__pyx_self, double __pyx_v_i, double __pyx_v_N, double __pyx_v_step) { 
    ... 
    __pyx_v_res = 0.0; 
    ... 
    while (1) { 
    __pyx_t_1 = ((__pyx_v_i < __pyx_v_N) != 0); 
    if (!__pyx_t_1) break; 
    __pyx_v_res = (__pyx_v_res + __pyx_v_i); 
    __pyx_v_i = (__pyx_v_i + __pyx_v_step); 
    } 
    ... 
    return __pyx_r; 
} 

Et le résultat est:

In [15]: %timeit c_fun(0.0,1.0e5,1.0) 
10000 loops, best of 3: 148 µs per loop 

Maintenant, c'est un Speed- de près de 100 par rapport à la version sans interprète mais avec dépêche. En fait, dire que dispatch + allocation est le goulot de la bouteille ici (parce que l'éliminer a provoqué une accélération de presque 100) est une erreur: l'interprète est responsable de plus de 50% du temps de fonctionnement (15 ms) et envoi et affectation "seulement" pendant 10ms.

---

Cependant, il y a plus de problèmes que « interprète » et l'expédition dynamique pour la performance: Float est immuable, donc chaque fois qu'il change un nouvel objet doit être créé et enregistré/non enregistré dans le collecteur des ordures.

Nous pouvons introduire des flotteurs mutables, qui sont changés en place et ne nécessitent pas l'enregistrement/désenregistrement:

%%cython 
cdef class MutableFloat: 
cdef double x  
def __cinit__(self, x): 
    self.x=x   
def __iadd__(self, MutableFloat other): 
    self.x=self.x+other.x 
    return self 
def __lt__(MutableFloat self, MutableFloat other): 
    return self.x<other.x 
def __gt__(MutableFloat self, MutableFloat other): 
    return self.x>other.x 
def __repr__(self): 
    return str(self.x) 

Les horaires (maintenant j'utiliser une autre machine, donc les timings un peu différents):

def py_fun(i,N,step,acc): 
     while i<N: 
      acc+=i 
      i+=step 
     return acc 

%timeit py_fun(1.0, 5e5,1.0,0.0) 
30.2 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each 
%timeit cy_fun(1.0, 5e5,1.0,0.0) 
16.9 ms ± 612 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit i,N,step,acc=MutableFloat(1.0),MutableFloat(5e5),MutableFloat(1 
    ...: .0),MutableFloat(0.0); py_fun(i,N,step,acc) 
23 ms ± 254 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 
%timeit i,N,step,acc=MutableFloat(1.0),MutableFloat(5e5),MutableFloat(1 
...: .0),MutableFloat(0.0); cy_fun(i,N,step,acc) 
11 ms ± 66.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

ne pas oublier de ré-initialiser i parce qu'il est mutable! Les résultats

  immutable  mutable 
py_fun  30ms   23ms 
cy_fun  17ms   11ms 

donc jusqu'à 7 ms (environ 20%) sont nécessaires pour l'enregistrement/flotteurs désinscription (je ne suis pas sûr qu'il n'y a pas quelque chose à jouer d'autre rôle) dans la version avec l'interprète et plus de 33 % dans la version sans l'interprète.

Comme il semble maintenant:

• 40% (13/30) du temps est utilisé par l'interprète
• jusqu'à 33% du temps est utilisé pour l'envoi dynamique
• jusqu'à 20% du temps est utilisé pour le collecteur d'ordures
• environ 1% pour les opérations arithmétiques

---

Un autre problème est la localité des données, qui devient évidente pour les problèmes liés à la bande passante mémoire: Les caches modernes fonctionnent bien pour si les données traitées linéairement une adresse mémoire consécutives après l'autre. Cela est vrai pour la boucle sur std::vector<> (ou array.array), mais pas pour la boucle sur les listes python, car cette liste est constituée de pointeurs qui peuvent pointer vers n'importe quel endroit de la mémoire.

Considérons les scripts python suivants:

#list.py 
N=int(1e7) 
lst=[0]*int(N) 
for i in range(N): 
    lst[i]=i 
print(sum(lst)) 

et

#byte 
N=int(1e7) 
b=bytearray(8*N) 
m=memoryview(b).cast('L') #reinterpret as an array of unsigned longs 
for i in range(N): 
    m[i]=i 
print(sum(m)) 

ils ont tous deux créent 1e7 des nombres entiers, les premiers nombres entiers de python-version et les seconds les petits c-ints qui sont placés en continu dans la mémoire.

La partie intéressante est, combien de défauts de cache (D), ces scripts produisent:

valgrind --tool=cachegrind python list.py 
... 
D1 misses:  33,964,276 ( 27,473,138 rd +  6,491,138 wr) 

contre

valgrind --tool=cachegrind python bytearray.py 
... 
D1 misses:   4,796,626 ( 2,140,357 rd +  2,656,269 wr) 

Cela signifie 8 fois plus de défauts de cache pour le python-entiers. Une partie de cela est due au fait que les entiers python ont besoin de plus de 8 octets (probablement 32 octets, c.-à-d.facteur 4) mémoire et (peut-être, pas sûr à 100%, parce que les entiers voisins sont créés les uns après les autres, donc les chances sont élevées, ils sont stockés les uns après les autres quelque part en mémoire, une enquête plus approfondie). ne sont pas alignés en mémoire comme c'est le cas pour c-entiers de bytearray.