memmove가 memcpy보다 빠른 이유는 무엇입니까?

memmove가 memcpy보다 빠른 이유는 무엇입니까?

---

memmove (3)에서 시간의 50 %를 소비하는 응용 프로그램의 성능 핫스팟을 조사하고 있습니다. 애플리케이션은 수백만 개의 4 바이트 정수를 정렬 된 배열에 삽입하고 삽입 된 값을위한 공간을 만들기 위해 memmove를 사용하여 데이터를 "오른쪽으로"이동합니다.

제 기대는 메모리 복사가 매우 빠르다는 것이었고, memmove에 너무 많은 시간이 소요되어 놀랐습니다. 그러나 memmove가 겹치는 영역을 이동하기 때문에 느리다는 생각이 들었습니다. 이는 메모리의 큰 페이지를 복사하는 대신 엄격한 루프로 구현되어야합니다. memcpy와 memmove 사이에 성능 차이가 있는지 알아보기 위해 작은 마이크로 벤치 마크를 작성했습니다. memcpy가 이길 것으로 예상했습니다.

두 대의 컴퓨터 (코어 i5, 코어 i7)에서 벤치 마크를 실행 한 결과 memmove가 실제로 memcpy보다 빠르다는 것을 알았습니다. 구형 코어 i7에서는 거의 두 배나 빠릅니다! 이제 설명을 찾고 있습니다.

여기 내 벤치 마크가 있습니다. memcpy로 100mb를 복사 한 다음 memmove로 약 100mb를 이동합니다. 소스와 대상이 겹칩니다. 소스 및 대상에 대한 다양한 "거리"가 시도됩니다. 각 테스트는 10 회 실행되며 평균 시간이 인쇄됩니다.

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

다음은 Core i5 (Linux 3.5.0-54-generic # 81 ~ precise1-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 ff)

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만큼 빠르기를 기대합니다.

추신 : 내 코드에서 memmove를 memcpy로 바꿀 수 없다는 것을 알고 있습니다. 코드 샘플이 C와 C ++를 혼합한다는 것을 알고 있습니다. 이 질문은 실제로 학문적 목적을위한 것입니다.

업데이트 1

다양한 답변을 바탕으로 다양한 테스트를 실행했습니다.

1. memcpy를 두 번 실행하면 두 번째 실행이 첫 번째 실행보다 빠릅니다.
2. When "touching" the destination buffer of memcpy (memset(b2, 0, BUFFERSIZE...)) then the first run of memcpy is also faster.
3. memcpy is still a little bit slower than memmove.

Here are the results:

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

My conclusion: based on a comment from @Oliver Charlesworth, the operating system has to commit physical memory as soon as the memcpy destination buffer is accessed for the very first time (if someone knows how to "proof" this then please add an answer!). In addition, as @Mats Petersson said, memmove is cache friendlier than memcpy.

Thanks for all the great answers and comments!

---

Your memmove calls are shuffling memory along by 2 to 128 bytes, while your memcpy source and destination are completely different. Somehow that's accounting for the performance difference: if you copy to the same place, you'll see memcpy ends up possibly a smidge faster, e.g. on 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

Hardly anything in it though - no evidence that writing back to an already faulted in memory page has much impact, and we're certainly not seeing a halving of time... but it does show that there's nothing wrong making memcpy unnecessarily slower when compared apples-for-apples.

---

When you are using memcpy, the writes need to go into the cache. When you use memmove where when you are copying a small step forward, the memory you are copying over will already be in the cache (because it was read 2, 4, 16 or 128 bytes "back"). Try doing a memmove where the destination is several megabytes (> 4 * cache size), and I suspect (but can't be bothered to test) that you'll get similar results.

I guarantee that ALL is about cache maintenance when you do large memory operations.

---

Historically, memmove and memcopy are the same function. They worked in the same way and had the same implementation. It was then realised that memcopy doesn't need to be (and frequently wasn't) defined to handle overlapping areas in any particular way.

The end result is that memmove was defined to handle overlapping regions in a particular way even if this impacts performance. Memcopy is supposed to use the best algorithm available for non-overlapping regions. The implementations are normally almost identical.

The problem you have run into is that there are so many variations of the x86 hardware that it is impossible to tell which method of shifting memory around will be the fastest. And even if you think you have a result in one circumstance something as simple as having a different 'stride' in the memory layout can cause vastly different cache performance.

You can either benchmark what you're actually doing or ignore the problem and rely on the benchmarks done for the C library.

Edit: Oh, and one last thing; shifting lots of memory contents around is VERY slow. I would guess your application would run faster with something like a simple B-Tree implementation to handle your integers. (Oh you are, okay)

Edit2: To summarise my expansion in the comments: The microbenchmark is the issue here, it isn't measuring what you think it is. The tasks given to memcpy and memmove differ significantly from each other. If the task given to memcpy is repeated several times with memmove or memcpy the end results will not depend on which memory shifting function you use UNLESS the regions overlap.

---

"memcpy is more efficient than memmove." In your case, you most probably are not doing the exact same thing while you run the two functions.

In general, USE memmove only if you have to. USE it when there is a very reasonable chance that the source and destination regions are over-lapping.

Reference: https://www.youtube.com/watch?v=Yr1YnOVG-4g Dr. Jerry Cain, (Stanford Intro Systems Lecture - 7) Time: 36:00

참고URL : https://stackoverflow.com/questions/28623895/why-is-memmove-faster-than-memcpy