Подтвердить что ты не робот

Почему массив C намного быстрее, чем std:: array?

В настоящее время мы пишем некоторый критический код производительности на С++, который работает на многих больших матрицах и векторах. Что касается наших исследований, не должно быть существенной разницы в производительности между std::array и стандартными массивами C (См. Этот вопрос или this). Тем не менее, во время тестирования мы испытали огромное улучшение производительности, используя массивы C над std::array. Это наш демо-код:

#include <iostream>
#include <array>
#include <sys/time.h>

#define ROWS 784
#define COLS 100
#define RUNS 50

using std::array;

void DotPComplex(array<double, ROWS> &result, array<double, ROWS> &vec1, array<double, ROWS> &vec2){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void DotPSimple(double result[ROWS], double vec1[ROWS], double vec2[ROWS]){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void MatMultComplex(array<double, ROWS> &result, array<array<double, COLS>, ROWS> &mat, array<double, ROWS> &vec){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

void MatMultSimple(double result[ROWS], double mat[ROWS][COLS], double vec[ROWS]){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

double getTime(){
    struct timeval currentTime;
    gettimeofday(&currentTime, NULL);
    double tmp = (double)currentTime.tv_sec * 1000.0 + (double)currentTime.tv_usec/1000.0;
    return tmp;
}

array<double, ROWS> inputVectorComplex = {{ 0 }};
array<double, ROWS> resultVectorComplex = {{ 0 }};
double inputVectorSimple[ROWS] = { 0 };
double resultVectorSimple[ROWS] = { 0 };

array<array<double, COLS>, ROWS> inputMatrixComplex = {{0}};
double inputMatrixSimple[ROWS][COLS] = { 0 };

int main(){
  double start;
  std::cout << "DotP test with C array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPSimple(resultVectorSimple, inputVectorSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "DotP test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPComplex(resultVectorComplex, inputVectorComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C array : " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultSimple(resultVectorSimple, inputMatrixSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultComplex(resultVectorComplex, inputMatrixComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;
}

Скомпилировано с помощью: icpc demo.cpp -std=c++11 -O0 Это результат:

DotP test with C array: 
Duration: 0.289795 ms
DotP test with C++ array: 
Duration: 1.98413 ms
MatMult test with C array : 
Duration: 28.3459 ms
MatMult test with C++ array: 
Duration: 175.15 ms

С флагом -O3:

DotP test with C array: 
Duration: 0.0280762 ms
DotP test with C++ array: 
Duration: 0.0288086 ms
MatMult test with C array : 
Duration: 1.78296 ms
MatMult test with C++ array: 
Duration: 4.90991 ms

Реализация массива C намного быстрее без оптимизации компилятора. Зачем? Используя оптимизацию компилятора, точечные продукты одинаково быстры. Но для матричного умножения по-прежнему наблюдается значительное ускорение при использовании C-массивов. Есть ли способ достичь равной производительности при использовании std::array?


Update:

Используемый компилятор: icpc 17.0.0

С gcc 4.8.5 наш код работает намного медленнее, чем с компилятором Intel, используя любой уровень оптимизации. Поэтому нас в основном интересует поведение компилятора Intel.

Как было предложено Jonas, мы скорректировали RUNS 50.000 со следующими результатами (компилятор Intel):

С флагом -O0:

DotP test with C array: 
Duration: 201.764 ms
DotP test with C++ array: 
Duration: 1020.67 ms
MatMult test with C array : 
Duration: 15069.2 ms
MatMult test with C++ array: 
Duration: 123826 ms

С флагом -O3:

DotP test with C array: 
Duration: 16.583 ms
DotP test with C++ array: 
Duration: 15.635 ms
MatMult test with C array : 
Duration: 980.582 ms
MatMult test with C++ array: 
Duration: 2344.46 ms
4b9b3361

Ответ 1

Во-первых, количество прогонов, которые вы используете, просто слишком мало. Лично я не понимал (до запуска кода), что ваши измерения продолжительности " miliseconds

Увеличивая RUNS до 5 000 000 для DotPSimple и DotPComplex, время выглядит примерно так:

Тест DotP с массивом C:

Продолжительность: 1074.89

Тест DotP с массивом С++:

Продолжительность: 1085.34

То есть, они очень близки к тому, чтобы быть одинаково быстрыми. Фактически, который когда-либо был самым быстрым, он отличался от теста к тесту, из-за стохастического характера эталона. То же самое было верно для MatMultSimple и MatMultComplex, хотя им потребовалось всего 50 000 прогонов.

Если вы действительно хотите измерить и узнать больше, вы должны принять стохастический характер этого теста и приблизиться к распределениям измерений "Длительность". Включая случайный порядок функций, чтобы удалить смещение порядка.

EDIT: код сборки (из ответа user2079303) полностью доказывают, что нет никаких различий в оптимизации. Таким образом, абстракции с нулевой стоимостью фактически являются нулевыми с оптимизацией, что является разумным требованием.

UPDATE:

Используемый мною компилятор:

g++ (Debian 6.3.0-6) 6.3.0 20170205

Со следующей командой:

g++ -Wall -Wextra -pedantic -O3 test.cpp

Использование этого процессора:

Intel(R) Core(TM) i5-4300U CPU @ 1.90GHz

Ответ 2

почему... намного быстрее без оптимизации компилятора. Почему?

По какой-то причине компилятор выбирает. Если вы не позволяете компилятору оптимизировать, то вы не можете ожидать, что две разные части кода будут иметь схожую производительность, даже если они имеют одинаковое поведение. Когда оптимизация включена, компилятор может преобразовать абстрактный код в эффективный, и производительность должна быть сопоставимой.

Использование std::array включает вызовы функций, в которых использование указателя не выполняется. Например, std::array::operator[] - это функция, а индексный оператор указателя - нет. Выполнение вызова функции потенциально медленнее, чем вызов функции. Все эти вызовы функций можно оптимизировать (расширенный встроенный), но если вы решите не включать оптимизацию, то вызовы функций остаются.

Но для матричного умножения при использовании C-массивов все еще существует значительное ускорение.

Вероятно, причуда в вашем тесте или компиляторе. Здесь обе функции имеют идентичную сборку, и поэтому имеют идентичную производительность

EDIT: Я согласен с ответом Джонаса. В эталоне слишком много итераций. Кроме того, невозможно сказать, является ли разница между двумя измерениями значимой без повторения эталона и анализа отклонения.


Конкусионы:

  • Массив C не быстрее, чем std::array, когда оптимизация включена. По крайней мере, не при компиляции с clang 3.9.1, как показано ссылкой. Возможно, ваш компилятор создает разные сборки, но я не вижу причин, почему это должно быть.

  • Абстракции нулевой стоимости С++ равны нулю только после оптимизации.

  • Написание значимых микро-тестов не является тривиальным.