这个memcpy实现有什么缺失/亚优化之处？

Question

我对编写 memcpy() 函数作为教育练习产生了兴趣。我不会写一篇关于我所思考和不思考的全部论文，但是这里有一个某人的实现：

__forceinline   // Since Size is usually known,
                // most useless code will be optimized out
                // if the function is inlined.

void* myMemcpy(char* Dst, const char* Src, size_t Size)
{
        void* start = Dst;
        for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
        {
                __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
                _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
        }

#define CPY_1B *((uint8_t * &)Dst)++ = *((const uint8_t * &)Src)++
#define CPY_2B *((uint16_t* &)Dst)++ = *((const uint16_t* &)Src)++
#define CPY_4B *((uint32_t* &)Dst)++ = *((const uint32_t* &)Src)++
#if defined _M_X64 || defined _M_IA64 || defined __amd64
#define CPY_8B *((uint64_t* &)Dst)++ = *((const uint64_t* &)Src)++
#else
#define CPY_8B _mm_storel_epi64((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const uint64_t* &)Src, ++(uint64_t* &)Dst
#endif
#define CPY16B _mm_storeu_si128((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const __m128i* &)Src, ++(__m128i* &)Dst

    switch (Size) {
    case 0x00:                                                      break;
    case 0x01:      CPY_1B;                                         break;
    case 0x02:              CPY_2B;                                 break;
    case 0x03:      CPY_1B; CPY_2B;                                 break;
    case 0x04:                      CPY_4B;                         break;
    case 0x05:      CPY_1B;         CPY_4B;                         break;
    case 0x06:              CPY_2B; CPY_4B;                         break;
    case 0x07:      CPY_1B; CPY_2B; CPY_4B;                         break;
    case 0x08:                              CPY_8B;                 break;
    case 0x09:      CPY_1B;                 CPY_8B;                 break;
    case 0x0A:              CPY_2B;         CPY_8B;                 break;
    case 0x0B:      CPY_1B; CPY_2B;         CPY_8B;                 break;
    case 0x0C:                      CPY_4B; CPY_8B;                 break;
    case 0x0D:      CPY_1B;         CPY_4B; CPY_8B;                 break;
    case 0x0E:              CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x0F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x10:                                      CPY16B;         break;
    case 0x11:      CPY_1B;                         CPY16B;         break;
    case 0x12:              CPY_2B;                 CPY16B;         break;
    case 0x13:      CPY_1B; CPY_2B;                 CPY16B;         break;
    case 0x14:                      CPY_4B;         CPY16B;         break;
    case 0x15:      CPY_1B;         CPY_4B;         CPY16B;         break;
    case 0x16:              CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x17:      CPY_1B; CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x18:                              CPY_8B; CPY16B;         break;
    case 0x19:      CPY_1B;                 CPY_8B; CPY16B;         break;
    case 0x1A:              CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1B:      CPY_1B; CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1C:                      CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1D:      CPY_1B;         CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1E:              CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    }
#undef CPY_1B
#undef CPY_2B
#undef CPY_4B
#undef CPY_8B
#undef CPY16B
        return start;
}

这条评论的意思是“通常大小在编译器优化代码时可以内联排除大部分无用内容”。

如果可能的话，我想改进一下这个实现——但也许没有太多可以改进的地方。我看到它对较大的内存块使用SSE/AVX，然后不是对最后小于32字节的循环进行循环，而是等效于手动展开，并进行了一些微调。那么，这里有我的问题：

• 为什么要展开最后几个字节的循环，而不是部分展开第一个（现在是单一的）循环？
• 对齐问题呢？它们不重要吗？我应该如何处理前几个字节，直到某个对齐量，然后在对齐的字节序列上执行256位操作？如果是这样，我如何确定适当的对齐量？
• 这个实现中最重要的缺失特性是什么（如果有的话）？

---

到目前为止，在答案中提到的功能/原则

• 您应该__restrict__您的参数。 (@chux)
• 内存带宽是一个限制因素；衡量您的实现是否达到它。(@Zboson)
• 对于小数组，您可以期望接近内存带宽；对于较大的数组-不太可能。 (@Zboson)
• 多个线程（可能）需要饱和内存带宽。 (@Zboson)
• 最好为大型和小型复制大小进行不同的优化。 (@Zboson)
• （对齐确实很重要吗？没有明确解释！）
• 编译器应该更加明确地了解它可以用于优化的“显而易见的事实”（例如Size < 32在第一个循环后）。 (@chux)
• 有关展开SSE/AVX调用的论点（@BenJackson，此处），以及不这样做的论点（@PaulR）
• 非暂态传输（告诉CPU您不需要将目标位置缓存）应该对复制较大缓冲区有用。 (@Zboson)

- einpoklum

---

@MichaelDorgan：我也以为他/她在做一些神秘和魔幻的事情，但仔细检查后发现它非常简单。对我来说，它看起来像一个管风琴的安排... - einpoklum

我非常喜欢表达丰富的switch分支。看起来非常不错。满分10分，我会提交的 :) - dom0

