Faster matmul for case sparse.coo * np.ndarray
I maintainer di solito rispondono entro 2 giorni
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 25/100
- Tipo di issue
- Funzionalità
- Chiarezza
- Da chiarire
- Stato di attività
- Ferma
- Stack tecnologico
- numpy, python
- Ambito
- data, performance
Direzione di ricerca
Iniziare esaminando l’attuale punto di ingresso di sparse.matmul e il modo in cui gestisce la moltiplicazione di sparse.coo per un NumPy ndarray. Confrontare questo percorso con le implementazioni proposte a thread singolo e parallela; il lavoro sarà completo solo quando il progetto avrà concordato l’ambito dell’implementazione e verificato miglioramenti delle prestazioni per il caso 2D indicato.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
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?
- Lingua principale
- Python
- Stelle
- 670
- Fork
- 167
- Merge medio
- 3g 4h
- PR unite (30g)
- 7
Preparare l'ambiente
- Nessun Dockerfile né file Docker Compose
- Ha un modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di pydata/sparse
-
Bug: full einsum contractions upcast the dtype and count booleansForse già presa @RaphaelFakhri l’ha presa 17 giorni fa. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
I maintainer di solito rispondono entro 2 giorni
-
BUG: ufunc outer rejects Python scalar and sequence operandsForse già presa @nawaaaaaAaar l’ha presa 29 giorni fa. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
I maintainer di solito rispondono entro 2 giorni
-
Bug: slices with a negative step and a negative stop return wrong elementsForse già presa @JoeyTan21 l’ha presa 19 giorni fa. Aperta
Difficoltà 3/5 1-2 giorni Idoneità per principianti 75/100
pydata/sparse#1019 · 1 commento ·
I maintainer di solito rispondono entro 2 giorni
-
BUG: matmul fails with zero-length broadcast batch dimensionsForse già presa @nawaaaaaAaar l’ha presa 29 giorni fa. Aperta
Difficoltà 3/5 1-2 giorni Idoneità per principianti 40/100
I maintainer di solito rispondono entro 2 giorni
-
BUG: zero-length tensor contractions ignore requested output typesForse già presa @nawaaaaaAaar l’ha presa 29 giorni fa. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 35/100
I maintainer di solito rispondono entro 2 giorni
Tutte le issue di pydata/sparse
Issue simili
-
needs-triage
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 88/100
flashinfer-ai/flashinfer#9803 ·
I maintainer di solito rispondono entro 1 giorno
-
bug frontend good first issue help wanted
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 89/100
cuadrao-ai/argus#2328 ·
I maintainer di solito rispondono entro 1 giorno
-
bug frontend good first issue help wanted
Difficoltà 2/5 1-3 ore Idoneità per principianti 88/100
nikhilb2/simple_invoicing#907 ·