C ++ Array vs vector

Question

при использовании вектора C ++ затраченное время составляет 718 миллисекунд, в то время как при использовании массива время составляет почти 0 миллисекунд.

Почему такая большая разница в производительности?

int _tmain(int argc, _TCHAR* argv[])
{
const int size = 10000; 
clock_t start, end; 
start = clock();
vector<int> v(size*size); 
for(int i = 0; i < size; i++)
{  
    for(int j = 0; j < size; j++)
    {   
        v[i*size+j] = 1;  
    } 
} 
end = clock();
cout<< (end - start)
    <<" milliseconds."<<endl; // 718 milliseconds

int f = 0;
start = clock(); 
int arr[size*size]; 
for(int i = 0; i < size; i++)
{  
    for(int j = 0; j < size; j++)
    {   
        arr[i*size+j] = 1;  
    } 
} 
end = clock();
cout<< ( end - start)
    <<" milliseconds."<<endl; // 0 milliseconds
return 0;
}

Answer 1

Ваш массив массив расположен в стеке, т.е. компилятор вычислил необходимое пространство во время компиляции. В начале метода компилятор вставит инструкцию на ассемблере, например

sub esp, 10000*10000*sizeof(int)

, что означает, что указатель стека (esp) уменьшается на 10000 * 10000 * sizeof(int) байт, чтобы освободить место для массива из 10000 ² целых чисел. Эта операция практически мгновенная.

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

Как говорит Андреас в комментариях, все ваше время уходит на эту строку:

vector<int> v(size*size); 

Доступ к вектору внутри цикла такой же быстрый, как и для массива.

Дополнительный обзор см., Например,

