C++ Vector vs Array (Время)

Question

У меня есть две программы со мной, обе выполняют точно такую ​​же задачу. Они просто устанавливают логический массив/вектор в значение true. Программа, использующая вектор , занимает 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 секунды

Platform - Visual Studio 2008 ОС - Windows Vista 32 бит SP 1 Процессор Intel (R) Pentium (R) Dual CPU T2370 @ 1.73GHz памяти (RAM) 1,00 GB

Благодаря

Амаре

Answer 1

Вы используете зЬй :: вектор BOOL и это не то, что вы думаете!

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

Click here for some info on vector of bool.

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

Click here for more info on proxied containers (Последняя половина о векторе BOOL)

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

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

Я должен был сделать свой цикл намного больше, чтобы проверить на моей машине, но вот две сборки вашего вектора петли BOOL на моей машине, показывающий воздействие оптимизатора флагов на STL код

$ g++ main.cpp 
$ ./a.out 
17 seconds. 
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds. 

Answer 2

Have A смотреть на это

Using arrays or std::vectors in C++, what’s the performance gap?

Answer 3

Другие ответы очень хорошо, но вы могли бы легко ответить на него сами по this method.

ADDED: В ответ на комментарии позвольте мне показать вам, что я имею в виду. Я запускаю VC On Windows, но это работает на любом языке/ОС. Я взял вашу первую программу и увеличил размер до 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, и причина, это провести это время в том, что оператор [] является позвонив оператору begin. Более подробно:

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, но включите отладочную информацию, все эти функции будут отклонены и оптимизированы, поэтому это будет примерно в 30 раз быстрее, и снова стеки показывают, что именно он делает.

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

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

Answer 4

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

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