STL find работает лучше, чем созданный вручную цикл

Question

У меня есть вопрос. Учитывая следующий фрагмент кода 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 find (вызов через find1) работает примерно в 10 раз быстрее, чем созданный вручную цикл (вызов через find2). Сначала я подумал, что Visual C ++ выполняет некоторую векторизацию (возможно, я здесь ошибаюсь), но насколько я вижу, сборка не выглядит так, как она использует векторизацию. Почему цикл STL быстрее? Ручная петля идентична петле из тела STL-find.

Меня попросили опубликовать вывод программы. Без перемешивания:

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

Большое спасибо,

Dusha.

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 версии нет предположений, как выравнивание. Я прав?

Answer 1

Алгоритм find Visual C ++ использует непроверенные итераторы, в то время как ваш рукописный цикл использует проверенные итераторы.

Мое другое предположение - вы вызываете std::vector<t>::end() на каждой итерации циклав find2, тогда как std::find приводит только к одному вызову начальных и конечных методов доступа. Я идиот.

Answer 2

Убедитесь, что вы компилируете свой код в режиме выпуска с проверенными итераторами выключен

Установите _SECURE_SCL = 0 в определениях вашего препроцессора.

Кроме того, boost ::Полагаю, у progress_timer есть разрешение в миллисекундах (оно основано на std :: clock), что делает его очень ненадежным для точных измерений коротких периодов времени.Вам нужно сделать код, который вы измеряете, значительно медленнее, чтобы избавиться от других факторов (таких как приостановка процесса и т. Д.).Вы должны измерять, используя высокопроизводительные счетчики, как предложено DeadMG.

Answer 3

find не принимает value_type, оно принимает const value_type &. Я бы сказал, что для unsigned int это не должно иметь значения. Однако вполне возможно, что ваш оптимизатор просто не заметил этого и не смог правильно оптимизировать тело вашего цикла.

Edit: Я бы сказал, что вы вроде как лжете компилятору, используя цикл for. Вы можете переписать его как

typename Vec::iterator i, end;
i = vec.begin();
end = vec.end();
while(i != end && *i != val)
    i++;
return i;

Конечно, парень, написавший std :: find, точно знает, насколько умным является оптимизатор, и с чем он может и не может справиться.

Редактировать: я провел ваш тест на моей машине. Это i7 930, без разгона в Visual Studio 2010. Я заменил boost :: progress_timer высокопроизводительным счетчиком.

__int64 frequency, begin, end;
QueryPerformanceCounter(frequency);
double d;
QueryPerformanceCounter(begin);
iter found=find1(vec, vec.capacity());
QueryPerformanceCounter(end);
d = ((end - begin) / (double)frequency) * 1000000;
cout << "first search required: " << d << endl;
cout << "first search found value: " << value_found(vec, found)<< endl;


QueryPerformanceCounter(begin);
found=find2(vec, vec.capacity());
QueryPerformanceCounter(end);
d = ((end - begin) / (double)frequency) * 1000000;
cout << "second search required: " << d << endl;
cout << "second search found value: " << value_found(vec, found)<< endl;

Говорит, что им обоим потребовалось 0,24 (примерно) наносекунды для работы, то есть разницы нет. Мое предложение состоит в том, что ваш оптимизатор является незрелым, и что ваша версия std :: find написана именно для того, чтобы представить правильные оптимизации, тогда как ваша находка просто не помечает правильные поля оптимизации.

Редактировать: Ваши данные о времени явно сбиты. Мой i7 работает за 0,23 наносекунды, то есть 0,00000023 секунды, тогда как ваш - 0,008 секунды. Если мой i7 примерно в 40000 раз быстрее, чем ваш, нет никакого способа. Нет никакого способа, которым i7 займет столько времени, чтобы пройти только десять миллионов предметов. Конечно, я на самом деле использую 64-битную Windows 7, хотя в 64-битном режиме не компилировался.

Собираюсь выложить дизассемблер сейчас.

FIND1:

00F810D3  mov         esi,dword ptr [esp+34h]  
00F810D7  mov         eax,dword ptr [esp+3Ch]  
00F810DB  mov         ecx,dword ptr [esp+38h]  
00F810DF  sub         eax,esi  
00F810E1  sar         eax,2  
00F810E4  cmp         esi,ecx  
00F810E6  je          main+0B3h (0F810F3h)  
00F810E8  cmp         dword ptr [esi],eax  
00F810EA  je          main+0B3h (0F810F3h)  
00F810EC  add         esi,4  
00F810EF  cmp         esi,ecx  
00F810F1  jne         main+0A8h (0F810E8h)  