这个实现中的“important missing feature”是错误的签名。期望匹配：void *memcpy(void * restrict s1, const void * restrict s2, size_t n);。 - chux - Reinstate Monica

即使使用优化编译器，可能也无法确定具有32个情况的 switch (Size) 是否与 Size 范围 0<=Size<32 匹配。或许可以尝试 switch (Size&31)？避免内部生成的 if size > 31。 - chux - Reinstate Monica

请注意，restrict关键字仅适用于没有内置函数的代码部分。在使用内置函数时，restrict关键字是无效的。 - Z boson

Answer 1

我一直在研究使用各种操作测量英特尔处理器的内存带宽，其中之一是memcpy。我已经在Core2、Ivy Bridge和Haswell上完成了这项工作。我大多数测试都使用了C/C++和内部函数（请参见下面的代码 - 但我目前正在用汇编重写我的测试）。

要编写自己有效的memcpy函数，了解绝对最佳带宽非常重要。该带宽是将被复制的数组大小的函数，因此高效的memcpy函数需要针对小型和大型（以及中间可能出现的情况）进行不同的优化。为了简单起见，我已经针对8192字节的小型数组和1 GB的大型数组进行了优化。

对于小型数组，每个核心的最大读取和写入带宽为：

Core2-Ivy Bridge             32 bytes/cycle
Haswell                      64 bytes/cycle

这是你应该针对小数组的基准。在我的测试中，我假设数组对齐到64字节，并且数组大小是 8*sizeof(float)*unroll_factor 的倍数。这是我目前在8192字节大小下的 memcpy 结果（Ubuntu 14.04，GCC 4.9，EGLIBC 2.19）：

                             GB/s     efficiency
    Core2 (p9600@2.66 GHz)  
        builtin               35.2    41.3%
        eglibc                39.2    46.0%
        asmlib:               76.0    89.3%
        copy_unroll1:         39.1    46.0%
        copy_unroll8:         73.6    86.5%
    Ivy Bridge (E5-1620@3.6 GHz)                        
        builtin              102.2    88.7%
        eglibc:              107.0    92.9%
        asmlib:              107.6    93.4%
        copy_unroll1:        106.9    92.8%
        copy_unroll8:        111.3    96.6%
    Haswell (i5-4250U@1.3 GHz)
        builtin:              68.4    82.2%     
        eglibc:               39.7    47.7%
        asmlib:               73.2    87.6%
        copy_unroll1:         39.6    47.6%
        copy_unroll8:         81.9    98.4%

"The asmlib 是 Agner Fog's asmlib。下面定义了 copy_unroll1 和 copy_unroll8 函数。

从这个表格中我们可以看出，GCC内置的memcpy在Core2上效果不佳，而EGLIBC中的memcpy在Core2或Haswell上也效果不佳。我最近确实检查过GLIBC的head版本，并且在Haswell上性能要好得多。在所有情况下，展开循环获得最佳结果。"

void copy_unroll1(const float *x, float *y, const int n) {
    for(int i=0; i<n/JUMP; i++) {
        VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    }
}

void copy_unroll8(const float *x, float *y, const int n) {
for(int i=0; i<n/JUMP; i+=8) {
    VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    VECNF().LOAD(&x[JUMP*(i+1)]).STORE(&y[JUMP*(i+1)]);
    VECNF().LOAD(&x[JUMP*(i+2)]).STORE(&y[JUMP*(i+2)]);
    VECNF().LOAD(&x[JUMP*(i+3)]).STORE(&y[JUMP*(i+3)]);
    VECNF().LOAD(&x[JUMP*(i+4)]).STORE(&y[JUMP*(i+4)]);
    VECNF().LOAD(&x[JUMP*(i+5)]).STORE(&y[JUMP*(i+5)]);
    VECNF().LOAD(&x[JUMP*(i+6)]).STORE(&y[JUMP*(i+6)]);
    VECNF().LOAD(&x[JUMP*(i+7)]).STORE(&y[JUMP*(i+7)]);
}

}

其中VECNF().LOAD对应SSE的_mm_load_ps()或AVX的_mm256_load_ps()，VECNF().STORE对应SSE的_mm_store_ps()或AVX的_mm256_store_ps()，JUMP为4（SSE）或8（AVX）。

对于大尺寸数据，最佳结果可通过使用非暂态存储指令和多线程实现。与许多人所认为的不同，单个线程通常无法饱和内存带宽。

void copy_stream(const float *x, float *y, const int n) {
    #pragma omp parallel for        
    for(int i=0; i<n/JUMP; i++) {
        VECNF v = VECNF().load_a(&x[JUMP*i]);
        stream(&y[JUMP*i], v);
    }
}

当使用SSE时，stream为_mm_stream_ps()，当使用AVX时，stream为_mm256_stream_ps()

以下是在我的E5-1620@3.6 GHz上使用四个线程对1 GB的memcpy结果，最大主存带宽为51.2 GB/s。

                         GB/s     efficiency
    eglibc:              23.6     46%
    asmlib:              36.7     72%
    copy_stream:         36.7     72%

再次表现不佳的是 EGLIBC。这是因为它没有使用非临时存储。

