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-12N-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++ -O2I got no speed up (インライン化された関数を 2M 回呼び出してみる) でコンパイルすると、なぜでしょうか?

4

2 に答える 2

2

乗算は、実行時間の点で加算よりもはるかにコストがかかります。また、プロセッサによっては、加算と乗算が並行して行われます。すなわち。加算の実行中に次の乗算が開始されます ( 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 に答える