这个memcpy实现中缺少什么/次优?

我对编写memcpy()作为一种教育练习感兴趣。 我不会写一篇关于我做了什么和没想过的论文,但这里有一些人的实现 :

 __forceinline //因为通常Size已知,内联后编译器可以优化掉大部分无用代码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位操作吗? 如果是这样,我如何确定适当的对齐量?
  • 这个实现中最重要的缺失function是什么(如果有的话)?

到目前为止答案中提到的function/原则

  • 你应该__restrict__您的参数。 (@chux)
  • 内存带宽是一个限制因素; 衡量你的实施情况。(@ Zboson)
  • 对于小型arrays,您可以期望接近内存带宽; 对于较大的arrays – 没有那么多。 (@Zboson)
  • 需要多个线程(可能是)使内存带宽饱和。 (@Zboson)
  • 对于大小复制尺寸进行不同的优化可能是明智之举。 (@Zboson)
  • (对齐重要?没有明确解决!)
  • 应该使编译器更明确地意识到它可以用于优化的“明显事实”(例如在第一个循环之后Size <32的事实)。 (@chux)
  • 有解释你的SSE / AVX调用的参数(@BenJackson, 这里 )和反对这样做的参数(@PaulR)
  • 非时间传输 (使用它告诉CPU你不需要它来缓存目标位置)对于复制较大的缓冲区应该是有用的。 (@Zboson)

我一直在研究测量具有各种操作的英特尔处理器的内存带宽,其中一个是memcpy 。 我在Core2,Ivy Bridge和Haswell上做过这个。 我使用带有内在函数的C / C ++完成了大部分测试(请参阅下面的代码 – 但我目前正在重新编写程序集中的测试)。

要编写自己的高效memcpy函数,了解可能的绝对最佳带宽非常重要。 这个带宽是将被复制的数组大小的函数,因此有效的memcpy函数需要针对小和大(以及可能之间)进行不同的优化。 为了简单起见,我针对8192字节的小型数组和1 GB的大型数组进行了优化。

对于小型arrays,每个内核的最大读写带宽为:

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

