c++ - 为什么矩阵加法比 Eigen 中的矩阵向​​量乘法慢？

Question

为什么矩阵加法比矩阵向量乘法需要更长的时间？

矩阵加法只需要 n^2 加法，而矩阵向量乘法需要 n*(n-1) 加法和 n^2 次乘法。

但是，在 Eigen 中，矩阵加法的时间是矩阵向量乘法的两倍。是否有任何选项可以加快 Eigen 中的 Matrix Add 操作？

#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <ctime>
#include <string>
#include <chrono>
#include <fstream>
#include <random>
#include <iomanip>

using namespace Eigen;
using namespace std;

int main()
{
const int l=100;
MatrixXf m=MatrixXf::Random(l,l);
MatrixXf n=MatrixXf::Random(l,l);
VectorXf v=VectorXf::Random(l,1);

MatrixXf qq=MatrixXf::Random(l,1);
MatrixXf pp=MatrixXf::Random(l,l);

auto start = chrono::steady_clock::now();
for(int j=0;j<10000;j++)
qq=m*v;
auto end = chrono::steady_clock::now();
double time_duration=chrono::duration_cast<chrono::milliseconds>(end - start).count();
std::cout << setprecision(6) << "Elapsed time in seconds : "<< time_duration/1000<< "s" << std::endl;
auto start1 = chrono::steady_clock::now();
for(int j=0;j<10000;j++)
pp=m+n;
auto end1 = chrono::steady_clock::now();
double time_duration1=chrono::duration_cast<chrono::milliseconds>(end1 - start1).count();
std::cout << setprecision(6) << "Elapsed time in seconds : "<< time_duration1/1000<< "s" << std::endl;
}

测试1：没有任何优化：

编译命令：g++-8 -test.cpp -o test

运行命令：./test

以秒为单位的经过时间：0.323s

以秒为单位的经过时间：0.635s

测试 2：使用 -march=native 优化：

g++-8 test.cpp -march=native -o test

运行命令：./test

以秒为单位的经过时间：0.21s

以秒为单位的经过时间：0.372s

测试 3：使用 -O3 优化：

编译命令：g++-8 -test.cpp -O3 -o test

运行命令：./test

以秒为单位的经过时间：0.009s

以秒为单位的经过时间：0.016s

测试 4：使用 -march=native、-O3 优化：

编译命令：g++-8 -test.cpp -march=native -O3 -o test

运行命令：./test

以秒为单位的经过时间：0.008s

以秒为单位的经过时间：0.016s

===============

我注意到编译器可能会作弊的评论，因为我没有使用上一次迭代的结果。为了解决这个问题，我改为进行一次迭代并使用更大的尺寸来获得稳定的时间统计信息。

#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <ctime>
#include <string>
#include <chrono>
#include <fstream>
#include <random>
#include <iomanip>

using namespace Eigen;
using namespace std;

int main()
{
const int l=1000;
MatrixXf m=MatrixXf::Random(l,l);
MatrixXf n=MatrixXf::Random(l,l);
VectorXf v=VectorXf::Random(l,1);

MatrixXf qq=MatrixXf::Random(l,1);
MatrixXf pp=MatrixXf::Random(l,l);

auto start = chrono::steady_clock::now();
qq=m*v;
auto end = chrono::steady_clock::now();
double time_duration=chrono::duration_cast<chrono::microseconds>(end - start).count();

auto start1 = chrono::steady_clock::now();
pp=m+n;
auto end1 = chrono::steady_clock::now();
double time_duration1=chrono::duration_cast<chrono::microseconds>(end1 - start1).count();
std::cout << setprecision(6) << "Elapsed time in microseconds : "<< time_duration<< "us" << std::endl;
std::cout << setprecision(6) << "Elapsed time in microseconds : "<< time_duration1<< "us" << std::endl;
}

测试1：没有任何优化：

编译命令：g++-8 -test.cpp -o test

运行命令：./test

以微秒为单位的经过时间：3125us

以微秒为单位的经过时间：6849us

测试 2：使用 -march=native 优化：

g++-8 test.cpp -march=native -o test

运行命令：./test

以微秒为单位的经过时间：1776us

以微秒为单位的经过时间：3815us

测试 3：使用 -O3 优化：

编译命令：g++-8 -test.cpp -O3 -o test

运行命令：./test

以微秒为单位的经过时间：449us

以微秒为单位的经过时间：760us

测试 4：使用 -march=native、-O3 优化：

编译命令：g++-8 -test.cpp -march=native -O3 -o test

运行命令：./test

以微秒为单位的经过时间：351us

以微秒为单位的经过时间：871us

标签： c++performancematrixeigen

Answer 1

简短的回答：您计算了操作的数量，但忽略了计算内存访问，对于加法情况，内存访问的成本几乎增加了 x2。详情如下。

首先，两种运算的实际运算次数是相同的，因为现代 CPU 能够同时执行一个独立的加法和乘法运算。两个顺序的 mul/add 类似x*y+z甚至可以融合为单个操作，其成本与 1 次加法或 1 次乘法相同。如果您的 CPU 支持 FMA，这就是发生的情况-march=native，但我怀疑 FMA 在这里起任何作用。

其次，在您的计算中，您忘记测量内存访问的次数。回想一下，除非数据已经在 L1 缓存中，否则一次内存加载比一次 add 或一次 mul 昂贵得多。

另外很简单：我们有2*n^2很多缓存未命中的负载，还有n^2存储。

对于具有列主矩阵的矩阵向量乘积，输入向量只读取一次，因此n^2+n会加载输入，并且由于列一次由 4 列的块处理，因此我们n^2/4对输出向量进行了读写，但是几乎零缓存未命中，因为它适合 L1 缓存。所以总的来说，加法的内存负载比矩阵向量乘积高出近 x2，因此 x2 速度因子并不异常。

此外，矩阵向量代码通过显式循环剥离进行了更积极的优化，尽管我怀疑这会对这个基准测试产生任何影响，因为您的矩阵根本不适合 L1 缓存。