我修改了 eglibc 和 asmlib 中的 memcpy 函数，使其像这样并行运行。

void COPY(const float * __restrict x, float * __restrict y, const int n) {
    #pragma omp parallel
    {
        size_t my_start, my_size;
        int id = omp_get_thread_num();
        int num = omp_get_num_threads();
        my_start = (id*n)/num;
        my_size = ((id+1)*n)/num - my_start;
        memcpy(y+my_start, x+my_start, sizeof(float)*my_size);
    }
}

一般的memcpy函数需要考虑到数组未对齐到64字节（甚至32或16字节）以及大小不是32字节或展开因子的倍数的情况。此外，还需要决定何时使用非临时存储器。经验法则是仅在大于最大缓存级别（通常为L3）一半大小的情况下使用非临时存储器。但这些都是“次要”细节，我认为应该在优化大和小的理想情况后再处理。如果理想情况表现不佳，那么担心修正不对齐或非理想大小倍数的问题就没有太多意义了。 更新 根据Stephen Canon的评论，我了解到在Ivy Bridge和Haswell上使用“rep movsb”比“movntdqa”（一种非临时存储指令）更有效。英特尔称之为“增强型rep movsb（ERMSB）”。这在Intel优化手册的第3.7.6节“增强型REP MOVSB和STOSB操作（ERMSB）”中有描述。

此外，在Agner Fog的汇编语言子例程优化手册中，他在第17.9节“移动数据块（所有处理器）”中写道：

“有几种移动大块数据的方法。最常见的方法是：”

1. REP MOVS指令。
2. 如果数据对齐：使用最大可用寄存器大小的循环读写。
3. 如果大小固定：内联移动指令。
4. 如果数据未对齐：先移动所需的字节数使目标对齐。然后使用最大可用寄存器大小的循环读取未对齐数据并写入对齐数据。
5. 如果数据未对齐：先读取对齐数据，然后进行移位以补偿不对齐，并写入对齐数据。
6. 如果数据大小过大无法缓存，则使用非临时写入来绕过缓存。如有必要，进行移位以补偿不对齐。

一般的memcpy应考虑到这些点。另外，对于Ivy Bridge和Haswell，似乎点1比点6更适用于大型数组。不同的技术迭代需要使用不同的技巧，适用于Intel和AMD。我认为很明显，编写自己通用高效的memcpy函数可能会相当复杂。但在我查看的特殊情况中，我已经成功地比GCC内置的memcpy或EGLIBC中的函数更好，因此认为您无法比标准库更好的假设是不正确的。

- Z boson

---

@einpoklum，我指的是最慢缓存的一半大小。在一个8 MB L3缓存的系统上，一半的大小将是4 MB。我不能说我从经验中知道这个经验法则。这是我读到的东西。但是毫无疑问，当大小远大于最慢的缓存时（例如1 GB），非临时存储会产生显着的差异。 - Z boson

@einpoklum，为了对齐，您应该尝试并查看。我只比较了对齐和未对齐的指令，使用对齐内存的对齐指令获得了更好的结果。我的缓冲区对齐到4096字节。请记住，我正在努力接近理论最大值。一旦我实现了这一点，我可以针对不太理想的情况进行优化，但我怀疑我会这样做，因为像您一样，这只是为了教育目的。 - Z boson

@einpoklum，我将线程数设置为物理核心数，然后绑定线程。要了解原因，请阅读https://dev59.com/9F8e5IYBdhLWcg3w9-Rs中的问题、答案和评论。但我认为使用多个线程并不是作弊。这可以真正用于提高大型数组的`memcpy`效率（速度），特别是对于NUMA系统。但是，对于小数组，OpenMP开销占主导地位，结果实际上会更糟。 - Z boson

еңЁIvybridgeе’ҢHaswellжһ¶жһ„дёҠпјҢдҪҝз”Ёrep movsbеҗ‘еҶ…еӯҳжөҒејҸдј иҫ“ж•°жҚ®жҜ”дҪҝз”Ёmovntdqaеҝ«еҫ—еӨҡпјҲдҪҶиҜ·жіЁж„ҸпјҢеңЁIvybridgeд№ӢеүҚзҡ„еӨ„зҗҶеҷЁдёҠе®ғдјҡеҫҲж…ўпјҒпјүгҖӮ - Stephen Canon

@StephenCanon，我终于开始研究“enhanced rep movsb”了 https://dev59.com/0ek5XIcBkEYKwwoY_O13。 - Z boson

Answer 2

这个问题没有精确的答案，需要一些额外的细节，例如：

• 目标平台是什么（CPU架构，大多数情况下，但内存配置也起到一定作用）？
• 复制长度的分布和可预测性如何（在某种程度上，对齐的分布和可预测性也是如此）？
• 复制大小在编译时是否会被静态知道？

即使如此，我还是可以指出几件事，它们在上述参数的某些组合中可能不太优化。

32-case Switch Statement

32个case语句是一种处理0到31个字节的巧妙方法，很可能基准测试表现良好，但由于至少两个因素，在实际世界中可能表现不佳。

代码大小

