Faster matmul for case sparse.coo * np.ndarray
Maintainer thường phản hồi trong vòng 2 ngày
Chưa có ai nhận issue này.
Đánh giá
- Độ khó
- 5/5
- Thời gian dự kiến
- Hơn một tuần
- Mức phù hợp với người mới
- 25/100
- Loại issue
- Tính năng
- Độ rõ ràng
- Cần làm rõ
- Mức độ hoạt động
- Đình trệ
- Công nghệ
- numpy, python
- Lĩnh vực
- data, performance
Hướng nghiên cứu
Bắt đầu bằng cách xem xét entry point hiện tại của sparse.matmul và cách nó xử lý việc nhân sparse.coo với một NumPy ndarray. So sánh đường đi đó với các triển khai single-threaded và song song được đề xuất; công việc chỉ hoàn tất khi dự án đã thống nhất về phạm vi triển khai và xác minh được các cải thiện hiệu năng cho trường hợp 2D đã nêu.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
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?
- Ngôn ngữ chính
- Python
- Star
- 670
- Fork
- 167
- Merge trung bình
- 3 ngày 4 giờ
- Pull request đã merge (30 ngày)
- 7
Chuẩn bị môi trường
- Không có Dockerfile hay tệp Docker Compose
- Có mẫu pull request
- Đọc hướng dẫn đóng góp
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của pydata/sparse
-
Bug: full einsum contractions upcast the dtype and count booleansCó thể đã có người làm @RaphaelFakhri đã nhận 17 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
Maintainer thường phản hồi trong vòng 2 ngày
-
BUG: ufunc outer rejects Python scalar and sequence operandsCó thể đã có người làm @nawaaaaaAaar đã nhận 29 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 76/100
Maintainer thường phản hồi trong vòng 2 ngày
-
Bug: slices with a negative step and a negative stop return wrong elementsCó thể đã có người làm @JoeyTan21 đã nhận 19 ngày trước. Đang mở
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 75/100
pydata/sparse#1019 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 2 ngày
-
BUG: matmul fails with zero-length broadcast batch dimensionsCó thể đã có người làm @nawaaaaaAaar đã nhận 29 ngày trước. Đang mở
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 40/100
Maintainer thường phản hồi trong vòng 2 ngày
-
BUG: zero-length tensor contractions ignore requested output typesCó thể đã có người làm @nawaaaaaAaar đã nhận 29 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 35/100
Maintainer thường phản hồi trong vòng 2 ngày
Tất cả issue của pydata/sparse
Issue tương tự
-
needs-triage
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 88/100
flashinfer-ai/flashinfer#9803 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
bug frontend good first issue help wanted
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 89/100
cuadrao-ai/argus#2328 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
bug frontend good first issue help wanted
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 88/100
nikhilb2/simple_invoicing#907 ·