在这个memcpy实现中最佳？
我一直在研究用各种操作测量英特尔处理器的内存带宽，其中之一是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 。 这里是我当前的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_unroll1和copy_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<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是_mm_load_ps()为SSE或_mm256_load_ps()为AVX， VECNF().STORE是_mm_store_ps()为SSE或_mm256_store_ps()为AVX，和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);
}
}
其中stream是_mm_stream_ps()用于SSE或_mm256_stream_ps()用于AVX
以下是E5-1620@3.6 GHz上的memcpy结果，其中4个线程为1 GB，最大主内存带宽为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）。 这在英特尔优化手册中的3.7.6节增强型REP MOVSB和STOSB操作（ERMSB）中进行了描述。
此外，在第17.9节“移动数据块（所有处理器）”中的Agner Fog的“优化子程序的汇编手册”中，他写道：
“移动大块数据有几种方法，最常用的方法是：
一般的memcpy应该考虑每一点。 此外，在Ivy Bridge和Haswell看来，对于大型阵列来说，点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循环没有被手动展开 - 有几种可能的原因：
[*]请注意，上面的最后两条评论适用于源和/或目的地不在高速缓存中的情况（即向/从DRAM写入/读取），因此加载/存储延迟较高。
如果没有一些额外的细节，这个问题就无法精确回答，例如：
尽管如此，我还是可以指出一些事情，对于上述参数的至少一些组合，可能是次优的。
32个开关语句
32个字母的switch语句是处理尾部0到31个字节的可爱方式，可能的基准非常好 - 但由于两个因素，在现实世界中可能表现不佳。
代码大小
除了一个32条目外，这个switch语句还需要几百个字节的代码。 这个成本不会在全尺寸CPU上的重要memcpy基准测试中显示出来，因为所有东西仍然适合最快的缓存级别：但是在现实世界中，您也执行其他代码，并且争夺uop缓存和L1数据和指令缓存。
许多指令可能会占用uop cache3的有效大小的20％，并且uop cache未命中（以及相应的cache-to-legacy编码器转换周期）可以很容易地消除这个精心设计的开关所带来的小小好处。
最重要的是，交换机需要一个32入口，256字节的跳转目标查找表4。 如果你在这个查询中对DRAM有些怀念，那么你说的惩罚是150+循环：那么你需要多少次非缺失才能使switch值得呢，因为它最多可以节省几个或两个？ 再次，这不会出现在微基准。
对于它的价值，这种memcpy并不罕见：即使在优化的库中，这种“详尽的枚举枚举”也很常见。 我可以得出结论，无论他们的开发主要是由微基准驱动的，还是尽管存在缺点，仍然值得用于大量通用代码。 也就是说，这是不理想的场景（指令和/或数据缓存压力）。
分支预测
switch语句依赖于单个间接分支来在替代方案中进行选择。 这在分支预测器可以预测这个间接分支的程度上是有效的，这基本上意味着观测长度的序列需要是可预测的。
由于它是一个间接分支，因此分支可预测性的限制比条件分支更多，因为BTB条目数量有限。 最近的CPU已经在这里取得了进展，但可以肯定地说，如果提供给memcpy的一系列长度不遵循短时间的简单重复模式（在较旧的CPU上短至1或2），则会有一个每次调用都会发生分支错误预测。
这个问题特别隐蔽，因为在微型基准显示switch为最佳长度的情况下，它可能会在现实世界中最受伤害：短长度。 对于非常长的长度，由于它被大容量拷贝支配，所以尾随31个字节上的行为并不是非常重要。 对于很短的长度来说， switch是非常重要的（实际上，对于31个字节或更少的副本，所有这些都是执行的）！
对于这些短的长度，由于间接跳转基本上是空闲的，所以可预测的一系列长度对于switch非常有效。 特别是，一个典型的memcpy基准测试“扫描”了一系列长度，对每个子测试重复使用相同的长度，以报告容易绘制“时间vs长度”图形的结果。 这些switch在这些测试中表现出色，通常会为2个或3个周期报告几个字节的小长度结果。
在现实世界中，你的身高可能很小，但难以预测。 在这种情况下，间接分支经常会错误预测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指令中删除两条。 请注意， rsi和rcx的基础在这里发生了变化：它们指向要复制的最后一个字节，而不是第一个字节。 这种变化是免费的或非常便宜，这取决于跳跃之前的代码。
您可以扩展长度（例如，您可以将长度15和31连接到上面的链上），并使用其他链为缺少的长度。 完整的练习留给读者。 这种方法你可以单独减小50％的尺寸，并且如果将它与其他东西结合起来以缩小16-31的尺寸，则会更好。
这种方法仅对代码大小有帮助（可能还有跳转表大小，如果按照4中的描述缩小大小，并且小于256字节，则允许使用字节大小的查找表，但它对于可预测性没有任何作用。
重叠商店
一种有助于代码大小和可预测性的技巧是使用重叠存储。 也就是说，8到15个字节的memcpy可以通过两个8字节存储以无分支方式完成，第二个存储与第一个存储部分重叠。 例如，要复制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个加载/存储对。
较老的处理器对这种“重叠的商店”遭受了一些惩罚，但更新的架构（至少在过去十年左右）似乎处理它们而不会受到惩罚6。 这有两个主要优势：
该行为对于一系列尺寸是免费的。 实际上，这会量化分支，以便许多值采用相同的路径。 所有尺寸从8到15（或8到16如果你想要）采取相同的路径，并没有遭受错误的预测压力。
switch至少有8或9种不同的情况会被包含在一个单一的情况下，其代码总量的一小部分。
这种方法可以与switch方法结合使用，但仅使用少数几种情况，或者可以通过条件移动将其扩展为更大的尺寸，例如，所有移动都可以从8移动到31个字节而不需要分支。
最好的解决方案取决于分支分布，但总体而言，这种“重叠”技术效果很好。
对准
现有的代码不能解决对齐问题。
事实上，它通常不是合法的或C或C ++，因为char *指针只是简单地转换为更大的类型并被取消引用，这是不合法的 - 尽管实际上它生成的代码适用于当今的x86编译器（但是实际上对于具有更严格对齐要求的平台而言会失败）。
除此之外，特别处理对齐通常更好。 主要有三种情况：
A可以添加到源和目标中，使得两者都对齐。 （1）情况下，现有的算法可以正常工作。 （2）由于小的介绍循环可能会将未对齐的副本变成对齐的副本，因此它可能会遗漏大规模优化。
在情况（3）中，它也可能表现不佳，因为在完全不对齐的情况下，您可以选择对齐目的地或来源，然后进行“半对齐”。
随着时间的推移，对齐惩罚越来越小，最新的芯片对于通用代码来说是适度的，但对于具有许多加载和存储的代码来说仍然是严重的。 对于较大的副本，可能无关紧要，因为您将最终限制DRAM带宽，但对于较小的副本，错位可能会将吞吐量降低50％或更多。
如果您使用NT商店，对齐方式也可能很重要，因为许多NT商店指令执行错误的参数时表现不佳。
没有展开
代码未展开，编译器默认按不同的数量展开。 很显然，这是不理想的，因为在两个不同展开策略的编译器中，最多只有一个最好。
最好的方法（至少对于已知的平台目标）决定了哪个展开因子最好，然后将其应用于代码中。
而且，展开过程通常可以用智能方式与“简介”我们的“outro”代码相结合，比编译器做得更好。
已知尺寸
主要的原因在于它是很难被击败的“内置” memcpy与现代编译程序是编译器不只是调用库memcpy时memcpy出现在源。 他们知道memcpy的合同，并且可以在合适的情况下通过单个内联指令自由实施，甚至更少。
这在memcpy已知长度的情况下尤其明显。 在这种情况下，如果长度很小，编译器只需插入一些指令即可高效地就地执行复制。 这不仅避免了函数调用的开销，而且还避免了所有关于大小等的检查 - 并且在编译时也为复制生成了高效的代码，就像上面实现中的大switch一样 - 但没有switch的开销。
同样，编译器知道很多关于调用代码中结构的对齐方式，并且可以创建能够有效处理对齐的代码。
如果您只是将memcpy2作为库函数实施，那么很难复制。 您可以在这里将我的方法分解为一小部分：小部分出现在头文件中，并执行一些大小检查，如果大小很小或委托给库，可能会调用现有的memcpy如果它很大，就是例行公事 通过内联的魔法，你可能会到达内建memcpy的同一个地方。
最后，您还可以尝试使用__builtin_constant_p或等价物来有效处理这个小的已知案例。
1请注意，我在这里区分了大小的“分布” - 例如，你可能会说 - 均匀分布在8到24个字节之间 - 和实际大小序列的“可预测性”（例如，大小是否有差异可预测的模式）？ 可预测性的问题有点微妙，因为它取决于实现，因为如上所述，某些实现本质上更具可预测性。
2特别地，在具有180-250条指令（分别为gcc和clang ）的交换机体的256字节跳转查询表的顶部， gcc主体中约clang字节的指令在clang主体中，在gcc约为600个字节。 Godbolt链接。
3基本上有200个融合的uop出自1000条指令的有效uop缓存大小。 尽管最近的x86的uop缓存大小约为1500微微秒，但由于代码到缓存的分配规则有限，所以不能在代码库的极其专用的填充之外使用它。
4开关情况有不同的编译长度，所以不能直接计算跳转。 对于它的价值，可以采用不同的方式：它们可以在查找表中使用16位值，但不以jmp内存源为代价，将其大小减小75％。
5与条件分支预测相比，典型的最坏情况预测率约为50％（对于完全随机分支），难以预测的间接分支很容易接近100％，因为您没有翻动硬币，所以选择几乎无限的分支目标。 这发生在现实世界中：如果使用memcpy复制长度均匀分布在0到30之间的小字符串， switch代码将错误预测大约97％的时间。
6当然，对于错位的商店可能会受到处罚，但这些商品通常都很小，并且一直在变小。
7例如，对堆栈执行memcpy ，然后在某处执行一些操作和复制操作可能会完全消除，直接将原始数据移动到其最终位置。 甚至像malloc和memcpy类的东西都可以完全消除。
上一篇: optimal in this memcpy implementation?
下一篇: c++ memory management memory allocation on local variables