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

Question

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

原型(prototype):

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

Answer 1

移动内存块的最快方法是memcpy()来自 <string.h> .如果您 memcpy()来自 a至temp , memmove()来自 b至a ，然后 memcpy()来自 temp至b ，你将有一个使用优化的库例程的交换，编译器可能内联。您不想一次复制整个 block ，而是以 vector 大小的 block 的形式复制。

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

但是，您真正想做的是让优化器更轻松。参加这个程序:

#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;
  }
}

如果你把它翻译成机器代码，那么这是一个糟糕的算法，一次复制一个字节，每次迭代做两个增量，等等。但在实践中，编译器会看到你真正想要做什么。

在带有 -std=c11 -O3 的 clang 5.0.1 中，它(部分)在 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

说服编译器一次生成对单个单词起作用的指令，而不是对循环进行矢量化，这与您想要的相反!