Warum sind memcpy () und memmove () schneller als Zeigerinkremente?

Ich kopiere N Bytes von pSrcnach pDest. Dies kann in einer einzigen Schleife erfolgen:

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Warum ist das langsamer als memcpyoder memmove? Welche Tricks verwenden sie, um es zu beschleunigen?

Da memcpy Wortzeiger anstelle von Bytezeigern verwendet, werden auch die memcpy-Implementierungen häufig mit SIMD- Anweisungen geschrieben, wodurch 128 Bit gleichzeitig gemischt werden können.

SIMD-Anweisungen sind Montageanweisungen, die dieselbe Operation für jedes Element in einem bis zu 16 Byte langen Vektor ausführen können. Dazu gehören Anweisungen zum Laden und Speichern.

Speicherkopierroutinen können weitaus komplizierter und schneller sein als eine einfache Speicherkopie über Zeiger wie:

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

Verbesserungen

Die erste Verbesserung, die man vornehmen kann, besteht darin, einen der Zeiger an einer Wortgrenze auszurichten (mit Wort meine ich native Ganzzahlgröße, normalerweise 32 Bit / 4 Byte, kann aber bei neueren Architekturen 64 Bit / 8 Byte betragen) und eine Bewegung in Wortgröße verwenden Anweisungen kopieren. Dies erfordert die Verwendung einer Byte-zu-Byte-Kopie, bis ein Zeiger ausgerichtet ist.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

Unterschiedliche Architekturen funktionieren unterschiedlich, je nachdem, ob der Quell- oder der Zielzeiger entsprechend ausgerichtet sind. Zum Beispiel auf einem XScale-Prozessor habe ich eine bessere Leistung erzielt, indem ich den Zielzeiger anstelle des Quellzeigers ausgerichtet habe.

Um die Leistung weiter zu verbessern, kann ein gewisses Abrollen der Schleife durchgeführt werden, so dass mehr Register des Prozessors mit Daten geladen werden. Dies bedeutet, dass die Lade- / Speicherbefehle verschachtelt werden können und ihre Latenz durch zusätzliche Anweisungen (wie Schleifenzählen usw.) verborgen bleibt. Der damit verbundene Vorteil variiert je nach Prozessor erheblich, da die Latenzen für Lade- / Speicherbefehle sehr unterschiedlich sein können.

Zu diesem Zeitpunkt wird der Code eher in Assembly als in C (oder C ++) geschrieben, da Sie die Lade- und Speicheranweisungen manuell platzieren müssen, um den maximalen Nutzen aus dem Ausblenden und dem Durchsatz der Latenz zu ziehen.

Im Allgemeinen sollte eine ganze Cache-Datenzeile in einer Iteration der nicht gerollten Schleife kopiert werden.

Das bringt mich zur nächsten Verbesserung, indem ich Pre-Fetching hinzufüge. Dies sind spezielle Anweisungen, die das Cache-System des Prozessors anweisen, bestimmte Teile des Speichers in seinen Cache zu laden. Da es eine Verzögerung zwischen der Ausgabe der Anweisung und dem Füllen der Cache-Zeile gibt, müssen die Anweisungen so platziert werden, dass die Daten verfügbar sind, wenn sie gerade kopiert werden sollen, und nicht früher / später.

Dies bedeutet, dass Prefetch-Anweisungen sowohl zu Beginn der Funktion als auch innerhalb der Hauptkopierschleife eingefügt werden. Mit den Prefetch-Anweisungen in der Mitte der Kopierschleife werden Daten abgerufen, die in mehreren Iterationen kopiert werden.

Ich kann mich nicht erinnern, aber es kann auch nützlich sein, sowohl die Zieladressen als auch die Quelladressen vorab abzurufen.

Faktoren

Die Hauptfaktoren, die beeinflussen, wie schnell Speicher kopiert werden kann, sind:

• Die Latenz zwischen dem Prozessor, seinen Caches und dem Hauptspeicher.
• Die Größe und Struktur der Cache-Zeilen des Prozessors.
• Die Anweisungen zum Verschieben / Kopieren des Arbeitsspeichers des Prozessors (Latenz, Durchsatz, Registergröße usw.).

Wenn Sie also eine effiziente und schnelle Speicherroutine schreiben möchten, müssen Sie viel über den Prozessor und die Architektur wissen, für die Sie schreiben. Es genügt zu sagen, dass es viel einfacher ist, nur die integrierten Speicherkopierroutinen zu verwenden, wenn Sie nicht auf einer eingebetteten Plattform schreiben.

memcpykann je nach Computerarchitektur mehr als ein Byte gleichzeitig kopieren. Die meisten modernen Computer können mit 32 Bit oder mehr in einem einzelnen Prozessorbefehl arbeiten.

Aus einer Beispielimplementierung :

    00026 * Optimieren Sie für schnelles Kopieren den allgemeinen Fall, in dem beide Zeiger verwendet werden
    00027 * und die Länge sind wortausgerichtet und kopieren stattdessen wortweise
    00028 * Byte für Stück. Andernfalls kopieren Sie nach Bytes.

Sie können memcpy()eine der folgenden Techniken implementieren , von denen einige von Ihrer Architektur abhängen, um Leistungssteigerungen zu erzielen. Alle Techniken sind viel schneller als Ihr Code:

1. Verwenden Sie größere Einheiten, z. B. 32-Bit-Wörter anstelle von Bytes. Sie können (oder müssen) sich auch hier mit der Ausrichtung befassen. Sie können beispielsweise auf einigen Plattformen kein 32-Bit-Wort an einem ungeraden Speicherort lesen / schreiben, und auf anderen Plattformen zahlen Sie eine massive Leistungsstrafe. Um dies zu beheben, muss die Adresse eine durch 4 teilbare Einheit sein. Sie können diese für 64-Bit-CPUs bis zu 64 Bit oder höher verwenden, indem Sie SIMD- Anweisungen ( Einzelanweisung , mehrere Daten) ( MMX , SSE usw.) verwenden.

2. Sie können spezielle CPU-Anweisungen verwenden, die Ihr Compiler möglicherweise nicht aus C optimieren kann. Auf einem 80386 können Sie beispielsweise den Präfixbefehl "rep" + den Befehl "movsb" verwenden, um N Bytes zu verschieben, die durch Platzieren von N in der Zählung diktiert werden registrieren. Gute Compiler erledigen dies nur für Sie, aber Sie befinden sich möglicherweise auf einer Plattform, auf der ein guter Compiler fehlt. Beachten Sie, dass dieses Beispiel in der Regel eine schlechte Demonstration der Geschwindigkeit darstellt. In Kombination mit Anweisungen für Ausrichtung und größere Einheiten kann es jedoch schneller sein als fast alles andere auf bestimmten CPUs.

3. Abrollen von Schleifen - Zweige können auf einigen CPUs recht teuer sein, sodass das Abrollen der Schleifen die Anzahl der Zweige verringern kann. Dies ist auch eine gute Technik zum Kombinieren mit SIMD-Anweisungen und sehr großen Einheiten.

Zum Beispiel hat http://www.agner.org/optimize/#asmlib eine memcpyImplementierung, die die meisten übertrifft (um einen winzigen Betrag). Wenn Sie den Quellcode lesen, ist er voller Tonnen von Inline-Assembly-Code, der alle oben genannten drei Techniken abruft und anhand der CPU, auf der Sie ausgeführt werden, auswählt, welche dieser Techniken verwendet werden sollen.

Beachten Sie, dass es ähnliche Optimierungen gibt, die auch zum Auffinden von Bytes in einem Puffer vorgenommen werden können. strchr()und Freunde werden oft schneller als Ihr handgerolltes Äquivalent. Dies gilt insbesondere für .NET und Java . In .NET ist die integrierte ZeichenfolgeString.IndexOf() beispielsweise viel schneller als eine Boyer-Moore-Zeichenfolgensuche , da die oben genannten Optimierungstechniken verwendet werden.

