Faster matmul for case sparse.coo * np.ndarray
维护者通常 2 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 25/100
- Issue 类型
- 功能
- 描述清晰度
- 需要澄清
- 活跃度
- 停滞
- 技术栈
- numpy, python
- 领域
- data, performance
调研方向
首先检查当前的 sparse.matmul 入口点,以及它如何处理 sparse.coo 与 NumPy ndarray 的乘法。将该路径与提议的单线程和并行实现进行比较;只有当项目就实现范围达成一致,并验证了所述 2D 情况下的性能改进后,这项工作才算完成。
由索引模型根据 Issue 内容生成。
描述
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?
- 主要语言
- Python
- 星标
- 670
- 派生
- 167
- 平均合并
- 3 天 4 小时
- 30 天内合并 PR
- 7
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue,再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库,在一个分支上完成修改。
- 提交 Pull Request,并在描述里引用这个 Issue 编号。
pydata/sparse 的其他 Issue
-
Bug: full einsum contractions upcast the dtype and count booleans可能已有人在做 @RaphaelFakhri 于 17 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 2 天内回复
-
BUG: ufunc outer rejects Python scalar and sequence operands可能已有人在做 @nawaaaaaAaar 于 29 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 76/100
维护者通常 2 天内回复
-
Bug: slices with a negative step and a negative stop return wrong elements可能已有人在做 @JoeyTan21 于 19 天前认领。 未关闭
难度 3/5 1-2 天 新手友好度 75/100
维护者通常 2 天内回复
-
BUG: matmul fails with zero-length broadcast batch dimensions可能已有人在做 @nawaaaaaAaar 于 29 天前认领。 未关闭
难度 3/5 1-2 天 新手友好度 40/100
维护者通常 2 天内回复
-
BUG: zero-length tensor contractions ignore requested output types可能已有人在做 @nawaaaaaAaar 于 29 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 35/100
维护者通常 2 天内回复
相似的 Issue
-
needs-triage
难度 1/5 1 小时以内 新手友好度 88/100
flashinfer-ai/flashinfer#9803 ·
维护者通常 1 天内回复
-
bug frontend good first issue help wanted
难度 2/5 1-3 小时 新手友好度 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
难度 2/5 1-3 小时 新手友好度 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
难度 1/5 1 小时以内 新手友好度 89/100
cuadrao-ai/argus#2328 ·
维护者通常 1 天内回复
-
bug frontend good first issue help wanted
难度 2/5 1-3 小时 新手友好度 88/100
nikhilb2/simple_invoicing#907 ·