なぜブースト行列の乗算が私よりも遅いのですか？

Question

私は（my full, working boost codeを参照）boost::numeric::ublas::matrixで

Result result = read(); 

boost::numeric::ublas::matrix<int> C; 
C = boost::numeric::ublas::prod(result.A, result.B); 

と標準アルゴリズムで別の1（full standard codeを参照）1行列の乗算を実装している：これは私が速度をテストする方法です

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
            vector< vector<int> > B) { 
    int n = A.size(); 

    // initialise C with 0s 
    vector<int> tmp(n, 0); 
    vector< vector<int> > C(n, tmp); 

    for (int i = 0; i < n; i++) { 
     for (int k = 0; k < n; k++) { 
      for (int j = 0; j < n; j++) { 
       C[i][j] += A[i][k] * B[k][j]; 
      } 
     } 
    } 
    return C; 
} 

を：

time boostImplementation.out > boostResult.txt 
diff boostResult.txt correctResult.txt 

time simpleImplementation.out > simpleResult.txt 
diff simpleResult.txt correctResult.txt 

どちらのプログラムも、2つの2000 x 2000 matri ces。 両方のプログラムは、これらのフラグでコンパイルされた：

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic 

私は私の実装と4 分以上のブースト実装のためのため15秒を持って！

編集：

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out 

でそれをコンパイルした後、私はIKJ-アルゴリズムとブーストのため60.99秒ため28.19秒を得ました。 Boostはまだかなり遅いです。

ブーストが私の実装よりもずっと遅いのはなぜですか？

Answer 1

UBLASバージョンのパフォーマンスの低下は、TJDが指摘したように後者のデバッグ機能によって部分的に説明できます。

ここでのデバッグとuBLASバージョンにかかる時間です：

real 0m19.966s 
user 0m19.809s 
sys  0m0.112s 

はここ（-DNDEBUG -DBOOST_UBLAS_NDEBUGコンパイラフラグが追加された）オフのデバッグとuBLASバージョンで撮影した時間です：

real 0m7.061s 
user 0m6.936s 
sys  0m0.096s 

そうでデバッグオフ、uBLASのバージョンはほぼ3倍高速です。 ublasの重要な設計目標は同じくらい一般的になることです

：

パフォーマンスの差を残り

は「（atlas-）BLASよりなぜuBLASがあるので、はるかに遅い」uBLAS FAQの次のセクションを引用して説明することができます可能。

この一般性は、ほとんどの場合、コストがかかります。特に、prod関数テンプレートは、疎または三角形のような異なるタイプの行列を扱うことができます。幸いにも、uBLASは、高密度マトリックス乗算に最適化された代替品、特にaxpy_prodとblock_prodを提供します。ここでは異なる方法を比較した結果は以下のとおりです。

ijkalgorithm prod axpy_prod block_prod 
    1.335  7.061 1.330  1.278 

あなたは両方axpy_prodとblock_prodがあなたの実装よりもやや速いです見ることができるように。I/Oなしで計算時間だけを測定し、不必要なコピーを削除し、block_prod（私は64を使用）のブロックサイズを慎重に選択することで、その違いをさらに深くすることができます。

uBLAS FAQおよびEffective uBlas and general code optimizationも参照してください。

Answer 2

あなたのコンパイラは十分に最適化していないと思います。 uBLASコードはテンプレートを大量に使用し、テンプレートは最適化を大量に必要とします。私は1000×1000の行列のためのリリースモードでMS VC 7.1コンパイラを通して、あなたのコードを実行し、それがuBLASベクトル

ため

7.851の差がまだあるが、決して圧倒的ために私に

10.064秒を与えます。 uBLASのコアコンセプトは怠惰な評価なので、prod(A, B)は必要なときにのみ結果を評価します。 prod(A, B)(10,100)は、その1つの要素だけが実際に計算されるため、すぐに実行されません。したがって、実際には行列全体の乗算に専用のアルゴリズムはなく、（下記参照）に最適化することができます。しかし、あなたは縛ら片手であなたの機能を打つ4.426 sまでの走行時間を短縮します

matrix<int, column_major> B; 

を宣言し、ライブラリーを少し助けることができます。この宣言により、行列の乗算時にメモリへのアクセスがより順調になり、キャッシュの使用が最適化されます。

P.S. uBLASのドキュメントを最後まで読んでください）、行列を一度に乗ずるという専用の関数が実際に存在することが分かりました。 2つの機能 - axpy_prodおよびopb_prod。だから、

opb_prod(A, B, C, true); 

にも最適化されていないrow_majorのBマトリックス上は8.091秒で実行し、あなたのベクトルアルゴリズム

P.P.S.と同等ですさらに最適化があります：

C = block_prod<matrix<int>, 1024>(A, B); 

は4.4秒で実行され、Bはcolumn_またはメジャーrow_であるかどうかに関係なく。 説明を検討してください： "関数block_prodは、高密度の行列用に設計されています。特定のタスクのための特定のツールを選択してください！

Answer 3

少しウェブサイトMatrix-Matrix Product Experiments with uBLASを作成しました。マトリックスマトリックス製品の新しい実装をuBLASに統合することです。ブーストライブラリーをすでにお持ちの場合は、追加の4ファイルのみで構成されます。だからそれはかなり自己完結型です。

別のマシンで簡単なベンチマークを実行できる人がいれば、私は興味があります。