Por que memmove é mais rápido que memcpy?

Estou investigando pontos de acesso de desempenho em um aplicativo que gasta 50% do tempo no memmove (3). O aplicativo insere milhões de inteiros de 4 bytes em matrizes classificadas e usa memmove para deslocar os dados "para a direita" a fim de liberar espaço para o valor inserido.

Minha expectativa era que copiar a memória fosse extremamente rápido, e fiquei surpreso ao ver que tanto tempo é gasto no memmove. Mas então eu tive a ideia de que memmove é lento porque está movendo regiões sobrepostas, que devem ser implementadas em um loop fechado, em vez de copiar grandes páginas de memória. Eu escrevi um pequeno microbenchmark para descobrir se havia uma diferença de desempenho entre memcpy e memmove, esperando que memcpy vencesse.

Eu executei meu benchmark em duas máquinas (core i5, core i7) e vi que memmove é realmente mais rápido que memcpy, no antigo core i7 quase duas vezes mais rápido! Agora estou procurando explicações.

Aqui está minha referência. Ele copia 100 MB com memcpy e move cerca de 100 MB com memmove; origem e destino estão sobrepostos. Várias "distâncias" para origem e destino são tentadas. Cada teste é executado 10 vezes, o tempo médio é impresso.

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

Aqui estão os resultados no 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). O número entre colchetes é a distância (tamanho da lacuna) entre a origem e o destino:

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 é implementado como um código assembler otimizado SSE, copiando de trás para frente. Ele usa pré-busca de hardware para carregar os dados no cache e copia 128 bytes para os registradores XMM e os armazena no destino.

( memcpy-ssse3-back.S , linhas 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)

Por que o memmove é mais rápido do que o memcpy? Eu esperaria que o memcpy copiasse páginas de memória, o que deve ser muito mais rápido do que o loop. Na pior das hipóteses, eu esperaria que memcpy fosse tão rápido quanto memmove.

PS: Eu sei que não posso substituir memmove por memcpy em meu código. Eu sei que o exemplo de código mistura C e C ++. Esta pergunta é realmente apenas para fins acadêmicos.

ATUALIZAÇÃO 1

Executei algumas variações dos testes, com base nas várias respostas.

1. Ao executar o memcpy duas vezes, a segunda execução é mais rápida do que a primeira.
2. Ao "tocar" no buffer de destino do memcpy ( memset(b2, 0, BUFFERSIZE...)), a primeira execução do memcpy também é mais rápida.
3. memcpy ainda é um pouco mais lento que memmove.

Aqui estão os resultados:

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

Minha conclusão: com base em um comentário de @Oliver Charlesworth, o sistema operacional precisa comprometer a memória física assim que o buffer de destino memcpy é acessado pela primeira vez (se alguém souber como "comprovar" isso, adicione uma resposta! ) Além disso, como @Mats Petersson disse, memmove é mais amigável para o cache do que memcpy.

Obrigado por todas as ótimas respostas e comentários!

Suas memmovechamadas estão embaralhando a memória em 2 a 128 bytes, enquanto sua memcpyorigem e destino são completamente diferentes. De alguma forma, isso é responsável pela diferença de desempenho: se você copiar para o mesmo lugar, verá que memcpytermina possivelmente um pouco mais rápido, por exemplo, em 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

Quase nada nele - nenhuma evidência de que escrever de volta para uma página já com falhas na memória tenha muito impacto e certamente não estamos vendo uma redução do tempo pela metade ... mas mostra que não há nada de errado em tornar memcpydesnecessariamente mais lento quando comparadas maçãs -para-maçãs.

Quando você está usando memcpy, as gravações precisam ir para o cache. Quando você usa memmovewhere quando está copiando um pequeno passo à frente, a memória que você está copiando já estará no cache (porque foi lida 2, 4, 16 ou 128 bytes "para trás"). Tente fazer um em memmoveque o destino tenha vários megabytes (> 4 * tamanho do cache) e suspeito (mas não posso me dar ao trabalho de testar) que você obterá resultados semelhantes.

Garanto que ALL é sobre manutenção de cache quando você faz operações de grande memória.

Historicamente, memmove e memcopy têm a mesma função. Eles funcionaram da mesma forma e tiveram a mesma implementação. Percebeu-se então que a memcopy não precisa ser (e frequentemente não era) definida para lidar com áreas sobrepostas de nenhuma maneira particular.

O resultado final é que memmove foi definido para lidar com regiões sobrepostas de uma maneira particular, mesmo que isso afete o desempenho. O Memcopy deve usar o melhor algoritmo disponível para regiões não sobrepostas. As implementações são normalmente quase idênticas.

O problema que você encontrou é que existem tantas variações do hardware x86 que é impossível dizer qual método de troca de memória será o mais rápido. E mesmo se você achar que tem um resultado em uma circunstância, algo tão simples como ter um 'avanço' diferente no layout da memória pode causar um desempenho de cache muito diferente.

Você pode avaliar o que está realmente fazendo ou ignorar o problema e confiar nos benchmarks feitos para a biblioteca C.

Edit: Oh, e uma última coisa; mudar muitos conteúdos da memória é MUITO lento. Eu acho que seu aplicativo seria executado mais rápido com algo como uma implementação B-Tree simples para lidar com seus inteiros. (Oh você está ok)

Edit2: Para resumir minha expansão nos comentários: O microbenchmark é o problema aqui, não é medir o que você pensa que é. As tarefas atribuídas a memcpy e memmove diferem significativamente umas das outras. Se a tarefa dada ao memcpy for repetida várias vezes com memmove ou memcpy, os resultados finais não dependerão de qual função de deslocamento de memória você usar, A MENOS que as regiões se sobreponham.

"memcpy é mais eficiente do que memmove." No seu caso, você provavelmente não está fazendo exatamente a mesma coisa enquanto executa as duas funções.

Em geral, USE memmove somente se for necessário. USE-o quando houver uma chance muito razoável de que as regiões de origem e destino estejam sobrepostas.

Referência: https://www.youtube.com/watch?v=Yr1YnOVG-4g Dr. Jerry Cain, (Stanford Intro Systems Lecture - 7) Horário: 36:00