wake-up-neo.com

Verbessertes REP MOVSB ​​für memcpy

Ich möchte erweitertes REP MOVSB ​​(ERMSB) verwenden, um eine hohe Bandbreite für ein benutzerdefiniertes memcpy zu erhalten.

ERMSB wurde mit der Ivy Bridge-Mikroarchitektur eingeführt. Lesen Sie den Abschnitt "Erweiterte REP MOVSB- und STOSB-Operation (ERMSB)" im Handbuch zur Intel-Optimierung , wenn Sie nicht wissen, was ERMSB ist.

Die einzige Möglichkeit, dies direkt zu tun, ist die Inline-Montage. Ich habe die folgende Funktion von https://groups.google.com/forum/#!topic/gnu.gcc.help/-Bmlm_EG_fE

static inline void *__movsb(void *d, const void *s, size_t n) {
  asm volatile ("rep movsb"
                : "=D" (d),
                  "=S" (s),
                  "=c" (n)
                : "0" (d),
                  "1" (s),
                  "2" (n)
                : "memory");
  return d;
}

Wenn ich dies jedoch benutze, ist die Bandbreite viel geringer als bei memcpy. __movsb Erreicht 15 GB/s und memcpy 26 GB/s mit meinem i7-6700HQ (Skylake) -System, Ubuntu 16.10, DDR4 @ 2400 MHz Dual Channel 32 GB, GCC 6.2.

Warum ist die Bandbreite mit REP MOVSB So viel geringer? Was kann ich tun, um es zu verbessern?

Hier ist der Code, den ich zum Testen verwendet habe.

//gcc -O3 -march=native -fopenmp foo.c
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stddef.h>
#include <omp.h>
#include <x86intrin.h>

static inline void *__movsb(void *d, const void *s, size_t n) {
  asm volatile ("rep movsb"
                : "=D" (d),
                  "=S" (s),
                  "=c" (n)
                : "0" (d),
                  "1" (s),
                  "2" (n)
                : "memory");
  return d;
}

int main(void) {
  int n = 1<<30;

  //char *a = malloc(n), *b = malloc(n);

  char *a = _mm_malloc(n,4096), *b = _mm_malloc(n,4096);
  memset(a,2,n), memset(b,1,n);

  __movsb(b,a,n);
  printf("%d\n", memcmp(b,a,n));

  double dtime;

  dtime = -omp_get_wtime();
  for(int i=0; i<10; i++) __movsb(b,a,n);
  dtime += omp_get_wtime();
  printf("dtime %f, %.2f GB/s\n", dtime, 2.0*10*1E-9*n/dtime);

  dtime = -omp_get_wtime();
  for(int i=0; i<10; i++) memcpy(b,a,n);
  dtime += omp_get_wtime();
  printf("dtime %f, %.2f GB/s\n", dtime, 2.0*10*1E-9*n/dtime);  
}

Der Grund, warum ich an rep movsb Interessiert bin, beruht auf diesen Kommentaren

Beachten Sie, dass Sie auf Ivybridge und Haswell mit zu großen Puffern, die in MLC passen, movntdqa mit rep movsb schlagen können. movntdqa verursacht eine RFO in LLC, rep movsb nicht ... rep movsb ist bedeutend schneller als movntdqa beim Streaming in den Speicher auf Ivybridge und Haswell (aber beachten Sie, dass es vor Ivybridge langsam ist!)

Was fehlt/suboptimal in dieser memcpy-Implementierung?


Hier sind meine Ergebnisse auf dem gleichen System von tinymembnech .

 C copy backwards                                     :   7910.6 MB/s (1.4%)
 C copy backwards (32 byte blocks)                    :   7696.6 MB/s (0.9%)
 C copy backwards (64 byte blocks)                    :   7679.5 MB/s (0.7%)
 C copy                                               :   8811.0 MB/s (1.2%)
 C copy prefetched (32 bytes step)                    :   9328.4 MB/s (0.5%)
 C copy prefetched (64 bytes step)                    :   9355.1 MB/s (0.6%)
 C 2-pass copy                                        :   6474.3 MB/s (1.3%)
 C 2-pass copy prefetched (32 bytes step)             :   7072.9 MB/s (1.2%)
 C 2-pass copy prefetched (64 bytes step)             :   7065.2 MB/s (0.8%)
 C fill                                               :  14426.0 MB/s (1.5%)
 C fill (shuffle within 16 byte blocks)               :  14198.0 MB/s (1.1%)
 C fill (shuffle within 32 byte blocks)               :  14422.0 MB/s (1.7%)
 C fill (shuffle within 64 byte blocks)               :  14178.3 MB/s (1.0%)
 ---
 standard memcpy                                      :  12784.4 MB/s (1.9%)
 standard memset                                      :  30630.3 MB/s (1.1%)
 ---
 MOVSB copy                                           :   8712.0 MB/s (2.0%)
 MOVSD copy                                           :   8712.7 MB/s (1.9%)
 SSE2 copy                                            :   8952.2 MB/s (0.7%)
 SSE2 nontemporal copy                                :  12538.2 MB/s (0.8%)
 SSE2 copy prefetched (32 bytes step)                 :   9553.6 MB/s (0.8%)
 SSE2 copy prefetched (64 bytes step)                 :   9458.5 MB/s (0.5%)
 SSE2 nontemporal copy prefetched (32 bytes step)     :  13103.2 MB/s (0.7%)
 SSE2 nontemporal copy prefetched (64 bytes step)     :  13179.1 MB/s (0.9%)
 SSE2 2-pass copy                                     :   7250.6 MB/s (0.7%)
 SSE2 2-pass copy prefetched (32 bytes step)          :   7437.8 MB/s (0.6%)
 SSE2 2-pass copy prefetched (64 bytes step)          :   7498.2 MB/s (0.9%)
 SSE2 2-pass nontemporal copy                         :   3776.6 MB/s (1.4%)
 SSE2 fill                                            :  14701.3 MB/s (1.6%)
 SSE2 nontemporal fill                                :  34188.3 MB/s (0.8%)

Beachten Sie, dass SSE2 copy prefetched Auf meinem System auch schneller ist als MOVSB copy.


In meinen ursprünglichen Tests habe ich den Turbo nicht deaktiviert. Ich habe den Turbo deaktiviert und erneut getestet und es scheint keinen großen Unterschied zu machen. Das Ändern der Energieverwaltung macht jedoch einen großen Unterschied.

Wenn ich es tue

Sudo cpufreq-set -r -g performance

Ich sehe manchmal über 20 GB/s mit rep movsb.

mit

Sudo cpufreq-set -r -g powersave

das Beste, was ich sehe, sind ungefähr 17 GB/s. Aber memcpy scheint nicht empfindlich auf die Energieverwaltung zu reagieren.


Ich überprüfte die Frequenz (mit turbostat) mit und ohne aktiviertem SpeedStep , mit performance und mit powersave auf Leerlauf, eine 1-Kernlast und a 4 Kernlast. Ich habe Intels MKL-Multiplikation mit dichter Matrix ausgeführt, um eine Last zu erstellen und die Anzahl der Threads mit OMP_SET_NUM_THREADS Festzulegen. Hier ist eine Tabelle der Ergebnisse (Zahlen in GHz).

              SpeedStep     idle      1 core    4 core
powersave     OFF           0.8       2.6       2.6
performance   OFF           2.6       2.6       2.6
powersave     ON            0.8       3.5       3.1
performance   ON            3.5       3.5       3.1

Dies zeigt, dass mit powersave auch bei deaktiviertem SpeedStep die CPU immer noch auf die Leerlauffrequenz von 0.8 GHz Heruntergetaktet wird. Nur mit performance ohne SpeedStep läuft die CPU mit einer konstanten Frequenz.

Ich habe beispielsweise Sudo cpufreq-set -r performance (Weil cpufreq-set Seltsame Ergebnisse lieferte) verwendet, um die Energieeinstellungen zu ändern. Dies schaltet den Turbo wieder ein, so dass ich den Turbo danach deaktivieren musste.

54
Z boson

Dies ist ein Thema, das mir sehr am Herzen liegt, und ich werde es aus einigen Blickwinkeln betrachten: Geschichte, einige technische Anmerkungen (hauptsächlich akademische), Testergebnisse auf meiner Box und schließlich den Versuch, Ihre eigentliche Frage zu beantworten von wann und wo rep movsb sinnvoll sein könnte.

Teilweise ist dies ein Aufruf zum Teilen von Ergebnissen - wenn Sie Tinymembench ausführen und die Ergebnisse zusammen mit Details Ihrer CPU- und RAM - Konfiguration teilen können es wäre toll. Vor allem, wenn Sie ein 4-Kanal-Setup, eine Ivy Bridge-Box, eine Server-Box usw. haben.

Geschichte und offizielle Beratung

