c++ Eigen在乘小矩阵时很慢吗?

nbnkbykc  于 2023-05-30  发布在  其他
关注(0)|答案(3)|浏览(182)

我写了一个函数,将维数为10 x10的特征矩阵相乘。然后我写了一个简单的乘法函数CustomMultiply,它比Eigen的实现快了2倍。
我尝试了几个不同的编译标志,如-O2和-O3,这并没有什么区别。

#include <Eigen/Core>

  constexpr int dimension = 10;
  using Matrix = Eigen::Matrix<double, dimension, dimension>;

  Matrix CustomMultiply(const Matrix& a, const Matrix& b) {
    Matrix result = Matrix::Zero();
    for (int bcol_idx = 0; bcol_idx < dimension; ++bcol_idx) {
      for (int brow_idx = 0; brow_idx < dimension; ++brow_idx) {
        result.col(bcol_idx).noalias() += a.col(brow_idx) * b(brow_idx, bcol_idx);
      }
    }
    return result;
  }

  Matrix PairwiseMultiplyEachMatrixNoAlias(int num_repetitions, const std::vector<Matrix>& input) {
    Matrix acc = Matrix::Zero();
    for (int i = 0; i < num_repetitions; ++i) {
      for (const auto& matrix_a : input) {
        for (const auto& matrix_b : input) {
          acc.noalias() += matrix_a * matrix_b;
        }
      }
    }
    return acc;
  }

  Matrix PairwiseMultiplyEachMatrixCustom(int num_repetitions, const std::vector<Matrix>& input) {
    Matrix acc = Matrix::Zero();
    for (int i = 0; i < num_repetitions; ++i) {
      for (const auto& matrix_a : input) {
        for (const auto& matrix_b : input) {
          acc.noalias() += CustomMultiply(matrix_a, matrix_b);
        }
      }
    }
    return acc;
  }

在我的机器上,当我传入100个随机矩阵作为input并使用100作为num_repetitions时,PairwiseMultiplyEachMatrixNoAliasPairwiseMultiplyEachMatrixCustom慢2倍。我的机器详细信息:Intel Xeon CPU E5-2630 v4,Ubuntu 16.04,Eigen 3
更新:在评论中进行有益讨论后,进行以下修改后,结果不变

  • num_repetitions = 1input.size() = 1000
  • 使用.lazyProduct()和使用.eval()实际上会导致进一步的减速
  • clang 8.0.0
  • g++ 9.2
  • 使用标志-march=native -DNDEBUG

