为什么 gcc 和 clang 为 std::find 生成这么多代码？

Question

我在 godbolt.org 中输入以下代码，并使用 gcc 10.1 和 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);
}

使用-O3或 with -Os，两个编译器都会生成我所期望的内容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

然而，对于std_find_int、-O3或-Os，它们都会生成几十条指令（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

根据 cppreference.com，myfind是 的有效实现std::find（他们将其描述为 的“可能实现” std::find）。

该行为似乎不特定于版本；至少追溯到 4.9 的每个主要版本的 gcc 的输出看起来都很相似。

看起来my_find_int并且应该在功能上相同，那么为什么两个编译器在使用std_find_int时都会生成这么多代码呢？std::find

Answer 1

原因很简单：std::findfor 随机访问迭代器的实现不是一个简单的for循环，而是更复杂的东西：

\n

template<typename _RandomAccessIterator, typename _Predicate>\n    _GLIBCXX20_CONSTEXPR\n    _RandomAccessIterator\n    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,\n          _Predicate __pred, random_access_iterator_tag)\n    {\n      typename iterator_traits<_RandomAccessIterator>::difference_type\n    __trip_count = (__last - __first) >> 2;\n\n      for (; __trip_count > 0; --__trip_count)\n    {\n      if (__pred(__first))\n        return __first;\n      ++__first;\n\n      if (__pred(__first))\n        return __first;\n      ++__first;\n\n      if (__pred(__first))\n        return __first;\n      ++__first;\n\n      if (__pred(__first))\n        return __first;\n      ++__first;\n    }\n\n      switch (__last - __first)\n    {\n    case 3:\n      if (__pred(__first))\n        return __first;\n      ++__first;\n      // FALLTHRU\n    case 2:\n      if (__pred(__first))\n        return __first;\n      ++__first;\n      // FALLTHRU\n    case 1:\n      if (__pred(__first))\n        return __first;\n      ++__first;\n      // FALLTHRU\n    case 0:\n    default:\n      return __last;\n    }\n    }\n

\n

该循环是手动展开的，因此每次迭代不仅包含一次谓词调用，而且包含四次调用。std::find是根据__find_if谓词作为比较来实现的。

\n

这个实现至少可以追溯到SGI STL 。亚历山大·斯捷潘诺夫解释说：

\n

\n

通常人们会展开4或8但不会更多。人们不去超越的主要原因8与收益递减定律有关。循环展开的目的是使循环开销与整体代码的比率获得相当大的百分比改善。从 30% 的循环开销开始，按 的因子展开后，4我们只剩下大约 8% 的开销。按 1 倍展开可将8开销降低至 4%。低于 4% 的开销通常被视为噪声 \xe2\x80\x93 结果可能因 CPU 不同而异，等等。在研究中，我们会展开循环 \xe2\x80\x93 当我们只想证明可行性时，30% 并不重要。但是，当需要将代码转移到实际应用程序时，则值得考虑展开。

\n

\n