Warum ist memmove schneller als memcpy?

Ich untersuche Leistungs-Hotspots in einer Anwendung, die 50 % ihrer Zeit in memmove(3) verbringt. Die Anwendung fügt Millionen von 4-Byte-Ganzzahlen in sortierte Arrays ein und verwendet memmove, um die Daten “nach rechts” zu verschieben, um Platz für den eingefügten Wert zu schaffen.

Meine Erwartung war, dass das Kopieren des Speichers extrem schnell ist, und ich war überrascht, dass so viel Zeit in memmove investiert wird. Aber dann hatte ich die Idee, dass memmove langsam ist, weil es überlappende Regionen verschiebt, die in einer engen Schleife implementiert werden müssen, anstatt große Speicherseiten zu kopieren. Ich habe einen kleinen Mikrobenchmark geschrieben, um herauszufinden, ob es einen Leistungsunterschied zwischen memcpy und memmove gibt, in der Erwartung, dass memcpy zweifellos gewinnen wird.

Ich habe meinen Benchmark auf zwei Rechnern (Core i5, Core i7) laufen lassen und gesehen, dass memmove tatsächlich schneller ist als memcpy, auf dem älteren Core i7 sogar fast doppelt so schnell! Jetzt suche ich nach Erklärungen.

Hier ist mein Maßstab. Es kopiert 100 MB mit memcpy und bewegt sich dann um etwa 100 MB mit memmove; Quelle und Ziel überschneiden sich. Es werden verschiedene “Entfernungen” für Quelle und Ziel ausprobiert. Jeder Test wird 10 Mal durchgeführt, die durchschnittliche Zeit wird ausgedruckt.

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

