为什么使用std::find生成不同的(并且更慢)?汇编代码比手写代码时，循环在一个std::数组?

Question

我有这段代码来循环std::array<int, 3>(参见编译器资源管理器)，并查找元素是否在数组中。

#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个元素上?

Answer 1

std::find在libstdc++中使用std::__find_if，它具有随机访问迭代器的专门化。虽然一般的实现是一个简单的循环，在一次测试一个元素的范围内线性迭代，但是专门化将循环展开为四个连续元素测试的组，并单独处理不适合任何四个组的剩余元素。

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