Die Leistungshistorie der Anweisungen zum schnellen Kopieren von Strings war eine Art Treppenschritt - d. H. Perioden mit stagnierender Leistung, die sich mit großen Upgrades abwechselten, die sie in Einklang brachten oder sogar schneller als konkurrierende Ansätze waren. Zum Beispiel gab es in Nehalem einen Leistungssprung (hauptsächlich im Hinblick auf Start-Overheads) und erneut in Ivy Bridge (am häufigsten im Hinblick auf den Gesamtdurchsatz bei großen Kopien). Sie können jahrzehntelange Einblicke in die Schwierigkeiten bei der Implementierung der Anweisungen rep movs Von einem Intel-Techniker erhalten in diesem Thread .

In Handbüchern, die der Einführung von Ivy Bridge vorausgehen, lautet der typische Ratschlag , sie zu vermeiden oder sehr vorsichtig zu verwenden1.

Der aktuelle (nun ja, Juni 2016) Leitfaden enthält eine Vielzahl von verwirrenden und etwas inkonsistenten Ratschlägen, wie z2:

Die spezifische Variante der Implementierung wird zur Ausführungszeit basierend auf Datenlayout, Ausrichtung und dem Zählerwert (ECX) ausgewählt. Beispielsweise sollte MOVSB ​​/ STOSB mit dem Präfix REP mit einem Zählerwert kleiner oder gleich drei verwendet werden, um die beste Leistung zu erzielen.

Also für Kopien von 3 oder weniger Bytes? Dafür benötigen Sie in erster Linie kein Präfix rep, da Sie bei einer angegebenen Startverzögerung von ~ 9 Zyklen mit einem einfachen DWORD oder QWORD mov mit einem mit ziemlicher Sicherheit besser dran sind Bit-Twiddling, um die nicht verwendeten Bytes zu maskieren (oder vielleicht mit 2 expliziten Bytes, Word mov s, wenn Sie wissen, dass die Größe genau drei beträgt).

Sie fahren fort zu sagen:

String MOVE/STORE-Anweisungen weisen mehrere Datengranularitäten auf. Für eine effiziente Datenübertragung sind größere Datengranularitäten vorzuziehen. Dies bedeutet, dass eine bessere Effizienz erzielt werden kann, indem ein beliebiger Zählerwert in eine Anzahl von Doppelwörtern plus Einzelbyte-Bewegungen mit einem Zählwert kleiner oder gleich 3 zerlegt wird.

Dies scheint auf aktueller Hardware mit ERMSB sicherlich falsch zu sein, wo rep movsb Mindestens genauso schnell oder schneller ist als die Varianten movd oder movq für große Kopien.

Im Allgemeinen enthält dieser Abschnitt (3.7.5) des aktuellen Handbuchs eine Mischung aus vernünftigen und schlecht veralteten Ratschlägen. Dies ist der übliche Durchsatz der Intel-Handbücher, da sie schrittweise für jede Architektur aktualisiert werden (und angeblich Architekturen im Wert von fast zwei Jahrzehnten auch im aktuellen Handbuch abdecken) und alte Abschnitte häufig nicht aktualisiert werden, um bedingte Ratschläge zu ersetzen oder zu erteilen Das gilt nicht für die aktuelle Architektur.

Anschließend behandeln sie ERMSB explizit in Abschnitt 3.7.6.

Ich werde die verbleibenden Ratschläge nicht erschöpfend behandeln, aber ich werde die guten Teile im folgenden Abschnitt "Warum es verwenden" zusammenfassen.

Andere wichtige Behauptungen aus dem Handbuch lauten, dass in Haswell rep movsb Für die interne Verwendung von 256-Bit-Operationen erweitert wurde.

Technische Überlegungen

Dies ist nur eine kurze Zusammenfassung der zugrunde liegenden Vor- und Nachteile, die die Anweisungen rep unter dem Gesichtspunktimplementierenaufweisen.

Vorteile für rep movs

  1. Wenn ein rep - Moving-Befehl ausgegeben wird, weiß die CPU,, dass ein ganzer Block einer bekannten Größe übertragen werden soll. Dies kann dazu beitragen, den Betrieb auf eine Weise zu optimieren, die mit diskreten Anweisungen nicht möglich ist, zum Beispiel:

    • Das Vermeiden der RFO-Anforderung, wenn bekannt ist, dass die gesamte Cache-Zeile überschrieben wird.
    • Vorablesezugriffsanforderungen sofort und genau ausgeben. Das Hardware-Prefetching leistet gute Arbeit beim Erkennen von memcpy - ähnlichen Mustern, erfordert jedoch noch ein paar Lesevorgänge und wird viele Cache-Zeilen über das Ende des kopierten Bereichs hinaus "vorab holen". rep movsb Kennt die Größe der Region genau und kann sie vorab abrufen.
  2. Anscheinend gibt es keine Garantie für die Bestellung innerhalb der Läden3 ein einziger rep movs, der dazu beitragen kann, den Kohärenzverkehr und andere Aspekte der Blockverschiebung zu vereinfachen, im Vergleich zu einfachen mov - Befehlen, die einer strengen Speicherreihenfolge unterliegen müssen4.

  3. Im Prinzip kann die Anweisung rep movs Verschiedene architektonische Tricks nutzen, die in der ISA nicht verfügbar sind. Beispielsweise können Architekturen breitere interne Datenpfade aufweisen, die von ISA verfügbar gemacht werden5 und rep movs könnte das intern verwenden.

Nachteile

  1. rep movsb Muss eine bestimmte Semantik implementieren, die möglicherweise stärker ist als die zugrunde liegende Softwareanforderung. Insbesondere verbietet memcpy das Überlappen von Regionen und ignoriert diese Möglichkeit möglicherweise, aber rep movsb Lässt sie zu und muss das erwartete Ergebnis liefern. Bei aktuellen Implementierungen wirkt sich dies hauptsächlich auf den Startaufwand aus, wahrscheinlich jedoch nicht auf den Durchsatz bei großen Blöcken. Ebenso muss rep movsb Bytegranulare Kopien unterstützen, auch wenn Sie damit große Blöcke kopieren, die ein Vielfaches einer großen Potenz von 2 sind.

  2. Die Software verfügt möglicherweise über Informationen zu Ausrichtung, Kopiengröße und möglichem Aliasing, die bei Verwendung von rep movsb Nicht an die Hardware übermittelt werden können. Compiler können häufig die Ausrichtung von Speicherblöcken bestimmen6 und kann so viel Startarbeit vermeiden, die rep movs fürjedenAufruf ausführen muss.

Testergebnisse

Hier sind Testergebnisse für viele verschiedene Kopiermethoden von tinymembench auf meinem i7-6700HQ mit 2,6 GHz (schade, dass ich die identische CPU habe, damit wir sie nicht bekommen ein neuer Datenpunkt ...):

 C copy backwards                                     :   8284.8 MB/s (0.3%)
 C copy backwards (32 byte blocks)                    :   8273.9 MB/s (0.4%)
 C copy backwards (64 byte blocks)                    :   8321.9 MB/s (0.8%)
 C copy                                               :   8863.1 MB/s (0.3%)
 C copy prefetched (32 bytes step)                    :   8900.8 MB/s (0.3%)
 C copy prefetched (64 bytes step)                    :   8817.5 MB/s (0.5%)
 C 2-pass copy                                        :   6492.3 MB/s (0.3%)
 C 2-pass copy prefetched (32 bytes step)             :   6516.0 MB/s (2.4%)
 C 2-pass copy prefetched (64 bytes step)             :   6520.5 MB/s (1.2%)
 ---
 standard memcpy                                      :  12169.8 MB/s (3.4%)
 standard memset                                      :  23479.9 MB/s (4.2%)
 ---
 MOVSB copy                                           :  10197.7 MB/s (1.6%)
 MOVSD copy                                           :  10177.6 MB/s (1.6%)
 SSE2 copy                                            :   8973.3 MB/s (2.5%)
 SSE2 nontemporal copy                                :  12924.0 MB/s (1.7%)
 SSE2 copy prefetched (32 bytes step)                 :   9014.2 MB/s (2.7%)
 SSE2 copy prefetched (64 bytes step)                 :   8964.5 MB/s (2.3%)
 SSE2 nontemporal copy prefetched (32 bytes step)     :  11777.2 MB/s (5.6%)
 SSE2 nontemporal copy prefetched (64 bytes step)     :  11826.8 MB/s (3.2%)
 SSE2 2-pass copy                                     :   7529.5 MB/s (1.8%)
 SSE2 2-pass copy prefetched (32 bytes step)          :   7122.5 MB/s (1.0%)
 SSE2 2-pass copy prefetched (64 bytes step)          :   7214.9 MB/s (1.4%)
 SSE2 2-pass nontemporal copy                         :   4987.0 MB/s

