C - 交换两个相同大小的内存块的最快方法？

Question

交换两个相同大小的非重叠内存区域的最快方法是什么？我说,我需要换(t_Some *a)用(t_Some *b).考虑到时空权衡,会增加临时空间提高速度吗？例如,(char *tmp)vs (int *tmp)？我正在寻找便携式解决方案.

原型:

void swap_elements_of_array(void* base, size_t size_of_element, int a, int b);

Answer 1

最好的选择是最大化寄存器的使用率，这样，当您读取临时文件时，就不会获得额外的（可能是缓存的）内存访问权限。寄存器的数量将取决于系统，寄存器的分配（将变量映射到实际寄存器的逻辑）将取决于编译器。因此，您最好的选择是我估计只需要一个寄存器，并希望其大小与指针相同。归结为一个简单的for循环，用于处理解释为的数组的块size_t。

Answer 2

最快的移动内存块的方法将是memcpy()从<string.h>。如果你memcpy()从a到temp， memmove()从b到a，然后memcpy()从temp到b，你就必须使用优化的库例程，编译器可能内联交换。您不想一次复制整个块，而是以矢量大小的块复制。

实际上，如果编写一个紧密循环，编译器可能会告诉您正在交换数组的每个元素并进行相应的优化。在大多数现代CPU上，您都希望生成矢量指令。如果确保所有三个缓冲区都对齐，它可能会生成更快的代码。

但是，您真正想做的是使优化程序更轻松。采取这个程序：

#include <stddef.h>

void swap_blocks_with_loop( void* const a, void* const b, const size_t n )
{
  unsigned char* p;
  unsigned char* q;
  unsigned char* const sentry = (unsigned char*)a + n;

  for ( p = a, q = b; p < sentry; ++p, ++q ) {
     const unsigned char t = *p;
     *p = *q;
     *q = t;
  }
}

如果按照字面意思将其转换为机器代码，那将是一个糟糕的算法，一次复制一个字节，每次迭代进行两次增量，依此类推。但是在实践中，编译器会看到您真正想做的事情。

在带有的clang 5.0.1中-std=c11 -O3，它在x86_64上（部分）产生以下内部循环：

.LBB0_7:                                # =>This Inner Loop Header: Depth=1
        movups  (%rcx,%rax), %xmm0
        movups  16(%rcx,%rax), %xmm1
        movups  (%rdx,%rax), %xmm2
        movups  16(%rdx,%rax), %xmm3
        movups  %xmm2, (%rcx,%rax)
        movups  %xmm3, 16(%rcx,%rax)
        movups  %xmm0, (%rdx,%rax)
        movups  %xmm1, 16(%rdx,%rax)
        movups  32(%rcx,%rax), %xmm0
        movups  48(%rcx,%rax), %xmm1
        movups  32(%rdx,%rax), %xmm2
        movups  48(%rdx,%rax), %xmm3
        movups  %xmm2, 32(%rcx,%rax)
        movups  %xmm3, 48(%rcx,%rax)
        movups  %xmm0, 32(%rdx,%rax)
        movups  %xmm1, 48(%rdx,%rax)
        addq    $64, %rax
        addq    $2, %rsi
        jne     .LBB0_7

具有相同标志的gcc 7.2.0也可以向量化，从而使循环展开得更少：

.L7:
        movdqa  (%rcx,%rax), %xmm0
        addq    $1, %r9
        movdqu  (%rdx,%rax), %xmm1
        movaps  %xmm1, (%rcx,%rax)
        movups  %xmm0, (%rdx,%rax)
        addq    $16, %rax
        cmpq    %r9, %rbx
        ja      .L7

说服编译器一次生成一个单词，而不是对循环进行矢量化处理，这与您想要的相反！