更新2:
在Google Benchmark库中跟踪@dtell的发现后,我发现了一个有趣的结果。将2个矩阵与特征值相乘比自定义快,但将许多矩阵与特征值相乘慢2倍,与之前的发现一致。
这是我的Google Benchmark代码。(注意:下面的GenerateRandomMatrices()函数中有一个off-by,现在已修复。

#include <Eigen/Core>
#include <Eigen/StdVector>
#include <benchmark/benchmark.h>

constexpr int dimension = 10;
constexpr int num_random_matrices = 10;
using Matrix = Eigen::Matrix<double, dimension, dimension>;
using Eigen_std_vector = std::vector<Matrix,Eigen::aligned_allocator<Matrix>>;

Eigen_std_vector GetRandomMatrices(int num_matrices) {
  Eigen_std_vector matrices;
  for (int i = 0; i < num_matrices; ++i) {
    matrices.push_back(Matrix::Random());
  }
  return matrices;
}

Matrix CustomMultiply(const Matrix& a, const Matrix& b) {
  Matrix result = Matrix::Zero();
  for (int bcol_idx = 0; bcol_idx < dimension; ++bcol_idx) {
    for (int brow_idx = 0; brow_idx < dimension; ++brow_idx) {
      result.col(bcol_idx).noalias() += a.col(brow_idx) * b(brow_idx, bcol_idx);
    }
  }
  return result;
}

Matrix PairwiseMultiplyEachMatrixNoAlias(int num_repetitions, const Eigen_std_vector& input) {
  Matrix acc = Matrix::Zero();
  for (int i = 0; i < num_repetitions; ++i) {
    for (const auto& matrix_a : input) {
      for (const auto& matrix_b : input) {
        acc.noalias() += matrix_a * matrix_b;
      }
    }
  }
  return acc;
}

Matrix PairwiseMultiplyEachMatrixCustom(int num_repetitions, const Eigen_std_vector& input) {
  Matrix acc = Matrix::Zero();
  for (int i = 0; i < num_repetitions; ++i) {
    for (const auto& matrix_a : input) {
      for (const auto& matrix_b : input) {
        acc.noalias() += CustomMultiply(matrix_a, matrix_b);
      }
    }
  }
  return acc;
}

void BM_PairwiseMultiplyEachMatrixNoAlias(benchmark::State& state) {
  // Perform setup here
  const auto random_matrices = GetRandomMatrices(num_random_matrices);
  for (auto _ : state) {
    benchmark::DoNotOptimize(PairwiseMultiplyEachMatrixNoAlias(1, random_matrices));
  }
}
BENCHMARK(BM_PairwiseMultiplyEachMatrixNoAlias);

void BM_PairwiseMultiplyEachMatrixCustom(benchmark::State& state) {
  // Perform setup here
  const auto random_matrices = GetRandomMatrices(num_random_matrices);
  for (auto _ : state) {
    benchmark::DoNotOptimize(PairwiseMultiplyEachMatrixCustom(1, random_matrices));
  }
}
BENCHMARK(BM_PairwiseMultiplyEachMatrixCustom);

void BM_MultiplySingle(benchmark::State& state) {
  // Perform setup here
  const auto random_matrices = GetRandomMatrices(2);
  for (auto _ : state) {
    benchmark::DoNotOptimize((random_matrices[0] * random_matrices[1]).eval());
  }
}
BENCHMARK(BM_MultiplySingle);

void BM_MultiplySingleCustom(benchmark::State& state) {
  // Perform setup here
  const auto random_matrices = GetRandomMatrices(2);
  for (auto _ : state) {
    benchmark::DoNotOptimize(CustomMultiply(random_matrices[0], random_matrices[1]));
  }
}
BENCHMARK(BM_MultiplySingleCustom);


double TestCustom() {
  const Matrix a = Matrix::Random();
  const Matrix b = Matrix::Random();

  const Matrix c = a * b;
  const Matrix custom_c = CustomMultiply(a, b);

  const double err = (c - custom_c).squaredNorm();
  return err;
}

// Just sanity check the multiplication
void BM_TestCustom(benchmark::State& state) {
  if (TestCustom() > 1e-10) {
    exit(-1);
  }
}
BENCHMARK(BM_TestCustom);

这就产生了以下神秘的报告

Run on (20 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x10)
  L1 Instruction 32K (x10)
  L2 Unified 256K (x10)
  L3 Unified 25600K (x1)
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
----------------------------------------------------------------------------
Benchmark                                     Time           CPU Iterations
----------------------------------------------------------------------------
BM_PairwiseMultiplyEachMatrixNoAlias      28283 ns      28285 ns      20250
BM_PairwiseMultiplyEachMatrixCustom       14442 ns      14443 ns      48488
BM_MultiplySingle                           791 ns        791 ns     876969
BM_MultiplySingleCustom                     874 ns        874 ns     802052
BM_TestCustom                                 0 ns          0 ns          0

我目前的假设是,减速是由于指令缓存未命中。这可能是Eigen的矩阵乘法函数对指令缓存做了不好的事情。
VTune自定义输出:

本征的VTune输出:

也许对VTune更有经验的人可以告诉我,我是否正确地解释了这个结果。DSB是解码的指令高速缓存,MITE与指令解码器带宽有关。本征版本表明,大多数指令丢失DSB(66%的未命中率),并且由于MITE带宽而导致停顿显著增加。
更新3:在得到自定义的单一版本更快的报告后,我也在我的机器上复制了它。这与@dtell在他们的机器上的最初发现背道而驰。

CPU Caches:
  L1 Data 32K (x10)
  L1 Instruction 32K (x10)
  L2 Unified 256K (x10)
  L3 Unified 25600K (x1)
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
----------------------------------------------------------------------------
Benchmark                                     Time           CPU Iterations
----------------------------------------------------------------------------
BM_PairwiseMultiplyEachMatrixNoAlias      34787 ns      34789 ns      16477
BM_PairwiseMultiplyEachMatrixCustom       17901 ns      17902 ns      37759
BM_MultiplySingle                           349 ns        349 ns    2054295
BM_MultiplySingleCustom                     178 ns        178 ns    4624183
BM_TestCustom                                 0 ns          0 ns          0

我想知道在我以前的基准测试结果中是否遗漏了一个优化标志。在任何情况下,我认为这个问题被证实,本征在乘以小矩阵时会产生开销。如果有人有一台不使用uop缓存的机器,我会有兴趣看看减速是否不那么严重。

ttisahbt

ttisahbt1#

(gdb) bt
#0  0x00005555555679e3 in Eigen::internal::gemm_pack_rhs<double, long, Eigen::internal::const_blas_data_mapper<double, long, 0>, 4, 0, false, false>::operator()(double*, Eigen::internal::const_blas_data_mapper<double, long, 0> const&, long, long, long, long) ()
#1  0x0000555555566654 in Eigen::internal::general_matrix_matrix_product<long, double, 0, false, double, 0, false, 0>::run(long, long, long, double const*, long, double const*, long, double*, long, double, Eigen::internal::level3_blocking<double, double>&, Eigen::internal::GemmParallelInfo<long>*) ()
#2  0x0000555555565822 in BM_PairwiseMultiplyEachMatrixNoAlias(benchmark::State&) ()
#3  0x000055555556d571 in benchmark::internal::(anonymous namespace)::RunInThread(benchmark::internal::Benchmark::Instance const*, unsigned long, int, benchmark::internal::ThreadManager*) ()
#4  0x000055555556b469 in benchmark::RunSpecifiedBenchmarks(benchmark::BenchmarkReporter*, benchmark::BenchmarkReporter*) ()
#5  0x000055555556a450 in main ()

从堆栈跟踪,特征的矩阵乘法是使用一个通用的乘法方法和循环通过一个动态的矩阵大小。对于自定义实现,clang积极地对其进行向量化并展开循环,因此分支要少得多。
也许有一些标志/选项用于eigen生成此特定大小的代码以进行优化。
但是,如果矩阵大小更大,本征版本的性能将比自定义版本好得多。

zpf6vheq

zpf6vheq2#

我已经使用适当的基准库(即Google Benchmark)重写了您的代码,无法重现您的测量结果。
我对-O0的结果,其中第二个模板参数是矩阵维数:

Running ./benchmark
Run on (12 X 2900 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 262K (x6)
  L3 Unified 12582K (x1)
---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
BM_CustomMultiply<double, 3>        5391 ns       5389 ns     105066
BM_CustomMultiply<double, 4>        9365 ns       9364 ns      73649
BM_CustomMultiply<double, 5>       15349 ns      15349 ns      44008
BM_CustomMultiply<double, 6>       20953 ns      20947 ns      32230
BM_CustomMultiply<double, 7>       33328 ns      33318 ns      21584
BM_CustomMultiply<double, 8>       44237 ns      44230 ns      15500
BM_CustomMultiply<double, 9>       57142 ns      57140 ns      11953
BM_CustomMultiply<double, 10>      69382 ns      69382 ns       9998
BM_EigenMultiply<double, 3>         2335 ns       2335 ns     295458
BM_EigenMultiply<double, 4>         1613 ns       1613 ns     457382
BM_EigenMultiply<double, 5>         4791 ns       4791 ns     142992
BM_EigenMultiply<double, 6>         3471 ns       3469 ns     206002
BM_EigenMultiply<double, 7>         9052 ns       9051 ns      78135
BM_EigenMultiply<double, 8>         8655 ns       8655 ns      81717
BM_EigenMultiply<double, 9>        11446 ns      11399 ns      67001
BM_EigenMultiply<double, 10>       15092 ns      15053 ns      46924

正如您所看到的,Google Benchmark使用的迭代次数比您的基准测试高出一个数量级。微基准测试是非常困难的,特别是当你处理几百纳秒的执行时间时。
公平地说,调用自定义函数涉及到一个副本,手动内联它会产生几纳秒的时间,但仍然不能击败Eigen。
使用手动内联CustomMultiply-O2 -DNDEBUG -march=native进行测量:

Running ./benchmark
Run on (12 X 2900 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 262K (x6)
  L3 Unified 12582K (x1)
---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
BM_CustomMultiply<double, 3>          51 ns         51 ns   11108114
BM_CustomMultiply<double, 4>          88 ns         88 ns    7683611
BM_CustomMultiply<double, 5>         147 ns        147 ns    4642341
BM_CustomMultiply<double, 6>         213 ns        213 ns    3205627
BM_CustomMultiply<double, 7>         308 ns        308 ns    2246391
BM_CustomMultiply<double, 8>         365 ns        365 ns    1904860
BM_CustomMultiply<double, 9>         556 ns        556 ns    1254953
BM_CustomMultiply<double, 10>        661 ns        661 ns    1027825
BM_EigenMultiply<double, 3>           39 ns         39 ns   17918807
BM_EigenMultiply<double, 4>           69 ns         69 ns    9931755
BM_EigenMultiply<double, 5>          119 ns        119 ns    5801185
BM_EigenMultiply<double, 6>          178 ns        178 ns    3838772
BM_EigenMultiply<double, 7>          256 ns        256 ns    2692898
BM_EigenMultiply<double, 8>          385 ns        385 ns    1826598
BM_EigenMultiply<double, 9>          546 ns        546 ns    1271687
BM_EigenMultiply<double, 10>         644 ns        644 ns    1104798
q9rjltbz

q9rjltbz3#

因为特征值将把矩阵压缩到小矩阵上,如果矩阵不回退到gemv。封装矩阵引入其他开销。

相关问题