为什么std::find的实现方式是这样的？

Question

我偶然遇到了std::find的源代码，并且发现它对我来说很难理解。基本上，它将项目数量除以4，并在每个回合中进行4次比较：

template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
__find(_RandomAccessIterator __first, _RandomAccessIterator __last,
   const _Tp& __val, random_access_iterator_tag)
{
  typename iterator_traits<_RandomAccessIterator>::difference_type
__trip_count = (__last - __first) >> 2;

  for (; __trip_count > 0; --__trip_count)
{
  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;
}

  switch (__last - __first)
{
case 3:
  if (*__first == __val)
    return __first;
  ++__first;
case 2:
  if (*__first == __val)
    return __first;
  ++__first;
case 1:
  if (*__first == __val)
    return __first;
  ++__first;
case 0:
default:
  return __last;
}
}

我不知道为什么要这样做。看起来像是一些优化。但我觉得这不会轻易地利用多核。无论如何，这都在单个线程中。

有什么想法吗？

- eltonsky

---

看起来是手动展开循环。这个实现来自哪里？ - R. Martinho Fernandes

一方面，它花费更少的时间将__trip_count与零进行比较，更多的时间实际上是在比较值。 - Bo Persson

Answer 1

看起来是循环展开，也称为循环展开。

- Some programmer dude

Answer 2

这是循环展开。结果相同，但对处理器更友好。

然而渐进复杂度仍然是一样的。

- Luchian Grigore

Answer 3

我不是很确定，但我认为这是一种循环展开。

请参见 http://www.codeproject.com/Articles/6154/Writing-Efficient-C-and-C-Code-Optimization 中的“循环展开”。

- Hayri Uğur Koltuk

Answer 4

这是Duff的设备。这是一种混合了while和switch语句的旧优化技巧，采用循环展开的特殊方式。在汇编中，您可以直接跳进一个展开的循环。

- Jan Herrmann

---

这不是 Duff 的设备，switch 语句不在循环内部。如果使用 Duff 的设备，生成的代码可能会更小一些。 - Steve Jessop

@SteveJessop：我认为你应该把Duff设备放在展开循环的末尾而不是内部。只有最后一次迭代会有一个非完整计数。 - Martin York

@LokiAstari：不，那不正确。达夫的发明是具体指滥用C开关结构跳到未卷展循环的中间位置，在这里，“中间”是“所需迭代次数对未卷展长度取模”。因此，事实上第一次迭代没有完全计数。 - Steve Jessop