c++ - 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 调用)的运行速度比手工循环(通过 find2 调用)快大约 10 倍。我首先认为 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

非常感谢，

杜莎。

附:我返回迭代器并写出结果(找到与否)，因为我想阻止编译器优化，它认为根本不需要循环。搜索到的值显然不在 vector 中。

附言我被要求发布为查找功能生成的程序集。这里是:

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-register 代替 esi。这两个寄存器有什么区别？难道esi会假设指针正确对齐，从而带来额外的性能？

读取一些程序集引用 ecx 只是一个计数器，而 esi 是内存源。所以我认为 STL 算法知道 Random Access Iterator 正确对齐，因此使用内存指针。在非 STL 版本中，没有推测对齐方式。我说的对吗？

Answer 1

Visual C++ 的 find算法使用未检查的迭代器，而您的手写循环使用的是检查的迭代器。

我的另一个猜测是你调用 std::vector<t>::end()在 find2 中循环的每次迭代, 而 std::find只调用一次 begin 和 end 访问器。我是个白痴。