У меня вопрос. Учитывая следующий фрагмент кода C ++:
#include <boost/progress.hpp>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
struct incrementor
{
incrementor() : curr_() {}
unsigned int operator()()
{ return curr_++; }
private:
unsigned int curr_;
};
template<class Vec>
char const* value_found(Vec const& v, typename Vec::const_iterator i)
{
return i==v.end() ? "no" : "yes";
}
template<class Vec>
typename Vec::const_iterator find1(Vec const& v, typename Vec::value_type val)
{
return find(v.begin(), v.end(), val);
}
template<class Vec>
typename Vec::const_iterator find2(Vec const& v, typename Vec::value_type val)
{
for(typename Vec::const_iterator i=v.begin(), end=v.end(); i<end; ++i)
if(*i==val) return i;
return v.end();
}
int main()
{
using namespace std;
typedef vector<unsigned int>::const_iterator iter;
vector<unsigned int> vec;
vec.reserve(10000000);
boost::progress_timer pt;
generate_n(back_inserter(vec), vec.capacity(), incrementor());
//added this line, to avoid any doubts, that compiler is able to
// guess the data is sorted
random_shuffle(vec.begin(), vec.end());
cout << "value generation required: " << pt.elapsed() << endl;
double d;
pt.restart();
iter found=find1(vec, vec.capacity());
d=pt.elapsed();
cout << "first search required: " << d << endl;
cout << "first search found value: " << value_found(vec, found)<< endl;
pt.restart();
found=find2(vec, vec.capacity());
d=pt.elapsed();
cout << "second search required: " << d << endl;
cout << "second search found value: " << value_found(vec, found)<< endl;
return 0;
}
На моей машине (Intel i7, Windows Vista) поиск STL (вызов через find1) выполняется примерно в 10 раз быстрее, чем цикл, созданный вручную (вызов через find2). Сначала я подумал, что Visual C ++ выполняет какую-то векторизацию (возможно, я здесь ошибаюсь), но, насколько я могу судить, сборка не выглядит так, как использует векторизацию. Почему цикл STL быстрее? Цикл, созданный вручную, идентичен циклу из тела поиска STL.
Меня попросили опубликовать вывод программы. Без перемешивания:
value generation required: 0.078
first search required: 0.008
first search found value: no
second search required: 0.098
second search found value: no
При случайном воспроизведении (эффекты кеширования):
value generation required: 1.454
first search required: 0.009
first search found value: no
second search required: 0.044
second search found value: no
Большое спасибо,
душа.
P.S. Я возвращаю итератор и записываю результат (найден он или нет), потому что я хотел бы предотвратить оптимизацию компилятора, поскольку он считает, что цикл вообще не требуется. Очевидно, искомое значение отсутствует в векторе.
P.P.S. Меня попросили опубликовать сборку, созданную для функций поиска. Вот:
found=find1(vec, vec.capacity());
001811D0 lea eax,[esp+5Ch]
001811D4 call std::vector<unsigned int,std::allocator<unsigned int> >::capacity (1814D0h)
001811D9 mov esi,dword ptr [esp+60h]
001811DD mov ecx,dword ptr [esp+64h]
001811E1 cmp esi,ecx
001811E3 je wmain+180h (1811F0h)
001811E5 cmp dword ptr [esi],eax
001811E7 je wmain+180h (1811F0h)
001811E9 add esi,4
001811EC cmp esi,ecx
001811EE jne wmain+175h (1811E5h)
found=find2(vec, vec.capacity());
001812AE lea eax,[esp+5Ch]
001812B2 call std::vector<unsigned int,std::allocator<unsigned int> >::capacity (1814D0h)
001812B7 mov ecx,dword ptr [esp+60h]
001812BB mov edx,dword ptr [esp+64h]
001812BF cmp ecx,edx
001812C1 je wmain+262h (1812D2h)
001812C3 cmp dword ptr [ecx],eax
001812C5 je wmain+34Fh (1813BFh)
001812CB add ecx,4
001812CE cmp ecx,edx
001812D0 jne wmain+253h (1812C3h)
find2 использует регистр ecx вместо esi. В чем разница между этими двумя регистрами? Может ли быть, что esi предполагает, что указатель правильно выровнен и, следовательно, обеспечивает дополнительную производительность?
Прочтите некоторую ссылку на сборку. Ecx - это просто счетчик, а esi - источник памяти. Поэтому я думаю, что алгоритм STL знает, что итератор произвольного доступа правильно выровнен и поэтому использует указатели памяти. Где в версии, отличной от STL, нет никаких предположений о том, как происходит выравнивание. Я прав?
i<endИспользуйтеi != end- person Martin York schedule 03.01.2011:)А как насчет stddev? - person Matteo Italia schedule 03.01.2011