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交换内容，使用新创建的内存块作为交换空间。

现在内存块的大小会对操作速度产生影响（同样依赖于平台），因此您可能会发现，对于非常大的数组来说，来回交换更少量的数据比交换大块更快每一次。

编辑

在注释的光让我解释一下，关于交换少量数据的我的最后评论。

你的目标是使用临时交换空间tmpa数据传送到b和b数据a。

作为tmp尺寸例如还原的tmp尺寸比的a或b大小和交换数据增加迭代的次数等于或小于如果tmp是a中的第10个，则需要10次迭代。

现在为了提高memcpy的速度，最好确保数组（a，b和tmp）分配对齐的内存空间。

Answer 3

您可以使用逻辑here。这样，你可以保存第三个缓冲区。

#include <stddef.h> 
#include <stdint.h> 
void swap(uint8_t *a, uint8_t *b, size_t length) { 
    size_t i; 
    for (i=0; i<length; i++) { 
     uint8_t aa = a[i]; 
     aa^=b[i]; 
     b[i]^=aa; 
     aa^=b[i]; 
     a[i] = aa; 
    } 
} 

即使只有这一个临时变量足以帮助编译器优化这一点。

---

但是如果你使用这样一个临时变量，你可以做的一样好

#include <stddef.h> 
#include <stdint.h> 
void swap(uint8_t *a, uint8_t *b, size_t length) { 
    size_t i; 
    for (i=0; i<length; i++) { 
     uint8_t aa = a[i]; 
     a[i] = b[i]; 
     b[i] = aa; 
    } 
} 

在乍看之下，他们都显得昂贵，由于许多数组访问（在第一种情况下）并且每循环运行只处理一个字节，但如果让编译器优化它，应该是可以的，因为（至少gcc）足够聪明，可以将总共4个步骤（x64：甚至16步）捆绑到一个循环中跑。

请注意，您的编译器可能不会如此积极地进行优化，因此您可能必须自己进行上述分割。在这种情况下，请注意对齐。

Answer 4

#include <string.h> 
#include <stdio.h> 

static void swap_elements_of_array(void* base, size_t size_of_element, int a, int b); 
static void swap_elements_of_array(void* base, size_t size_of_element, int a, int b) 
{ 
union { 
    int i; /* force alignment */ 
    char zzz[size_of_element] ; /* VLA */ 
    } swap; 
memcpy (swap.zzz, (char*)base + a * size_of_element,size_of_element); 
memcpy ((char*)base + a * size_of_element,(char*)base + b * size_of_element,size_of_element); 
memcpy ((char*)base + b * size_of_element, swap.zzz, size_of_element); 
} 

int main (void) 
{ 
unsigned idx,array[] = {0,1,2,3,4,5,6,7,8,9}; 

swap_elements_of_array(array, sizeof array[0], 2, 5); 

for (idx=0; idx < 10; idx++) { 
    printf("%u%c", array[idx], (idx==9) ? '\n' : ' '); 
    } 
return 0; 
} 

上述片段的目的是允许（由编译器或内联）的memcpy的高度优化的libc版本，以充分他们所需要的所有的自由。这种一致性至关重要。如果VLA不可用（在C99之前），可以使用时髦的do-while来编写宏。

Answer 5

显然，您必须将A复制到Temp，将B复制到A，然后将Temp复制到B.您可以一次对所有区域执行此操作，也可以在较大区域执行所有操作，不想分配这么大的Temp值。截面尺寸的选择取决于你，尽管考虑到适合硬件的对齐和缓存问题对于大型频繁移动很重要。

（嗯，其实还有另外一种方法，它不需要任何临时空间：XOR A与B，然后XOR B，其中A，然后XOR A与B.一个老汇编编程人员的惯用伎俩。）

Answer 6

字写入将是最快的。但是，需要考虑块大小和对齐。在实践中，事情通常是合理的，但你不应该指望它。 memcpy()可以安全地处理所有事情，并且可以根据合理原因专门设计（内置）恒定大小的内容。

这里是一个便携的解决方案，工程相当不错在大多数情况下。

static void swap_byte(void* a, void* b, size_t count) 
{ 
    char* x = (char*) a; 
    char* y = (char*) b; 

    while (count--) { 
     char t = *x; *x = *y; *y = t; 
     x += 1; 
     y += 1; 
    } 
} 

static void swap_word(void* a, void* b, size_t count) 
{ 
    char* x = (char*) a; 
    char* y = (char*) b; 
    long t[1]; 

    while (count--) { 
     memcpy(t, x, sizeof(long)); 
     memcpy(x, y, sizeof(long)); 
     memcpy(y, t, sizeof(long)); 
     x += sizeof(long); 
     y += sizeof(long); 
    } 
} 

void memswap(void* a, void* b, size_t size) 
{ 
    size_t words = size/sizeof(long); 
    size_t bytes = size % sizeof(long); 
    swap_word(a, b, words); 
    a = (char*) a + words * sizeof(long); 
    b = (char*) b + words * sizeof(long); 
    swap_byte(a, b, bytes); 
} 

Answer 7

如果2个存储区域大且适合在内存页整数倍，那么你可以交换他们的页表项，以交换他们的内容，而无需使用的memcpy（）或异或。

从理论上讲，有两个大2MiB页面，你需要编写只有16字节分页结构的交换虚拟地址空间的映射......因此它们的内容了。

1GiB页是可能在64位模式和2这样1GiB存储器块内容的x86-64的CPU也可以与只写几个分页结构的字节交换。

这种方法的需要注意的是，该访问分页结构需要内核模式权限或使用从用户模式共享存储器映射函数。

随着近年来消融斑块（KPTI），从用户模式过渡到内核模式已经变得更加昂贵。使4kiB内存页面swapp与memcpy（）具有竞争力可能过于昂贵...但如果您有2MB或更大的内存块进行交换，那么交换其寻呼结构的速度会更快。

Answer 8

移动的存储器块中的最快的方法将是从<string.h>memcpy()。如果您memcpy()从a到temp，memmove()从b到a，然后从tempmemcpy()到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; 
    } 
} 

如果翻译成机器代码字面上写的，这是一个可怕的算法，一次复制一个字节，每个迭代做两个增量，依此类推。但实际上，编译器会看到你真正想要做的事情。

在铛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 

说服编译器生成一次只能处理一个单词的指令，而不是向量化循环，这与你想要的相反！