Faster matmul for case sparse.coo * np.ndarray
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
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
- Sin Dockerfile ni archivo de Docker Compose
- Tiene una plantilla de pull request
- Leer la guía de contribución
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de pydata/sparse
-
Bug: full einsum contractions upcast the dtype and count booleansPosiblemente ocupada @RaphaelFakhri la tomó hace 17 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
Los mantenedores suelen responder en 2 días
-
BUG: ufunc outer rejects Python scalar and sequence operandsPosiblemente ocupada @nawaaaaaAaar la tomó hace 29 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 76/100
Los mantenedores suelen responder en 2 días
-
Bug: slices with a negative step and a negative stop return wrong elementsPosiblemente ocupada @JoeyTan21 la tomó hace 19 días. Abierto
Dificultad 3/5 1-2 días Aptitud para principiantes 75/100
pydata/sparse#1019 · 1 comentario ·
Los mantenedores suelen responder en 2 días
-
BUG: matmul fails with zero-length broadcast batch dimensionsPosiblemente ocupada @nawaaaaaAaar la tomó hace 29 días. Abierto
Dificultad 3/5 1-2 días Aptitud para principiantes 40/100
Los mantenedores suelen responder en 2 días
-
BUG: zero-length tensor contractions ignore requested output typesPosiblemente ocupada @nawaaaaaAaar la tomó hace 29 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 35/100
Los mantenedores suelen responder en 2 días
Todos los issues de pydata/sparse
Issues similares
-
needs-triage
Dificultad 1/5 Menos de una hora Aptitud para principiantes 88/100
flashinfer-ai/flashinfer#9803 ·
Los mantenedores suelen responder en 1 día
-
bug frontend good first issue help wanted
Dificultad 2/5 1-3 horas Aptitud para principiantes 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
Dificultad 2/5 1-3 horas Aptitud para principiantes 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
Dificultad 1/5 Menos de una hora Aptitud para principiantes 89/100
cuadrao-ai/argus#2328 ·
Los mantenedores suelen responder en 1 día
-
bug frontend good first issue help wanted
Dificultad 2/5 1-3 horas Aptitud para principiantes 88/100
nikhilb2/simple_invoicing#907 ·