为什么memcpy()和memmove()比指针增量更快?

我从pSrc复制N个字节到pDest 。 这可以在一个循环中完成:

 for (int i = 0; i < N; i++) *pDest++ = *pSrc++ 

为什么这比memcpymemmove慢? 他们用什么技巧来加速?

由于memcpy使用字指针而不是字节指针,所以memcpy实现通常也是用SIMD指令写的,这使得一次可以对128位进行混洗。

SIMD指令是汇编指令,可以对长达16个字节的向量中的每个元素执行相同的操作。 这包括加载和存储指令。

内存复制例程可以比通过如下指针的简单内存复制复杂得多:

 void simple_memory_copy(void* dst, void* src, unsigned int bytes) { unsigned char* b_dst = (unsigned char*)dst; unsigned char* b_src = (unsigned char*)src; for (int i = 0; i < bytes; ++i) *b_dst++ = *b_src++; } 

改进

我们可以做的第一个改进就是alignment一个字边界上的指针(通过字我的意思是本地整数大小,通常是32位/ 4字节,但在新体系结构上可以是64位/ 8字节),并使用字大小的移动/复制说明。 这需要使用一个字节来复制字节,直到指针alignment。

 void aligned_memory_copy(void* dst, void* src, unsigned int bytes) { unsigned char* b_dst = (unsigned char*)dst; unsigned char* b_src = (unsigned char*)src; // Copy bytes to align source pointer while ((b_src & 0x3) != 0) { *b_dst++ = *b_src++; bytes--; } unsigned int* w_dst = (unsigned int*)b_dst; unsigned int* w_src = (unsigned int*)b_src; while (bytes >= 4) { *w_dst++ = *w_src++; bytes -= 4; } // Copy trailing bytes if (bytes > 0) { b_dst = (unsigned char*)w_dst; b_src = (unsigned char*)w_src; while (bytes > 0) { *b_dst++ = *b_src++; bytes--; } } } 

不同的体系结构将根据源或目标指针是否适当alignment来执行不同的操作。 例如在XScale处理器上,我通过alignment目标指针而不是源指针获得了更好的性能。

为了进一步提高性能,可以进行一些循环展开,以使更多的处理器寄存器被加载数据,这意味着加载/存储指令可以被交错,并且通过额外的指令(例如循环计数等)隐藏延迟。 由于加载/存储指令的延迟可能会有很大的不同,所以处理器带来的好处也不尽相同。

在这个阶段,代码最终会被编写成Assembly而不是C(或C ++),因为您需要手动放置加载和存储指令以获得延迟隐藏和吞吐量的最大好处。

一般来说,整个caching行数据应该在展开循环的一个迭代中被复制。

这带来了下一个改进,增加了预取。 这些是特殊的指令,告诉处理器的caching系统将特定的内存部分加载到它的caching中。 由于在发布指令和填充caching行之间存在延迟,所以需要将指令放置为使得数据在被复制时可用,并且不迟。

这意味着将预取指令放在函数的开头以及主复制循环内部。 利用预取指令在复制循环中获取将在几次迭代中复制的数据。

我不记得了,但预取目标地址和源地址也是有好处的。

因素

影响内存复制速度的主要因素是:

  • 处理器,高速caching和主内存之间的延迟。
  • 处理器caching行的大小和结构。
  • 处理器的内存移动/复制指令(延迟,吞吐量,寄存器大小等)。

所以,如果你想写一个高效快速的内存应对程序,你需要知道很多关于你正在编写的处理器和体系结构。 不用多说,除非你在一些embedded式平台上编写代码,否则只要使用内置的内存复制例程会容易得多。

memcpy可以一次复制多个字节,具体取决于计算机的体系结构。 大多数现代计算机可以在单个处理器指令中使用32位或更多。

从一个示例实现 :

     00026 *为了快速复制,优化两个指针的常见情况
     00027 *和长度是字alignment的,而不是复制一次字
     00028 *的字节在一次。 否则,按字节复制。

您可以使用以下任何一种技术来实现memcpy() ,一些依赖于您的体系结构来提高性能,而且它们都比您的代码快得多:

  1. 使用较大的单位,如32位字,而不是字节。 您也可以(或可能必须)在这里处理alignment。 例如,在某些平台上,您不能读/写32位字到奇数内存位置,而在其他平台上,您会付出巨大的性能损失。 要解决这个问题,地址必须是一个可被4整除的单位。对于64位CPU,可以使用64位,或者使用SIMD (单指令,多数据)指令( MMX , SSE等)

  2. 您可以使用编译器可能无法从C优化的特殊CPU指令。例如,在80386上,可以使用“rep”前缀指令+“movsb”指令移动N个字节寄存器。 好的编译器会为你做这个,但是你可能在一个缺乏良好编译器的平台上。 请注意,这个例子往往是一个不好的速度演示,但结合alignment+较大的单位指令,它可以比某些CPU上的其他任何东西都快。

  3. 循环展开 – 某些CPU上的分支可能相当昂贵,所以展开循环可以降低分支数量。 这与SIMD指令和非常大的单位相结合也是一个很好的技术。

例如, http : memcpy有一个memcpy实现,在那里击败最多(非常less量)。 如果你阅读了源代码,它将会充满大量的内联汇编代码,这些代码会将上述三种技术全部取消,并根据你正在运行的CPUselect哪种技术。

请注意,对于在缓冲区中查找字节也有类似的优化。 strchr()和朋友往往会比你手卷的速度相当。 .NET和Java尤其如此。 例如,在.NET中,内置的String.IndexOf()比Boyer-Moorestringsearch要快得多,因为它使用了上述优化技术。

简短的回答:

  • caching填充
  • 在可能的情况下将字节传输代替字节传输
  • SIMD魔术

像其他人一样,memcpy副本大于1个字节的块。 以字大小的块进行复制要快得多。 但是,大多数实现在循环之前进一步运行几个MOV(字)指令。 复制每个循环的8个字块的优点是循环本身是昂贵的。 这种技术将条件分支的数量减less了8倍,优化了巨块的拷贝。

我不知道它是否真的被用在任何真实的memcpy实现中,但我认为Duff的Device在这里值得一提。

维基百科 :

 send(to, from, count) register short *to, *from; register count; { register n = (count + 7) / 8; switch(count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while(--n > 0); } } 

请注意,上面的内容不是memcpy因为它故意不增加指针。 它实现了一个稍微不同的操作:写入内存映射寄存器。 详情请参阅维基百科文章。

答案很好,但如果你仍然想自己实现一个快速的memcpy ,有一个有趣的博客文章关于快速memcpy, 快速memcpy在C中

 void *memcpy(void* dest, const void* src, size_t count) { char* dst8 = (char*)dest; char* src8 = (char*)src; if (count & 1) { dst8[0] = src8[0]; dst8 += 1; src8 += 1; } count /= 2; while (count--) { dst8[0] = src8[0]; dst8[1] = src8[1]; dst8 += 2; src8 += 2; } return dest; } 

甚至,优化内存访问可能会更好。

因为像许多库例程一样,它已经针对您正在运行的体系结构进行了优化。 其他人已经发布了各种可以使用的技术。

给出的select,使用库例程而不是自己推出。 这是DRY上的一个变体,我称之为DRO(不要重复其他人)。 此外,库例程不太可能是错误的比你自己的实现。

我看到内存访问检查器抱怨内存或string缓冲区的边界读取不是字大小的倍数。 这是使用优化的结果。