c++ - 优化数学计算(乘法和求和)

Question

假设您要计算项目差异的平方和:

$\sum_{i=1}^{N-1} (x_i - x_{i+1})^2$

最简单的代码(输入为 std::vector<double> xs ，输出为 sum2 )是:

double sum2 = 0.;
double prev = xs[0];
for (vector::const_iterator i = xs.begin() + 1;
 i != xs.end(); ++i)
{
sum2 += (prev - (*i)) * (prev - (*i)); // only 1 - with compiler optimization
prev = (*i);
}

我希望编译器在上面的评论中进行优化。如果N是xs的长度你有 N-1乘法和2N-3总和(总和表示 + 或 - )。

现在假设你知道这个变量:

$x_1^2 + x_N^2 + 2\sum_{i=2}^{N-1} x_i^2$

并称它为sum .展开二项式平方:

$sum_i^{N-1} (x_i-x_{i+1})^2 = sum - 2\sum_{i=1}^{N-1} x_i x_{i+1}$

所以代码变成:

double sum2 = 0.;
double prev = xs[0];
for (vector::const_iterator i = xs.begin() + 1;
 i != xs.end(); ++i)
{
sum2 += (*i) * prev;
prev = (*i);
}
sum2 = -sum2 * 2. + sum;

这里我有 N 次乘法和 N-1 次加法。在我的例子中，N 大约是 100。

嗯，用g++ -O2编译我没有加速(我尝试调用内联函数 2M 次)，为什么？

Answer 1

就执行时间而言，乘法比加法消耗更多。此外，根据处理器的不同，加法和乘法将并行进行。 IE。它将在进行加法时开始下一次乘法(参见 http://en.wikipedia.org/wiki/Out-of-order_execution )。

因此减少添加次数对性能没有太大帮助。

您可以做的是让编译器更容易对您的代码进行矢量化，或者您自己进行矢量化。为了让编译器更容易进行矢量化，我会使用常规的 double 组，使用下标而不是指针。

编辑:N = 100 也可能是一个很小的数字，可以看出执行时间的差异。尝试大 N。

脏代码但显示性能改进。输出:

1e+06
59031558
1e+06
18710703

您获得的加速约为 3 倍。

#include <vector>
#include <iostream>

using namespace std;

unsigned long long int rdtsc(void)
{
  unsigned long long int x;
  unsigned a, d;

  __asm__ volatile("rdtsc" : "=a" (a), "=d" (d));

  return ((unsigned long long)a) | (((unsigned long long)d) << 32);;
}



double f(std::vector<double>& xs)
{
  double sum2 = 0.;
  double prev = xs[0];

  vector<double>::const_iterator iend = xs.end();
  for (vector<double>::const_iterator i = xs.begin() + 1;
       i != iend; ++i)
    {
      sum2 += (prev - (*i)) * (prev - (*i)); // only 1 - with compiler optimization
      prev = (*i);
    }

  return sum2;
}

double f2(double *xs, int N)
{
  double sum2 = 0;

  for(int i = 0; i < N - 1; i+=1) {
    sum2 += (xs[i+1] - xs[i])*(xs[i+1] - xs[i]);

  }

  return sum2;
}

int main(int argc, char* argv[])
{
  int N = 1000001;
  std::vector<double> xs;
  for(int i=0; i<N; i++) {
    xs.push_back(i);
  }

  unsigned long long int a, b;
  a = rdtsc();
  std::cout << f(xs) << endl;
  b = rdtsc();
  cout << b - a << endl;

  a = rdtsc();
  std::cout << f2(&xs[0], N) << endl;
  b = rdtsc();
  cout << b - a << endl;
}