Wie funktionieren realloc und memcpy?

Ich habe zwei Fragen.

1. Tun realloc() und memcpy() Kopieren Sie die Einträge in einem Array schneller in ein anderes, als nur über jedes Element zu iterieren O(N) ? Wenn die Antwort ja lautet, was denken Sie, ist die Komplexität?

2. Wenn die zugewiesene Größe kleiner als die Originalgröße ist, tut dies realloc() Kopieren Sie die Einträge an einen anderen Ort oder lassen Sie sie einfach, da sie die Größe des Arrays verringern?

Schauen wir uns das etwas genauer an memcpy und wo wir gerade dabei sind, bei “big O” oder Landau-Notation.

Zuerst, großes O. Wie ich bereits an anderer Stelle erwähnt habe, lohnt es sich, sich an die Definition des großen O zu erinnern, nämlich dass es eine Funktion gibt g(n) wird gesagt, dass O(f(n)) wenn es eine Konstante gibt k wofür g(n) ≤ kf(n). Die Konstante lässt Sie die kleinen Details zugunsten des wichtigen Teils ignorieren. Wie alle bemerkt haben, memcpy von n Bytes werden An) in fast jeder normalen architektur, denn egal was man zu bewegen hat n Bytes, ein Stück nach dem anderen. Also eine erste, naive Implementierung von memcpy in C geschrieben werden könnte

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

Dies ist in der Tat An), und vielleicht fragen Sie sich, warum wir uns überhaupt mit einer Bibliotheksroutine beschäftigen. aber die Sache mit dem libc Funktionen ist, dass sie der Ort sind, an dem plattformspezifische Dienstprogramme geschrieben werden; Wenn Sie die Architektur optimieren möchten, ist dies einer der Orte, an denen Sie dies tun können. So, je nach Architektur, gibt es möglicherweise effizientere Implementierungsoptionen; Beispielsweise gibt es in der IBM 360-Architektur a MOVL Anweisung, die Daten verschiebt, besteht aus großen Blöcken, die einen sehr hochoptimierten Mikrocode verwenden. Anstelle dieser Schleife könnte eine 360-Grad-Implementierung von memcpy stattdessen so aussehen

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(Übrigens keine Garantie dafür, dass es genau der richtige 360-Code ist, aber er dient zur Veranschaulichung.) Diese Implementierung sieht aus mögen statt tun n Schritte um die Schleife herum, wie es der C-Code getan hat, es führt nur 3 Anweisungen aus.

Was Ja wirklich passiert, aber ist, dass es ausgeführt wird O(n) Mikro Anleitung unter der Decke. Was ist anders zwischen beiden ist die Konstante k; weil der Mikrocode viel schneller ist und weil die Anweisungen nur drei Decodierungsschritte enthalten, ist er es dramatisch schneller als die naive Version, aber es ist immer noch An) — es ist nur die Konstante kleiner.

Und genau das können Sie gut gebrauchen memcpy — es ist nicht asymptotisch schneller, aber die Implementierung ist so schnell, wie es jemand machen könnte auf dieser besonderen Architektur.

1 – Nein. Sie kopieren jeweils einen Block. Sehen http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed für eine ziemlich gute Analyse.

2 – Dies ist implementierungsabhängig. Sehen http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html für glibc-Details. “In mehreren Zuweisungsimplementierungen erfordert das Verkleinern eines Blocks manchmal das Kopieren.”

1. Es gibt absolut keine Möglichkeit, N Elemente schneller als O(N) zu kopieren. Es kann jedoch möglicherweise mehrere Elemente gleichzeitig kopieren oder spezielle Prozessoranweisungen verwenden – es ist also möglicherweise immer noch schneller, als Sie es selbst tun könnten.
2. Ich weiß es nicht genau, aber ich würde davon ausgehen, dass der Speicher vollständig neu zugewiesen wird. Das ist die sicherste Annahme und wahrscheinlich sowieso von der Implementierung abhängig.

1. Die Leistung von memcpy kann nicht wirklich besser als O(N) sein, aber es kann so optimiert werden, dass es das manuelle Kopieren übertrifft; Beispielsweise kann es 4 Bytes in der Zeit kopieren, die Sie zum Kopieren von 1 Byte benötigen. Viele memcpy Implementierungen werden in Assembler mit optimierten Anweisungen geschrieben, die mehrere Elemente gleichzeitig kopieren können, was normalerweise schneller ist als das Kopieren von Daten byteweise.

2. Ich verstehe diese Frage nicht ganz, wenn Sie verwenden realloc um die Größe des Speichers zu verringern und es erfolgreich ist (gibt nicht-NULL zurück), enthält der neue Speicherort die gleichen Daten wie der alte Speicherort bis zur Größe der neuen Anforderung. Wenn durch den Anruf der Speicherplatz geändert wurde realloc (nicht üblich beim Verkleinern) Der Inhalt wird kopiert, ansonsten muss nicht kopiert werden, da der Speicher nicht verschoben wurde.

1. Es kann vermutet werden, dass memcpy so geschrieben werden könnte, dass es eine große Anzahl von Bits umherbewegen würde. zB Es ist durchaus möglich, die Daten mit SSE-Anweisungen zu kopieren, wenn es vorteilhaft ist.

Wie bereits erwähnt, ist es nicht schneller als O (n), aber Speichersysteme haben häufig eine bevorzugte Blockgröße, und es ist auch möglich, beispielsweise die Größe einer Cache-Zeile auf einmal zu schreiben.

Angenommen, Sie sprechen über glibc, und da Ihre Fragen von der Implementierung abhängig sind, ist es wahrscheinlich am besten, nur die Quelle zu überprüfen:

malloc.c

memcpy.c

So wie ich es gelesen habe, wären die Antworten:

1. O(N) — Es gibt keine Möglichkeit, Elemente in besserer als linearer Zeit zu kopieren.
2. Gelegentlich werden große Elemente kopiert, wenn realloc() verwendet wird, um sie zu verkleinern.

Der x86 hat spezielle Anweisungen zum Scannen und Abgleichen eines Bytes/Wortes in einem Speicherblock sowie eine, die zum Kopieren eines Speicherblocks verwendet werden kann (es ist immerhin eine CISC-CPU). Viele C-Compiler, die die Inline-Assemblersprache und ein Pragma zum Inlining ganzer Funktionen implementieren, nutzen dies seit vielen Jahren in ihren Bibliotheksfunktionen.

Die für die Speicherkopie verwendeten sind movsb/movsw in Kombination mit der rep-Anweisung.

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

Setup-Register mit src/trg-Adressen und int-Anzahl und los geht’s.