Einige wichtige Imbissbuden:

  • Die Methoden rep movs Sind schneller als alle anderen Methoden, die nicht "nicht-zeitlich" sind.7und erheblich schneller als das "C", das jeweils 8 Bytes kopiert.
  • Die "nicht-zeitlichen" Methoden sind um bis zu 26% schneller als die rep movs - aber das ist ein viel kleineres Delta als das von Ihnen gemeldete (26 GB/s vs. 15 GB/s = ~ 73) %).
  • Wenn Sie keine nicht temporären Speicher verwenden, ist die Verwendung von 8-Byte-Kopien von C ziemlich genau so gut wie das Laden/Speichern mit 128-Bit-Breite SSE. Dies liegt daran, dass eine gute Kopierschleife genügend Speicherdruck erzeugen kann, um die Bandbreite zu sättigen (z. B. 2,6 GHz * 1 Speicher/Zyklus * 8 Bytes = 26 GB/s für Speicher).
  • Es gibt keine expliziten 256-Bit-Algorithmen in tinymembench (außer wahrscheinlich dem "Standard" memcpy), aber aufgrund des obigen Hinweises spielt dies wahrscheinlich keine Rolle.
  • Der erhöhte Durchsatz der nicht-temporären Speicheransätze gegenüber den temporären Ansätzen beträgt etwa 1,45x, was sehr nahe an dem 1,5x liegt, das Sie erwarten würden, wenn NT 1 von 3 Übertragungen eliminiert (dh 1 Lesen, 1 Schreiben für NT vs 2) liest, 1 schreiben). Die rep movs - Ansätze liegen in der Mitte.
  • Die Kombination aus relativ geringer Speicherlatenz und bescheidener 2-Kanal-Bandbreite bedeutet, dass dieser bestimmte Chip seine Speicherbandbreite zufällig von einem einzelnen Thread aus sättigen kann, wodurch sich das Verhalten dramatisch ändert.
  • rep movsd Scheint die gleiche Magie wie rep movsb Auf diesem Chip zu verwenden. Das ist interessant, da ERMSB nur explizit auf movsb und frühere Tests mit früheren Bögen abzielt, wobei ERMSB zeigt, dass movsb viel schneller als movsd ist. Dies ist größtenteils akademisch, da movsb ohnehin allgemeiner ist als movsd.

Haswell

Wenn wir uns die von iwillnotexist in den Kommentaren zur Verfügung gestellten Haswell-Ergebnisse ansehen, sehen wir die gleichen allgemeinen Trends (die relevantesten Ergebnisse extrahiert):

 C copy                                               :   6777.8 MB/s (0.4%)
 standard memcpy                                      :  10487.3 MB/s (0.5%)
 MOVSB copy                                           :   9393.9 MB/s (0.2%)
 MOVSD copy                                           :   9155.0 MB/s (1.6%)
 SSE2 copy                                            :   6780.5 MB/s (0.4%)
 SSE2 nontemporal copy                                :  10688.2 MB/s (0.3%)

Der Ansatz rep movsb Ist immer noch langsamer als der nicht-zeitliche Ansatz memcpy, hier jedoch nur um ca. 14% (im Vergleich zu ~ 26% im Skylake-Test). Der Vorteil der NT-Techniken gegenüber ihren zeitlichen Verwandten beträgt jetzt ~ 57%, sogar etwas mehr als der theoretische Vorteil der Bandbreitenreduzierung.

Wann sollten Sie rep movs Verwenden?

Endlich ein Stich auf Ihre eigentliche Frage: Wann oder warum sollten Sie es verwenden? Es stützt sich auf das oben Gesagte und führt einige neue Ideen ein. Leider gibt es keine einfache Antwort: Sie müssen verschiedene Faktoren gegeneinander abwägen, darunter einige, die Sie wahrscheinlich nicht genau kennen, wie z. B. zukünftige Entwicklungen.

Beachten Sie, dass die Alternative zu rep movsb Die optimierte libc memcpy (einschließlich der vom Compiler eingefügten Kopien) oder eine von Hand gerollte memcpy - Version sein kann. Einige der folgenden Vorteile gelten nur im Vergleich zu der einen oder anderen dieser Alternativen (z. B. "Einfachheit" hilft gegen eine handgerollte Version, aber nicht gegen integrierte memcpy), aber einige gelten für beide .

Einschränkungen für verfügbare Anweisungen

In einigen Umgebungen sind bestimmte Anweisungen oder die Verwendung bestimmter Register eingeschränkt. Beispielsweise ist im Linux-Kernel die Verwendung von SSE/AVX- oder FP -Registern im Allgemeinen nicht zulässig. Daher können die meisten der optimierten memcpy - Varianten nicht verwendet werden, da sie auf SSE - oder AVX-Registern basieren. Auf x86 wird eine einfache 64-Bit-Kopie mov verwendet. Für diese Plattformen ermöglicht die Verwendung von rep movsb Den größten Teil der Leistung eines optimierten memcpy, ohne die Einschränkung des SIMD-Codes zu überschreiten.

Ein allgemeineres Beispiel könnte Code sein, der auf viele Hardwaregenerationen abzielen muss und der kein hardwarespezifisches Dispatching verwendet (z. B. mit cpuid). Hier könnten Sie gezwungen sein, nur ältere Befehlssätze zu verwenden, was AVX usw. ausschließt. rep movsb Könnte hier ein guter Ansatz sein, da es "verborgenen" Zugriff auf breitere Lasten und Speicher ermöglicht, ohne neue Anweisungen zu verwenden. Wenn Sie auf Hardware vor ERMSB abzielen, müssen Sie allerdings prüfen, ob die Leistung von rep movsb Dort akzeptabel ist ...

Zukunftssicher

Ein netter Aspekt von rep movsb Ist, dass estheoretischdie architektonische Verbesserung zukünftiger Architekturen nutzen kann, ohne dass sich die Quelle ändert, was explizite Bewegungen nicht können. Als beispielsweise 256-Bit-Datenpfade eingeführt wurden, konnte rep movsb Diese nutzen (wie von Intel behauptet), ohne dass Änderungen an der Software erforderlich waren. Software, die 128-Bit-Moves verwendet (was vor Haswell optimal war), müsste modifiziert und neu kompiliert werden.

Dies ist sowohl ein Vorteil für die Softwarewartung (es muss nicht die Quelle geändert werden) als auch ein Vorteil für vorhandene Binärdateien (es müssen keine neuen Binärdateien bereitgestellt werden, um die Verbesserung zu nutzen).

Wie wichtig dies ist, hängt von Ihrem Wartungsmodell ab (z. B. wie oft neue Binärdateien in der Praxis bereitgestellt werden) und es ist sehr schwierig zu beurteilen, wie schnell diese Anweisungen in Zukunft wahrscheinlich sind. Zumindest Intel ist eine Art Leitsatz in dieser Richtung, indem es sich zu mindestensangemessenerLeistung in der Zukunft verpflichtet ( 15.3.3.6 ):

REP MOVSB ​​und REP STOSB werden auf zukünftigen Prozessoren weiterhin eine recht gute Leistung erbringen.

Überlappung mit nachfolgenden Arbeiten

Dieser Vorteil wird natürlich nicht in einem einfachen Benchmark memcpy angezeigt, der per Definition keine Überlappungsarbeit nach sich zieht, sodass die Höhe des Vorteils in einem realen Szenario sorgfältig gemessen werden müsste . Um den größtmöglichen Nutzen daraus zu ziehen, muss der Code, der die memcpy umgibt, möglicherweise neu organisiert werden.

Auf diesen Vorteil wird Intel in seinem Optimierungshandbuch (Abschnitt 11.16.3.4) und in seinen Worten hingewiesen:

Wenn bekannt ist, dass die Anzahl mindestens tausend Byte oder mehr beträgt, kann die Verwendung von erweitertem REP MOVSB ​​/ STOSB einen weiteren Vorteil bieten, um die Kosten des nicht verbrauchenden Codes zu amortisieren. Die Heuristik kann am Beispiel von Cnt = 4096 und memset () verstanden werden:

• Eine 256-Bit-SIMD-Implementierung von memset () muss 128 Instanzen eines 32-Byte-Speichervorgangs mit VMOVDQA ausgeben/ausführen, bevor die nicht verbrauchenden Anweisungssequenzen in den Ruhestand versetzt werden können.

• Eine Instanz von Enhanced REP STOSB mit ECX = 4096 wird als langer, von der Hardware bereitgestellter Micro-Op-Flow dekodiert, wird jedoch als ein Befehl zurückgezogen. Es gibt viele store_data-Vorgänge, die abgeschlossen werden müssen, bevor das Ergebnis von memset () verarbeitet werden kann. Da der Abschluss des Vorgangs zum Speichern von Daten von der Stilllegung der Programmreihenfolge abgekoppelt ist, kann ein wesentlicher Teil des nicht verbrauchenden Codestroms die Ausgabe/Ausführung und Stilllegung durchlaufen, was im Wesentlichen kostenlos ist, wenn die nicht verbrauchende Sequenz nicht konkurriert für Speicherpufferressourcen.