这个switch语句的代码体本身就需要几百字节，再加上一个32项查找表以跳转到每个长度的正确位置。这样做的代价在完整CPU的最快缓存级别中不会在memcpy的专注基准测试中显示出来，但在现实世界中，您也要执行其他代码，并且对于uop缓存、L1数据和指令缓存存在争用。

那么多的指令可能占据您的uop缓存有效大小的20%³，并且uop缓存未命中（以及相应的缓存到遗留编码器的转换周期）很容易抵消此复杂开关所带来的微小好处。

除此之外，该开关还需要一个32项、256字节的查找表以获取跳转目标⁴。如果您在该查找中错过了DRAM，那么惩罚将达到150个以上的周期：考虑到它可能只能节省一两个周期，那么您需要多少次非命中才能使switch值得？同样，在微基准测试中不会显示出来。

就其价值而言，这个 memcpy 并不罕见：即使在优化的库中也常见到这种“详尽列举情况”的方式。我可以得出结论，要么他们的开发主要受微基准测试驱动，要么即使有缺点，它对大量通用代码仍然很有价值。话虽如此，在某些场景下（指令和/或数据缓存压力），这种方式是次优的。

分支预测

switch 语句依赖一个单独的 间接分支 来选择其中的一种情况。这将在分支预测器可以预测这个间接分支的程度上变得高效，这基本上意味着观察到的长度序列需要是可预测的。

由于它是一个间接分支，与条件分支相比，对分支的可预测性有更多的限制，因为 BTB 条目数量有限。最近的 CPU 在这方面取得了进展，但可以肯定的是，如果传递给 memcpy 的长度序列不遵循简单的重复模式（在旧 CPU 上可能短至 1 或 2），每次调用都会出现分支预测错误。

这个问题特别难以察觉，因为在现实世界中，它很可能会在微基准测试显示switch是最好的情况下对你造成最大的伤害：短长度。对于非常长的长度，由于受到大量复制的支配，尾部31字节的行为并不重要。对于短长度，switch非常重要（事实上，对于31字节或更少的复制，它是唯一执行的代码）！

对于这些短长度，可预测的一系列长度非常适合使用switch，因为间接跳转基本上是免费的。特别地，一个典型的memcpy基准测试会“扫描”一系列长度，对于每个子测试重复使用相同的长度，以便报告"时间vs长度"图表的结果。在这些测试中，switch表现出色，通常报告小几字节的小长度需要2或3个周期的结果。

在现实世界中，你的长度可能是小但不可预测的。在这种情况下，间接分支经常会出现错误预测，对于现代CPU而言，惩罚大约为20个周期。与最佳情况下的几个周期相比，它差了一个数量级。因此，在这里容易遇到非常严重的问题（即，在这种典型情况下，switch的行为可能比最佳情况差一个数量级，而在较长的长度上，不同策略之间的差异通常最多只有50%）。

解决方案

那么在switch失效的条件下，如何做得更好呢？

使用Duff's Device 解决代码大小问题的一种方法是将switch case组合在一起，类似于Duff's Device。

例如，长度为1、3和7的情况的汇编代码如下：

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

长度为3

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx

长度为7

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx
    mov     edx, DWORD PTR [rsi+3]
    mov     DWORD PTR [rcx+3], edx
    ret

这可以合并成单个案例，并带有各种跳转：

    len7:
    mov     edx, DWORD PTR [rsi-6]
    mov     DWORD PTR [rcx-6], edx
    len3:
    movzx   edx, WORD PTR [rsi-2]
    mov     WORD PTR [rcx-2], dx
    len1:
    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

标签不需要任何费用，它们将案例组合在一起，并删除了三个中的两个ret指令。请注意，此处rsi和rcx的基础已更改：它们指向要从/复制到的最后一个字节，而不是第一个字节。该更改是免费或非常便宜的，具体取决于跳转之前的代码。

您可以将其扩展到更长的长度（例如，您可以将长度15和31附加到上面的链中），并使用其他链来处理缺失的长度。完整的练习留给读者。您可能仅通过此方法就能获得50％的大小减小，如果将其与其他东西结合使用以折叠16-31的大小，则效果会更好。

此方法只有助于代码大小（如果按照⁴中所述缩小大小并使其小于256字节，则可能还有助于跳转表大小，从而允许使用一个字节大小的查找表）。它对可预测性没有任何作用。

重叠存储

一种有助于减小代码大小和提高可预测性的技巧是使用重叠存储。也就是说，可以通过两个8字节的存储器实现8到15字节的memcpy，其中第二个存储器部分地与第一个存储器重叠。例如，要复制11个字节，您需要在相对位置0和11-8 == 3处进行8字节的复制。中间的一些字节会被“复制两次”，但在实践中，这是可以接受的，因为8字节的复制速度与1、2或4字节的复制速度相同。

C代码如下：

  if (Size >= 8) {
    *((uint64_t*)Dst) = *((const uint64_t*)Src);
    size_t offset = Size & 0x7;
    *(uint64_t *)(Dst + offset) = *(const uint64_t *)(Src + offset);
  }

