У меня есть здесь две программы со мной, оба делают точно ту же задачу. Они просто устанавливают булев массив / вектор к верному значению. Программа с помощью вектора занимает 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
Вы используете 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.
Взгляните на это
Использование массивов или std :: vectors в C ++, каков разрыв в производительности?
std::vector
оптимизирован на потребление памяти, а не на производительность.
Его можно обмануть, используя std::vector
. Тогда у вас не должно быть недостатков в производительности
Другие ответы очень хороши, но вы можете легко ответить на них сами с помощью этого метода .
ДОБАВЛЕНИЕ: В ответ на комментарии позвольте мне показать вам, что я имею в виду. Я запускаю 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 раз быстрее, и снова стековые снимки точно скажут, что он делает.
Итак - люди могут рассказать вам, что он может делать, но это покажет , как узнать для себя , что он на самом деле делает.
В вашем окружении он, несомненно, будет отличаться.