Warum ist memmove schneller als memcpy?

89

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

Meine Erwartung war, dass das Kopieren von Speicher extrem schnell ist, und ich war überrascht, dass so viel Zeit für memmove aufgewendet wird. Aber dann kam mir die Idee, dass memmove langsam ist, weil es überlappende Bereiche verschiebt, die in einer engen Schleife implementiert werden müssen, anstatt große Speicherseiten zu kopieren. Ich habe ein kleines Mikrobenchmark geschrieben, um herauszufinden, ob es einen Leistungsunterschied zwischen memcpy und memmove gibt, und erwartet, dass memcpy zweifellos gewinnt.

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

Hier ist mein Benchmark. Es kopiert 100 MB mit memcpy und bewegt sich dann mit memmove um 100 MB. Quelle und Ziel überschneiden sich. Es werden verschiedene "Entfernungen" für Quelle und Ziel versucht. Jeder Test wird 10 Mal ausgeführt, die durchschnittliche Zeit wird gedruckt.

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

Hier sind die Ergebnisse auf dem Core i5 (Linux 3.5.0-54-generisch # 81 ~ präzise1-Ubuntu SMP x86_64 GNU / Linux, gcc ist 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). Die Zahl in Klammern ist die Entfernung (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.S , Zeilen 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.

UPDATE 1

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

  1. Wenn Sie memcpy zweimal ausführen, ist der zweite Lauf schneller als der erste.
  2. Wenn Sie den Zielpuffer von memcpy ( memset(b2, 0, BUFFERSIZE...)) "berühren", ist auch der erste Durchlauf von memcpy 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

Mein Fazit: 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", fügen Sie bitte eine Antwort hinzu! ). Darüber hinaus ist memmove, wie @Mats Petersson sagte, cachefreundlicher als memcpy.

Vielen Dank für all die tollen Antworten und Kommentare!

cruppstahl
quelle
1
Sie haben sich den memmove-Code angesehen. Haben Sie sich auch den memcpy-Code angesehen?
Oliver Charlesworth
8
Meine Erwartung war, dass das Kopieren von Speicher extrem schnell ist - nur wenn sich der Speicher im L1-Cache befindet. Wenn die Daten nicht in Caches passen, nimmt Ihre Kopierleistung ab.
Maxim Egorushkin
1
Übrigens haben Sie nur einen Zweig von kopiert memmove. Dieser Zweig kann keine Verschiebung verarbeiten, wenn die Quelle das Ziel überlappt und sich das Ziel an niedrigeren Adressen befindet.
Maxim Egorushkin
2
Ich hatte keine Zeit, auf einen Linux-Computer zuzugreifen, daher kann ich diese Theorie noch nicht testen. Eine andere mögliche Erklärung ist übermäßiges Engagement . Auf Ihre memcpySchleife wird zum ersten Mal b2zugegriffen, wenn auf deren Inhalt zugegriffen wird. Daher muss das Betriebssystem im Laufe der Zeit physischen Speicher dafür bereitstellen.
Oliver Charlesworth
2
PS: Wenn dies ein Engpass ist, würde ich den Ansatz überdenken. Wie wäre es, wenn Sie die Werte in eine Liste oder Baumstruktur (z. B. einen Binärbaum) einfügen und sie am Ende in ein Array einlesen. Die Knoten in einem solchen Ansatz wären ein ausgezeichneter Kandidat für die Poolzuweisung. Sie werden nur bis zum Ende hinzugefügt, wenn sie massenhaft veröffentlicht werden. Dies gilt insbesondere dann, wenn Sie wissen, wie viele Sie zu Beginn benötigen. Die Boost-Bibliotheken verfügen über einen Pool-Allokator.
Persixty

Antworten:

56

Ihre memmoveAnrufe mischen den Speicher um 2 bis 128 Bytes, während Ihre memcpyQuelle und Ihr Ziel völlig unterschiedlich sind. Irgendwie erklärt dies den Leistungsunterschied: Wenn Sie an denselben Ort kopieren, werden Sie memcpymöglicherweise schneller einen Smidge erhalten, z. B. 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

Kaum etwas drin - kein Beweis dafür, dass das Zurückschreiben auf eine bereits fehlerhafte Speicherseite große Auswirkungen hat, und wir sehen sicherlich keine Halbierung der Zeit ... aber es zeigt, dass nichts falsch daran ist, memcpyim Vergleich zu Äpfeln unnötig langsamer zu werden -für Äpfel.

Tony Delroy
quelle
Ich hätte erwartet, dass die CPU-Caches den Unterschied nicht verursachen, da meine Puffer viel größer als die Caches sind.
Cruppstahl
2
Aber jeder benötigt die gleiche Gesamtzahl an Hauptspeicherzugriffen, oder? (Dh 100 MB Lesen und 100 MB Schreiben). Das Cache-Muster umgeht das nicht. Der eine Weg, wie einer langsamer sein kann als der andere, besteht darin, dass einige Dinge mehr als einmal aus dem / in den Speicher gelesen / geschrieben werden müssen.
Oliver Charlesworth
2
@ Tony D - Mein Fazit war, Leute zu fragen, die schlauer sind als ich;)
Cruppstahl
1
Was passiert auch, wenn Sie an denselben Ort kopieren, dies aber memcpyzuerst erneut tun ?
Oliver Charlesworth
1
@OliverCharlesworth: Der erste Testlauf hat immer einen signifikanten Treffer, führt jedoch zwei memcpy-Tests durch: memcpy 0.0688002 0.0583162 | memmove 0.0577443 0.05862 0.0601029 ... siehe ideone.com/8EEAcA
Tony Delroy
24

