función en línea con Cython gama numpy como parámetro

Question

Considere código como este:

import numpy as np 
cimport numpy as np 

cdef inline inc(np.ndarray[np.int32_t] arr, int i): 
    arr[i]+= 1 

def test1(np.ndarray[np.int32_t] arr): 
    cdef int i 
    for i in xrange(len(arr)): 
     inc(arr, i) 

def test2(np.ndarray[np.int32_t] arr): 
    cdef int i 
    for i in xrange(len(arr)): 
     arr[i] += 1 

que utilizan ipython para medir la velocidad de test1 y test2:

In [7]: timeit ttt.test1(arr) 
100 loops, best of 3: 6.13 ms per loop 

In [8]: timeit ttt.test2(arr) 
100000 loops, best of 3: 9.79 us per loop 

¿Hay una manera de optimizar test1? ¿Por qué Cython no implementa esta función como se le dijo?

ACTUALIZACIÓN: En realidad lo que necesito es el código multidimensional de esta manera:

# cython: infer_types=True 
# cython: boundscheck=False 
# cython: wraparound=False 

import numpy as np 
cimport numpy as np 

cdef inline inc(np.ndarray[np.int32_t, ndim=2] arr, int i, int j): 
    arr[i, j] += 1 

def test1(np.ndarray[np.int32_t, ndim=2] arr): 
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      inc(arr, i, j) 


def test2(np.ndarray[np.int32_t, ndim=2] arr):  
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      arr[i,j] += 1 

El tiempo para ello:

In [7]: timeit ttt.test1(arr) 
1 loops, best of 3: 647 ms per loop 

In [8]: timeit ttt.test2(arr) 
100 loops, best of 3: 2.07 ms per loop 

procesos en línea explícita da aumento de velocidad 300x. Y mi función real es bastante grande, así inlining que hace que el código de mantenimiento mucho peor

Update2:

# cython: infer_types=True 
# cython: boundscheck=False 
# cython: wraparound=False 

import numpy as np 
cimport numpy as np 

cdef inline inc(np.ndarray[np.float32_t, ndim=2] arr, int i, int j): 
    arr[i, j]+= 1 

def test1(np.ndarray[np.float32_t, ndim=2] arr): 
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      inc(arr, i, j) 


def test2(np.ndarray[np.float32_t, ndim=2] arr):  
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      arr[i,j] += 1  

cdef class FastPassingFloat2DArray(object): 
    cdef float* data 
    cdef int stride0, stride1 
    def __init__(self, np.ndarray[np.float32_t, ndim=2] arr): 
     self.data = <float*>arr.data 
     self.stride0 = arr.strides[0]/arr.dtype.itemsize 
     self.stride1 = arr.strides[1]/arr.dtype.itemsize 
    def __getitem__(self, tuple tp): 
     cdef int i, j 
     cdef float *pr, r 
     i, j = tp   
     pr = (self.data + self.stride0*i + self.stride1*j) 
     r = pr[0] 
     return r 
    def __setitem__(self, tuple tp, float value): 
     cdef int i, j 
     cdef float *pr, r 
     i, j = tp   
     pr = (self.data + self.stride0*i + self.stride1*j) 
     pr[0] = value   


cdef inline inc2(FastPassingFloat2DArray arr, int i, int j): 
    arr[i, j]+= 1 


def test3(np.ndarray[np.float32_t, ndim=2] arr):  
    cdef int i,j  
    cdef FastPassingFloat2DArray tmparr = FastPassingFloat2DArray(arr) 
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      inc2(tmparr, i,j) 

Tiempos:

In [4]: timeit ttt.test1(arr) 
1 loops, best of 3: 623 ms per loop 

In [5]: timeit ttt.test2(arr) 
100 loops, best of 3: 2.29 ms per loop 

In [6]: timeit ttt.test3(arr) 
1 loops, best of 3: 201 ms per loop 

Answer 1

El problema es que la asignación de una matriz numpy (o, equivalentemente, pasándolo en función argumento) no es solo una asignación simple, sino una "extracción de memoria intermedia" que rellena una estructura y extrae la información de la zancada y el puntero en las variables locales necesarias para la indexación rápida. Si está iterando sobre un número moderado de elementos, esta sobrecarga de O (1) se amortiza fácilmente a lo largo del ciclo, pero ciertamente no es el caso para las funciones pequeñas.

Mejorar esto es muy importante en la lista de deseos de muchas personas, pero es un cambio no trivial. Consulte, por ejemplo, la discusión en http://groups.google.com/group/cython-users/browse_thread/thread/8fc8686315d7f3fe

Answer 2