Intel sagt also, dass der Code nach der Ausgabe von rep movsb Immerhin ein paar Uops ist, aber während sich noch viele Geschäfte im Flug befinden und der rep movsb Insgesamt noch nicht zurückgezogen ist, hoppla! Anweisungen können durch die außer Betrieb befindliche Maschine mehr Fortschritte machen, als wenn dieser Code nach einer Kopierschleife käme.

Die Ups aus einer expliziten Lade- und Speicherschleife müssen alle in der Programmreihenfolge separat beendet werden. Das muss passieren, um im ROB Platz für nachfolgende Ups zu schaffen.

Es scheint nicht viele detaillierte Informationen darüber zu geben, wie lange Mikrocodierungsbefehle wie rep movsb Genau funktionieren. Wir wissen nicht genau, wie Mikrocode-Verzweigungen einen anderen Uop-Stream vom Mikrocode-Sequenzer anfordern oder wie sich die Uops zurückziehen. Wenn die einzelnen Uops nicht separat in den Ruhestand gehen müssen, belegt der gesamte Befehl möglicherweise nur einen Platz im ROB?

Wenn das Front-End, das die OoO-Maschine versorgt, einen rep movsb - Befehl im UOP-Cache sieht, aktiviert es den Microcode Sequencer ROM (MS-ROM), um Mikrocode-Uops in die Warteschlange zu senden, die das Problem versorgt/Bühne umbenennen. Es ist wahrscheinlich nicht möglich, dass sich andere Uops damit mischen und ausgeben/ausführen8 Während rep movsb noch ausgegeben wird, können nachfolgende Anweisungen abgerufen/dekodiert und direkt nach dem letzten rep movsb uop ausgegeben werden, während ein Teil der Kopie noch nicht ausgeführt wurde. Dies ist nur sinnvoll, wenn zumindest ein Teil Ihres nachfolgenden Codes nicht vom Ergebnis der memcpy abhängt (was nicht ungewöhnlich ist).

Jetzt ist die Größe dieses Vorteils begrenzt: Sie können höchstens N Befehle ausführen (uops tatsächlich), die über den langsamen Befehl rep movsb Hinausgehen. An diesem Punkt werden Sie blockieren, wobei N ) ist ROB Größe . Bei aktuellen ROB-Größen von ~ 200 (192 bei Haswell, 224 bei Skylake) ergibt sich ein maximaler Vorteil von ~ 200 Zyklen freier Arbeit für nachfolgenden Code mit einem IPC von 1. In 200 Zyklen können Sie ungefähr 800 kopieren Bytes bei 10 GB/s, so dass Sie für Kopien dieser Größe möglicherweise freie Arbeit in der Nähe der Kosten für die Kopie erhalten (auf eine Weise, die die Kopie frei macht).

Mit zunehmender Größe der Kopien nimmt die relative Bedeutung jedoch rapide ab (z. B. wenn Sie stattdessen 80 KB kopieren, beträgt die freie Arbeit nur 1% der Kopierkosten). Trotzdem ist es für Kopien in bescheidener Größe sehr interessant.

Kopierschleifen blockieren die Ausführung nachfolgender Anweisungen ebenfalls nicht vollständig. Intel geht nicht im Detail auf die Größe des Vorteils ein oder darauf, welche Art von Kopien oder Umgebungscode den größten Nutzen bringt. (Heißes oder kaltes Ziel oder Quelle, hoher ILP oder niedriger ILP-Code mit hoher Latenzzeit danach).

Codegröße

Die ausgeführte Codegröße (einige Bytes) ist im Vergleich zu einer typischen optimierten Routine memcpy mikroskopisch. Wenn die Leistung durch Ausfälle des i-Cache (einschließlich des uop-Cache) überhaupt eingeschränkt wird, kann die reduzierte Codegröße von Vorteil sein.

Auch hier können wir die Größe dieses Vorteils anhand der Größe der Kopie festlegen. Ich werde es nicht wirklich numerisch ausarbeiten, aber die Intuition ist, dass das Reduzieren der dynamischen Codegröße um B Bytes höchstens C * B Cache-Fehler für einige konstante C einsparen kann. Everycallto memcpy verursacht einmalig die Kosten (oder den Nutzen) eines Cache-Fehlschlags, aber der Vorteil eines höheren Durchsatzes skaliert mit der Anzahl der kopierten Bytes. Bei großen Übertragungen dominiert also ein höherer Durchsatz die Cache-Effekte.

Auch dies wird nicht in einem einfachen Benchmark angezeigt, bei dem die gesamte Schleife zweifellos in den UOP-Cache passt. Sie benötigen einen praktischen Test, um diesen Effekt zu bewerten.

Architekturspezifische Optimierung

Sie haben berichtet, dass rep movsb Auf Ihrer Hardware erheblich langsamer war als die Plattform memcpy. Allerdings gibt es auch hier Berichte über das gegenteilige Ergebnis bei früherer Hardware (wie Ivy Bridge).

Das ist durchaus plausibel, da es den Anschein hat, als würden sich die Saitenbewegungsoperationen von Zeit zu Zeit lieben - aber nicht jede Generation. Daher ist es möglicherweise schneller oder zumindest an den Architekturen gebunden (an denen es aufgrund anderer Vorteile gewinnt), an denen es sich befand auf den neuesten Stand gebracht, nur um in nachfolgender Hardware ins Hintertreffen zu geraten.

Quoting Andy Glew, der ein oder zwei Dinge darüber wissen sollte, nachdem er diese auf dem P6 implementiert hat:

die große Schwäche bei der Ausführung schneller [...] Zeichenfolgen im Mikrocode war, dass der Mikrocode mit jeder Generation verstimmte und immer langsamer wurde, bis sich jemand daran machte, ihn zu reparieren. Genau wie eine Bibliothek fällt Männerkopie aus dem Takt. Ich nehme an, es ist möglich, dass eine der verpassten Möglichkeiten darin bestand, 128-Bit-Ladevorgänge und -Speicher zu verwenden, als sie verfügbar wurden, und so weiter.

In diesem Fall kann dies nur als eine weitere "plattformspezifische" Optimierung angesehen werden, die in den typischen Routinen memcpy angewendet wird, die in Standardbibliotheken und JIT-Compilern zu finden sind, jedoch nur zur Verwendung auf architekturen wo es besser ist. Für JIT- oder AOT-kompilierte Inhalte ist dies einfach, für statisch kompilierte Binärdateien ist jedoch ein plattformspezifischer Versand erforderlich, der jedoch häufig bereits vorhanden ist (manchmal zum Zeitpunkt der Verknüpfung implementiert), oder Sie können das Argument mtune verwenden eine statische Entscheidung.

Einfachheit

Selbst auf Skylake, wo es den Anschein hat, als ob es hinter den absolut schnellsten nicht-zeitlichen Techniken zurückgeblieben ist, ist es immer noch schneller als die meisten Ansätze und istsehr einfach. Dies bedeutet weniger Zeit für die Validierung, weniger Rätsel, weniger Zeit für die Optimierung und Aktualisierung einer Monster-Implementierung memcpy (oder umgekehrt weniger Abhängigkeit von den Launen der Standard-Bibliotheksimplementierer, wenn Sie sich darauf verlassen).

Latenzgebundene Plattformen

Algorithmen, die an den Speicherdurchsatz gebunden sind9 kann tatsächlich in zwei Haupt-Gesamtregimen betrieben werden: DRAM-Bandbreitenbegrenzung oder Parallelität/Latenzzeitbegrenzung.

Der erste Modus ist derjenige, den Sie wahrscheinlich kennen: Das DRAM-Subsystem verfügt über eine bestimmte theoretische Bandbreite, die Sie anhand der Anzahl der Kanäle, der Datenrate/-breite und der Frequenz recht einfach berechnen können. Zum Beispiel hat mein DDR4-2133-System mit 2 Kanälen eine maximale Bandbreite von 2,133 * 8 * 2 = 34,1 GB/s, genau wie bei ARK .

Sie werden nicht mehr als diese Rate von DRAM (und normalerweise etwas weniger aufgrund verschiedener Ineffizienzen) aufrechterhalten, die über alle Kerne auf dem Sockel hinzugefügt werden (d. H. Es ist eine globale Grenze für Systeme mit einem Sockel).

Die andere Grenze wird dadurch festgelegt, wie viele gleichzeitige Anforderungen ein Kern tatsächlich an das Speichersubsystem senden kann. Stellen Sie sich vor, ein Core könnte für eine 64-Byte-Cache-Zeile nur eine Anforderung gleichzeitig ausführen. Wenn die Anforderung abgeschlossen ist, könnten Sie eine weitere ausgeben. Nehmen wir auch eine sehr schnelle Speicherlatenz von 50 ns an. Dann würden Sie trotz der großen DRAM-Bandbreite von 34,1 GB/s tatsächlich nur 64 Bytes/50 ns = 1,28 GB/s oder weniger als 4% der maximalen Bandbreite erhalten.

