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

Question

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

95

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

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

为什么这比memcpy或memmove慢？它们使用了什么技巧来加速？

- wanderer

2

你的循环只复制了一个位置。我认为你想要增加指针。 - Mysticial

15

或者，你可以像我一样为他们修复它。顺便说一下，真正的 C 程序员从 0 计数到 N-1，绝不从 1 计数到 N :-) - paxdiablo

6

如果你正在循环数组，那么是的。但是有很多情况下从1到N循环也可以。这取决于你用数据做什么--例如，如果你要向用户显示一个以1开始的编号列表，那么从1开始可能更有意义。无论如何，它忽略了更大的问题，即在计数器上使用int时，应该使用无符号类型如size_t。 - Billy ONeal

2

@paxdiablo 你也可以从N数到1。在某些处理器上，这将消除一条比较指令，因为当减量达到零时，它将为分支指令设置适当的位。 - onemasse

6

我认为这个问题的前提是错误的。现代编译器会将其转换成memcpy或memmove（取决于它们是否能确定指针可能别名）。 - David Schwartz

显示剩余9条评论

10个回答

83

内存复制程序比简单的指针内存复制要复杂得多，速度也更快，例如：

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 处理器上，通过对齐目标指针而不是源指针，我获得了更好的性能。

为了进一步提高性能，可以进行一些循环展开，这样处理器的寄存器可以加载更多的数据，这意味着加载/存储指令可以交错，并且它们的延迟可以由其他指令（如循环计数）隐藏。这带来的好处因处理器而异，因为加载/存储指令的延迟可能会相差很大。

在此阶段，代码最终会以 Assembly 而非 C（或 C++）编写，因为您需要手动放置加载和存储指令，以获取潜在的延迟隐藏和吞吐量的最大收益。

通常情况下，应该在展开循环的一次迭代中复制整个缓存行的数据。

接下来就是另一个改进——添加预取。这些是特殊指令，告诉处理器的缓存系统将内存的特定部分加载到其缓存中。由于发出指令和填充缓存行之间存在延迟，因此必须以这样的方式放置指令，以便在刚好要复制数据的时候获取数据，而不是过早或过晚。

这意味着需要在函数的开头和主要复制循环内添加预取指令。在复制循环中间放置预取指令，以获取将在几次迭代中复制的数据。

我记不清了，但对目标地址进行预取可能也是有益的。

影响内存复制速度的主要因素包括：

- 处理器、其缓存和主内存之间的延迟。 - 处理器缓存行的大小和结构。 - 处理器的内存移动/复制指令（延迟、吞吐量、寄存器大小等）。

因此，如果您想编写一个高效且快速的内存复制例程，您需要了解所编写的处理器和架构方面的知识。总之，除非您在某些嵌入式平台上编写代码，否则最好使用内置的内存复制例程。

- Dominik Grabiec

现代CPU会检测到线性内存访问模式并自动进行预取操作。因此，我认为预取指令可能不会产生太大的影响。 - maxy

@maxy 在我实现的一些架构上，添加预取已经明显地提高了内存复制例程的效率。虽然当前的英特尔/AMD芯片确实可以预取足够远的数据，但是还有很多旧芯片和其他架构无法做到这一点。 - Dominik Grabiec

有人能解释一下 "(b_src & 0x3) != 0" 吗？我无法理解它，而且它也无法编译（抛出错误：invalid operator to binary &: unsigned char and int）。 - Maverick Meerkat

"(b_src＆0x3)！= 0"正在检查最低的2位是否不为0。因此，如果源指针对4字节的倍数进行了对齐或未对齐。您的编译错误发生是因为它将0x3视为字节而不是int，您可以通过使用0x00000003或0x3i（我认为）来修复它。 - Dominik Grabiec

b_src & 0x3不会通过编译，因为在指针类型上不允许进行位运算。您必须首先将其转换为(u)intptr_t。 - phuclv

18

memcpy函数根据计算机的架构可以一次性复制多个字节。现代计算机中，单处理器指令可以同时处理32位或更多。

下面是一个示例实现：

    00026          * 为了加快速度，当两个指针和长度都对齐时，会进行优化，使用每次复制一个字而不是一个字节的方式。否则，按字节复制。

- Mark Byers

8

