Вектор инициализируется медленнее, чем массив ... почему?

Question

Я попробовал 2 вещи: (псевдокод ниже)

int arr[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

и

vector<int> arr(10000);
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

Я запустил обе программы и рассчитал время, используя команду оболочки "time". Программа 1 запускается за 5 секунд, программа 2 - за 30 секунд. Я запустил обе программы с включенной оптимизацией компилятора, и обе программы запустились примерно в одно и то же время (0,38 с). Я смущен этими результатами. Может кто-нибудь объяснить мне, почему это происходит?

Спасибо!

Answer 1

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

Answer 2

В режиме отладки реализации std::vector обеспечивают большую проверку во время выполнения для простоты использования. Эта проверка недоступна для собственных массивов. Например, в VC2008, если вы скомпилируете пример vector в режиме отладки, в случае operator[].

будет range-checking , даже .

Answer 3

Если ваша неоптимизированная векторная реализация выполняет проверку границ, это будет связано с расхождением.

Answer 4

Это хорошие ответы, но есть быстрый способ выяснить для себя.

Вы видите разницу в производительности 6: 1, верно? Просто запустите медленный и нажмите кнопку «пауза». Тогда посмотрите на стек вызовов. Вероятность того, что он тратит эти 25 дополнительных секунд, составляет 5 из 6 (83%). Сделайте это несколько раз, чтобы получить столько информации, сколько хотите.

Для оптимизированного случая проделайте то же самое с программой 1. Поскольку она в 13 раз медленнее, чем оптимизированная, вы увидите причину каждой «паузы» с вероятностью 12/13 = 92%.

Это применение этой техники .

Answer 5

В ваших примерах массив находится в стеке. Доступ к данным в массиве предполагает доступ к данным в стеке. Это быстро.

С другой стороны, пока vector находится в стеке, данные для std::vector размещаются где-то еще (по умолчанию они размещаются в куче через std::allocator). Доступ к данным в vector предполагает доступ к данным в куче. Это намного медленнее, чем доступ к данным в стеке.

Вы получаете что-то за штраф за производительность. std::vector является расширяемым, а обычный массив - нет. Кроме того, размер std::vector не обязательно должен быть постоянной времени компиляции, в то время как размер массива в стеке имеет значение. Выделенный в куче массив (через operator new[]) не обязательно должен быть константой времени компиляции. Если вы сравните массив, выделенный для кучи, с std::vector, то увидите, что производительность намного ближе.

int* arr = new int[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

delete[] arr; // std::vector does this for you

Answer 6

потому что при записи вектора arr (10000); вы создаете объект, вызываете его функции ... когда и это будет медленнее, чем когда вы создаете int arr [10000];