In der Praxis können Kerne mehr als eine Anforderung gleichzeitig ausgeben, jedoch nicht eine unbegrenzte Anzahl. Es versteht sich normalerweise, dass es nur 10Zeilenfüllpufferpro Kern zwischen dem L1 und dem Rest der Speicherhierarchie gibt, und vielleicht 16 oder so Füllpuffer zwischen L2 und DRAM. Prefetching konkurriert um die gleichen Ressourcen, hilft aber zumindest dabei, die effektive Latenz zu reduzieren. Weitere Informationen finden Sie in den großartigen Posts, die Dr. Bandwidth zum Thema geschrieben hat, hauptsächlich in den Intel-Foren.

Trotzdem sinddie meistenaktuellen CPUs durchdiesenFaktor begrenzt, nicht durch die RAM Bandbreite. Normalerweise erreichen sie 12 - 20 GB/s pro Kern, während die Bandbreite RAM 50+ GB/s betragen kann (auf einem 4-Kanal-System). Nur einige neuere 2-Kanal "Client" -Kerne, die einen besseren Uncore zu haben scheinen, vielleicht mehr Zeilenpuffer, können die DRAM-Grenze für einen einzelnen Kern erreichen, und unsere Skylake-Chips scheinen einer von ihnen zu sein.

Nun gibt es natürlich einen Grund, warum Intel Systeme mit einer DRAM-Bandbreite von 50 GB/s entwickelt und aufgrund von Parallelitätsbeschränkungen nur <20 GB/s pro Kern unterstützt: Die erstere Beschränkung gilt für den gesamten Socket und die letztere für den Kern. Jeder Kern auf einem 8-Kern-System kann also Anfragen im Wert von 20 GB/s senden. Ab diesem Zeitpunkt sind sie wieder auf DRAM beschränkt.

Warum mache ich so weiter? Weil die beste Implementierung memcpy oft davon abhängt, in welchem ​​Regime Sie arbeiten. Sobald Sie DRAM BW-beschränkt sind (wie es unsere Chips anscheinend sind, aber die meisten nicht auf einem einzigen Kern), wird die Verwendung von nicht-temporalen Schreibvorgängen Dies ist sehr wichtig, da es das Read-for-Ownership spart, das normalerweise 1/3 Ihrer Bandbreite verschwendet. Sie sehen das genau in den obigen Testergebnissen: Die memcpy-Implementierungen, dienichtNT-Speicher verwenden, verlieren 1/3 ihrer Bandbreite.

Wenn Sie jedoch auf Nebenläufigkeit beschränkt sind, gleicht sich die Situation aus und kehrt sich manchmal um. Sie haben DRAM-Bandbreite zur Verfügung, daher helfen NT-Speicher nicht und können sogar Schaden anrichten, da sie die Latenz erhöhen können, da die Übergabezeit für den Leitungspuffer länger sein kann als in einem Szenario, in dem Prefetch die RFO-Leitung in LLC (oder sogar in LLC) bringt L2) und dann wird der Speicher in LLC für eine effektiv niedrigere Latenz abgeschlossen. Schließlich neigenserveruncores dazu, viel langsamere NT-Speicher als Client-Speicher (und hohe Bandbreite) zu haben, was diesen Effekt verstärkt.

Auf anderen Plattformen sind NT-Speicher möglicherweise weniger nützlich (zumindest, wenn Sie sich für Single-Thread-Leistung interessieren), und vielleicht gewinnt rep movsb, Wo (wenn es das Beste aus beiden Welten bekommt).

Wirklich, dieser letzte Punkt ist ein Aufruf für die meisten Tests. Ich weiß, dass NT-Stores ihren offensichtlichen Vorteil für Single-Thread-Tests auf den meisten Archs (einschließlich der aktuellen Server-Archs) verlieren, aber ich weiß nicht, wie sich rep movsb Relativ verhält ...

Verweise

Andere gute Informationsquellen, die nicht in das oben Gesagte integriert sind.

Comp.Arch Untersuchung von rep movsb versus Alternativen. Viele gute Hinweise zur Verzweigungsvorhersage und eine Implementierung des Ansatzes, den ich oft für kleine Blöcke vorgeschlagen habe: Verwenden überlappender erster und/oder letzter Lese-/Schreibvorgänge, anstatt zu versuchen, nur genau die erforderliche Anzahl von Bytes zu schreiben (z. B. Implementierung) alle Kopien von 9 bis 16 Bytes als zwei 8-Byte-Kopien, die sich in bis zu 7 Bytes überlappen können).


1 Vermutlich soll es auf Fälle beschränkt werden, in denen beispielsweise die Codegröße sehr wichtig ist.

2 Siehe Abschnitt 3.7.5: REP-Präfix und Datenverschiebung.

3 Es ist wichtig anzumerken, dass dies nur für die verschiedenen Geschäfte innerhalb der einzelnen Anweisung selbst gilt: Nach Abschluss des Vorgangs wird der Geschäftsblock weiterhin in Bezug auf vorherige und nachfolgende Geschäfte sortiert angezeigt. Der Code kann also die Läden von rep movs In der Reihenfolgein Bezug aufeinander sehen, jedoch nicht in Bezug auf vorherige oder nachfolgende Läden (und dies ist die letztere Garantie, die Sie normalerweise benötigen). Dies ist nur dann ein Problem, wenn Sie das Ende des Kopierziels anstelle eines separaten Speichers als Synchronisierungsflag verwenden.

4 Beachten Sie, dass nicht-zeitlich getrennte Speicher auch die meisten Bestellanforderungen umgehen, obwohl in der Praxis rep movs Noch mehr Freiheiten bietet, da WC/NT-Speicher immer noch einige Bestellbeschränkungen aufweisen.

5 Dies war im letzten Teil der 32-Bit-Ära üblich, wo viele Chips 64-Bit-Datenpfade hatten (z. B. zur Unterstützung von FPUs, die den 64-Bit-Typ double unterstützen). Heutzutage haben "kastrierte" Chips wie die Pentium- oder Celeron-Marken AVX deaktiviert, aber vermutlich kann der rep movs - Mikrocode immer noch 256b-Ladevorgänge/Speicher belegen.

6 Zum Beispiel aufgrund von Regeln zur Sprachausrichtung, Ausrichtungsattributen oder Operatoren, Aliasing-Regeln oder anderen Informationen, die zum Zeitpunkt der Kompilierung festgelegt wurden. Im Falle der Ausrichtung können sie, selbst wenn die genaue Ausrichtung nicht bestimmt werden kann, zumindest Ausrichtungsprüfungen aus Schleifen herausheben oder auf andere Weise redundante Überprüfungen beseitigen.

7 Ich gehe davon aus, dass "Standard" memcpy einen nicht-zeitlichen Ansatz wählt, was für diese Puffergröße sehr wahrscheinlich ist.

8 Dies ist nicht unbedingt offensichtlich, da der vom rep movsb Generierte UOP-Stream den Versand einfach monopolisiert und dann dem expliziten mov - Fall sehr ähnlich ist. Es scheint jedoch nicht so zu funktionieren - Uops aus nachfolgenden Befehlen können sich mit Uops aus dem Mikrocode rep movsb Vermischen.

9 Das heißt, diejenigen, die eine große Anzahl unabhängiger Speicheranforderungen ausgeben und damit die verfügbare DRAM-zu-Kern-Bandbreite auslasten können, von denen memcpy ein Aushängeschild wäre (und rein latenzgebundenen Lasten wie Zeigern dienen soll) jagen).

68
BeeOnRope

Verbessertes REP MOVSB ​​(Ivy Bridge und höher)

Die Ivy Bridge-Mikroarchitektur (Prozessoren, die in den Jahren 2012 und 2013 veröffentlicht wurden) führte das verbesserte REP-MOVSB ​​ ein (wir müssen noch das entsprechende Bit überprüfen) und ermöglichten uns, den Speicher schnell zu kopieren .

Günstigste Versionen späterer Prozessoren - Kaby Lake Celeron und Pentium, veröffentlicht 2017, haben kein AVX, das für eine schnelle Speicherkopie hätte verwendet werden können, aber immer noch das Enhanced REP MOVSB.

REP MOVSB ​​(ERMSB) ist nur schneller als eine AVX-Kopie oder eine allgemeine Registerkopie, wenn die Blockgröße mindestens 256 Byte beträgt. Für die Blöcke unter 64 Bytes ist es VIEL langsamer, weil in ERMSB ein hoher interner Anlauf vorliegt - ungefähr 35 Zyklen.

