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

Question

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

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

为什么这比memcpy或慢memmove？他们用什么技巧加快速度？

Answer 1

因为memcpy使用字指针而不是字节指针,所以memcpy实现通常用SIMD指令编写,这使得一次可以混洗128位.

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

Answer 2

内存复制例程可以比通过指针的简单内存复制更加复杂和快速,例如:

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

改进

可以做的第一个改进是对齐字边界上的一个指针(通过字我的意思是原生整数大小,通常是32位/ 4字节,但在较新的架构上可以是64位/ 8字节)并使用字大小的移动/复制说明.这需要使用字节到字节的复制,直到指针对齐.

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

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

为了进一步提高性能,可以进行一些循环展开,以便更多的处理器寄存器加载数据,这意味着加载/存储指令可以交错,并通过其他指令隐藏其延迟(例如循环计数等).这带来的好处因处理器而有很大差异,因为加载/存储指令延迟可能完全不同.

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

通常,应在展开循环的一次迭代中复制整个高速缓存行数据.

这带来了我的下一个改进,增加了预取.这些是特殊指令,告诉处理器的缓存系统将特定的内存部分加载到其缓存中.由于在发出指令和填充高速缓存行之间存在延迟,因此需要以这样的方式放置指令,使得数据在被复制时可用,并且不会迟早.

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

我记不起来了,但预取目标地址和源地址也可能是有益的.

因素

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

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

因此,如果您想编写一个高效且快速的内存应对程序,您需要了解很多关于您正在编写的处理器和体系结构.可以说,除非你在某个嵌入式平台上编写,否则使用内置的内存复制例程要容易得多.

Answer 3

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

从一个示例实现:

    00026          * For speedy copying, optimize the common case where both pointers
    00027          * and the length are word-aligned, and copy word-at-a-time instead
    00028          * of byte-at-a-time. Otherwise, copy by bytes.

Answer 4

您可以memcpy()使用以下任何一种技术实现,一些技术取决于您的体系结构以获得性能提升,并且它们都将比您的代码快得多:

1. 使用更大的单位,例如32位字而不是字节.您也可以(或可能必须)处理对齐.您不能将32位字读取/写入奇数存储器位置,例如在某些平台上,而在其他平台上,您需要承担巨大的性能损失.要解决此问题,地址必须是可被4整除的单位.对于64位CPU,最高可达64位,甚至更高,使用SIMD(单指令,多数据)指令(MMX,SSE等)

2. 您可以使用编译器可能无法从C优化的特殊CPU指令.例如,在80386上,您可以使用"rep"前缀指令+"movsb"指令移动N个字节,方法是将N放入计数中寄存器.好的编译器会为你做这个,但你可能在一个缺乏良好编译器的平台上.请注意,该示例往往是速度的不良演示,但结合对齐+更大的单位指令,它可能比某些CPU上的大多数其他内容更快.

3. 循环展开 - 某些CPU上的分支可能非常昂贵,因此展开循环可以降低分支数量.这也是与SIMD指令和超大单元组合的好技术.

例如,httpmemcpy://www.agner.org/optimize/#asmlib 有一个实现最多的实现(非常少).如果你阅读了源代码,它将充满大量的内联汇编代码,它们可以完成上述三种技术,根据你运行的CPU选择哪种技术.

注意,也可以进行类似的优化,以便在缓冲区中查找字节.strchr()而且朋友们往往比你的手滚动速度更快.对于.NET和Java尤其如此.例如,在.NET中,内置String.IndexOf()比Boyer-Moore字符串搜索快得多,因为它使用了上述优化技术.

Answer 5

我不知道它是否实际用于任何现实世界的实现中memcpy，但我认为Duff 的设备值得在这里提及。

来自维基百科：

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

请注意，上面的内容不是 a，memcpy因为它故意不增加to指针。它实现了一个稍微不同的操作：写入内存映射寄存器。有关详细信息，请参阅维基百科文章。

Answer 6

简短回答:

• 缓存填充
• 尽可能使用字大小的传输而不是字节传输
• SIMD魔术