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

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; 
    } 
} 

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

Спасибо!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Это хорошие ответы, но есть быстрый способ, который вы можете узнать сами.

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

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

Это приложение this technique.