交换两个相同大小的非重叠内存区域的最快方法是什么? 说,我需要用(t_Some *b)
交换(t_Some *b)
。 考虑到时空权衡,会增加临时空间来提高速度吗? 例如, (char *tmp)
vs (int *tmp)
? 我正在寻找便携式解决方案。
原型:
void swap_elements_of_array(void* base, size_t size_of_element, int a, int b);
最好的办法是最大限度地提高寄存器的使用率,这样当你读取一个临时文件时,你不会得到额外的(可能是高速缓存的)内存访问。 寄存器数量取决于系统和寄存器分配(将变量映射到实际寄存器的逻辑)将取决于编译器。 所以你最好的选择是我希望只有一个寄存器,并期望它的大小与指针相同。 这归结为一个简单的for循环处理解释为size_t
数组的块。
移动内存块的最快方法是从memcpy()
。 如果你从memmove()
到temp
, memmove()
从b
到a
,然后memcpy()
从temp
到b
,你将有一个使用优化库例程的交换,编译器可能会编译。 您不希望一次复制整个块,而是使用矢量大小的块。
实际上,如果你编写一个紧密循环,编译器可能会告诉你正在交换数组的每个元素并相应地进行优化。 在大多数现代CPU上,您需要生成向量指令。 如果确保所有三个缓冲区都已对齐,它可能能够生成更快的代码。
但是,您真正想要做的是让优化器更容易。 参加这个计划:
#include 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
说服编译器生成一次处理单个单词的指令,而不是向量化循环,这与你想要的相反!
Word写入将是最快的。 但是,需要考虑块大小和对齐。 在实践中,事情通常是合理的,但你不应该依赖它。 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); }
如果2个内存区域很大并且适合整数个内存页面,那么您可以交换它们的页表条目,以便在不使用memcpy()或XOR的情况下交换它们的内容。
理论上,对于两个大的2MiB页面,您只需要编写16个字节的分页结构来交换它们在虚拟地址空间中的映射……因此也是它们的内容。
在64位模式的x86-64 CPU上可以使用1GiB页面,也可以交换2个这样的1GiB内存块的内容,只写入几个字节的分页结构。
此方法的警告是,对分页结构的访问需要内核模式特权或使用用户模式的共享内存映射function。
使用最近的Meltdown补丁(KPTI),从用户模式转换到内核模式变得更加昂贵。 将4kiB内存页面swapp与memcpy()竞争可能太昂贵了…但如果你有2MB或更大的内存块可以交换,那么交换它们的Paging Structures会更快。
#include #include 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版本(或编译器的内联)获得他们所需的所有自由。 对齐至关重要。 如果VGA不可用(在C99之前),可以使用时髦的do-while组成宏。
这种速度将部分取决于平台,并且只有通过测试才能真正得到证实。
我个人赞成创建一个与其中一个数组大小相同的内存块; 使用memcpy交换内容,使用新创建的内存块作为交换空间。
现在,内存块的大小将对操作速度产生影响(再次取决于平台),因此您可能会发现,对于非常大的arrays来说,来回交换少量数据比每次交换大块更快。
编辑
根据评论,让我解释一下,关于交换少量数据的最后评论。
您的目标是使用临时交换空间tmp
将数据传输到b
和b
数据。
tmp
的大小等于或小于a
或b
的大小,并且交换数据的迭代次数随着tmp
的大小减小而增加,例如,如果tmp
是a的10,那么将需要10次迭代。
现在为了提高memcpy的速度,最好确保为数组(a,b和tmp)分配对齐的内存空间。
显然,您必须将A复制到Temp,将B复制到A,然后将Temp复制到B.您可以一次性完成所有操作,对于较小的区域,或者在较大区域中执行此操作,您不需要分配如此大的Temp值。 部分大小的选择取决于您,但考虑到适合硬件的对齐和缓存问题对于大型,频繁的移动非常重要。
(嗯,实际上有另一种方式,它不需要任何临时空间:XOR A与B,然后XOR B与A,然后XOR A与B.旧的汇编程序员的技巧。)
您可以使用此处描述的逻辑。 这样,您可以保存第三个缓冲区。
#include #include void swap(uint8_t *a, uint8_t *b, size_t length) { size_t i; for (i=0; i
即使只有这一个临时变量也足以帮助编译器优化它。
但是如果你使用这样一个临时变量,你也可以这样做
#include #include void swap(uint8_t *a, uint8_t *b, size_t length) { size_t i; for (i=0; i
乍一看,由于许多数组访问(在第一种情况下)和每次循环运行只处理一个字节,它们看起来都很昂贵,但是如果你让你的编译器优化它,它应该没问题,因为(在至少gcc)足够聪明,可以将4个步骤(x64:甚至16个步骤)捆绑到一个循环运行中。
请注意,您的编译器可能不会如此积极地进行优化,因此您可能必须自己进行上述拆分。 在这种情况下,请注意对齐。
需要了解更多c/c++开发分享C – 交换两个相同大小的内存块的最快方法?,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享C – 交换两个相同大小的内存块的最快方法?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/978936.html