为什么memmove比memcpy更快？

Question

我正在研究应用程序中的性能热点,它将50%的时间花在memmove(3)上.应用程序将数百万个4字节整数插入到已排序的数组中,并使用memmove将数据"向右"移位,以便为插入的值腾出空间.

我的期望是复制内存非常快,我很惊讶在memmove上花了这么多时间.但后来我认为memmove很慢,因为它正在移动重叠区域,这必须在紧密的循环中实现,而不是复制大页面的内存.我写了一个小的微基准测试,以确定memcpy和memmove之间是否存在性能差异,期望memcpy能够取胜.

我在两台机器(核心i5,核心i7)上运行我的基准测试,看到memmove实际上比memcpy更快,在旧核心i7上甚至快了两倍!现在我正在寻找解释.

这是我的基准.它用memcpy复制100 mb,然后用memmove移动大约100 mb; 来源和目的地重叠.尝试了源和目的地的各种"距离".每次测试运行10次,打印平均时间.

https://gist.github.com/cruppstahl/78a57cdf937bca3d062c

以下是Core i5的结果(Linux 3.5.0-54-generic#81~precision1-Ubuntu SMP x86_64 GNU/Linux,gcc是4.6.3(Ubuntu/Linaro 4.6.3-1ubuntu5).括号中的数字是源和目的地之间的距离(间隙大小):

memcpy        0.0140074
memmove (002) 0.0106168
memmove (004) 0.01065
memmove (008) 0.0107917
memmove (016) 0.0107319
memmove (032) 0.0106724
memmove (064) 0.0106821
memmove (128) 0.0110633

Memmove实现为SSE优化的汇编代码,从后到前复制.它使用硬件预取将数据加载到缓存中,并将128个字节复制到XMM寄存器,然后将它们存储在目标中.

(memcpy-ssse3-back.S,第1650行)

L(gobble_ll_loop):
    prefetchnta -0x1c0(%rsi)
    prefetchnta -0x280(%rsi)
    prefetchnta -0x1c0(%rdi)
    prefetchnta -0x280(%rdi)
    sub $0x80, %rdx
    movdqu  -0x10(%rsi), %xmm1
    movdqu  -0x20(%rsi), %xmm2
    movdqu  -0x30(%rsi), %xmm3
    movdqu  -0x40(%rsi), %xmm4
    movdqu  -0x50(%rsi), %xmm5
    movdqu  -0x60(%rsi), %xmm6
    movdqu  -0x70(%rsi), %xmm7
    movdqu  -0x80(%rsi), %xmm8
    movdqa  %xmm1, -0x10(%rdi)
    movdqa  %xmm2, -0x20(%rdi)
    movdqa  %xmm3, -0x30(%rdi)
    movdqa  %xmm4, -0x40(%rdi)
    movdqa  %xmm5, -0x50(%rdi)
    movdqa  %xmm6, -0x60(%rdi)
    movdqa  %xmm7, -0x70(%rdi)
    movdqa  %xmm8, -0x80(%rdi)
    lea -0x80(%rsi), %rsi
    lea -0x80(%rdi), %rdi
    jae L(gobble_ll_loop)

为什么memmove比memcpy更快？我希望memcpy能够复制内存页面,这应该比循环更快.在最坏的情况下,我希望memcpy和memmove一样快.

PS:我知道我无法在代码中用memcpy替换memmove.我知道代码示例混合了C和C++.这个问题实际上只是出于学术目的.

更新1

我根据各种答案运行了一些测试变体.

1. 当运行memcpy两次时,第二次运行比第一次运行得快.
2. 当"触摸"memcpy(memset(b2, 0, BUFFERSIZE...))的目标缓冲区时,第一次运行memcpy也会更快.
3. memcpy仍然比memmove慢一点.

结果如下:

memcpy        0.0118526
memcpy        0.0119105
memmove (002) 0.0108151
memmove (004) 0.0107122
memmove (008) 0.0107262
memmove (016) 0.0108555
memmove (032) 0.0107171
memmove (064) 0.0106437
memmove (128) 0.0106648

我的结论:基于@Oliver Charlesworth的评论,操作系统必须在第一次访问memcpy目标缓冲区时提交物理内存(如果有人知道如何"证明"这个,那么请添加答案! ).另外,正如@Mats Petersson所说,memmove比memcpy更友好.

感谢所有伟大的答案和评论!

Answer 1

您的memmove呼叫正在将内存拖曳2到128个字节,而您的memcpy源和目标完全不同.不知何故,这会影响性能差异:如果你复制到同一个地方,你会看到memcpy最终可能更快,例如在ideone.com上:

memmove (002) 0.0610362
memmove (004) 0.0554264
memmove (008) 0.0575859
memmove (016) 0.057326
memmove (032) 0.0583542
memmove (064) 0.0561934
memmove (128) 0.0549391
memcpy 0.0537919

虽然几乎没有任何东西 - 没有证据表明写回已经存在故障的内存页面会产生很大的影响,而且我们肯定没有看到时间缩短了一半......但它确实表明,memcpy与苹果相比,做出不必要的减速并没有什么不妥-用于-苹果.

Answer 2

在使用时memcpy,写入需要进入缓存.当您memmove在向前复制一小步时使用的位置时,您正在复制的内存已经在缓存中(因为它被"读回"2,4,16或128字节).尝试做一个memmove目标是几兆字节(> 4*缓存大小)的地方,我怀疑(但不能打扰测试)你会得到类似的结果.

我保证在执行大内存操作时ALL都是关于缓存维护的.

Answer 3

从历史上看,memmove和memcopy功能相同.他们以相同的方式工作并具有相同的实现.然后意识到memcopy不需要(通常不是)定义来以任何特定方式处理重叠区域.

最终结果是memmove被定义为以特定方式处理重叠区域,即使这会影响性能.Memcopy应该使用可用于非重叠区域的最佳算法.实现通常几乎相同.

您遇到的问题是x86硬件的变化太多,以至于无法判断哪种移动内存的方法最快.即使你认为你在一种情况下有一个结果就像在内存布局中有一个不同的"步幅"一样简单,可能会导致缓存性能大不相同.

您既可以对您实际执行的操作进行基准测试,也可以忽略该问题,并依赖于为C库执行的基准测试.

编辑:哦,最后一件事; 移动大量内存内容非常慢.我猜你的应用程序会运行得更快,就像一个简单的B-Tree实现来处理你的整数.(哦,你,好吧)

编辑2:总结我在评论中的扩展:微基准测试是这里的问题,它不是衡量你的想法.给memcpy和memmove的任务彼此差异很大.如果使用memmove或memcpy重复给memcpy的任务几次,最终结果将不依赖于您使用的内存移位功能,除非区域重叠.