оптимизация математических вычислений (умножение и суммирование) - PullRequest
Новая
       17

оптимизация математических вычислений (умножение и суммирование)

2 голосов
/ 15 мая 2010

Предположим, вы хотите вычислить сумму квадратов разностей предметов:

$ \ 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 раз), почему?

Ответы [ 2 ]

2 голосов
/ 15 мая 2010

Умножения намного дороже, чем сложения по времени выполнения. Также в зависимости от процессора сложения и умножения будут выполняться параллельно. То есть. во время сложения начнется следующее умножение (см. 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;
}
1 голос
/ 15 мая 2010

Добавление может быть бесплатным, если сделано как x + = a * b. Компилятор должен быть способен выяснить это в первой версии, если архитектура поддерживает это.

Математика, вероятно, происходит параллельно с *i, который может быть медленнее.

Не вызывайте xs.end() на каждой итерации цикла, если только вы не ожидаете изменения возвращаемого значения. Если компилятор не может оптимизировать его, он затмит остальную часть цикла.

...