Hier sind die Ergebnisse auf dem Core i5 (Linux 3.5.0-54-generic #81~precise1-Ubuntu SMP x86_64 GNU/Linux, gcc ist 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5). Die Zahl in Klammern ist der Abstand (Lückengröße) zwischen Quelle und Ziel:

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 ist als SSE-optimierter Assembler-Code implementiert, der von hinten nach vorne kopiert. Es verwendet Hardware-Prefetch, um die Daten in den Cache zu laden, kopiert 128 Bytes in XMM-Register und speichert sie dann am Ziel.

(memcpy-ssse3-back.SZeilen 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)

Warum ist memmove schneller als memcpy? Ich würde erwarten, dass memcpy Speicherseiten kopiert, was viel schneller sein sollte als das Schleifen. Im schlimmsten Fall würde ich erwarten, dass memcpy so schnell ist wie memmove.

PS: Ich weiß, dass ich memmove in meinem Code nicht durch memcpy ersetzen kann. Ich weiß, dass das Codebeispiel C und C++ mischt. Diese Frage ist wirklich nur für akademische Zwecke.

AKTUALISIERUNG 1

Ich habe einige Variationen der Tests durchgeführt, basierend auf den verschiedenen Antworten.

1. Wenn memcpy zweimal ausgeführt wird, ist der zweite Durchlauf schneller als der erste.
2. Beim “Berühren” des Zielpuffers von memcpy (memset(b2, 0, BUFFERSIZE...)) dann ist der erste Lauf von memcpy auch schneller.
3. memcpy ist immer noch etwas langsamer als memmove.

Hier sind die Ergebnisse:

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

Meine Schlussfolgerung: Basierend auf einem Kommentar von @Oliver Charlesworth muss das Betriebssystem physischen Speicher festschreiben, sobald zum ersten Mal auf den Memcpy-Zielpuffer zugegriffen wird (wenn jemand weiß, wie man dies “beweist”, dann fügen Sie bitte eine Antwort hinzu! ). Darüber hinaus ist memmove, wie @Mats Petersson sagte, Cache-freundlicher als memcpy.

Danke für all die tollen Antworten und Kommentare!

Dein memmove Aufrufe verschieben den Speicher um 2 bis 128 Byte, während Ihr memcpy Quelle und Ziel sind völlig unterschiedlich. Irgendwie erklärt das den Leistungsunterschied: Wenn Sie an dieselbe Stelle kopieren, werden Sie sehen memcpy landet eventuell einen Tick schneller, zB auf 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

Allerdings kaum etwas drin – kein Hinweis darauf, dass das Zurückschreiben auf eine bereits im Speicher fehlerhafte Seite hat viel Auswirkungen, und wir sehen sicherlich keine Halbierung der Zeit … aber es zeigt, dass nichts falsch gemacht werden kann memcpy unnötig langsamer im Vergleich Äpfel-für-Äpfel.

Wenn Sie verwenden memcpy, müssen die Schreibvorgänge in den Cache gehen. Wenn Sie verwenden memmove Wenn Sie einen kleinen Schritt vorwärts kopieren, befindet sich der Speicher, über den Sie kopieren, bereits im Cache (weil er 2, 4, 16 oder 128 Bytes “rückwärts” gelesen wurde). Versuchen Sie, a memmove wo das Ziel mehrere Megabyte (> 4 * Cache-Größe) ist, und ich vermute (aber ich habe keine Lust zu testen), dass Sie ähnliche Ergebnisse erhalten.

Ich garantiere, dass es bei ALLEN um die Cache-Wartung geht, wenn Sie große Speicheroperationen durchführen.

Historisch gesehen sind memmove und memcpy dieselbe Funktion. Sie arbeiteten auf die gleiche Weise und hatten die gleiche Implementierung. Es wurde dann erkannt, dass memcpy nicht definiert werden muss (und häufig auch nicht war), um überlappende Bereiche auf eine bestimmte Weise zu handhaben.

Das Endergebnis ist, dass memmove so definiert wurde, dass überlappende Bereiche auf eine bestimmte Weise gehandhabt werden, auch wenn dies die Leistung beeinträchtigt. memcpy soll den besten verfügbaren Algorithmus für nicht überlappende Regionen verwenden. Die Implementierungen sind normalerweise fast identisch.

Das Problem, auf das Sie gestoßen sind, besteht darin, dass es so viele Variationen der x86-Hardware gibt, dass es unmöglich ist, zu sagen, welche Methode zum Verschieben des Speichers am schnellsten ist. Und selbst wenn Sie glauben, in einem bestimmten Fall ein Ergebnis zu erzielen, kann etwas so Einfaches wie ein unterschiedlicher „Schritt“ im Speicherlayout zu einer erheblich unterschiedlichen Cache-Leistung führen.

Sie können entweder Benchmarks erstellen, was Sie tatsächlich tun, oder das Problem ignorieren und sich auf die Benchmarks verlassen, die für die C-Bibliothek durchgeführt wurden.

Bearbeiten: Oh, und eine letzte Sache; Das Verschieben von vielen Speicherinhalten ist SEHR langsam. Ich würde vermuten, dass Ihre Anwendung mit so etwas wie einer einfachen B-Tree-Implementierung schneller laufen würde, um Ihre Ganzzahlen zu verarbeiten. (Oh du bist, okay)

Edit2: Um meine Erweiterung in den Kommentaren zusammenzufassen: Der Mikrobenchmark ist hier das Problem, er misst nicht, was Sie denken. Die Aufgaben von memcpy und memmove unterscheiden sich erheblich voneinander. Wenn die an memcpy gegebene Aufgabe mehrmals mit memmove oder memcpy wiederholt wird, hängen die Endergebnisse nicht davon ab, welche Speicherverschiebungsfunktion Sie verwenden, es sei denn, die Regionen überlappen sich.

“memcpy ist effizienter als memmove.” In Ihrem Fall tun Sie höchstwahrscheinlich nicht genau dasselbe, während Sie die beiden Funktionen ausführen.

Verwenden Sie memmove im Allgemeinen nur, wenn Sie müssen. VERWENDEN Sie es, wenn die Wahrscheinlichkeit sehr hoch ist, dass sich die Quell- und Zielregionen überschneiden.

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