Вектор C++ по сравнению с массивом (время)

У меня есть здесь две программы со мной, оба делают точно ту же задачу. Они просто устанавливают булев массив / вектор к верному значению. Программа с помощью вектора занимает 27 секунд для выполнения, тогда как программа, связавшая массив с в 5 раз большим размером, занимает меньше чем 1 с. Я хотел бы знать точную причину, относительно того, почему существует такое существенное различие? Действительно настолько неэффективны векторы?

Программа с помощью векторов

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main(){
 const int size = 2000;
 time_t start, end;
 time(&start);
 vector<bool> v(size);
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

Время выполнения - 27 секунд

Программа с помощью Массива

#include <iostream>
#include <ctime>

using namespace std;

int main(){
 const int size = 10000; // 5 times more size
 time_t start, end;
 time(&start);
 bool v[size];
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

Время выполнения - <1 секунда

Платформа - ОС Visual Studio 2008 - процессор SP 1 Windows Vista 32 битов Intel(R) Pentium(R) Dual CPU T2370 Память на 1.73 ГГц (RAM) 1,00 ГБ

Спасибо

Amare

10
задан user235022 19 December 2009 в 07:02
поделиться

4 ответа

Вы используете std :: vector of bool, и это не то, что вы думаете!

vector of bool - это незаконченная дочерняя специализация шаблона, которой никогда не должно было существовать и на самом деле хранит 1 bool в каждом бите. Доступ к нему более сложен из-за логики маскирования и сдвига, поэтому он определенно будет несколько медленнее.

Щелкните здесь, чтобы получить некоторую информацию о векторе bool.

Кроме того, вы можете запускать неоптимизированную сборку (почти наверняка с учетом раз вы перечислили, 27 секунд возмутительно для 4 миллионов итераций). Стандартная библиотека шаблонов очень сильно полагается на оптимизатор, выполняя такие вещи, как вызов встроенных функций и удаление временных файлов. Отсутствие этой оптимизации приводит к особенно сильному снижению производительности для вектора bool, потому что он должен возвращать прокси-объект, когда вы индексируете его, потому что вы можете ' t принимает адрес бита, поэтому оператор [] не может вернуть ссылку.

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

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

После того, как вы включите оптимизатор, получите правильные настройки (т. Е. Не включена отладка STL) и фактически тестируете одно и то же в обоих циклах, вы почти не увидит разницы.

Мне пришлось сделать ваш цикл намного больше, чтобы протестировать его на моей машине, но вот две сборки вашего вектора цикла bool на моей машине, показывает влияние флагов оптимизатора на код STL

$ g++ main.cpp 
$ ./a.out 
17 seconds.
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds.
41
ответ дан 3 December 2019 в 13:34
поделиться

std::vector оптимизирован на потребление памяти, а не на производительность.

Его можно обмануть, используя std::vector. Тогда у вас не должно быть недостатков в производительности

.
1
ответ дан 3 December 2019 в 13:34
поделиться

Другие ответы очень хороши, но вы можете легко ответить на них сами с помощью этого метода .

ДОБАВЛЕНИЕ: В ответ на комментарии позвольте мне показать вам, что я имею в виду. Я запускаю VC под Windows, но это работает на любом языке/OS. Я взял вашу первую программу и увеличил ее размер до 20000, чтобы она работала достаточно долго. Потом, пока она работала, я сделал несколько стэкшотов. Все они выглядят следующим образом:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes
std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes
main() line 24 + 12 bytes
mainCRTStartup() line 206 + 25 bytes
KERNEL32! 7c817077()

Итак, это говорит о том, что он тратит по существу все своего времени в операции индексации на 24 линии, и причина, по которой он тратит это время, заключается в том, что оператор [] вызывает оператор start. Подробнее:

main() line 24 + 12 bytes

- вот этот код:

for(int j = 0; j < size; j++){
==> v[i] = true;
}

- вызывающий:

std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes

- вот этот код (который я немного переформатировал):

reference operator[](size_type _P){
==> return (*(begin() + _P));
}

- вызывающий:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes

-действующий (подробнее):

92:       iterator begin()
93:           {return (_First); }
00402890   push        ebp
00402891   mov         ebp,esp
00402893   sub         esp,44h
00402896   push        ebx
00402897   push        esi
00402898   push        edi
00402899   push        ecx
0040289A   lea         edi,[ebp-44h]
0040289D   mov         ecx,11h
004028A2   mov         eax,0CCCCCCCCh
004028A7   rep stos    dword ptr [edi]
004028A9   pop         ecx    <===============
004028AA   mov         dword ptr [ebp-4],ecx
004028AD   mov         eax,dword ptr [ebp-4]
004028B0   mov         eax,dword ptr [eax+4]
004028B3   pop         edi
004028B4   pop         esi
004028B5   pop         ebx
004028B6   mov         esp,ebp
004028B8   pop         ebp
004028B9   ret

Что он делает, так это записывает 68 байт 0xCC на стеке (по какой-то отладочной причине), как часть получения адреса begin вектора, как часть вычисления адреса v[i], перед выполнением присваивания.

Доля времени, затрачиваемая на это, составляет почти 100%, так как она делала это на каждом из нескольких отсчетов, которые были взяты. Могли бы вы догадаться, что именно на это он тратит почти все свое время? Я бы не смог.

Это, конечно, отладочная конструкция. Если вы переключитесь на Release build, но включите отладочную информацию, то все эти функции будут отлаживаться и оптимизироваться, так что все пойдет в 30 раз быстрее, и снова стековые снимки точно скажут, что он делает.

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

В вашем окружении он, несомненно, будет отличаться.

1
ответ дан 3 December 2019 в 13:34
поделиться
Другие вопросы по тегам:

Похожие вопросы: