复制范围的优化

Question

在阅读 GNU C++ 标准库的源代码时，我发现了一些用于复制（或移动，如果可能的话）一系列迭代器（文件 stl_algobase.h）的代码，它使用模板专门化进行某些优化。对应的评论说：

All of these auxiliary structs serve two purposes. (1) Replace calls to copy with memmove whenever possible. (Memmove, not memcpy, because the input and output ranges are permitted to overlap.) (2) If we're using random access iterators, then write the loop as a for loop with an explicit count.

使用第二次优化的特化如下所示：

template<>
struct __copy_move<false, false, random_access_iterator_tag>
{
  template<typename _II, typename _OI>
    static _OI
    __copy_m(_II __first, _II __last, _OI __result)
    { 
  typedef typename iterator_traits<_II>::difference_type _Distance;
  for(_Distance __n = __last - __first; __n > 0; --__n)
    {
      *__result = *__first;
      ++__first;
      ++__result;
    }
  return __result;
  }
};

那么，关于这个我有两个问题

如何memmove提高复制速度？它的实现方式是否比简单循环更有效？
在 for 循环中使用显式计数器如何影响性能？

一些说明：我想看看编译器实际使用的一些优化示例，而不是详细说明这些的可能性。

编辑：第一个问题回答得很好here。

Answer 1

回答第二个问题，显式计数确实会带来更多循环展开的机会，尽管即使指针遍历固定大小的数组，gcc 也不会执行主动展开，除非使用 -funroll-loops.另一个好处来自对非平凡迭代器的可能更简单的循环结束比较测试。

在 Core i7-4770 上，我对使用 while 循环和显式计数复制实现执行最大对齐的 2048 长整数数组的复制所花费的时间进行了基准测试。（以微秒为单位的时间，包括调用开销；最少 200 个带预热的定时循环样本。）

                                            while      count

gcc -O3                                     0.179      0.178
gcc -O3 -march=native                       0.097      0.095
gcc -O3 -march=native -funroll-loops        0.066      0.066

在每种情况下，生成的代码都非常相似； while 版本在每种情况下都在最后做了更多的工作，处理检查是否没有任何要复制的条目未填满整个 128 位 (SSE) 或 256 位 ( AVX) 寄存器，但分支预测器几乎负责这些。每个的 gcc -O3 汇编如下（省略汇编器指令）。 while 版本：

array_copy_while(int (&) [2048], int (&) [2048]):
        leaq    8192(%rdi), %rax
        leaq    4(%rdi), %rdx
        movq    %rax, %rcx
        subq    %rdx, %rcx
        movq    %rcx, %rdx
        shrq    , %rdx
        leaq    1(%rdx), %r8
        cmpq    , %r8
        jbe     .L11
        leaq    16(%rsi), %rdx
        cmpq    %rdx, %rdi
        leaq    16(%rdi), %rdx
        setae   %cl
        cmpq    %rdx, %rsi
        setae   %dl
        orb     %dl, %cl
        je      .L11
        movq    %r8, %r9
        xorl    %edx, %edx
        xorl    %ecx, %ecx
        shrq    , %r9
        leaq    0(,%r9,4), %r10
.L9:
        movdqa  (%rdi,%rdx), %xmm0
        addq    , %rcx
        movdqa  %xmm0, (%rsi,%rdx)
        addq    , %rdx
        cmpq    %rcx, %r9
        ja      .L9
        leaq    0(,%r10,4), %rdx
        addq    %rdx, %rdi
        addq    %rdx, %rsi
        cmpq    %r10, %r8
        je      .L1
        movl    (%rdi), %edx
        movl    %edx, (%rsi)
        leaq    4(%rdi), %rdx
        cmpq    %rdx, %rax
        je      .L1
        movl    4(%rdi), %edx
        movl    %edx, 4(%rsi)
        leaq    8(%rdi), %rdx
        cmpq    %rdx, %rax
        je      .L20
        movl    8(%rdi), %eax
        movl    %eax, 8(%rsi)
        ret
.L11:
        movl    (%rdi), %edx
        addq    , %rdi
        addq    , %rsi
        movl    %edx, -4(%rsi)
        cmpq    %rdi, %rax
        jne     .L11
.L1:
        rep ret
.L20:
        rep ret

count版本：

array_copy_count(int (&) [2048], int (&) [2048]):
        leaq    16(%rsi), %rax
        movl    48, %ecx
        cmpq    %rax, %rdi
        leaq    16(%rdi), %rax
        setae   %dl
        cmpq    %rax, %rsi
        setae   %al
        orb     %al, %dl
        je      .L23
        movw    2, %cx
        xorl    %eax, %eax
        xorl    %edx, %edx
.L29:
        movdqa  (%rdi,%rax), %xmm0
        addq    , %rdx
        movdqa  %xmm0, (%rsi,%rax)
        addq    , %rax
        cmpq    %rdx, %rcx
        ja      .L29
        rep ret
.L23:
        xorl    %eax, %eax
.L31:
        movl    (%rdi,%rax,4), %edx
        movl    %edx, (%rsi,%rax,4)
        addq    , %rax
        cmpq    %rax, %rcx
        jne     .L31
        rep ret

然而，当迭代器更复杂时，差异变得更加明显。考虑一个假设的容器，它在一系列固定大小的已分配缓冲区中存储值。迭代器包括指向块链的指针、块索引和块偏移量。两个迭代器的比较可能需要两次比较。递增迭代器需要检查我们是否弹出块边界。

我制作了这样一个容器，并执行了相同的基准测试，用于复制一个 2000 长的 int 容器，块大小为 512 ints。

                                            while      count

gcc -O3                                     1.560      2.818
gcc -O3 -march=native                       1.660      2.854
gcc -O3 -march=native -funroll-loops        1.432      2.858

这看起来很奇怪！哦等等，这是因为 gcc 4.8 有一个错误的优化，它使用条件移动而不是漂亮的、分支预测器友好的比较。 (gcc bug 56309).

让我们在另一台机器 (Xeon E5-2670) 上试试 icc。

                                            while      count

icc -O3                                     3.952      3.704
icc -O3 -xHost                              3.898      3.624

这更接近我们的预期，与更简单的循环条件相比，这是一个很小但很重要的改进。在不同的架构上，增益更为明显。 clang 以 1.6GHz 的 PowerA2 为目标：

                                            while      count

bgclang -O3                                36.528     31.623

我会省略汇编，因为它很长！

复制范围的优化

Optimizations in copying a range

c++

optimization