...而相应的汇编并不成问题：

    cmp     rdx, 7
    jbe     .L8
    mov     rcx, QWORD PTR [rsi]
    and     edx, 7
    mov     QWORD PTR [rdi], rcx
    mov     rcx, QWORD PTR [rsi+rdx]
    mov     QWORD PTR [rdi+rdx], rcx

特别要注意的是，你会得到正好两个加载、两个存储和一个and（除了cmp和jmp，它们的存在取决于如何组织周围的代码）。这已经与大多数编译器生成的 8-15 字节的方法相当或更好，这些方法可能使用高达 4 个加载/存储对。

旧的处理器对这种“重叠存储”会有一些惩罚，但新的架构（至少过去十年左右）似乎可以处理它们而没有惩罚。这有两个主要优点：

1. 在一定范围内，行为是无分支的。有效地，这将分支量化，使得许多值采用相同的路径。所有大小从 8 到 15（或 8 到 16 如果您愿意）采用相同的路径，并且没有错误预测压力。

2. 来自 switch 的至少 8 或 9 种不同情况被合并为单个情况，总代码大小的一小部分。

这种方法可以与“switch”方法结合使用，但仅使用少量情况，或者可以通过条件移动扩展到更大的大小，例如可以执行从8到31字节的所有移动而无需分支。具体取决于分支分布，但总体而言，“重叠”技术非常有效。

对齐

现有代码没有解决对齐问题。事实上，在一般情况下，这不是C或C ++的合法用法，因为“char *”指针仅被强制转换为较大的类型并进行了间接引用，这是不合法的 - 尽管在实践中，它生成的代码适用于今天的x86编译器（但实际上会在具有更严格对齐要求的平台上失败）。除此之外，通常最好专门处理对齐。有三种主要情况：

1. 源地址和目标地址已对齐。即使使用原始算法也可以正常工作。
2. 源地址和目标地址是相对对齐的，但绝对上未对齐。也就是说，有一个值 A 可以添加到源地址和目标地址上，使它们都对齐。
3. 源地址和目标地址完全不对齐（即它们实际上没有对齐，且情况（2）不适用）。

现有算法在情况（1）下可以正常工作。在情况（2）中，它可能错过了一个很大的优化机会，因为小的引入循环可以将未对齐的复制变成对齐的。

同时，在情况（3）下其表现可能非常差，因为通常在完全不对齐的情况下你可以选择将目标或源地址对齐，然后“半对齐”地进行。

随着时间的推移，对齐惩罚越来越小，在最近的芯片上对于通用代码而言惩罚较小，但对于具有许多加载和存储操作的代码仍可能造成严重影响。对于大型复制，这可能并不太重要，因为最终会受到 DRAM 带宽限制，但对于较小的复制，未对齐可能会将吞吐量降低 50% 或更多。

如果使用 NT 存储，则对齐也很重要，因为许多 NT 存储指令在参数不对齐时性能表现较差。

不展开循环

代码未被展开，而不同编译器默认的展开数量也不同。显然这是次优的，因为在两个具有不同展开策略的编译器中，最多只有一个是最佳的。

最好的方法（至少对于已知的平台目标）是确定哪个展开因子最好，然后将其应用于代码中。

此外，展开循环通常可以与“intro”或“outro”代码以一种聪明的方式结合使用，做得比编译器更好。

已知大小

现代编译器之所以难以击败"内置"的memcpy例程，主要原因是编译器不仅在源代码中出现memcpy时调用库memcpy，而且它们知道memcpy的约定，并可以在适当情况下用单个内联指令甚至更少来实现它。

这在memcpy中的已知长度尤其明显。在这种情况下，如果长度很小，编译器将只插入几个指令以有效地原地执行复制。这不仅避免了函数调用的开销，而且还避免了所有与大小相关的检查 - 并且还生成了在编译时有效的复制代码，就像上面实现的大型switch一样 - 但没有switch的成本。

同样，编译器对于调用代码中的结构体对齐方式了解很多，并且可以创建有效处理对齐的代码。

如果你只是把memcpy2实现为库函数，则很难复制。你可以通过将该方法分成一个小和大部分来部分实现： 小部分出现在头文件中，执行一些大小检查并在大小较小时可能只调用现有的memcpy或者委派给库例程如果它很大。通过内联的魔法，你可能会得到与内置memcpy相同的结果。

最后，您还可以尝试使用__builtin_constant_p或等效方法来有效处理小型已知情况的技巧。

---

¹请注意，我在这里区分了“尺寸的分布”（例如，您可能会说在8到24字节之间均匀分布），以及实际尺寸序列的“可预测性”（例如，这些尺寸是否具有可预测的模式）？可预测性的问题有点微妙，因为它取决于实现方式，正如上面所述，某些实现方式本质上更加可预测。

²特别是，在 clang 中大约有750个字节的指令，在代码体中只有约600个字节的 gcc ，除此之外还有256字节的跳转查找表，其中包含了180-250个指令（分别针对gcc和clang）。 Godbolt链接。

³基本上是1000条指令缓存大小中的200个融合uops。虽然最近的x86处理器的uop缓存大小约为~1500 uops，但由于严格的代码/缓存分配规则，您不能在极为专用的填充代码库的情况下使用它们全部。

