为什么提升matrix乘法比我的慢?

我用boost::numeric::ublas::matrix实现了一个matrix乘法(请参阅我的完整工作boost代码 )

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

另一个是标准algorithm(见完整的标准代码 ):

 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; } 

这是我如何testing速度:

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

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

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

我有15秒的执行时间,超过4分钟的升压执行!

编辑:编译后

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

ikjalgorithm得到28.19 ,Boost得到60.99秒 。 所以Boost仍然相当慢。

为什么提升比我的实现慢得多?

TJD指出,uBLAS版本的性能降低部分可以通过后者的debuggingfunction来解释。

下面是uBLAS版本debugging的时间:

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

下面是closuresdebugging的uBLAS版本所用的时间(添加了-DNDEBUG -DBOOST_UBLAS_NDEBUG编译器标志):

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

所以在debuggingclosures的情况下,uBLAS版本几乎快了3倍。

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

ublas的一个重要的devise目标是尽可能通用。

这种普遍性几乎总是伴随着成本。 特别是prod函数模板可以处理不同types的matrix,比如稀疏或者三angular形。 幸运的是,uBLAS为密集matrix乘法提供了优化select,特别是axpy_prod和block_prod 。 以下是比较不同方法的结果:

 ijkalgorithm prod axpy_prod block_prod 1.335 7.061 1.330 1.278 

正如你所看到的, axpy_prodblock_prod比你的实现要快一些。 只测量没有I / O的计算时间,删除不必要的复制,并仔细selectblock_prod (我用64)的块大小可以使差异更深刻。

另请参阅uBLAS常见问题和有效的uBlas和一般的代码优化 。

我相信,你的编译器不够优化。 uBLAS代码大量使用模板,模板需要大量优化。 我通过MS VC 7.1编译器以1000x1000matrix的发行模式运行你的代码,它给了我

10.064秒为uBLAS

向量为7.851

差异仍然存在,但决不是压倒性的。 uBLAS的核心概念是懒惰评估,因此prod(A, B)仅在需要时评估结果,例如prod(A, B)(10,100)将立即执行,因为只有这一个元素将被计算。 因此,实际上没有可以优化的整个matrix乘法的专用algorithm (见下文)。 但是你可以帮助图书馆一点,宣布

 matrix<int, column_major> B; 

将运行时间减less到4.426秒,一手绑定您的function。 这个声明使得在matrix乘法时访问内存更加顺序,优化了caching的使用。

PS读完uBLAS文档到最后;),你应该已经发现实际上有一个专门的函数来一次乘以整个matrix。 2个函数 – axpy_prodopb_prod 。 所以

 opb_prod(A, B, C, true); 

即使在未优化的row_major Bmatrix执行8.091秒,并与您的vectoralgorithm相提并论

PPS还有更多的优化:

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

无论B是column_还是row_ major,都会在4.4秒内执行。 考虑描述:“函数block_prod是为大型密集matrixdevise的。” 为特定任务select特定的工具!

我用uBLAS创build了一个网站Matrix-Matrix Product Experiments 。 这是关于将matrix – matrix产品的新实现集成到uBLAS中的。 如果您已经拥有增强库,则它只包含其他4个文件。 所以它是非常独立的。

如果其他人可以在不同的机器上运行简单的基准testing,我会感兴趣。