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

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 секунд </p>

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

Спасибо

Амаре

Answer 1

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

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

Нажмите здесь для получения дополнительной информации о векторе bool.

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

Нажмите здесь для получения дополнительной информации о прокси-контейнерах (последняя половина о векторе bool)

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

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

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

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

Answer 2

Посмотрите на это

С использованием массивов или std :: vectors в C ++, какой разрыв в производительности?

Answer 3

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

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

Answer 4

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

ДОБАВЛЕНО: В ответ на комментарии позвольте мне показать вам, что я имею в виду. Я использую VC на 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%, потому что он делал это на каждом из нескольких взятых образцов. Могли бы вы догадаться, что именно этим он и занимался почти все свое время? Я не мог иметь.

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

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

В вашей среде он, несомненно, будет другим.