⁴ switch语句的编译长度不同，因此无法直接计算跳转。值得一提的是，可以采用不同的方法：在查找表中使用16位值，代价是不能使用内存源进行jmp，将其大小缩小75%。

⁵ 与典型最坏预测率为约50%的条件分支预测不同（对于完全随机的分支），难以预测的间接分支很容易接近100%，因为您不是抛硬币，而是选择一个几乎无限的分支目标集。这在现实世界中发生：如果使用memcpy复制长度在0到30之间均匀分布的小字符串，则switch代码会97%的时间错误预测。

⁶ 当然，可能存在未对齐存储的惩罚，但这些惩罚通常很小，并且越来越小。

例如，将数据复制到堆栈中，然后进行一些操作并将其复制到其他位置的memcpy可能会被完全消除，直接将原始数据移动到其最终位置。甚至像malloc后跟memcpy这样的事情也可以完全消除。

- BeeOnRope

---

@MaximMasiutin - 你的“跳转链”可能比间接跳转方法更糟糕。基本上，你必须看每个序列的可预测性。一般来说，当序列是不可预测的时，你的序列也会是不可预测的，否则就像间接跳转一样没问题。无论是直接还是间接跳转，一个错误的分支预测都差不多，所以通过将其改为一系列条件分支通常不会在预测方面获胜。你会失去很多东西：更多的指令，逐字节复制，消耗更多的分支预测资源等。 - BeeOnRope

（3）关于分支预测 - 实际上，每当您复制固定长度的内容时 - 短复制很可能是固定长度 - 编译器应该（？）在内联时完全放弃分支。对于长时间、在编译时未知的复制 - 尽管它们理论上可以是任意长度，但假设常见情况将是长度可被32整除的情况，即0x0的开关情况。我知道这一切都是推测，但这并不是牵强附会的推测... - einpoklum

@einpoklum - 编译器对此并没有做任何事情（除了合理地编译它，但仍然是32个单独的情况），我在我的答案中涵盖了它，并包括了在x86上为gcc和clang生成的汇编链接（见脚注2）。 - BeeOnRope

@einpoklum - 编译器肯定不会将整个memcpy内联，据我所知他们也不会进行“部分内联”（即内联函数的初始部分，然后调用其余部分）- 这就是我的观点，你可能需要拆分函数以便有机会进行内联。当然，长度不固定的复制非常普遍。我不知道哪种更常见，但可以肯定的是，大多数复制都非常短，许多复制都是任意长度的。几乎每个C++数据结构在幕后都在进行小型可变长度的复制。 - BeeOnRope

最近的英特尔芯片可以从一个核心驱动约30 GB/s，许多芯片有大约这么多的带宽。对于具有四通道内存的较大部件，你肯定需要超过一个核心。基本上，你可以在一个核心中达到最大带宽，你肯定需要NT存储。如果你不能做到这一点，你可能会发现普通存储更快（但只适用于一个核心，一旦你增加到更多的核心，NT将最终获胜，因为它节省了带宽）。 - BeeOnRope

Answer 3

利用ERMSB的好处

请考虑对更大的块使用REP MOVSB。

您知道，自从1993年生产第一款Pentium CPU以来，英特尔开始加速简单的命令，并使复杂的命令（如REP MOVSB）变慢。因此，REP MOVSB变得非常缓慢，没有使用它的理由。在2013年，英特尔决定重新审视REP MOVSB。如果CPU具有CPUID ERMSB（增强REP MOVSB）位，则REP MOVSB命令的执行方式与旧处理器不同，应该很快。实际上，只有在满足以下条件时才适用于大块，即256字节及以上：

• 源地址和目标地址都必须对齐到16字节边界；
• 源区域不应与目标区域重叠；
• 长度必须是64的倍数，才能产生更高性能；
• 方向必须是前向（CLD）。

请参考英特尔优化手册第3.7.6节“增强REP MOVSB和STOSB操作（ERMSB）”，链接如下：http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf。英特尔建议对小于2048字节的块使用AVX，对于更大的块，建议使用REP MOVSB，因为REP MOVSB的初始启动成本较高（约35个周期）。我进行了速度测试，对于2048字节及以上的块，REP MOVSB的性能是无与伦比的。然而，对于小于256字节的块，REP MOVSB非常缓慢，甚至比在循环中来回移动MOV RAX还要慢。请注意，ERMSB仅影响MOVSB，而不影响MOVSD（MOVSQ），因此MOVSB比MOVSD（MOVSQ）稍快一些。

因此，您可以使用AVX来实现memcpy()，如果块大于2048字节并且所有条件都满足，则调用REP MOVSB - 这样您的memcpy()实现将是无与伦比的。

利用乱序执行引擎的优势

您还可以在“Intel® 64和IA-32体系结构优化参考手册”http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf的2.1.2节中了解乱序执行引擎，并从中获益。

例如，在2015年推出的Intel SkyLake处理器系列中，它具有：