在386处理器中（举个例子），因为没有板载缓存，这个操作确实会有很大的影响。但在现代大部分处理器上，读写通常会以一条缓存线为单位进行，并且与内存的总线连接通常是瓶颈，所以预计只会有少数几个百分点的提升，远达不到四倍。 - Jerry Coffin

2

当你说“来自源代码”时，我认为你应该更加明确一些。当然，在某些体系结构中，“源代码”就是那样，但在 BSD 或 Windows 机器上却完全不是这样。（说实话）即使在 GNU 系统之间，这个功能的实现也经常存在很大差异。 - Billy ONeal

@Billy ONeal：+1 绝对正确......有许多种方法可以解决问题。那只是一个例子。已经修复！感谢您的建设性评论。 - Mark Byers

7

您可以使用以下任何技术来实现memcpy()，其中一些依赖于您的架构以获得性能提升，并且它们都比您的代码快得多：

使用更大的单元，例如32位字而不是字节。您还可以（或可能必须）在此处处理对齐。例如，在某些平台上，您不能读取/写入32位字到奇数内存位置，而在其他平台上，您需要支付巨大的性能惩罚。为了解决这个问题，地址必须是可被4整除的单位。对于64位CPU，您可以将其提高到64位，甚至使用SIMD（单指令，多数据）指令（MMX，SSE等）。
您可以使用特殊的CPU指令，您的编译器可能无法从C中进行优化。例如，在80386上，您可以使用“rep”前缀指令+“movsb”指令来移动由将N放置在计数寄存器中指定的N个字节。好的编译器会为您执行此操作，但您可能在缺乏良好编译器的平台上。请注意，该示例往往是速度不佳的演示，但与对齐+较大单元指令相结合，它可以比某些CPU上的几乎所有其他东西都更快。
展开循环 - 分支在某些CPU上可能非常昂贵，因此展开循环可以降低分支数量。这也是将SIMD指令和非常大的大小单位组合使用的好技术。

例如，http://www.agner.org/optimize/#asmlib具有一个memcpy实现，它击败了大多数其他实现（微不足道地）。如果您阅读源代码，它将充满大量内联汇编代码，执行上述三个技术中的哪一个取决于您正在运行的CPU。

请注意，在查找缓冲区中的字节时，也可以进行类似的优化。使用 strchr() 等函数通常比自己编写的代码更快。这在 .NET 和 Java 中尤其如此。例如，在 .NET 中，内置的 String.IndexOf() 比甚至 Boyer–Moore 字符串搜索算法更快，因为它使用了上述的优化技术。

- Danny Dulai

1

你所链接的Agner Fog也提出了一个理论，即在现代CPU上展开循环是适得其反的。 - user824425

现今大多数的CPU都有良好的分支预测能力，这使得在典型情况下循环展开的优势被抵消了。但是一个好的优化编译器仍然可以有时候使用它。 - thomasrutter

6

我不知道memcpy是否在任何真实的实现中使用，但我认为达夫设备(Duff's Device)在这里值得一提。

来自维基百科(Wikipedia)：

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 函数，因为它故意不会增加 to 指针。它实现了一个略微不同的操作：向内存映射寄存器写入数据。详情请参阅维基百科文章。

- NPE

Duff的装置，或者仅仅是初始跳转机制，是一个很好的用途，可以复制前1..3（或1..7）个字节，使得指针对齐到更好的边界，从而可以使用更大的内存移动指令。 - Dominik Grabiec

@MarkByers：这段代码展示了一个稍微不同的操作（*to指的是一个内存映射寄存器，故意没有增加 - 请参阅链接的文章）。正如我所说，我的答案并没有试图提供一个高效的memcpy，它只是提到了一种相当奇特的技术。 - NPE

@Daemin 同意你所说的，可以跳过 do {} while()，编译器会将 switch 翻译为跳转表，非常有用，特别是当你想要处理剩余数据时。需要提醒一下 Duff's device，在较新的架构（新 x86）上，分支预测效率非常高，因此 Duff's device 实际上比简单循环更慢。 - onemasse

1

哦不..不要用Duff的设备。请不要使用Duff的设备。请使用PGO，让编译器在有意义的地方为您执行循环展开。 - Billy ONeal

不，Duff的设备绝对不会在任何现代实现中使用。 - gnasher729

5

简短回答：

缓存填充
尽可能使用字节大小的传输，而非单字节传输
SIMD技术（单指令多数据）

- moshbear

3

正如其他人所说，memcpy复制的是大于1字节的块。按字大小块进行复制速度更快。然而，大多数实现进一步运行几个MOV（字）指令后再执行循环。每次循环复制8个字大小的块的优势在于循环本身成本很高。这种技术将条件分支数量降低了8倍，优化了大块复制。

- VoidStar

1

我不认为这是正确的。你可以展开循环，但在目标架构上，你不能在单个指令中复制超过可寻址数据的数量。此外，展开循环还会有开销... - Billy ONeal

@Billy ONeal：我认为VoidStar的意思不是这样的。通过有几个连续的移动指令，计算单位数量的开销就会减少。 - wallyk

@Billy ONeal：你没有理解重点。逐字逐句的方式就像MOV，JMP，MOV，JMP等等。而你可以使用MOV MOV MOV MOV JMP的方式。我以前写过mempcy，并且对很多实现方式进行了基准测试 ;) - VoidStar

