Faster matmul for case sparse.coo * np.ndarray

オープン
#653 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
25/100
issue の種類
機能追加
明瞭さ
説明が足りない
活発さ
停滞
技術スタック
numpy, python
領域
data, performance

調査の方向性

まず、現在の sparse.matmul のエントリーポイントと、sparse.coo に NumPy ndarray を乗算する処理の扱いを確認します。その経路を、提案されている単一スレッド実装および並列実装と比較します。プロジェクトが実装範囲について合意し、指定された 2D ケースでの性能向上を検証して初めて、作業は完了となります。

索引モデルが issue の本文から書いたものです。

説明

enhancement

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

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

pydata/sparse のほかの issue

pydata/sparse の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。