• 算术逻辑单元(ALU)有4个执行单元(加、与、比较、或、测试、异或、movzx、movsx、mov、(v)movdqu、(v)movdqa、(v)movap*、(v)movup)，
• 向量ALU有3个执行单元((v)pand、(v)por、(v)pxor、(v)movq、(v)movq、(v)movap*、(v)movup*、(v)andp*、(v)orp*、(v)paddb/w/d/q、(v)blendv*、(v)blendp*、(v)pblendd)。

如果我们使用仅寄存器操作，就可以并行占用上述单元(3+4)。但是我们不能在内存复制时同时使用3+4条指令。即使我们使用一级缓存，我们也最多可以同时使用两条32字节指令从内存中加载和一条32字节指令存储到内存中。

请再次查看英特尔手册以了解如何进行最快的memcpy实现：http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf 第2.2.2节（Haswell微架构的乱序引擎）：“调度程序控制将微操作分派到分派端口。有八个分派端口支持乱序执行核心。其中四个分派端口提供计算操作的执行资源。另外4个端口在一个周期内支持多达两个256位负载和一个256位存储操作的内存操作。”

第2.2.4节（高速缓存和存储器子系统）有以下说明：“第一级数据缓存每个周期支持两个负载微操作；每个微操作可以获取高达32字节的数据。”

第2.2.4.1节（加载和存储操作增强）包含以下信息：L1数据缓存每个周期可以处理两个256位（32字节）的加载和一个256位（32字节）的存储操作。统一的L2每个周期可以服务于一个缓存行（64字节）。此外，有72个加载缓冲区和42个存储缓冲区可用于支持正在执行的微操作。

其他部分（2.3等，专门针对Sandy Bridge和其他微架构）基本上重申了上述信息。

第2.3.4节（执行核心）提供了额外的细节。

调度程序每个周期可以分派最多六个微操作，每个端口一个。下表总结了哪些操作可以在哪个端口上分派。

• 端口0: 算术逻辑单元, 移位, 乘法, STTNI, 整除, 128b-Mov, 混合指令, 256b-Mov
• 端口1: 算术逻辑单元, 快速LEA, 慢速LEA, 乘法, Shuf, 混合指令, 128bMov, 加法, CVT
• 端口2 & 端口3: Load_Addr, Store_addr
• 端口4: Store_data
• 端口5: 算术逻辑单元, 移位, 分支, 快速LEA, Shuf, 混合指令, 128b-Mov, 256b-Mov

第2.3.5.1节（加载和存储操作概述）对于了解如何进行快速内存复制也可能是有用的，以及第2.4.4.1节（加载和存储）。

对于其他处理器架构，又是两个加载单元和一个存储单元。表2-4（Skylake微体系结构的高速缓存参数）提供以下信息：

峰值带宽（字节/周期）：

• 一级数据缓存：96字节（2x32B加载+1×32B存储）
• 二级缓存：64字节
• 三级缓存：32字节。

我还在我的Intel Core i5 6600 CPU（Skylake，14nm，于2015年9月发布）上进行了速度测试，并且这证实了这个理论。例如，我的测试表明，即使是许多寄存器并行使用通用64位寄存器进行内存复制，性能也会下降。此外，仅使用2个XMM寄存器就足够了-添加第3个不会增加性能。

如果您的CPU具有AVX CPUID位，则可以利用大型256位（32字节）YMM寄存器来复制内存，以占用两个完整的加载单元。 AVX支持最初由英特尔在Sandy Bridge处理器中引入，该处理器于2011年第一季度发货，并由AMD在Bulldozer处理器中随后发货，该处理器于2011年第三季度发货。

// first cycle  
vmovdqa ymm0, ymmword ptr [rcx+0]      // load 1st 32-byte part using first load unit
vmovdqa ymm1, ymmword ptr [rcx+20h]    // load 2nd 32-byte part using second load unit

// second cycle
vmovdqa ymmword ptr [rdx+0], ymm0      // store 1st 32-byte part using the single store unit

// third cycle
vmovdqa ymmword ptr [rdx+20h], ymm1    ; store 2nd 32-byte part - using the single store unit (this instruction will require a separate cycle since there is only one store unit, and we cannot do two stores in a single cycle)

add ecx, 40h // these instructions will be used by a different unit since they don't invoke load or store, so they won't require a new cycle
add edx, 40h

另外，如果您将此代码展开循环至少8次，还可以获得速度优势。正如我之前所写的那样，除了ymm0和ymm1之外再添加更多的寄存器并不能提高性能，因为只有两个加载单元和一个存储单元。像“dec r9 jnz @@again”这样的循环会降低性能，但简单的“add ecx/edx”则不会。

最后，如果您的CPU具有AVX-512扩展，您可以使用512位（64字节）寄存器来复制内存：

vmovdqu64   zmm0, [rcx+0]           ; load 1st 64-byte part
vmovdqu64   zmm1, [rcx+40h]         ; load 2nd 64-byte part 

vmovdqu64   [rdx+0], zmm0           ; store 1st 64-byte part
vmovdqu64   [rdx+40h], zmm1         ; store 2nd 64-byte part 

add     rcx, 80h
add     rdx, 80h    

