Pourquoi memmove est-il plus rapide que memcpy?

J'étudie les points chauds de performance dans une application qui passe 50% de son temps dans memmove (3). L'application insère des millions d'entiers de 4 octets dans des tableaux triés et utilise memmove pour déplacer les données «vers la droite» afin de faire de la place pour la valeur insérée.

Je m'attendais à ce que la copie de la mémoire soit extrêmement rapide, et j'ai été surpris que tant de temps soit passé dans memmove. Mais ensuite, j'ai eu l'idée que memmove est lent car il déplace des régions qui se chevauchent, ce qui doit être implémenté en boucle serrée, au lieu de copier de grandes pages de mémoire. J'ai écrit un petit microbenchmark pour savoir s'il y avait une différence de performance entre memcpy et memmove, en m'attendant à ce que memcpy gagne haut la main.

J'ai exécuté mon benchmark sur deux machines (core i5, core i7) et j'ai vu que memmove est en fait plus rapide que memcpy, sur l'ancien core i7 même presque deux fois plus rapide! Maintenant je cherche des explications.

Voici ma référence. Il copie 100 mb avec memcpy, puis se déplace d'environ 100 mb avec memmove; la source et la destination se chevauchent. Diverses "distances" pour la source et la destination sont essayées. Chaque test est exécuté 10 fois, la durée moyenne est imprimée.

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

Voici les résultats sur le Core i5 (Linux 3.5.0-54-generic # 81 ~ precise1-Ubuntu SMP x86_64 GNU / Linux, gcc vaut 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). Le nombre entre parenthèses est la distance (taille de l'écart) entre la source et la destination:

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 est implémenté en tant que code assembleur optimisé SSE, copiant de l'arrière vers l'avant. Il utilise la prélecture matérielle pour charger les données dans le cache, copie 128 octets dans les registres XMM, puis les stocke à la destination.

( memcpy-ssse3-back.S , lignes 1650 et suivantes)

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)

Pourquoi memmove est-il plus rapide que memcpy? Je m'attendrais à ce que memcpy copie les pages de mémoire, ce qui devrait être beaucoup plus rapide que la boucle. Dans le pire des cas, je m'attendrais à ce que memcpy soit aussi rapide que memmove.

PS: Je sais que je ne peux pas remplacer memmove par memcpy dans mon code. Je sais que l'exemple de code mélange C et C ++. Cette question est vraiment juste à des fins académiques.

MISE À JOUR 1

J'ai effectué quelques variantes des tests, en fonction des différentes réponses.

1. Lorsque vous exécutez memcpy deux fois, la deuxième exécution est plus rapide que la première.
2. Lorsque vous "touchez" le tampon de destination de memcpy ( memset(b2, 0, BUFFERSIZE...)), la première exécution de memcpy est également plus rapide.
3. memcpy est encore un peu plus lent que memmove.

Voici les résultats:

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

Ma conclusion: sur la base d'un commentaire de @Oliver Charlesworth, le système d'exploitation doit engager de la mémoire physique dès que le tampon de destination memcpy est accédé pour la toute première fois (si quelqu'un sait comment "prouver" cela, veuillez ajouter une réponse! ). De plus, comme l'a dit @Mats Petersson, memmove est plus convivial pour le cache que memcpy.

Merci pour toutes les bonnes réponses et commentaires!

Vos memmoveappels mélangent la mémoire de 2 à 128 octets, tandis que votre memcpysource et votre destination sont complètement différentes. Cela explique en quelque sorte la différence de performances: si vous copiez au même endroit, vous verrez memcpypeut-être un peu plus vite, par exemple sur 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

Cependant, il n'y a presque rien - aucune preuve que le fait d'écrire sur une page de mémoire déjà défectueuse a beaucoup d' impact, et nous ne voyons certainement pas une réduction de moitié du temps ... mais cela montre qu'il n'y a rien de mal à rendre memcpyinutilement plus lent par rapport aux pommes -pour-pommes.

Lorsque vous utilisez memcpy, les écritures doivent aller dans le cache. Lorsque vous utilisez memmovewhere lorsque vous copiez un petit pas en avant, la mémoire que vous copiez sera déjà dans le cache (car elle a été lue 2, 4, 16 ou 128 octets "en arrière"). Essayez de faire un memmoveoù la destination est de plusieurs mégaoctets (> 4 * taille du cache), et je soupçonne (mais je ne peux pas être dérangé de tester) que vous obtiendrez des résultats similaires.

Je vous garantis que ALL concerne la maintenance du cache lorsque vous effectuez de grandes opérations de mémoire.

Historiquement, memmove et memcopy sont la même fonction. Ils ont travaillé de la même manière et ont eu la même implémentation. On s'est alors rendu compte que memcopy n'avait pas besoin d'être (et n'était souvent pas) défini pour gérer les zones qui se chevauchent d'une manière particulière.

Le résultat final est que memmove a été défini pour gérer les régions qui se chevauchent d'une manière particulière, même si cela affecte les performances. Memcopy est censé utiliser le meilleur algorithme disponible pour les régions ne se chevauchant pas. Les implémentations sont normalement presque identiques.

Le problème que vous avez rencontré est qu'il existe tellement de variantes du matériel x86 qu'il est impossible de dire quelle méthode de transfert de mémoire sera la plus rapide. Et même si vous pensez avoir un résultat dans une circonstance, quelque chose d'aussi simple que d'avoir une «foulée» différente dans la disposition de la mémoire peut entraîner des performances de cache très différentes.

Vous pouvez comparer ce que vous faites réellement ou ignorer le problème et vous fier aux benchmarks effectués pour la bibliothèque C.

Edit: Oh, et une dernière chose; déplacer beaucoup de contenu de mémoire est TRÈS lent. Je suppose que votre application fonctionnerait plus rapidement avec quelque chose comme une simple implémentation B-Tree pour gérer vos entiers. (Oh tu l'es, d'accord)

Edit2: Pour résumer mon expansion dans les commentaires: Le microbenchmark est le problème ici, il ne mesure pas ce que vous pensez que c'est. Les tâches confiées à memcpy et memmove diffèrent considérablement l'une de l'autre. Si la tâche donnée à memcpy est répétée plusieurs fois avec memmove ou memcpy, les résultats finaux ne dépendront pas de la fonction de décalage de mémoire que vous utilisez, SAUF les régions se chevauchent.

"memcpy est plus efficace que memmove." Dans votre cas, vous ne faites probablement pas exactement la même chose pendant que vous exécutez les deux fonctions.

En général, n'utilisez memmove que si vous devez le faire. UTILISEZ-le lorsqu'il y a une chance très raisonnable que les régions source et destination se chevauchent.

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