Faster matmul for case sparse.coo * np.ndarray
メンテナーはふだん 2 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 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時間
- マージ済み PR(30日)
- 7
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- 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
pydata/sparse#1019 · コメント 1 件 ·
メンテナーはふだん 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 ·