AVX-512被以下处理器支持：2016年发布的Xeon Phi x200；Skylake EP/EX Xeon“Purley”（Xeon E5-26xx V5）处理器（H2 2017）；Cannonlake处理器（H2 2017），Skylake-X处理器-Core i9-7×××X，i7-7×××X，i5-7×××X-于2017年6月发布。请注意，内存必须对齐到您正在使用的寄存器大小。如果没有，请使用“不对齐”的指令：vmovdqu和moveups。

- Maxim Masiutin

---

我能用某种类似于C/C++的包装器实现这个吗？还是必须编写汇编代码？ - einpoklum

微软和英特尔编译器都有C包装器，但在我看来，汇编代码，无论是内联还是在单独的.asm文件中，应该更可取。问题是，你的目标是memcpy()速度，还是可移植性/简单性。 - Maxim Masiutin

@MaximMasiutin - 你试图混合使用SSE和64位的mov指令是不行的，因为ALU不执行加载。即使在最先进的x86 CPU上也只有两个加载单元，所以每个周期最多只能发出两个加载。所有大小（8位、16位、32位、...、256位）的加载都会发送到这些单元，因此通常最好使用可用的最大加载来复制大部分数据。 - BeeOnRope

@BeeOnRope - 我已经解决了这个问题。正如我在评论中提到的：“实际上，当我在我的Intel Core i5 6600 CPU（Skylake，14nm，于2015年9月发布）上使用DDR4内存进行速度测试时，使用通用64位寄存器进行内存复制会降低性能。此外，仅使用2个XMM寄存器就足够了-添加第3个不会增加性能。可能，CPU与其缓存之间的内存带宽受到限制-我已经测试过非常小的块，这些块完全适合我的CPU上32KB的L1缓存，其中32KB用于数据，32KB用于指令。”--因此只需要2个XMM即可。 - Maxim Masiutin

没错，但你的回答形式是“理论上应该可以，但实际上不行”。然而，事实是“在理论和实践中都不行”。这不是有用的信息吗？此外，你得出结论说你的“混合GP / SIMD”技术由于带宽问题而无法工作，但这并不完全正确：它无法工作是因为基于错误的机器模型。当然，如果你在大缓冲区上进行测试，你最终会受到带宽限制，因此即使使用错误的理论创建的低质量实现也可以“并列”好的实现，但如果你在小缓冲区上进行测试，你会发现你的理论是错误的。 - BeeOnRope

@BeeOnRope，非常感谢您指出这一点。我已经重写了相关部分。再次感谢。 - Maxim Masiutin

Answer 4

首先，主循环使用未对齐的AVX向量加载/存储每次复制32字节，直到剩下要复制的字节数小于32:

    for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
    {
        __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
        _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
    }

然后，最终的switch语句以尽可能高效的方式处理剩余的0..31个字节，使用适当的8/4/2/1字节复制的组合。请注意，这不是一个展开的循环 - 它只是32个不同的优化代码路径，使用最少的加载和存储来处理残留字节。

至于为什么主要的32字节AVX循环没有手动展开 - 这可能有几个原因：

- 大多数编译器会自动展开小循环（取决于循环大小和优化开关） - 过度展开会导致小循环溢出LSD缓存（通常只有28个解码µops） - 在当前的Core iX CPU上，您只能发出两个并发的加载/存储指令，然后就会停顿 - 通常，即使像这样未展开的AVX循环也可以饱和可用的DRAM带宽

[*]请注意，上面的最后两条评论适用于源和/或目标不在缓存中的情况下（即写入/读取到/从DRAM），因此加载/存储延迟较高。

- Paul R

---

switch语句不是展开的循环——它只是32种不同的代码路径，取决于剩余要复制的字节数。 - Paul R

请注意不同的复制大小（1、2、4、8字节）- 这不是展开的标量循环，而只是31个不同的小优化副本来清除剩余的字节。无论你怎么称呼它，但你错过了重点 - 在一般情况下，重要的工作是由AVX循环完成的。 - Paul R

循环没有展开，因为它不需要展开。如果它已经被展开了，那么小数组大小的结果将会有很大不同。在 Core2-Haswell 上，使用循环展开四次或八次可以获得更好的结果。在 Haswell 上，不进行展开只能得到峰值性能的50%以下（我得到的结果约为47%）。在 Haswell 上展开八次可以获得约98%的性能。 - Z boson

@Zboson：我在你的回答中对NT存储作了评论，但我在这里会进一步展开：x86 NT存储的语义在memcpy中使用时存在缺陷；当它们命中L1时，速度极慢，并且当它们错过L3时需要进行读取所有权。因此，vmovaps在小拷贝上要快得多，而rep movs在大拷贝上要快得多（在Ivybridge及更高版本中）。此外，请记住，NT存储需要一个屏障，这不是很麻烦，但这是要记住的另一个细节。 - Stephen Canon

@Zboson：仅限IVB及其以后版本。这是IVB和SNB之间的主要微架构差异之一。英特尔将此功能称为“ERMSB”（增强型rep movsb/stosb）。 - Stephen Canon