Weitere Informationen finden Sie im Intel-Handbuch zur Optimierung, Abschnitt 3.7.6, Erweiterte REP-Funktionen für MOVSB ​​und STOSB (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/). 64-ia-32-Architekturen-Optimierungshandbuch.pdf

  • die Startkosten betragen 35 Zyklen.
  • sowohl die Quell- als auch die Zieladresse müssen an einer 16-Byte-Grenze ausgerichtet sein.
  • die Quellregion sollte sich nicht mit der Zielregion überschneiden.
  • die Länge muss ein Vielfaches von 64 sein, um eine höhere Leistung zu erzielen.
  • die Richtung muss vorwärts sein (CLD).

Wie ich bereits sagte, beginnt REP MOVSB, andere Methoden zu übertreffen, wenn die Länge mindestens 256 Bytes beträgt. Um jedoch den klaren Vorteil gegenüber der AVX-Kopie zu sehen, muss die Länge mehr als 2048 Bytes betragen.

Über die Auswirkung der Ausrichtung, wenn REP MOVSB ​​vs. AVX kopiert wird, gibt das Intel-Handbuch folgende Informationen:

  • wenn der Quellpuffer nicht ausgerichtet ist, sind die Auswirkungen auf die ERMSB-Implementierung im Vergleich zu 128-Bit-AVX ähnlich.
  • wenn der Zielpuffer nicht ausgerichtet ist, kann sich dies auf die ERMSB-Implementierung um 25% verschlechtern, während die 128-Bit-AVX-Implementierung von memcpy im Vergleich zum 16-Byte-ausgerichteten Szenario nur um 5% beeinträchtigt wird.

Ich habe Tests mit Intel Core i5-6600 unter 64-Bit durchgeführt und REP MOVSB ​​memcpy () mit einem einfachen MOV RAX, [SRC], verglichen. MOV [DST], RAX-Implementierung wenn die Daten in den L1-Cache passen:

REP MOVSB ​​memcpy ():

 - 1622400000 data blocks of  32 bytes took 17.9337 seconds to copy;  2760.8205 MB/s
 - 1622400000 data blocks of  64 bytes took 17.8364 seconds to copy;  5551.7463 MB/s
 - 811200000 data blocks of  128 bytes took 10.8098 seconds to copy;  9160.5659 MB/s
 - 405600000 data blocks of  256 bytes took  5.8616 seconds to copy; 16893.5527 MB/s
 - 202800000 data blocks of  512 bytes took  3.9315 seconds to copy; 25187.2976 MB/s
 - 101400000 data blocks of 1024 bytes took  2.1648 seconds to copy; 45743.4214 MB/s
 - 50700000 data blocks of  2048 bytes took  1.5301 seconds to copy; 64717.0642 MB/s
 - 25350000 data blocks of  4096 bytes took  1.3346 seconds to copy; 74198.4030 MB/s
 - 12675000 data blocks of  8192 bytes took  1.1069 seconds to copy; 89456.2119 MB/s
 - 6337500 data blocks of  16384 bytes took  1.1120 seconds to copy; 89053.2094 MB/s

MOV RAX ... memcpy ():

 - 1622400000 data blocks of  32 bytes took  7.3536 seconds to copy;  6733.0256 MB/s
 - 1622400000 data blocks of  64 bytes took 10.7727 seconds to copy;  9192.1090 MB/s
 - 811200000 data blocks of  128 bytes took  8.9408 seconds to copy; 11075.4480 MB/s
 - 405600000 data blocks of  256 bytes took  8.4956 seconds to copy; 11655.8805 MB/s
 - 202800000 data blocks of  512 bytes took  9.1032 seconds to copy; 10877.8248 MB/s
 - 101400000 data blocks of 1024 bytes took  8.2539 seconds to copy; 11997.1185 MB/s
 - 50700000 data blocks of  2048 bytes took  7.7909 seconds to copy; 12710.1252 MB/s
 - 25350000 data blocks of  4096 bytes took  7.5992 seconds to copy; 13030.7062 MB/s
 - 12675000 data blocks of  8192 bytes took  7.4679 seconds to copy; 13259.9384 MB/s

Selbst in 128-Bit-Blöcken ist REP MOVSB ​​also langsamer als nur eine einfache MOV RAX-Kopie in einer Schleife (nicht abgewickelt). Die ERMSB-Implementierung beginnt, die MOV RAX-Schleife erst ab 256-Byte-Blöcken zu übertreffen.

Normal (nicht erweitert) REP MOVS auf Nehalem und höher

Überraschenderweise hatten frühere Architekturen (Nehalem und später), die Enhanced REP MOVB noch nicht hatten, eine recht schnelle Implementierung von REP MOVSD/MOVSQ (aber nicht REP MOVSB ​​/ MOVSW) für große Blöcke, die jedoch nicht groß genug waren, um den L1-Cache zu überdimensionieren.

Das Intel Optimization Manual (2.5.6 REP String Enhancement) enthält die folgenden Informationen zur Nehalem-Mikroarchitektur - Intel Core i5-, i7- und Xeon-Prozessoren, die in den Jahren 2009 und 2010 veröffentlicht wurden.

REP MOVSB

Die Latenz für MOVSB ​​beträgt 9 Zyklen, wenn ECX <4; Andernfalls verursachen REP MOVSB ​​mit ECX> 9 Startkosten in Höhe von 50 Zyklen.

  • winziger String (ECX <4): die Latenz von REP MOVSB ​​beträgt 9 Zyklen;
  • kleiner String (ECX ist zwischen 4 und 9): keine offiziellen Informationen im Intel-Handbuch, wahrscheinlich mehr als 9 Zyklen, aber weniger als 50 Zyklen;
  • langer String (ECX> 9): Startkosten für 50 Zyklen.

Mein Fazit: REP MOVSB ​​ist auf Nehalem fast unbrauchbar.

MOVSW/MOVSD/MOVSQ

Zitat aus dem Intel Optimization Manual (2.5.6 REP String Enhancement):

  • Kurzer String (ECX <= 12): Die Latenz von REP MOVSW/MOVSD/MOVSQ beträgt ca. 20 Zyklen.
  • Schnelle Zeichenfolge (ECX> = 76: ohne REP MOVSB): Die Prozessorimplementierung bietet Hardwareoptimierung, indem so viele Daten wie möglich in 16 Byte verschoben werden. Die Latenz der REP-String-Latenz variiert, wenn eine der 16-Byte-Datenübertragungsspannen die Cache-Zeilengrenze überschreitet: = Aufteilungsfrei: Die Latenz besteht aus Startkosten von etwa 40 Zyklen und jeder 64-Byte-Datenzugabe von 4 Zyklen. = Cache-Aufteilung: Die Latenz besteht aus Startkosten von ca. 35 Zyklen und je 64 Byte Daten kommen 6 Zyklen hinzu.
  • Intermediate-String-Längen: Die Latenz von REP MOVSW/MOVSD/MOVSQ hat Startkosten von ungefähr 15 Zyklen plus einem Zyklus für jede Iteration der Datenbewegung in Word/dword/qword.

Intel scheint hier nicht richtig zu sein. Aus dem obigen Zitat geht hervor, dass REP MOVSW für sehr große Speicherblöcke genauso schnell ist wie REP MOVSD/MOVSQ. Tests haben jedoch gezeigt, dass nur REP MOVSD/MOVSQ schnell sind, während REP MOVSW auf Nehalem und Westmere sogar langsamer ist als REP MOVSB .

Nach Angaben von Intel im Handbuch sind die Startkosten bei früheren Intel-Mikroarchitekturen (vor 2008) noch höher.

Fazit: Wenn Sie nur Daten kopieren müssen, die in den L1-Cache passen, sind nur 4 Zyklen zum Kopieren von 64 Byte Daten exzellent, und Sie müssen keine XMM-Register verwenden!

REP MOVSD/MOVSQ ist die universelle Lösung, die auf allen Intel-Prozessoren hervorragend funktioniert (kein ERMSB erforderlich), wenn die Daten in den L1-Cache passen

Hier sind die Tests von REP MOVS *, bei denen sich die Quelle und das Ziel im L1-Cache befanden. Dabei handelt es sich um Blöcke, die groß genug sind, um nicht ernsthaft von den Startkosten betroffen zu sein, aber nicht so groß sind, dass sie die L1-Cache-Größe überschreiten. Quelle: http://users.atw.hu/instlatx64/

Yonah (2006-2008)

    REP MOVSB 10.91 B/c
    REP MOVSW 10.85 B/c
    REP MOVSD 11.05 B/c

Nehalem (2009-2010)

    REP MOVSB 25.32 B/c
    REP MOVSW 19.72 B/c
    REP MOVSD 27.56 B/c
    REP MOVSQ 27.54 B/c

Westmere (2010-2011)

    REP MOVSB 21.14 B/c
    REP MOVSW 19.11 B/c
    REP MOVSD 24.27 B/c