@wallyk：也许吧。但他说“复制更大的块”——这实际上是不可能的。如果他的意思是循环展开，那么他应该说“大多数实现会更进一步地展开循环”。这篇答案写得最好是误导性的，最坏的情况下是错误的。 - Billy ONeal

@VoidStar：同意——现在好多了。+1。 - Billy ONeal

2

答案很好，但如果你仍想自己实现快速的memcpy，有一篇关于快速memcpy的有趣博客文章：C语言中的快速memcpy。请参考。

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

即使如此，通过优化内存访问，它可能会变得更好。

- masoud

1

你可以查看MacOS中memset，memcpy和memmove的实现。

在启动时，操作系统确定它正在运行的处理器。它内置了针对每个受支持处理器特别优化的代码，并在启动时将jmp指令存储到固定的只读位置以调用正确的代码。

C memset，memcpy和memmove实现只是跳转到该固定位置的跳转指令。

实现根据memcpy和memmove源和目标的对齐方式使用不同的代码。它们显然使用所有可用的向量功能。当您复制大量数据时，它们还使用非缓存变体，并具有最小化页面表等待的指令。这不仅仅是汇编代码，而是由具有极好的每个处理器架构知识的人编写的汇编代码。

英特尔还添加了汇编指令，可以使字符串操作更快。例如，支持strstr的指令可以在一个周期内执行256字节比较。

- gnasher729

1

苹果的开源版本memset/memcpy/memmove只是一个通用版本，使用SIMD的真实版本会比它慢很多。 - phuclv

我在哪里可以找到真正的Mac OS实现？ - Sergei Kulik

1

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

如果有选择的话，请使用库例程而不是自己编写。这是DRY的变体，我称之为DRO（不要重复别人）。此外，库例程比您自己的实现更不可能出错。

我曾看到内存访问检查器抱怨在非字大小倍数的内存或字符串缓冲区上进行越界读取。这是使用优化的结果。

- BillThor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- onemasse · Accepted Answer

131

由于memcpy使用单词指针而不是字节指针，因此memcpy的实现通常使用SIMD指令编写，可以一次处理128位数据。

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

- onemasse

15

当你将 GCC 的优化等级提高到“-O3”时，它会在循环中使用 SIMD 技术，至少在其知道 pDest 和 pSrc 不会发生别名的情况下会这样做。 - Dietrich Epp

我目前正在使用带有64字节（512位）SIMD的Xeon Phi进行工作，所以这种“最多16字节”的东西让我感到很轻松。此外，您必须指定要启用SIMD的CPU，例如使用-march=native。 - yakoudbz

也许我应该修改我的回答。 :) - onemasse

即使在发布时，这已经非常过时了。x86上的AVX向量（2011年发布）长度为32字节，而AVX-512长度为64字节。有一些具有1024位或2048位向量的架构，甚至像ARM SVE一样具有可变向量宽度。 - phuclv

@phuclv，尽管当时可能已经有这些指令的说明，但您是否有任何证据表明memcpy使用它们？通常需要一段时间才能使库与其保持同步，而我能找到的最新库使用SSSE3并且比2011年要新得多。 - Pete Kirkham

显示剩余4条评论