C++ Array vs Vector Объяснение теста производительности

Question

Чтобы измерить разницу в производительности массива C-like и Векторов в C++, я написал эту небольшую программу. https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

Чтобы сравнить их по общему признаку, я решил проверить как случайный, так и последовательный доступ. Я добавил итераторы, просто чтобы сравнить их (но это не то, на чем сосредоточен вопрос).

Результаты для 64-разрядной машины Linux с 7,7 ГБ ОЗУ с размером массива / вектора 1 миллион выглядят следующим образом:

• Время, необходимое для записи в массив.: 12,0378 мс
• Время, необходимое для чтения из массива последовательно.: 2,44813 мс
• Время, необходимое для чтения из массива в случайном порядке.: 37,3931 мс
• Время, необходимое для записи в динамический массив.: 11,7458 мс
• Время, необходимое для чтения из динамического массива последовательно.: 2,85107 мс
• Время, необходимое для чтения из динамического массива случайным образом.: 36,0579 мс
• Время, необходимое для записи в вектор с использованием индексов.: 11,3909 мс
• Время, необходимое для чтения из вектора с использованием индексов, последовательно.: 4.09106 мс
• Время, затраченное на чтение из вектора с использованием индексов, случайным образом.: 39 мс
• Время, необходимое для записи в вектор с использованием итераторов.: 24.9949 мс
• Время, затраченное на чтение из вектора с использованием итераторов.: 18,8049 мс

Размер вектора устанавливается во время инициализации и не изменяется, поэтому изменение размера вектора не выполняется (утверждение в программе помогает это проверить). Времена не включают время инициализации какого-либо статически распределенного массива, динамически распределенного массива или вектора.

Согласно статистике, время записи в Vector меньше, чем у массива, но время чтения из вектора в два раза больше, чем у массива.

Разница довольно небольшая, но есть ли объяснение, почему существует разница в производительности? Что-то не так с тестом? Я ожидал, что оба будут работать с одинаковой скоростью. Повторение этого теста показывает ту же тенденцию.

Код:

#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
#include <cassert>

#define ARR_SIZE 1000000

using std::string;

void printtime (struct timeval& start, struct timeval& end, string str);   

int main (void)
{
  int arr[ARR_SIZE];
  int tmp;
  struct timeval start, stop;

  srand (time (NULL));

  /* Writing data to array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    arr[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to array."));

  /* Reading data from array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = arr[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from array sequentially."));

  /* Reading data from array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = arr[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from array randomly."));


  int *darr = (int *) calloc (sizeof (int), ARR_SIZE);  

  /* Writing data to array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    darr[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to dynamic array."));

  /* Reading data from array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = darr[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from dynamic array sequentially."));

  /* Reading data from dynamic array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = darr[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from dynamic array randomly."));

  std::vector<int> v(ARR_SIZE);
  assert (v.capacity() == ARR_SIZE);

  /* Writing to vector using indices*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    v[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to vector using indices."));
  assert (v.capacity() == ARR_SIZE);

  /* Reading from vector using indices*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = v[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using indices, sequentially."));

  /* Reading data from dynamic array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = v[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using indices, randomly."));

  std::vector<int> v2(ARR_SIZE);

  /* Writing to vector using iterators*/
  gettimeofday (&start, NULL);
  std::vector<int>::iterator itr, itr_end;
  for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
  {
    *itr = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to vector using iterators."));


  /* Reading from vector using iterators*/
  gettimeofday (&start, NULL);
  for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
  {
    tmp = *itr;
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using iterators."));

  return 0;
}

void printtime (struct timeval& start, struct timeval& end, string str)
{
  double start_time, end_time, diff;

  start_time = ((start.tv_sec) * 1000 + start.tv_usec/1000.0);
  end_time   = ((end.tv_sec) * 1000 + end.tv_usec/1000.0);
  diff = end_time - start_time;

  std::cout << str << " : " << diff << " ms" << std::endl;
}

---

РЕДАКТИРОВАТЬ

Как предлагается в комментариях, здесь больше информации:

• Компилятор:- g++ - 4.5.2
• Флаги: - нет (т.е. значения по умолчанию)
• Оптимизации: - Нет (я хотел протестировать поведение в обычном режиме. Оптимизация может изменить поведение программы, например, поскольку переменная tmp никогда не используется, шаг чтения вектора / массива можно вообще пропустить или уменьшить до только последнее задание. По крайней мере это я так понимаю).

Answer 1

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