Usted está de paso de la matriz a inc() como Objeto Python del tipo numpy.ndarray. Pasar objetos de Python es costoso debido a problemas como el recuento de referencias, y parece impedir la creación de líneas internas. Si pasa la matriz la forma en C, es decir, como un puntero, test1() se vuelve incluso más rápido que test2() en mi máquina:

cimport numpy as np 

cdef inline inc(int* arr, int i): 
    arr[i] += 1 

def test1(np.ndarray[np.int32_t] arr): 
    cdef int i 
    for i in xrange(len(arr)): 
     inc(<int*>arr.data, i) 

Answer 3

Han transcurrido más de 3 años desde la publicación de la pregunta y se han realizado grandes progresos mientras tanto. En este código (Actualización 2 de la pregunta):

# cython: infer_types=True 
# cython: boundscheck=False 
# cython: wraparound=False 
import numpy as np 
cimport numpy as np 

cdef inline inc(np.ndarray[np.int32_t, ndim=2] arr, int i, int j): 
    arr[i, j]+= 1 

def test1(np.ndarray[np.int32_t, ndim=2] arr): 
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      inc(arr, i, j) 

def test2(np.ndarray[np.int32_t, ndim=2] arr):  
    cdef int i,j  
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      arr[i,j] += 1 

consigo los siguientes tiempos:

arr = np.zeros((1000,1000), dtype=np.int32) 
%timeit test1(arr) 
%timeit test2(arr) 
    1 loops, best of 3: 354 ms per loop 
1000 loops, best of 3: 1.02 ms per loop 

Así que el problema es reproducible, incluso después de más de 3 años. Cython ahora tiene typed memoryviews, AFAIK se introdujo en Cython 0.16, por lo que no estaba disponible en el momento en que se publicó la pregunta.Con este:

# cython: infer_types=True 
# cython: boundscheck=False 
# cython: wraparound=False 
import numpy as np 
cimport numpy as np 

cdef inline inc(int[:, ::1] tmv, int i, int j): 
    tmv[i, j]+= 1 

def test3(np.ndarray[np.int32_t, ndim=2] arr): 
    cdef int i,j 
    cdef int[:, ::1] tmv = arr 
    for i in xrange(tmv.shape[0]): 
     for j in xrange(tmv.shape[1]): 
      inc(tmv, i, j) 

def test4(np.ndarray[np.int32_t, ndim=2] arr):  
    cdef int i,j 
    cdef int[:, ::1] tmv = arr 
    for i in xrange(tmv.shape[0]): 
     for j in xrange(tmv.shape[1]): 
      tmv[i,j] += 1 

con esta me sale:

arr = np.zeros((1000,1000), dtype=np.int32) 
%timeit test3(arr) 
%timeit test4(arr) 
1000 loops, best of 3: 977 µs per loop 
1000 loops, best of 3: 838 µs per loop 

Estamos casi allí y ya más rápido que la antigua usanza! Ahora, la función inc() es elegible para ser declarada nogil, ¡así que vamos a declararlo! Pero oops:

Error compiling Cython file: 
[...] 

cdef inline inc(int[:, ::1] tmv, int i, int j) nogil: 
    ^
[...] 
Function with Python return type cannot be declared nogil 

Aaah, estoy totalmente perdido que el tipo de retorno void faltaba! Una vez de nuevo, pero ahora con void:

cdef inline void inc(int[:, ::1] tmv, int i, int j) nogil: 
    tmv[i, j]+= 1 

Y finalmente consigo:

%timeit test3(arr) 
%timeit test4(arr) 
1000 loops, best of 3: 843 µs per loop 
1000 loops, best of 3: 853 µs per loop 

Tan rápido como procesos en línea manual!

---

Ahora, sólo por diversión, he intentado Numba en este código:

import numpy as np 
from numba import autojit, jit 

@autojit 
def inc(arr, i, j): 
    arr[i, j] += 1 

@autojit 
def test5(arr): 
    for i in xrange(arr.shape[0]): 
     for j in xrange(arr.shape[1]): 
      inc(arr, i, j) 

me sale:

arr = np.zeros((1000,1000), dtype=np.int32) 
%timeit test5(arr) 
100 loops, best of 3: 4.03 ms per loop 

pesar de que es 4.7x más lento que Cython, muy probablemente debido a que la El compilador JIT no pudo alinear inc(), creo que es ¡INCREÍBLE! Todo lo que necesitaba hacer era agregar @autojit y no tenía que estropear el código con declaraciones de tipos torpes; ¡88x de aceleración por casi nada!

He intentado otras cosas con Numba, como

@jit('void(i4[:],i4,i4)') 
def inc(arr, i, j): 
    arr[i, j] += 1 

o nopython=True pero no para mejorarlo aún más.

Improving inlining is on the Numba developers' list, solo necesitamos presentar más solicitudes para que tenga una mayor prioridad. ;)