2

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

$\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 次），为什么？

4

2 回答 2

2

就执行时间而言，乘法比加法成本高得多。此外，根据处理器的不同，加法和乘法将并行完成。IE。它将在进行加法时开始下一次乘法（请参阅http://en.wikipedia.org/wiki/Out-of-order_execution）。

所以减少添加的数量对性能没有多大帮助。

你可以做的是让编译器更容易向量化你的代码，或者自己向量化。为了使编译器更容易向量化，我将使用常规的双精度数组，使用下标而不是指针。

编辑：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;
}
于 2010-05-15T17:00:57.520 回答
1

当 x+=a*b 完成时，加法是免费的。如果架构支持，编译器应该能够在第一个版本中解决这个问题。

数学可能同时发生*i，可能会更慢。

xs.end()除非您期望返回值发生变化，否则不要在每次循环迭代时调用。如果编译器无法对其进行优化，它将使循环的其余部分相形见绌。

于 2010-05-15T17:07:50.460 回答