title: Why do gcc and clang generate so much code for std::find?
body: <p>I entered the following code into godbolt.org, and compiled it with gcc 10.1 and clang 10:</p>
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;vector&gt;
  
  typedef std::vector&lt;int&gt; V;
  
  template&lt;class InputIt, class T&gt;
  InputIt myfind(InputIt first, InputIt last, const T&amp; value) {
      for (; first != last; ++first) {
          if (*first == value) {
              return first;
          }
      }
      return last;
  }
  
  V::iterator my_find_int(V&amp; v, int i) {
      return myfind(v.begin(), v.end(), i);
  }
  
  V::iterator std_find_int(V&amp; v, int i) {
      return std::find(v.begin(), v.end(), i);
  }
  </code></pre>
  <p>With either <code>-O3</code> or with <code>-Os</code>, both compilers generate about what I would expect for <code>my_find_int</code> (gcc 10.1, <code>-Os</code>):</p>
  <pre><code>my_find_int(std::vector&lt;int, std::allocator&lt;int&gt; &gt;&amp;, int):
          mov     rdx, QWORD PTR [rdi+8]
          mov     rax, QWORD PTR [rdi]
  .L3:
          mov     r8, rax
          cmp     rdx, rax
          je      .L2
          add     rax, 4
          cmp     DWORD PTR [rax-4], esi
          jne     .L3
  .L2:
          mov     rax, r8
          ret
  </code></pre>
  <p>However, for <code>std_find_int</code>, with either <code>-O3</code> or <code>-Os</code>, they both generate <em>several dozen</em> instructions (gcc 10.1, <code>-Os</code>):</p>
  <pre><code>std_find_int(std::vector&lt;int, std::allocator&lt;int&gt; &gt;&amp;, int):
          mov     rax, rdi
          mov     rdi, QWORD PTR [rdi+8]
          mov     rdx, QWORD PTR [rax]
          mov     rcx, rdi
          sub     rcx, rdx
          sar     rcx, 4
  .L12:
          mov     rax, rdx
          test    rcx, rcx
          jle     .L7
          cmp     DWORD PTR [rdx], esi
          je      .L8
          cmp     DWORD PTR [rdx+4], esi
          jne     .L9
          add     rax, 4
          ret
  .L9:
          cmp     DWORD PTR [rdx+8], esi
          jne     .L10
          add     rax, 8
          ret
  .L10:
          lea     rdx, [rdx+16]
          cmp     DWORD PTR [rax+12], esi
          jne     .L11
          add     rax, 12
          ret
  .L11:
          dec     rcx
          jmp     .L12
  .L7:
          mov     rdx, rdi
          sub     rdx, rax
          cmp     rdx, 8
          je      .L13
          cmp     rdx, 12
          je      .L14
          cmp     rdx, 4
          jne     .L23
          jmp     .L15
  .L14:
          cmp     esi, DWORD PTR [rax]
          je      .L8
          add     rax, 4
  .L13:
          cmp     esi, DWORD PTR [rax]
          je      .L8
          add     rax, 4
  .L15:
          cmp     esi, DWORD PTR [rax]
          je      .L8
  .L23:
          mov     rax, rdi
  .L8:
          ret
  </code></pre>
  <p>According to cppreference.com, <code>myfind</code> is a valid implementation of <code>std::find</code> (they describe it as a &quot;possible implementation&quot; of <code>std::find</code>).</p>
  <p>The behavior does not seem to be version-specific; the output of every major version of gcc going back to at least 4.9 looks similar.</p>
  <p>It seems like <code>my_find_int</code> and <code>std_find_int</code> should be functionally identical, so why do both compilers generate so much more code when <code>std::find</code> is used?</p>