Ivy Bridge (2012-2013) - mit erweitertem REP MOVSB

    REP MOVSB 28.72 B/c
    REP MOVSW 19.40 B/c
    REP MOVSD 27.96 B/c
    REP MOVSQ 27.89 B/c

SkyLake (2015-2016) - mit erweitertem REP MOVSB

    REP MOVSB 57.59 B/c
    REP MOVSW 58.20 B/c
    REP MOVSD 58.10 B/c
    REP MOVSQ 57.59 B/c

Kaby Lake (2016-2017) - mit erweitertem REP MOVSB

    REP MOVSB 58.00 B/c
    REP MOVSW 57.69 B/c
    REP MOVSD 58.00 B/c
    REP MOVSQ 57.89 B/c

Wie Sie sehen, unterscheidet sich die Implementierung von REP MOVS erheblich von einer Mikroarchitektur zur anderen. Auf einigen Prozessoren, wie Ivy Bridge, ist REP MOVSB ​​am schnellsten, wenn auch nur geringfügig schneller als REP MOVSD/MOVSQ, aber zweifellos funktioniert REP MOVSD/MOVSQ auf allen Prozessoren seit Nehalem sehr gut - Sie brauchen nicht einmal "Enhanced REP" MOVSB ​​", da REP MOVSD auf Ivy Bridge (2013) mit Enhacnced REP MOVSB ​​ die gleichen Daten pro Byte anzeigt wie auf Nehalem (2010) ohne Verbessertes REP MOVSB ​​, während REP MOVSB ​​erst seit SkyLake (2015) sehr schnell wurde - doppelt so schnell wie auf Ivy Bridge. Also kann dieses verbesserte REP MOVSB ​​ Bit in der CPUID verwirrend sein - es zeigt nur, dass REP MOVSB an sich ist OK, aber nicht, dass REP MOVS* ist schneller.

Die verwirrendste ERMBSB-Implementierung befindet sich in der Ivy Bridge-Mikroarchitektur. Ja, auf sehr alten Prozessoren verwendete REP MOVS * für große Blöcke vor ERMSB eine Cache-Protokollfunktion, die für normalen Code nicht verfügbar war (kein RFO). Dieses Protokoll wird jedoch auf Ivy Bridge mit ERMSB nicht mehr verwendet. Laut Andy Glews Kommentar zu einer Antwort auf "Warum ist Memcpy/Memset kompliziert überlegen?" In einer Antwort von Peter Cordes wurde eine Cache-Protokoll-Funktion, die für normalen Code nicht verfügbar ist, auf älteren Prozessoren verwendet. aber nicht mehr auf der Ivy Bridge. Und es gibt eine Erklärung dafür, warum die Anlaufkosten für REP MOVS * so hoch sind: „Der große Aufwand für die Auswahl und Einrichtung der richtigen Methode ist hauptsächlich auf das Fehlen einer Mikrocode-Verzweigungsvorhersage zurückzuführen.“ Es gab auch einen interessanten Hinweis, dass Pentium Pro (P6) 1996 REP MOVS * mit 64-Bit-Mikrocode-Lade- und -Speicherfunktionen und einem No-RFO-Cache-Protokoll implementierte - im Gegensatz zu ERMSB in Ivy Bridge wurde die Speicherreihenfolge nicht verletzt.

Haftungsausschluss

  1. Diese Antwort ist nur für die Fälle relevant, in denen die Quell- und Zieldaten in den L1-Cache passen. Abhängig von den Umständen sollten die Besonderheiten des Speicherzugriffs (Cache usw.) berücksichtigt werden. Prefetch und NTI können in bestimmten Fällen bessere Ergebnisse liefern, insbesondere bei Prozessoren, die noch nicht über Enhanced REP MOVSB ​​verfügen. Selbst auf diesen älteren Prozessoren hat REP MOVSD möglicherweise eine Cache-Protokollfunktion verwendet, die für normalen Code nicht verfügbar ist.
  2. Die Informationen in dieser Antwort beziehen sich nur auf Intel-Prozessoren und nicht auf Prozessoren anderer Hersteller wie AMD, die möglicherweise die REP MOVS * -Anweisungen besser oder schlechter implementieren.
  3. Ich habe die Testergebnisse für SkyLake und Kaby Lake nur zur Bestätigung vorgelegt - diese Architekturen haben dieselben Zyklusdaten pro Anweisung.
  4. Alle Produktnamen, Marken und eingetragenen Marken sind Eigentum ihrer jeweiligen Inhaber.
10
Maxim Masiutin

Sie sagen, dass Sie wollen:

eine Antwort, die zeigt, wann ERMSB nützlich ist

Aber ich bin mir nicht sicher, ob es das bedeutet, was Sie denken. In den 3.7.6.1-Dokumenten, auf die Sie verweisen, heißt es explizit:

je nach Länge und Ausrichtungsfaktoren erreicht die Implementierung von memcpy mit ERMSB möglicherweise nicht das gleiche Durchsatzniveau wie die Verwendung von 256-Bit- oder 128-Bit-AVX-Alternativen.

Nur weil CPUID die Unterstützung für ERMSB anzeigt, ist dies keine Garantie dafür, dass REP MOVSB ​​der schnellste Weg zum Kopieren von Speicher ist. Es bedeutet nur, dass es nicht so schlecht ist wie bei einigen früheren CPUs.

Nur weil es Alternativen gibt, die unter bestimmten Umständen schneller laufen können, bedeutet dies nicht, dass REP MOVSB ​​unbrauchbar ist. Jetzt, da die Performance-Einbußen, die diese Anweisung früher verursachte, weg sind, ist sie möglicherweise wieder eine nützliche Anweisung.

Denken Sie daran, es ist ein winziges Stück Code (2 Byte!) Im Vergleich zu einigen der komplizierteren memcpy-Routinen, die ich gesehen habe. Da das Laden und Ausführen großer Codestücke ebenfalls mit einem Nachteil verbunden ist (das Auswerfen eines Teils Ihres anderen Codes aus dem Cache des Prozessors), wird der „Vorteil“ von AVX et al. Manchmal durch die Auswirkungen auf den Rest Ihres Codes ausgeglichen Code. Kommt darauf an, was du tust.

Sie fragen auch:

Warum ist die Bandbreite bei REP MOVSB ​​so viel geringer? Was kann ich tun, um es zu verbessern?

Es wird nicht möglich sein, "etwas zu tun", um REP MOVSB ​​schneller laufen zu lassen. Es macht was es macht.

Wenn Sie die höheren Geschwindigkeiten von memcpy wünschen, können Sie die Quelle dafür ausgraben. Es ist irgendwo da draußen. Oder Sie können von einem Debugger aus darauf zugreifen und sehen, welche Codepfade tatsächlich verwendet werden. Ich gehe davon aus, dass es einige dieser AVX-Anweisungen verwendet, um mit 128 oder 256 Bit gleichzeitig zu arbeiten.

Oder Sie können einfach ... Nun, Sie haben uns gebeten, es nicht zu sagen.

7
David Wohlferd

Dies ist keine Antwort auf die angegebene (n) Frage (n), sondern nur meine Ergebnisse (und persönlichen Schlussfolgerungen), wenn ich versuche, dies herauszufinden.

Zusammenfassend: GCC optimiert bereits memset()/memmove()/memcpy() (siehe zB gcc/config/i386/i386.c: expand_set_or_movmem_via_rep () in den GCC-Quellen; suchen Sie auch nach stringop_algs in derselben Datei, um architekturabhängige Varianten zu sehen). Es gibt also keinen Grund, massive Gewinne zu erwarten, wenn Sie Ihre eigene Variante mit GCC verwenden (es sei denn, Sie haben wichtige Dinge wie Ausrichtungsattribute für Ihre ausgerichteten Daten vergessen oder aktivieren keine ausreichend spezifischen Optimierungen wie -O2 -march= -mtune=). Wenn Sie damit einverstanden sind, sind die Antworten auf die gestellte Frage in der Praxis mehr oder weniger irrelevant.

(Ich wünschte nur, es gäbe eine memrepeat(), das Gegenteil von memcpy() im Vergleich zu memmove(), die den anfänglichen Teil eines Puffers wiederholen würde, um den gesamten Puffer zu füllen. )


Ich habe derzeit eine Ivy Bridge-Maschine im Einsatz (Core i5-6200U-Laptop, Linux 4.4.0 x86-64-Kernel, mit erms in /proc/cpuinfo - Flags). Da ich herausfinden wollte, ob ich einen Fall finden kann, in dem eine benutzerdefinierte memcpy () - Variante, die auf rep movsb Basiert, eine einfache memcpy() übertrifft, habe ich einen übermäßig komplizierten Benchmark geschrieben.

