Was ist der schnellste Weg, um zwei nicht überlappende Speicherbereiche gleicher Größe zu tauschen? Sagen wir, ich muss (t_Some *a) gegen (t_Some *b) tauschen. Betrachtet man den Raum-Zeit-Kompromiss, wird der temporäre Raum die Geschwindigkeit erhöhen? Beispiel: (char *tmp) vs (int *tmp) ? Ich suche nach einer tragbaren Lösung.
Prototyp:
%Vor% Am besten ist es, die Registerbenutzung zu maximieren, so dass Sie beim Lesen eines temporären Speichers nicht mit zusätzlichen (wahrscheinlich zwischengespeicherten) Speicherzugriffen enden. Die Anzahl der Register hängt von einer System- und Registerzuordnung ab (die Logik, die Ihre Variablen auf tatsächliche Register abbildet) hängt von einem Compiler ab. Also denke ich, dass Sie nur ein Register erwarten und erwarten, dass seine Größe der des Zeigers entspricht. Dies führt zu einer einfachen Schleife, die Blöcke behandelt, die als Arrays von size_t interpretiert werden.
Word schreibt wird am schnellsten sein. Allerdings müssen sowohl die Blockgröße als auch die Ausrichtung berücksichtigt werden. In der Praxis sind die Dinge in der Regel vernünftig ausgerichtet, aber Sie sollten nicht darauf zählen. memcpy() handhabt alles sicher und kann für konstante Größen innerhalb des Grundes spezialisiert (eingebaut) sein.
Hier ist eine portable Lösung, die in den meisten Fällen gut funktioniert .
%Vor%Wenn die 2 Speicherbereiche groß sind und in ganze Zahlen von Speicherseiten passen, können Sie ihre Seitentabelleneinträge austauschen, um ihren Inhalt zu tauschen, ohne memcpy () oder XORs zu verwenden.
Theoretisch müssen Sie bei zwei großen 2MiB-Seiten nur 16 Bytes an Paging-Strukturen schreiben, um ihre Zuordnung im virtuellen Adressraum ... und damit auch deren Inhalt zu vertauschen.
1GiB-Seiten sind auf x86-64-CPUs im 64-Bit-Modus möglich, und der Inhalt von 2 solcher 1GiB-Speicherblöcke kann auch durch das Schreiben von nur einigen Bytes von Paging-Strukturen vertauscht werden.
Der Nachteil dieser Methode besteht darin, dass der Zugriff auf Paging-Strukturen Kernel-Modus-Privilegien oder die Verwendung von Shared-Memory-Mapping-Funktionen aus dem Benutzermodus erfordert.
Mit den letzten Meltdown-Patches (KPTI) ist der Wechsel vom Benutzermodus zum Kernel-Modus viel teurer geworden. Wahrscheinlich zu teuer, um 4kB Speicher-Swaps mit memcpy () konkurrieren zu können ... aber wenn Sie 2MB oder mehr Speicherblöcke austauschen müssen, ist der Wechsel der Paging-Strukturen schneller.
Der schnellste Weg, um einen Speicherblock zu verschieben, ist memcpy() from <string.h> . Wenn Sie memcpy() von a bis temp , memmove() von b bis a , dann memcpy() von temp bis b , haben Sie einen Swap, der die optimierte Bibliothek verwendet Routinen, die der Compiler wahrscheinlich einleitet. Sie möchten nicht den gesamten Block auf einmal kopieren, sondern in Blöcken von Vektorgröße.
Wenn Sie in der Praxis eine enge Schleife schreiben, kann der Compiler wahrscheinlich feststellen, dass Sie jedes Element der Arrays austauschen und entsprechend optimieren. Bei den meisten modernen CPUs möchten Sie Vektoranweisungen generieren. Es kann möglicherweise schneller Code generieren, wenn Sie sicherstellen, dass alle drei Puffer ausgerichtet sind.
Was Sie jedoch wirklich tun möchten, ist, die Dinge für den Optimierer einfacher zu machen. Nimm dieses Programm:
%Vor%Wenn Sie das in maschinengeschriebenen Code übersetzen, ist das ein schrecklicher Algorithmus, der ein Byte nach dem anderen kopiert, zwei Inkremente pro Iteration macht und so weiter. In der Praxis sieht der Compiler jedoch, was Sie wirklich tun wollen.
In clang 5.0.1 mit -std=c11 -O3 wird (teilweise) die folgende innere Schleife auf x86_64 erzeugt:
Während gcc 7.2.0 mit den gleichen Flags auch vektorisiert, wird die Schleife weniger abgerollt:
%Vor%Den Compiler zu überzeugen, Anweisungen zu erstellen, die jeweils nur an einem Wort arbeiten, anstatt die Schleife zu vektorisieren, ist das Gegenteil von dem, was Sie wollen!
Die Absicht des obigen Fragments besteht darin, den hochoptimierten libc-Versionen von memcpy (oder dem Inlining durch den Compiler) zu erlauben, alle Freiheiten zu nehmen, die sie brauchen. Die Ausrichtung ist entscheidend. Wenn VLAs nicht verfügbar sind (vor C99), kann ein Makro unter Verwendung eines funky do-while erstellt werden.
Die Geschwindigkeit dafür wird teilweise plattformabhängig sein und nur durch Tests bestätigt werden.
Persönlich würde ich bevorzugen, einen Speicherblock gleicher Größe zu einem der Arrays zu erstellen; Verwenden Sie memcpy, um den Inhalt zu wechseln, indem Sie den neu erstellten Speicherblock als Auslagerungsspeicher verwenden.
Die Größe des Speicherblocks wirkt sich nun auf die Betriebsgeschwindigkeit aus (wiederum abhängig von der Plattform). Daher können Sie bei sehr großen Arrays kleinere Datenmengen schneller hin- und herwechseln als jeweils einen großen Zeit.
Bearbeiten
Angesichts des Kommentars möchte ich meinen letzten Kommentar zum Austausch kleinerer Datenmengen erläutern.
Ihr Ziel ist es, a Daten in b und b Daten in a mit einem temporären Swap Space tmp zu übertragen.
Die Größe von tmp ist gleich oder kleiner als die Größe von a oder b , und die Anzahl von Iterationen von Swapping-Daten erhöht sich, wenn die Größe von tmp z. Wenn tmp ein Zehntel der a ist, werden 10 Iterationen benötigt.
Um die Geschwindigkeit von memcpy zu unterstützen, ist es am besten sicherzustellen, dass den Arrays (a, b und tmp) ausgerichteter Speicherplatz zugewiesen wird.
Offensichtlich musst du A nach Temp kopieren, B nach A kopieren und dann Temp nach B kopieren. Du kannst das alles auf einmal tun, für einen kleinen Bereich, oder mach es in Abschnitten für einen größeren Bereich, wo du nicht willst Ich möchte einen so großen Temp-Wert nicht zuweisen. Die Auswahl der Sektionsgröße liegt bei Ihnen, obwohl die Berücksichtigung von Alignment- und Cache-Problemen, die für die Hardware geeignet sind, für große, häufige Verschiebungen wichtig ist.
(Nun, eigentlich gibt es einen anderen Weg, der keinen temporären Raum benötigt: XOR A mit B, dann XOR B mit A, dann XOR A mit B. Ein alter Assembler-Trick.)
Sie können die hier beschriebene hier verwenden. Auf diese Weise können Sie einen dritten Puffer speichern.
%Vor%Selbst diese eine temporäre Variable reicht aus, um den Compiler bei der Optimierung zu unterstützen.
Aber wenn Sie eine solche temporäre Variable verwenden, können Sie das auch tun
%Vor%Auf den ersten Blick sehen beide wegen der vielen Array-Zugriffe (im ersten Fall) und der Verarbeitung von nur einem Byte pro Schleifenlauf teuer aus, aber wenn Sie Ihren Compiler dies optimieren lassen, sollte es in Ordnung sein, als (zumindest gcc) ist schlau genug, um immer 4 Schritte (in x64: sogar 16 Schritte) in einen Loop-Lauf zu bündeln.
Beachten Sie, dass Ihr Compiler möglicherweise nicht so aggressiv optimiert wird, so dass Sie diese Aufteilung möglicherweise selbst vornehmen müssen. Achten Sie in diesem Fall auf die Ausrichtung.