为什么矩阵加法在特征上比矩阵向量乘法慢？

Question

为什么矩阵加法比矩阵向量乘法要长得多？

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

然而，在本征中，矩阵加法所需的时间是矩阵向量乘法的两倍.是否有任何选项可以加快矩阵添加操作在本征？

#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

运行时间(秒)：0.323s

运行时间(秒)：0.635s

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

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

运行命令：./test

运行时间(秒)：0.21s

运行时间(秒)：0.372 s

测试3:使用-O3优化：

编译命令: g++-8 -test.cpp -O3 -o测试

运行命令：./test

运行时间(秒)：0.009s

运行时间(秒)：0.016s

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

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

运行命令：./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

经过的时间(以微秒计)：3125 in

经过的时间(以微秒计)：6849 in

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

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

运行命令：./test

运行时间(以微秒计)：1776 in

经过的时间(以微秒计)：3815 in

测试3:使用-O3优化：

编译命令: g++-8 -test.cpp -O3 -o测试

运行命令：./test

经过的时间(以微秒计)：449 in

运行时间(以微秒计)：760 in

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

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

运行命令：./test

运行时间(以微秒计)：351 in

运行时间(以微秒计)：871 in

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缓存。