Faster matmul for case sparse.coo * np.ndarray

Abierto
#653 1 comentario 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 2 días

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
numpy, python
Área
data, performance

Línea de trabajo

Comience revisando el punto de entrada actual de sparse.matmul y cómo gestiona la multiplicación de sparse.coo por un NumPy ndarray. Compare ese recorrido con las implementaciones propuestas de un solo hilo y paralela; el trabajo solo estará completo cuando el proyecto haya acordado el alcance de la implementación y haya verificado mejoras de rendimiento para el caso 2D indicado.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

enhancement

I am using this module quite heavily in a recent project and found that sparse.matmul could work faster.
I have implemented a faster version for the case matmul(sparse.coo, np.ndarray) using numba for the case of 2D arrays (cut be generalized). I also implemented a parallellized Version. The single threaded version is roughly 3 times faster than sparse.matmul in this case and scales linearly with the number of entries in the sparse matrix. The multi-threaded Version has some overhead but scales well for very large matrices (10000000+ entries).

Here is the code:

@numba.njit()
def matmul_fast(dim1:np.ndarray,dim2:np.ndarray,V:np.ndarray,Arr: np.ndarray,out: np.ndarray):
    for i in range(V.shape[0]):
        out[dim1[i]] += V[i] * Arr[dim2[i]]
    return out
@numba.njit(parallel=True,fastmath=True,boundscheck=False)
def matmul_fast_parallel(dim1:np.ndarray,dim2:np.ndarray,V:np.ndarray,Arr: np.ndarray,out: np.ndarray,n: np.int64 = 100000):
    f = V.shape[0]
    s = out.shape
    out_loc = np.zeros(s,dtype=np.float64)
    g = 0
    i = 0
    for i_0 in numba.prange(0,f//n+1):
        i = i_0 * n
        out_loc = np.zeros(s,dtype=np.float64)
        for g in range(i,i+n):
            if g>=f:
                break
            out_loc[dim1[g]] += V[g] * Arr[dim2[g]]
        out += out_loc
    return out

These functions can be driven by a non numba function that unpacks the sparse array object into coordinates, data and shape.

def matmul_sparse(Arr_sparse, Arr):
    out = np.zeros((Arr_sparse.shape[0],Arr.shape[1]))
    return matmul_fast_parallel(Arr_sparse.coords[0],Arr_sparse.coords[1],Arr_sparse.data,Arr,out)

Are there any optimizations planned that improve the performance of sparse.matmul?
If not would there be interest in introducing specific solutions like this as an option in the current implementation?

Lenguaje dominante
Python
Estrellas
670
Forks
167
Merge medio
3 d 4 h
PR fusionados (30 d)
7

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de pydata/sparse

Todos los issues de pydata/sparse

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.