Why do gcc and clang generate so much code for std::find?

Question

I entered the following code into godbolt.org, and compiled it with gcc 10.1 and clang 10:

#include <algorithm>
#include <vector>

typedef std::vector<int> V;

template<class InputIt, class T>
InputIt myfind(InputIt first, InputIt last, const T& value) {
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

V::iterator my_find_int(V& v, int i) {
    return myfind(v.begin(), v.end(), i);
}

V::iterator std_find_int(V& v, int i) {
    return std::find(v.begin(), v.end(), i);
}

With either -O3 or with -Os, both compilers generate about what I would expect for my_find_int (gcc 10.1, -Os):

my_find_int(std::vector<int, std::allocator<int> >&, 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

However, for std_find_int, with either -O3 or -Os, they both generate several dozen instructions (gcc 10.1, -Os):

std_find_int(std::vector<int, std::allocator<int> >&, 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

According to cppreference.com, myfind is a valid implementation of std::find (they describe it as a "possible implementation" of std::find).

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.

It seems like my_find_int and std_find_int should be functionally identical, so why do both compilers generate so much more code when std::find is used?

Answer 1

The reason is simple: the implementation of std::find for random access iterators is not a simple for loop, but something more complicated:

template<typename _RandomAccessIterator, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    _RandomAccessIterator
    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Predicate __pred, random_access_iterator_tag)
    {
      typename iterator_traits<_RandomAccessIterator>::difference_type
    __trip_count = (__last - __first) >> 2;

      for (; __trip_count > 0; --__trip_count)
    {
      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;
    }

      switch (__last - __first)
    {
    case 3:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 2:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 1:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 0:
    default:
      return __last;
    }
    }

The loop is manually unrolled, so that each iteration contains not just one predicate invocation, but four invocations. std::find is implemented in terms of __find_if with the predicate being a comparison.

This implementation dates back to SGI STL, at least. Alexander Stepanov explains:

Typically people unroll by 4 or 8 but not more. The main reason that people don’t go beyond 8 has to do with the law of diminishing returns. The point of loop unrolling is to gain a decent percent improvement in the ratio loop overhead to overall code. Starting with, say 30% loop overhead, unrolling by a factor of 4 leaves us with about 8% overhead. Unrolling by a factor of 8 brings it down to a 4% overhead. Overhead below 4% is commonly viewed as noise – results could vary from CPU to CPU, etc. In research we do unroll loops – 30% does not matter when we only want to demonstrate feasibility. But when it is time to transfer code to real applications then unrolling can be worth considering.