Kurze Antwort:

• Cache füllen
• Wortgrößenübertragungen statt Byte-Übertragungen, wo dies möglich ist
• SIMD Magie

Ich weiß nicht, ob es tatsächlich in realen Implementierungen von verwendet wird memcpy, aber ich denke, Duffs Gerät verdient hier eine Erwähnung.

Aus Wikipedia :

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

Beachten Sie, dass memcpydies nicht der Fall ist, da der toZeiger absichtlich nicht erhöht wird . Es implementiert eine etwas andere Operation: das Schreiben in ein speicherabgebildetes Register. Weitere Informationen finden Sie im Wikipedia-Artikel.

Wie andere sagen, sind memcpy-Kopien größer als 1-Byte-Blöcke. Das Kopieren in wortgroßen Blöcken ist viel schneller. Die meisten Implementierungen gehen jedoch noch einen Schritt weiter und führen vor dem Schleifen mehrere MOV-Anweisungen (Wortanweisungen) aus. Der Vorteil des Kopierens in beispielsweise 8 Wortblöcken pro Schleife besteht darin, dass die Schleife selbst teuer ist. Diese Technik reduziert die Anzahl der bedingten Verzweigungen um den Faktor 8 und optimiert die Kopie für Riesenblöcke.

Die Antworten sind groß, aber wenn Sie noch einem schnelles wollen implementieren memcpyselbst, gibt es eine interessante Blog - Post über schnelle Memcpy, schnelle Memcpy in C .

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

Es kann sogar besser sein, die Speicherzugriffe zu optimieren.

Weil es wie viele Bibliotheksroutinen für die Architektur optimiert wurde, auf der Sie ausgeführt werden. Andere haben verschiedene Techniken veröffentlicht, die verwendet werden können.

Wenn Sie die Wahl haben, verwenden Sie Bibliotheksroutinen, anstatt Ihre eigenen zu rollen. Dies ist eine Variation von DRY, die ich DRO nenne (andere nicht wiederholen). Außerdem sind Bibliotheksroutinen weniger wahrscheinlich falsch als Ihre eigene Implementierung.

Ich habe Speicherzugriffsprüfer gesehen, die sich über außerhalb der Grenzen liegende Lesevorgänge in Speicher- oder Zeichenfolgenpuffern beschwerten, die nicht ein Vielfaches der Wortgröße waren. Dies ist ein Ergebnis der verwendeten Optimierung.

Sie können sich die MacOS-Implementierung von memset, memcpy und memmove ansehen.

Beim Booten bestimmt das Betriebssystem, auf welchem ​​Prozessor es ausgeführt wird. Es hat speziell optimierten Code für jeden unterstützten Prozessor eingebaut und speichert beim Booten einen jmp-Befehl im richtigen Code an einem festen schreibgeschützten Ort.

Die Implementierungen C memset, memcpy und memmove sind nur ein Sprung zu diesem festen Ort.

Die Implementierungen verwenden je nach Ausrichtung von Quelle und Ziel für memcpy und memmove unterschiedlichen Code. Sie nutzen offensichtlich alle verfügbaren Vektorfunktionen. Sie verwenden auch Nicht-Caching-Varianten, wenn Sie große Datenmengen kopieren, und verfügen über Anweisungen, um das Warten auf Seitentabellen zu minimieren. Es ist nicht nur Assembler-Code, sondern Assembler-Code, der von jemandem geschrieben wurde, der über äußerst gute Kenntnisse der einzelnen Prozessorarchitekturen verfügt.

Intel hat außerdem Assembler-Anweisungen hinzugefügt, die Zeichenfolgenoperationen beschleunigen können. Zum Beispiel mit einer Anweisung zur Unterstützung von strstr, die 256-Byte-Vergleiche in einem Zyklus durchführt.