Wenn Sie verwenden memcpy, müssen die Schreibvorgänge in den Cache verschoben werden. Wenn Sie memmovebeim Kopieren einen kleinen Schritt vorwärts verwenden, befindet sich der Speicher, über den Sie kopieren, bereits im Cache (da er 2, 4, 16 oder 128 Byte "zurück" gelesen wurde). Versuchen Sie es mit einem memmoveZiel, bei dem das Ziel mehrere Megabyte (> 4 * Cache-Größe) beträgt, und ich vermute (kann aber nicht getestet werden), dass Sie ähnliche Ergebnisse erhalten.

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

Mats Petersson
quelle
+1 Ich denke, aus den von Ihnen genannten Gründen ist ein Memmove mit Rückwärtsschleife cachefreundlicher als memcpy. Ich habe jedoch festgestellt, dass beim zweiten Ausführen des memcpy-Tests der zweite Durchlauf so schnell ist wie memmove. Warum? Die Puffer sind so groß, dass ein zweiter Lauf von memcpy genauso ineffizient (cache-weise) sein sollte wie der erste Lauf. Es scheint also, dass es hier zusätzliche Faktoren gibt, die den Leistungsverlust verursachen.
Cruppstahl
3
Unter den richtigen Umständen wird eine Sekunde memcpydeutlich schneller sein, einfach weil der TLB vorgefüllt ist. Außerdem muss eine Sekunde memcpynicht den Cache mit Dingen leeren, die Sie möglicherweise "loswerden" müssen (schmutzige Cache-Zeilen sind in vielerlei Hinsicht "schlecht" für die Leistung. Um sicher zu sein, müssten Sie dies jedoch tun Führen Sie so etwas wie "perf" aus und probieren Sie Dinge wie Cache-Misses, TLB-Misses und so weiter.
Mats Petersson
15

In der Vergangenheit haben memmove und memcopy dieselbe Funktion. Sie arbeiteten auf die gleiche Weise und hatten die gleiche Implementierung. Es wurde dann erkannt, dass Memcopy nicht definiert werden muss (und häufig auch nicht definiert wurde), um überlappende Bereiche auf eine bestimmte Weise zu behandeln.

Das Endergebnis ist, dass memmove so definiert wurde, dass überlappende Bereiche auf eine bestimmte Weise behandelt werden, auch wenn dies die Leistung beeinträchtigt. Memcopy 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, ist, dass es so viele Variationen der x86-Hardware gibt, dass es unmöglich ist zu sagen, welche Methode zum Verschieben des Speichers die schnellste ist. Und selbst wenn Sie glauben, unter bestimmten Umständen ein Ergebnis zu erzielen, kann etwas so Einfaches wie ein anderer Schritt im Speicherlayout zu einer sehr unterschiedlichen Cache-Leistung führen.

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

Edit: Oh, und noch eine letzte Sache; Das Verschieben vieler Speicherinhalte 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 ganzen Zahlen zu verarbeiten. (Oh du bist, okay)

Edit2: Um meine Erweiterung in den Kommentaren zusammenzufassen: Das Mikrobenchmark ist hier das Problem, es misst nicht, was Sie denken, dass es ist. Die Aufgaben von memcpy und memmove unterscheiden sich erheblich voneinander. Wenn die Aufgabe, die memcpy zugewiesen wurde, 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.

user3710044
quelle
Aber darum geht es - ich vergleiche, was ich tatsächlich tue. Bei dieser Frage geht es darum, die Ergebnisse des Benchmarks zu interpretieren, die Ihren Behauptungen widersprechen: Memcpy ist für nicht überlappende Regionen schneller.
Cruppstahl
Meine Bewerbung ist ein B-Baum! Immer wenn Ganzzahlen in einen Blattknoten eingefügt werden, wird memmove aufgerufen, um Platz zu schaffen. Ich arbeite an einer Datenbank-Engine.
Cruppstahl
1
Sie verwenden einen Mikro-Benchmark und lassen Memcopy und Memmove nicht einmal dieselben Daten verschieben. Die genauen Speicherorte, an denen sich die Daten befinden, die Sie kopieren, wirken sich auf das Caching aus und darauf, wie viele Roundtrips zum Speicher die CPU durchführen muss.
user3710044
Obwohl diese Antwort richtig ist, erklärt sie nicht, warum sie in diesem Fall langsamer ist. Sie sagt im Wesentlichen: "Sie ist langsamer, weil sie in einigen Fällen langsamer sein kann."
Oliver Charlesworth
Ich sage, dass unter den gleichen Umständen, einschließlich des gleichen Speicherlayouts zum Kopieren / Verschieben der Benchmarks, das gleiche sein wird, weil die Implementierungen gleich sind. Das Problem liegt in der Mikrobank.
user3710044
2

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

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

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

Ehsan
quelle