为什么使用 std::find 会产生不同的结果（并且速度更慢）？在 std::array 上循环时，汇编代码比手写代码更好吗？

Question

我有这段代码可以循环遍历 a std::array<int, 3>（请参阅Compiler Explorer）并查找元素是否在数组中。

#include <algorithm>
#include <iterator>
#include <array>
constexpr std::array<int, 3> arr = { 0, 1, 2};
bool forLoop(int inp) 
{
    for (int i {0}; i < arr.size(); ++i)
    {
        if (arr[i] == inp) 
        {
            return true;
        }
    }
    return false;
}
bool forEachLoop(int inp)
{
    for (int i : arr) 
    {
        if (i == inp) 
        {
            return true;
        }
    }
    return false;
}
bool STL(int inp)
{
    return std::find(arr.begin(), arr.end(), inp) != arr.end();
}

使用x86-64 clang 15.0.0和编译-std=c++17 -O3，两者forLoop()都forEachLoop()生成：

        cmp     edi, 3
        setb    al
        ret

但STL()生成的程序集有很大不同

        test    edi, edi
        je      .LBB2_1
        cmp     edi, 1
        jne     .LBB2_3
        lea     rax, [rip + arr+4]
        lea     rcx, [rip + arr+12]
        cmp     rax, rcx
        setne   al
        ret
.LBB2_1:
        lea     rax, [rip + arr]
        lea     rcx, [rip + arr+12]
        cmp     rax, rcx
        setne   al
        ret
.LBB2_3:
        xor     eax, eax
        cmp     edi, 2
        setne   al
        lea     rcx, [rip + arr]
        lea     rax, [rcx + 4*rax]
        add     rax, 8
        lea     rcx, [rip + arr+12]
        cmp     rax, rcx
        setne   al
        ret

我尝试使用gcc它，但STL()仍然生成更长的程序集

当我尝试更改它以使其arr具有其他数量的元素（例如 4）时，这 3 个函数都会生成相同的程序集。

那么这是一个错过的优化问题吗？为什么它只发生在 3 个元素上？

Answer 1

std::find用于std::__find_iflibstdc++，它专门用于随机访问迭代器。虽然一般实现是一个简单的循环，每次测试一个元素，线性迭代范围，但专门化将循环展开为四个连续元素测试的组，并单独处理最后不适合任何四个组的剩余元素。参见github镜像。

显然，编译器正在努力优化这种专业化。我不确定该函数的这种专门化是否是为了在更大的范围内实现高性能而编写的，或者它背后的想法是否不再适用（查看存储库，这自 1998 年以来一直存在），但我也不知道为什么编译器特别努力优化这个部分展开的循环。也许是因为在实现结束时对剩余元素的测试取决于__first初始循环中的修改（顺便说一句，我也没有看到一个很好的理由）。