有没有一种方法可以优化性病算法？

Question

搜索有关std算法性能的任何信息，我发现了关于std::max_element()与自写函数之间的性能差异的堆栈溢出问题。我已经用GCC 9.2.0测试了问题中的功能，没有发现性能差异，即my_max_element_orig()和my_max_element_changed()（从接受的答案中）显示出相同的性能。因此，这似乎只是GCC 4.8.2中的优化程序问题。对于GCC 9.2.0，我真正发现的是在使用指针和迭代器的情况下的显着差异-与原始指针相比，使用迭代器的情况要差2倍。如果使用，则迭代器和原始指针也有类似的区别std::max_element()。

让我们接受my_max_element_orig函数实现（见下文）并尝试运行测试。

template<typename _ForwardIterator>
_ForwardIterator my_max_element_orig(_ForwardIterator __first, _ForwardIterator __last)
{
  if (__first == __last) return __first;
  _ForwardIterator __result = __first;
  while (++__first != __last)
    if (*__result < *__first)
      __result = __first;
  return __result;
}

以下用法示例

int maxValue = *my_max_element_orig(begin(vec), end(vec));

比以下情况差（原始指针）

int maxValue = *my_max_element_orig(vec.data(), vec.data() + vec.size());

可能有人说，原因是迭代器类的实现带来了一些开销。但是我发现原因是以下行的存在：

if (__first == __last) return __first;

如果从函数中删除了上面的行，则迭代器显示的性能与原始指针相同。经过一些实验，我决定干预优化器的分支预测，并用以下内容替换该行：

#define unlikely(x)     __builtin_expect((x),0)
...
if (unlikely(__first == __last)) return __first;

进行上述更改后，my_max_element_orig()无论使用迭代器还是原始指针，函数都将显示相同的性能。我在文件中对std::max_element()函数进行了类似的更改std_algo.h，并获得了相同的结果-现在std::max_element()对迭代器和原始指针都显示了相同的性能。

事实既是我链接的原始问题，也是我发现的有关“ GCC优化器如何工作”或“这是优化器问题”的问题。但是我想使用std算法，并且我不想重写它们以获得更优化的代码。所以我想知道是否有一种方法可以更改的分支预测std::max_element()，就像我上面为自己的功能所做的那样。或更笼统地说，有没有一种方法可以使标准算法更优化而不用重写它们？

• GCC 9.2.0
• SUSE Linux Enterprise Server 11（x86_64）
• g++ -DNDEBUG -O3 -Wall -fmessage-length=0 --std=c++17
• 测试程序：https：//godbolt.org/z/HrABJt