c++ - 为什么 boosts 矩阵乘法比我的慢？

Question

我已经用 boost::numeric::ublas::matrix 实现了一个矩阵乘法(参见 my full, working boost code)

Result result = read ();

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

另一种使用标准算法(见 full standard code):

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

两个程序都读取包含两个 2000 x 2000 矩阵的硬编码文本文件。 这两个程序都是用这些标志编译的:

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

我的实现获得了 15 秒，而 boost 实现获得了超过 4 分钟!

edit: 用

编译后

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

ikj 算法得到 28.19 秒，Boost 得到 60.99 秒。所以 Boost 仍然相当慢。

为什么 boost 比我的实现慢这么多？

Answer 1

正如 TJD 所指出的，uBLAS 版本的性能较慢可以部分解释为后者的调试功能。

这是 uBLAS 版本在调试时所用的时间:

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

这是关闭调试的 uBLAS 版本所用的时间(添加了-DNDEBUG -DBOOST_UBLAS_NDEBUG 编译器标志):

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

所以在关闭调试的情况下，uBLAS 版本几乎快了 3 倍。

可以通过引用 uBLAS FAQ 的以下部分来解释剩余的性能差异。 “为什么 uBLAS 比(atlas-)BLAS 慢这么多”:

An important design goal of ublas is to be as general as possible.

这种普遍性几乎总是有代价的。特别是 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 的 block 大小(我使用 64)可以使差异更加深刻。

另见 uBLAS FAQ和 Effective uBlas and general code optimization .