江苏龙网

  1. 首页 > 生活 > >

Eigen的速度为啥这么快( 三 )



从上到下，expression tree是通过c++ template的方法把计算提取成AST一样的东西，并惰性求值，从而减少了对中间变量的需求，这种优化被称为expression template。具体来说，就是对于这样一个计算
A = B + C - D;按正常的C++，展开直接计算应该类似：
// tmp1 = B + CMatrix tmp1(n);for (int i=0; i\u0026lt;n; i++) tmp1 = B + C;// tmp2 = tmp1 - DMatrix tmp2(n);for (int i=0; i\u0026lt;n; i++) tmp2 = tmp1 - D;// A = tmp2for (int i=0; i\u0026lt;n; i++) A = tmp2;而通过抽象成AST，把A和B, C, D通过树连接起来之后再对A的每个元素求值，就可以达到这样的效果：
for (int i=0; i\u0026lt;n; i++) A = B + C - D;可以很明显对比出两者之间的区别。这里需要注意的是，他的AST用的是C template做的，可能因为Eigen这个库是只有头文件的。以及为了防止重复实现，使用了CRTP这种设计模式。
不过这种优化仅限于element-wise的操作，矩阵乘法就不行了。所以eigen对于乘法做了2件事，第一是把常见的乘法操作提取出来，提取为：
Eigen的速度为啥这么快

单独进行优化。然后因为矩阵乘法需要得到中间变量，所以为了更好的利用expression template，eigen用tree optimizer把矩阵乘法运算往后移。tree optimizer主要就是这样的2条运算顺序调整：
// catch A * B + Y and builds Y\u0026#39; + A\u0026#39; * B\u0026#39;TreeOpt\u0026lt;Sum\u0026lt;Product\u0026lt;A,B\u0026gt;,Y\u0026gt; \u0026gt; { … };// catch X + A * B + Y and builds (X\u0026#39; + Y\u0026#39;) + (A\u0026#39; * B\u0026#39;)TreeOpt\u0026lt;Sum\u0026lt;Sum\u0026lt;X,Product\u0026lt;A,B\u0026gt; \u0026gt;,Y\u0026gt; \u0026gt; { … };这样就可以把运算
res -= m1 + m2 + m3*m4 + 2*m5 + m6*m7;调整为
res -= m1 + m2 + 2*m5;res -= m3*m4;res -= m6*m7;注意这其中的每一行可以理解为一个中间变量。
做完tree optimizer，就要开始利用硬件信息优化了，比如做向量化来利用SIMD，进行loop unrolling什么的。对于是否要进行这些优化，eigen对于运算记录了一个经验性的cost model（这里我说经验性的是因为我没看到他利用上了矩阵的形状，所以判断其可能认为所有加法cost都一样，如果有误请大家及时纠正），然后设置了阈值来判断优化是否有益。
还是希望有兴趣的同学去看一下pdf，应该比我这里说的详细很多。
以上。

■网友
感觉Eigen相比于其他线性代数库最突出的特点是，“不是效率高的事情不做，不是最快的算法就不提供”。看下Eigen自己说的，Eigen: What happens inside Eigen, on a simple example总结来说Eigen做了这么几件事：1. 不用中间变量2. 小矩阵和大矩阵根据实际情况选用3. 特殊的赋值处理4. 矢量化 SSE指令市面上Eigen库最快，对于Armadillo+数学库的组合速度取决于数学库的速度，Armadillo本身数学库就不用提了。
■网友
先上结论：Eigen可以很快，但前提是编译器优化，多线程支持，MKL等加速库要到位。
举个栗子：
10000*10000的两个随机矩阵相乘。用了Intel MKL加速，其他的blas库没有时间去试了，应该差不多。
main.cpp
#define EIGEN_USE_MKL_ALL#define EIGEN_VECTORIZE_SSE4_2#include \u0026lt;iostream\u0026gt;#include \u0026lt;Eigen/Dense\u0026gt;#include \u0026lt;time.h\u0026gt;#include \u0026lt;chrono\u0026gt;using namespace std;using namespace Eigen;using namespace chrono;int main(){ MatrixXd m1 = MatrixXd::Random(10000, 10000); MatrixXd m2 = MatrixXd::Random(10000, 10000); cout\u0026lt;\u0026lt;"begin product"\u0026lt;\u0026lt;endl; auto start = system_clock::now(); MatrixXd p = m1 * m2; auto end = system_clock::now(); auto duration = duration_cast\u0026lt;microseconds\u0026gt;(end - start); cout \u0026lt;\u0026lt; double(duration.count()) * microseconds::period::num / microseconds::period::den \u0026lt;\u0026lt; endl; return 1;}


推荐阅读


上一篇：互联网造车是传统汽车从业者的末日吗

下一篇：腾讯目前可以做自己的操作系统吗