Die Grundidee ist, dass das Hauptprogramm drei große Speicherbereiche zuweist: original, current und correct, die jeweils exakt gleich groß und mindestens seitenausgerichtet sind. Die Kopiervorgänge werden in Gruppen zusammengefasst, wobei jede Gruppe unterschiedliche Eigenschaften aufweist, z. B. dass alle Quellen und Ziele ausgerichtet sind (auf eine bestimmte Anzahl von Bytes) oder dass sich alle Längen innerhalb des gleichen Bereichs befinden. Jede Menge wird mit einem Array von src, dst, n Triplets beschrieben, wobei alle src zu src+n-1 Und dst bis dst+n-1 befinden sich vollständig im Bereich current.

Ein Xorshift * PRNG wird verwendet, um original für zufällige Daten zu initialisieren. (Wie ich oben gewarnt habe, ist dies zu kompliziert, aber ich wollte sicherstellen Ich überlasse dem Compiler keine einfachen Verknüpfungen.) Der Bereich correct wird erhalten, indem mit original Daten in current begonnen wird und alle Drillinge in der aktuellen Menge angewendet werden. Verwenden von memcpy(), das von der C-Bibliothek bereitgestellt wird, und Kopieren des Bereichs current nach correct. Auf diese Weise kann überprüft werden, ob sich jede Benchmark-Funktion richtig verhält.

Jeder Satz von Kopiervorgängen wird mit derselben Funktion häufig zeitgesteuert, und der Median dieser Vorgänge wird zum Vergleich herangezogen. (Meiner Meinung nach ist Median beim Benchmarking am sinnvollsten und bietet eine sinnvolle Semantik - die Funktion ist mindestens die Hälfte der Zeit so schnell.)

Um Compiler-Optimierungen zu vermeiden, muss das Programm die Funktionen und Benchmarks zur Laufzeit dynamisch laden. Die Funktionen haben alle die gleiche Form, void function(void *, const void *, size_t) - Beachten Sie, dass sie im Gegensatz zu memcpy() und memmove() nichts zurückgeben. Die Benchmarks (benannte Mengen von Kopiervorgängen) werden dynamisch durch einen Funktionsaufruf generiert (der unter anderem den Zeiger auf den Bereich current und seine Größe als Parameter verwendet).

Leider habe ich noch keinen Satz gefunden wo

static void rep_movsb(void *dst, const void *src, size_t n)
{
    __asm__ __volatile__ ( "rep movsb\n\t"
                         : "+D" (dst), "+S" (src), "+c" (n)
                         :
                         : "memory" );
}

würde schlagen

static void normal_memcpy(void *dst, const void *src, size_t n)
{
    memcpy(dst, src, n);
}

unter Verwendung von gcc -Wall -O2 -march=ivybridge -mtune=ivybridge unter Verwendung von GCC 5.4.0 auf dem oben genannten Core i5-6200U-Laptop, auf dem ein Linux-4.4.0-64-Bit-Kernel ausgeführt wird. Das Kopieren von Blöcken mit einer Größe von 4096 Byte und einer Ausrichtung von 4096 Byte kommt dem jedoch sehr nahe.

Dies bedeutet, dass ich zumindest bisher keinen Fall gefunden habe, in dem die Verwendung einer rep movsb - Memcpy-Variante sinnvoll wäre. Dies bedeutet nicht, dass es keinen solchen Fall gibt. Ich habe einfach keinen gefunden.

(An dieser Stelle ist der Code ein Spaghetti-Durcheinander, auf das ich eher schäme als stolz bin. Daher werde ich die Veröffentlichung der Quellen unterlassen, sofern nicht jemand danach fragt. Die obige Beschreibung sollte jedoch ausreichen, um eine bessere zu schreiben.)


Das wundert mich allerdings nicht sehr. Der C-Compiler kann viele Informationen über die Ausrichtung der Operandenzeiger ableiten und feststellen, ob die Anzahl der zu kopierenden Bytes eine Konstante für die Kompilierungszeit ist, ein Vielfaches einer geeigneten Zweierpotenz. Diese Informationen können und sollen vom Compiler verwendet werden, um die Funktionen der C-Bibliothek memcpy()/memmove() durch eigene zu ersetzen.

GCC tut genau dies (siehe zB gcc/config/i386/i386.c: expand_set_or_movmem_via_rep () in den GCC-Quellen; suchen Sie auch nach stringop_algs In derselben Datei, um architekturabhängig zu sehen Varianten). Tatsächlich wurde memcpy()/memset()/memmove() bereits für einige x86-Prozessormodelle separat optimiert. es würde mich sehr überraschen, wenn die gcc-entwickler nicht bereits erms-support aufgenommen hätten.

GCC bietet mehrere Funktionsattribute , mit denen Entwickler einen gut generierten Code sicherstellen können. Beispielsweise teilt alloc_align (n) GCC mit, dass die Funktion Speicher zurückgibt, der auf mindestens n Bytes ausgerichtet ist. Eine Anwendung oder Bibliothek kann auswählen, welche Implementierung einer Funktion zur Laufzeit verwendet werden soll, indem sie eine "Resolver-Funktion" erstellt (die einen Funktionszeiger zurückgibt) und die Funktion mit dem Attribut ifunc (resolver) definiert.

Eines der häufigsten Muster, das ich in meinem Code verwende, ist

some_type *pointer = __builtin_assume_aligned(ptr, alignment);

wobei ptr ein Zeiger ist, alignment die Anzahl der Bytes ist, auf die ausgerichtet wird; GCC weiß/geht dann davon aus, dass pointer an alignment Bytes ausgerichtet ist.

Ein weiteres nützliches eingebautes Element ist __builtin_prefetch() , obwohl es viel schwieriger ist, es korrekt zu verwenden . Um die gesamte Bandbreite/Effizienz zu maximieren, habe ich festgestellt, dass das Minimieren der Latenzen in jeder Unteroperation die besten Ergebnisse liefert. (Beim Kopieren von verstreuten Elementen in aufeinanderfolgende Zwischenspeicher ist dies schwierig, da das Vorabrufen normalerweise eine vollständige Cache-Zeile umfasst. Wenn zu viele Elemente vorab abgerufen werden, wird der größte Teil des Caches durch das Speichern nicht verwendeter Elemente verschwendet.)

6
Nominal Animal

Es gibt weitaus effizientere Möglichkeiten zum Verschieben von Daten. In diesen Tagen generiert die Implementierung von memcpy architekturspezifischen Code aus dem Compiler, der basierend auf der Speicherausrichtung der Daten und anderen Faktoren optimiert wird. Dies ermöglicht eine bessere Verwendung von nicht temporären Cache-Anweisungen und XMM- und anderen Registern in der x86-Welt.

Wenn Sie rep movsb verhindert diese Verwendung von Intrinsics.

Daher für etwas wie memcpy, es sei denn, Sie schreiben etwas, das an ein bestimmtes Hardwareteil gebunden ist, und Sie nehmen sich die Zeit, eine hochoptimierte memcpy -Funktion zu schreiben In Assembly (oder mit C Level Intrinsics) sind Sie weit davon entfernt, es dem Compiler zu ermöglichen, es für Sie herauszufinden.

3
David Hoelzer

Als allgemeine memcpy() Anleitung:

a) Wenn die zu kopierenden Daten winzig sind (weniger als 20 Byte) und eine feste Größe haben, lassen Sie den Compiler dies tun. Grund: Der Compiler kann normale mov Anweisungen verwenden und die Systemstart-Overheads vermeiden.

b) Wenn die zu kopierenden Daten klein sind (weniger als etwa 4 KiB) und die Ausrichtung garantiert ist, verwenden Sie rep movsb (falls ERMSB unterstützt wird) oder rep movsd (wenn ERMSB nicht unterstützt wird). Grund: Die Verwendung einer SSE oder AVX-Alternative hat einen enormen "Start-Overhead", bevor etwas kopiert wird.

c) Wenn die zu kopierenden Daten klein sind (weniger als etwa 4 KiB) und die Ausrichtung nicht garantiert ist, verwenden Sie rep movsb. Grund: Mit SSE oder AVX, oder mit rep movsd für den Großteil plus einige rep movsb am Anfang oder Ende hat zu viel Aufwand.

d) Verwenden Sie für alle anderen Fälle Folgendes:

    mov edx,0
.again:
    pushad
.nextByte:
    pushad
    popad
    mov al,[esi]
    pushad
    popad
    mov [edi],al
    pushad
    popad
    inc esi
    pushad
    popad
    inc edi
    pushad
    popad
    loop .nextByte
    popad
    inc edx
    cmp edx,1000
    jb .again

Grund: Dies wird so langsam sein, dass Programmierer gezwungen sind, eine Alternative zu finden, bei der keine großen Datenmengen kopiert werden müssen. und die resultierende Software wird bedeutend schneller sein, da das Kopieren großer Datenmengen vermieden wurde.

1
Brendan