• [ Что и где находится стек и куча?

• [http://computer.howstuffworks.com/c28.htm][2]

• [http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html][3]

Edit:

После всех комментариев об оптимизации производительности и настройках компилятора я провел некоторые измерения сегодня утром. Я должен был установить size=3000, поэтому я провел измерения примерно с одной десятой первоначальных записей. Все измерения выполнены на 2,66 ГГц Xeon:

1. При настройках отладки в Visual Studio 2008 (без оптимизации, проверок времени выполнения и времени отладки) векторный тест занял 920 мс по сравнению с 0 мс для теста массива.

   98,48% от общего времени было потрачено на vector::operator[], то есть время действительно было потрачено на проверки во время выполнения.

2. При полной оптимизации для векторного теста потребовалось 56 мс (с одной десятой от исходного числа записей) по сравнению с 0 мс для массива.

   Векторному ктору требовалось 61,72% от общего времени выполнения приложения.

Так что, думаю, все правы в зависимости от используемых настроек компилятора. Синхронизация OP предполагает оптимизированную сборку или STL без проверок во время выполнения.

Как всегда, мораль такова: сначала профиль, второй - оптимизация.

Answer 2

Если вы компилируете это с помощью компилятора Microsoft, чтобы сделать это справедливое сравнение, вам нужно отключить проверки безопасности итератора и отладку итератора, определив _SECURE_SCL = 0 и _HAS_ITERATOR_DEBUGGING = 0.

Во-вторых, используемый вами конструктор инициализирует каждое значение вектора нулем, и вы не устанавливаете массив в ноль перед его заполнением. Итак, вы пересекаете вектор дважды.

Попытка:

vector<int> v; 
v.reserve(size*size);

Answer 3

Чтобы получить справедливое сравнение, я думаю, что должно подойти что-то вроде следующего:

#include <sys/time.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>


int main()
{
  static size_t const size = 7e6;

  timeval start, end;
  int sum;

  gettimeofday(&start, 0);
  {
    std::vector<int> v(size, 1);
    sum = std::accumulate(v.begin(), v.end(), 0);
  }
  gettimeofday(&end, 0);

  std::cout << "= vector =" << std::endl
        << "(" << end.tv_sec - start.tv_sec
        << " s, " << end.tv_usec - start.tv_usec
        << " us)" << std::endl
        << "sum = " << sum << std::endl << std::endl;

  gettimeofday(&start, 0);
  int * const arr =  new int[size];
  std::fill(arr, arr + size, 1);
  sum = std::accumulate(arr, arr + size, 0);
  delete [] arr;
  gettimeofday(&end, 0);

  std::cout << "= Simple array =" << std::endl
        << "(" << end.tv_sec - start.tv_sec
        << " s, " << end.tv_usec - start.tv_usec
        << " us)" << std::endl
        << "sum = " << sum << std::endl << std::endl;
}

В обоих случаях выполняется динамическое распределение и освобождение, а также доступ к элементам.

На моей Linux-коробке:

$ g++ -O2 foo.cpp 
$ ./a.out 
= vector =
(0 s, 21085 us)
sum = 7000000

= Simple array =
(0 s, 21148 us)
sum = 7000000

Оба варианта std::vector<> и массива имеют сопоставимую производительность. Дело в том, что std::vector<> может быть таким же быстрым, как простой массив, если ваш код структурирован надлежащим образом.

---

Для связанной заметки оптимизация отключения имеет огромное значение в этом случае:

$ g++ foo.cpp 
$ ./a.out 
= vector =
(0 s, 120357 us)
sum = 7000000

= Simple array =
(0 s, 60569 us)
sum = 7000000

Многие из утверждений об оптимизации, сделанных такими людьми, как Нил и Джалф, полностью верны.

НТН!

РЕДАКТИРОВАТЬ : исправленный код для принудительного включения вектора разрушения в измерения времени.

Answer 4

Измените присвоение, например, на. arr[i*size+j] = i*j или другое непостоянное выражение. Я думаю, что компилятор оптимизирует весь цикл, так как назначенные значения никогда не используются, или заменяет массив некоторыми предварительно рассчитанными значениями, так что цикл даже не выполняется, и вы получаете 0 миллисекунд.

Изменив 1 на i*j, i получит одинаковое время для вектора и массива, если только не передать флаг -O1 в gcc, тогда в обоих случаях я получу 0 миллисекунд.

Итак, прежде всего, дважды проверьте, действительно ли ваши циклы выполнены.

Answer 5

Вероятно, вы используете VC ++, и в этом случае стандартные библиотечные компоненты по умолчанию выполняют много проверок во время выполнения (например, находится ли индекс в диапазоне). Эти проверки можно отключить, определив некоторые макросы как 0 (я думаю _SECURE_SCL).

Другое дело, что я даже не могу запустить ваш код как есть: автоматический массив слишком велик для стека. Когда я делаю его глобальным, то с MingW 3.5 время, которое я получаю, составляет 627 мс для вектора и 26875 мс (!!) для массива, что указывает на действительно большие проблемы с массивом такого размера.

Что касается этой конкретной операции (заполнение значением 1), вы можете использовать конструктор вектора:

std::vector<int> v(size * size, 1);

и алгоритм заполнения для массива:

std::fill(arr, arr + size * size, 1);

Answer 6

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

Первый вопрос является основным. Для одного миллиона байтов даже перераспределение памяти в дюжину раз не должно занять много времени (это не сработает с каждым добавленным элементом).

В моих экспериментах предварительное распределение не сильно меняет свою медлительность. Когда содержимое является реальным объектом, оно в основном останавливается, если вы пытаетесь сделать что-то простое, например, отсортировать его.

Заключение, не используйте векторы stl или mfc для чего-либо большого или тяжелого для вычислений. Они реализованы плохо / медленно и вызывают большую фрагментацию памяти.

Answer 7

При профилировании кода убедитесь, что вы сравниваете похожие вещи.

vector<int> v(size*size); 

инициализирует каждый элемент в векторе,

int arr[size*size]; 

нет. Попробуйте

int arr[size * size];
memset( arr, 0, size * size );

и измерить снова ...

Answer 8

Когда вы объявляете массив, он живет в стеке (или в статической зоне памяти), что очень быстро, но не может увеличить его размер.

Когда вы объявляете вектор, он назначает динамическую память, которая не такая быстрая, но более гибкая в распределении памяти, так что вы можете изменить размер и не измерять его до максимального размера.