这是您应该针对小型arrays的基准。 对于我的测试,我假设数组对齐到64字节,并且数组大小是8*sizeof(float)*unroll_factor 。 以下是我目前的memcpy结果,大小为8192字节(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% 

asmlib是Agner Fog的asmlib 。 copy_unroll1copy_unroll8函数定义如下。

从这个表中我们可以看到GCC内置memcpy在Core2上不能很好地工作,并且EGLIBC中的memcpy在Core2或Haswell上不能很好地工作。 我最近检查了GLIBC的头版本,并且在Haswell上的表现要好得多。 在所有情况下,展开都会获得最佳结果。

 void copy_unroll1(const float *x, float *y, const int n) { for(int i=0; i 

}

其中VECNF().LOAD是SSE的_mm256_load_ps()或AVX的VECNF().STOREVECNF().STORE对于VECNF().STORE_mm_store_ps() ,对于AVX, VECNF().STORE_mm256_store_ps()对于_mm256_store_ps() ,JUMP是4,对于AVX,JUMP是8。

对于大尺寸,通过使用非临时存储指令和使用多个线程来获得最佳结果。 与许多人可能认为的相反, 单个线程通常不会使内存带宽饱和 。

 void copy_stream(const float *x, float *y, const int n) { #pragma omp parallel for for(int i=0; i 

对于SSE, stream_mm_stream_ps() ,对于AVX,是_mm_stream_ps()

以下是我的E5-1620@3.6 GHz上的memcpy结果,其中四个线程为1 GB, 最大主内存带宽为51.2 GB / s 。

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

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

我修改了eglibcasmlib 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) 。 英特尔优化手册中的3.7.6增强型REP MOVSB和STOSB操作(ERMSB)一节对此进行了描述

另外,在第17.9移动数据块(所有处理器)的 Agner Fog的assembly手册中的优化子程序中 ,他写道:

“有几种方法可以移动大块数据。最常见的方法是:

  1. REP MOVS指令。
  2. 如果数据是对齐的:在具有最大可用寄存器大小的循环中进行读写。
  3. 如果大小不变:内联移动指令。
  4. 如果数据未对齐:首先移动所需的字节数以使目标对齐。 然后读取未对齐并在具有最大可用寄存器大小的循环中进行对齐。
  5. 如果数据未对齐:读取对齐,移位以补偿未对准并写入对齐。
  6. 如果数据大小太大而无法进行缓存,请使用非临时写入来绕过缓存。 如有必要,转移以补偿错位。“

一般的memcpy应该考虑这些要点。 此外,对于Ivy Bridge和Haswell来说,对于大型arrays来说,点1似乎优于点6。 英特尔和AMD以及每次技术迭代都需要不同的技术。 我认为编写自己的通用高效memcpy函数显然非常复杂。 但是在我看到的特殊情况下,我已经设法比GCC内置memcpy或EGLIBC中的那个做得更好,所以假设你不能做得比标准库更好是不正确的。

首先,主循环使用未对齐的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)的情况,因此加载/存储延迟很高。

如果没有一些额外的细节,这个问题就无法准确回答:

  • 什么是目标平台(CPU架构,大多数,但内存配置也起作用)?
  • 复制长度的分布和可预测性1是什么(在较小程度上,比对的分布和可预测性)?
  • 复制大小是否会在编译时静态知道?

尽管如此,我仍然可以指出一些对于上述参数的至少一些组合可能是次优的事情。

32个案例的Switch语句

32个案例的switch语句是处理0到31个字节的可爱方式,并且很可能是基准测试 – 但由于两个因素,可能在现实世界中表现不佳。

代码大小

除了32项之外,这个switch语句本身只需要几百个字节的代码。 这样的成本不会出现在全尺寸CPU上的memcpy聚焦基准测试中,因为所有内容仍然适用于最快的缓存级别:但在现实世界中,您也执行其他代码并且存在对uop的争用缓存和L1数据和指令缓存。

许多指令可能占用uop缓存3的有效大小的20%,并且uop缓存未命中(以及相应的缓存到传统编码器转换周期)可以轻易地消除这个复杂交换机给出的小优势。

最重要的是,交换机需要一个32条,256字节的查找表用于跳转目标4 。 如果您在查找中错过了DRAM,那么您正在谈论150多个周期的惩罚:您需要多少次非失误才能使switch值得,因为它可能最多可以节省几个或两个? 同样,这不会出现在微基准测试中。

值得一提的是,这个memcpy并不罕见:即使在优化的库中,这种“详尽的枚举案例”也很常见。 我可以得出结论,要么它们的开发主要是由微基准测试驱动的,要么它仍然值得用于大量的通用代码,尽管存在缺点。 也就是说,确实有一些情况(指令和/或数据缓存压力),这是不理想的。

分支预测

switch语句依赖于单个间接分支来在备选方案中进行选择。 这在分支预测器可以预测这种间接分支的程度上是有效的,这基本上意味着观察到的长度序列需要是可预测的。

因为它是间接分支,所以对分支的可预测性的限制比条件分支更多,因为存在有限数量的BTB条目。 最近的CPU已经取得了长足的进步,但可以肯定的是,如果送入memcpy的一系列长度不遵循短周期的简单重复模式(在旧CPU上短至1或2),则会有一个每次通话时都会错误预测。

这个问题特别阴险,因为在微基准测试表明switch最佳的情况下,它可能会在现实世界中给您带来最大的伤害:短的长度。 对于非常长的长度,尾随31个字节的行为不是很重要,因为它由批量复制支配。 对于较短的长度, switch是非常重要的(实际上,对于31字节或更少的副本,它就是所有执行的)!

对于这些短的长度,可预测的一系列长度对于switch非常有效,因为间接跳跃基本上是免费的。 特别是,典型的memcpy基准测试“扫描”一系列长度,每个子测试重复使用相同的长度来报告结果,以便轻松绘制“时间与长度”图形。 该switch在这些测试中表现很好,通常会报告两个或三个周期的结果,只需几个字节的小长度。

在现实世界中,你的长度可能很小但不可预测 。 在这种情况下,间接分支将经常错误预测5 ,在现代CPU上惩罚约20个周期。 与几个周期的最佳情况相比,它更糟糕一个数量级。 因此,这里的玻璃钳口可能非常严重(即,在这种典型情况下, switch的行为可能比最佳情况差一个数量级,而在长距离情况下,您通常会看到最多50%的差异。不同的策略)。

解决方案

那么你怎么能比上面做得更好,至少在switch分崩离析的情况下呢?

使用Duff的设备

代码大小问题的一个解决方案是将开关案例组合在一起, duff的设备风格。

例如,长度为1,3和7的组合代码如下所示:

长度1

  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 

标签不需要任何费用,它们将这些案例组合在一起并删除3个ret中的两个。 请注意, rsircx的基础在这里发生了变化:它们指向要复制的最后一个字节,而不是第一个。 根据跳转前的代码,这种变化是免费的或非常便宜的。

您可以将其延长更长的长度(例如,您可以将长度15和31连接到上面的链),并使用其他链来查找缺失的长度。 完整的练习留给读者。 你可以通过这种方法单独减少50%的尺寸,如果你将它与其他东西结合起来,可以将尺寸从16 – 31缩小到更好。

这种方法只对代码大小(以及可能的跳转表大小有帮助,如果你缩小4中所述的大小,你得到256字节以下,允许一个字节大小的查找表。它没有任何可预测性。

重叠商店

有助于代码大小和可预测性的一个技巧是使用重叠存储。 也就是说,8到15个字节的memcpy可以通过两个8字节存储以无分支方式完成,第二个存储部分与第一个存储部分重叠。 例如,要复制11个字节,您将在相对位置011 - 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 

特别要注意的是,你得到两个加载,两个存储和一个(除了cmpjmp它的存在取决于你如何组织周围的代码)。 这已经与大多数编译器生成的8-15字节方法相关联或更好,最多可能使用4个加载/存储对。

较旧的处理器在这种“重叠商店”中受到了一定的惩罚,但是较新的架构(至少在过去十年左右)似乎处理它们而没有受到惩罚6 。 这有两个主要优点:

  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存储指令在未对齐的参数下表现不佳。

没有展开

代码未展开,默认情况下编译器以不同的数量展开。 很明显,这是次优的,因为在具有不同展开策略的两个编译器中,最多只有一个是最好的。

最佳方法(至少对于已知平台目标)确定哪个展开因子最佳,然后将其应用于代码中。

此外,展开通常可以通过“介绍”我们的“outro”代码以智能方式组合,比编译器做得更好。

已知尺寸

使用现代编译器很难击败“内置” memcpy例程的主要原因是,只要memcpy出现在源代码中,编译器就不会只调用库memcpy 。 他们知道memcpy的合同,并且可以在正确的场景中使用单个内联指令自由实现它,甚至更少7个

对于memcpy已知的长度,这一点尤其明显。 在这种情况下,如果长度很小,编译器将只插入一些指令来有效地和就地执行复制。 这不仅避免了函数调用的开销,而且还避免了所有关于大小等的检查 – 并且还在编译时生成了复制的高效代码,就像上面实现中的大switch一样 – 但没有switch的成本。

类似地,编译器知道很多关于调用代码中结构的对齐,并且可以创建有效处理对齐的代码。

如果您只是将memcpy2实现为库函数,则很难复制。 你可以在这里将部分方法分成一个部分: 部分出现在头文件中,并进行一些大小检查,如果大小很小或者委托给库,可能只调用现有的memcpy常规如果很大。 通过内联的魔力,你可能会和内置的memcpy一样到达同一个地方。

最后,您还可以尝试使用__builtin_constant_p或等效函数来有效处理小的已知案例。


1请注意,我在这里区分尺寸的“分布” – 例如,您可能会说_在8到24个字节之间均匀分布 – 以及实际尺寸序列的“可预测性”(例如,尺寸是否具有可预测的模式)? 可预测性的问题有些微妙,因为它取决于实现,因为如上所述,某些实现本质上更可预测。

2特别是, clang约750字节的指令和gcc约600字节的单独主体,在具有180-250指令(分别为gccclang )的交换机主体的256字节跳转查找表之上。 Godbolt链接。

3基本上200个融合的uop,有效的uop缓存大小为1000条指令。 虽然最近x86的uop缓存大小约为~1500 uop,但由于代码到缓存的分配规则限制,你不能在代码库的极其专用的填充之外使用它。

4开关盒具有不同的编译长度,因此无法直接计算跳转。 对于它的价值,可能会有不同的做法:它们可能在查找表中使用了16位值,代价是不使用jmp内存源,将其大小减少了75%。

5与条件分支预测不同,条件分支预测具有~50%的典型最坏情况预测率(对于完全随机分支),难以预测的间接分支可以轻松接近100%,因为您没有翻转硬币,您是选择几乎无限的分支目标。 这种情况发生在现实世界中:如果使用memcpy来复制长度均匀分布在0到30之间的小字符串,则switch代码将错误预测~97%的时间。

6当然,对于未对齐的商店可能会受到处罚,但这些商店通常也很小并且变得越来越小。

7例如,可以完全消除堆栈的memcpy ,然后在其他地方进行一些操作和复制,直接将原始数据移动到其最终位置。 甚至像malloc后跟memcpy这样的东西也可以完全消除。

Taking Benefits of The ERMSB

Please also consider using REP MOVSB for larger blocks.

As you know, since first Pentium CPU produced in 1993, Intel began to make simple commands faster and complex commands (like REP MOVSB) slower. So, REP MOVSB became very slow, and there was no more reason to use it. In 2013, Intel decided to revisit REP MOVSB. If the CPU has CPUID ERMSB (Enhanced REP MOVSB) bit, then REP MOVSB commands are executed differently than on older processors, and are supposed to be fast. On practice, it is only fast for large blocks, 256 bytes and larger, and only when certain conditions are met:

  • both the source and destination addresses have to be aligned to a 16-Byte boundary;
  • the source region should not overlap with the destination region;
  • the length has to be a multiple of 64 to produce higher performance;
  • the direction has to be forward (CLD).

See the Intel Manual on Optimization, section 3.7.6 Enhanced REP MOVSB and STOSB operation (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel recommends using AVX for blocks smaller than 2048 bytes. For the larger blocks, Intel recommends using REP MOVSB. This is because high initial startup costs of REP MOVSB (about 35 cycles).

I have done speed tests, and for the blocks of than 2048 bytes and higher, the performance of REP MOVSB is unbeatable. However, for blocks smaller than 256 bytes, REP MOVSB is very slow, even slower than plain MOV RAX back and forth in a loop.

Please not that ERMSB only affects MOVSB, not MOVSD (MOVSQ), so MOVSB is little bit faster than MOVSD (MOVSQ).

So, you can use AVX for your memcpy() implementation, and if the block is larger than 2048 bytes and all the conditions are met, then call REP MOVSB – so your memcpy() implementation will be unbeatable.

Taking Benefits of The Out-of-Order Execution Engine

You can also read about The Out-of-Order Execution Engine in the “Intel® 64 and IA-32 Architectures Optimization Reference Manual” http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf section the 2.1.2, and take benefits of it.

For example, in Intel SkyLake processor series (launched in 2015), it has:

  • 4 execution units for the Arithmetic logic unit (ALU) (add, and, cmp, or, test, xor, movzx, movsx, mov, (v)movdqu, (v)movdqa, (v)movap*, (v)movup),
  • 3 execution units for Vector ALU ( (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)

So we can occupy above units (3+4) in parallel if we use register-only operations. We cannot use 3+4 instructions in parallel for memory copy. We can use simultaneously maximum of up to two 32-bytes instructions to load from memory and one 32-bytes instructions to store from memory, and even if we are working with Level-1 cache.

Please see the Intel manual again to understand on how to do the fastest memcpy implementation: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Section 2.2.2 (The Out-of-Order Engine of the Haswelll microarchitecture): “The Scheduler controls the dispatch of micro-ops onto the dispatch ports. There are eight dispatch ports to support the out-of-order execution core. Four of the eight ports provided execution resources for computational operations. The other 4 ports support memory operations of up to two 256-bit load and one 256-bit store operation in a cycle.”

Section 2.2.4 (Cache and Memory Subsystem) has the following note: “First level data cache supports two load micro-ops each cycle; each micro-op can fetch up to 32-bytes of data.”

Section 2.2.4.1 (Load and Store Operation Enhancements) has the following information: The L1 data cache can handle two 256-bit (32 bytes) load and one 256-bit (32 bytes) store operations each cycle. The unified L2 can service one cache line (64 bytes) each cycle. Additionally, there are 72 load buffers and 42 store buffers available to support micro-ops execution in-flight.

The other sections (2.3 and so on, dedicated to Sandy Bridge and other microarchitectures) basically reiterate the above information.

The section 2.3.4 (The Execution Core) gives additional details.

The scheduler can dispatch up to six micro-ops every cycle, one on each port. The following table summarizes which operations can be dispatched on which port.

  • Port 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
  • Port 1: ALU, Fast LEA, Slow LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
  • Port 2 & Port 3: Load_Addr, Store_addr
  • Port 4: Store_data
  • Port 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

The section 2.3.5.1 (Load and Store Operation Overview) may also be useful to understand on how to make fast memory copy, as well as the section 2.4.4.1 (Loads and Stores).

For the other processor architectures, it is again – two load units and one store unit. Table 2-4 (Cache Parameters of the Skylake Microarchitecture) has the following information:

Peak Bandwidth (bytes/cyc):

  • First Level Data Cache: 96 bytes (2x32B Load + 1*32B Store)
  • Second Level Cache: 64 bytes
  • Third Level Cache: 32 bytes.

I have also done speed tests on my Intel Core i5 6600 CPU (Skylake, 14nm, released in September 2015) with DDR4 memory, and this has confirmed the teory. For example, my test have shown that using generic 64-bit registers for memory copy, even many registers in parallel, degrades performance. Also, using just 2 XMM registers is enough – adding the 3rd doesn’t add performance.

If your CPU has AVX CPUID bit, you may take benefits of the large, 256-bit (32 byte) YMM registers to copy memory, to occupy two full load units. The AVX support was first introduced by Intel with the Sandy Bridge processors, shipping in Q1 2011 and later on by AMD with the Bulldozer processor shipping in Q3 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 

Also, there is speed benefit if you loop-unroll this code at least 8 times. As I wrote before, adding more registers besides ymm0 and ymm1 doesn’t increase performance, because there are just two load units and one store unit. Adding loops like “dec r9 jnz @@again” degrades the performance, but simple “add ecx/edx” does not.

Finally, if your CPU has AVX-512 extension, you can use 512-bit (64-byte) registers to copy memory:

 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 is supported by the following processors: Xeon Phi x200, released in 2016; Skylake EP/EX Xeon “Purley” (Xeon E5-26xx V5) processors (H2 2017); Cannonlake processors (H2 2017), Skylake-X processors – Core i9-7×××X, i7-7×××X, i5-7×××X – released on June 2017.

Please note that the memory have to be aligned on the size of the registers that you are using. If it is not, please use “unaligned” instructions: vmovdqu and moveups.