find2:

00F8119A  mov         ecx,dword ptr [esp+34h]  
00F8119E  mov         eax,dword ptr [esp+3Ch]  
00F811A2  mov         edx,dword ptr [esp+38h]  
00F811A6  sub         eax,ecx  
00F811A8  sar         eax,2  
00F811AB  cmp         ecx,edx  
00F811AD  jae         main+17Fh (0F811BFh)  
00F811AF  nop  
00F811B0  cmp         dword ptr [ecx],eax  
00F811B2  je          main+254h (0F81294h)  
00F811B8  add         ecx,4  
00F811BB  cmp         ecx,edx  
00F811BD  jb          main+170h (0F811B0h)  
00F811BF  mov         esi,edx  

Вы можете видеть, что find2 немного отличается от find1. Я проверил, заменив вызов find2 другим вызовом find1, который действительно производит идентичные разборки. Любопытно, что они производят разные сборки.

Answer 4

Ваша методология измерения нарушена. Измерение скорости выполнения кода очень трудно сделать правильно, потому что общее истекшее время зависит от факторов, которые могут не контролироваться явно написанным вами кодом.

Некоторые вещи, которые нужно проверить (вы можете считать некоторые из них очевидными):

• Какие настройки оптимизации вы используете? Вы тестируете сборку релиза, верно?
• Вы сказали, что проверили код сборки, сгенерированный версией STL, и он не использует векторизацию. Но, может быть, он использует какой-то другой общий метод оптимизации, такой как развертывание цикла?
• Почему вы используете i < end вместо i != end в цикле? (Я действительно сомневаюсь, что это имеет какое-то значение, но кто знает?)

---

(Мой первоначальный ответ был совершенно глупым - не уверен, почему он получил голосование - я оставляю его здесь, так как некоторые комментарии касаются его)

В этом случае, я подозреваю, вы просто видите влияние иерархии памяти. Когда вы вызываете find1 (), CPU должен прочитать все данные из RAM. Эти данные затем будут храниться в кеше ЦП, что намного (легко в 10-100 раз) быстрее, чем доступ к ОЗУ. Когда вы вызываете find2 (), процессор может читать весь массив из кеш-памяти, и поэтому find2 () занимает меньше времени.

Чтобы получить больше доказательств, попробуйте поменять местами код, чтобы сначала измерить find2 (), а затем find1 (). Если ваши результаты поменялись местами, вероятно, вы видите эффект кеша. Если нет, то это что-то еще.

Редактировать После некоторых дальнейших размышлений (на самом деле, сразу после некоторых размышлений) я думаю, что мое первоначальное подозрение должно быть неверным (размер массива, который вы просматриваете, делает маловероятным, чтобы весь массив был помещен в кэш). Могут все еще быть эффекты кэша, но они, вероятно, несколько более тонкие. Тем не менее, попробуйте поменять измерения в любом случае, было бы интересно посмотреть, какой эффект это имеет.

Answer 5

Я не использую Visual C ++ сам, но с GCC я также получил результат, что find2 немного медленнее. Тем не менее, я смог сделать find2 немного быстрее, чем find1, вручную развернув цикл:

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; ) {
    if (i[0]==val) return i;
    if (i[1]==val) return i + 1;
    i += 2;
  }
  return v.end();
}

Я думаю, почему std::find быстрее, так это то, что компилятор имеет всю информацию, чтобы выяснить, что размер вектора кратен 2, и что это можно сделать, развернув.

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

Answer 6

Многие пользователи C / C ++ жалуются на то, что, как только они пишут специализацию функции, ее выполняет не специализированная версия!

Причина заключается в том, что вы просто пишете оптимизацию, проходящую в бэкэнде компилятора., вы будете думать о способах улучшения генерации кода std::find и, следовательно, он будет выполнять вашу реализацию.

Кроме того, узел, по крайней мере std::find для VC ++, имеет разные версии, которые будут вызывать различные функции и поискалгоритмы для различных типов итераторов.

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