Ich hatte kürzlich eine Interviewfrage, wo ich memcpy implementieren musste. Ich habe memcpy reichlich in meiner Erfahrung verwendet, also schien es kein schwieriges Problem.
Also habe ich angefangen, eine Schleife zu implementieren, um eine Adresse von Zeiger zu Zeiger zu kopieren, etwa so:
%Vor%Die Interviewer unterbrachen jedoch die Notiz, dass die Manpage für memcpy "n Bytes von src nach dest kopieren" (was ich später bestätigte) und dann verlangte, dass ich stattdessen nach size / 4 iterierte und dann den Rest mit einem anderen aufnahm Schleife des Index & lt; Größe% 4 (Ich nehme an, es handelt sich um ein 32-Bit-System?)
Nun, das schien merkwürdig zu sein, da ich Memcpy jahrelang problemlos benutzt habe, ohne ihm einen * 4 Modifier geben zu müssen. Als ich nach Hause kam, startete ich gdb und kopierte eine kleine Zeichenfolge "Hallo" und war vorsichtig, die Größe sowohl mit strlen () und Konstanten einzugeben, um zu sehen, wo es beginnt und stoppt.
%Vor%Nun untersuchte ich src und dest mit gdb, die beide "Hallo \ 0" enthielten.
Meine Frage ist also: Was verstehe ich nicht, wenn ich die Zahl 4 (oder "Größe in Bytes") verwende? Und warum sagt die Dokumentation "n Bytes", wenn das nicht wirklich das Verhalten ist? Was sehe ich hier nicht klar?
Sie haben Sie gebeten, Ihre Implementierung zu optimieren und ein 32-Bit-Wort gleichzeitig innerhalb der Schleife gegen ein Byte kopieren zu lassen. Dies würde einige sorgfältige Überprüfung erfordern, um die Grenzfälle zu behandeln, wie zum Beispiel size ist kein Vielfaches von 4 oder dest oder src wird nicht auf einer 4-Byte-Grenze ausgerichtet.
Wie andere bereits gesagt haben, ist das Kopieren von 4 Bytes gleichzeitig schneller als das Kopieren von 1 Byte zu einem Zeitpunkt. Der Interviewer wollte, dass Sie so etwas tun:
%Vor%Die Logik für Ihr Memcpy ist korrekt und Ihr Interviewer hat Sie nicht gebeten, es zu ändern oder eine Einschränkung hinzuzufügen. Das Kopieren von 4 Bytes gleichzeitig ist zwar schneller, wird jedoch zu einem Problem, wenn Ihre Größe kein Vielfaches von 4 ist. Ihr Interviewer hat Ihnen also zwei Schleifen gegeben: die erste Kopie 4 Bytes gleichzeitig und die zweite Schleife ein Byte bei a Zeit (es wird maximal 3 mal durchlaufen).
Der Großteil der Kopie wird also mit der schnellen 4-Byte-Kopie erstellt, aber Sie sind nicht darauf beschränkt, dass die Größe ein Vielfaches von 4 ist, da die 2. "Bereinigungsschleife" alles kopiert, was nicht ein Vielfaches von 4 ist / p>
1. Schleife: Kopieren Sie uint32_t und erhöhen Sie um 4
2. Schleife: Kopieren Sie uint8_t und erhöhen Sie um 1
Der Interviewer hat Ihr Wissen über die Computerarchitektur getestet und wollte, dass Sie Ihren Algorithmus optimieren. Der Speicher arbeitet mit Wörtern statt mit Bytes. In einem 32-Bit-System ist ein Wort typischerweise 4 Bytes, es benötigt die gleiche Zeit zum Lesen / Schreiben von 1 Byte, wie es zum Lesen / Schreiben von 1 Wort tut. Die zweite Schleife soll den Fall behandeln, in dem die Anzahl der Bytes, die Sie kopieren möchten, nicht genau durch 4 Bytes teilbar ist.
Was du eigentlich willst, sind 3 Loops. 2 Schleifen für die Bytes nach dem Ziel und vor dem Ziel + Größe, die, wenn nicht Wort ausgerichtet ist. Dann noch eine Schleife für alle dazwischen liegenden Wörter.
Sie können sogar noch mehr optimieren, indem Sie architekturspezifische Anweisungen nutzen. Sehen Sie sich diesen Artikel an, wenn Sie interessiert sind: Ссылка
Die Interviewer haben Sie gebeten, aus dem einen oder anderen Grund eine vorzeitige Optimierung vorzunehmen. Dies ist normalerweise eine schlechte Idee.
Es ist richtig, dass ein 32-Bit-Rechner einen 32-Bit-Chuck schneller kopiert als 4x1-Bytes kopiert. Aber es gibt mehr zur Optimierung als das.
Es besteht die große Chance, dass ein 32-Bit-Rechner Ihre Daten in den Cache-Speicher legt, und dann ist der schnelle Speicherzugriff möglicherweise weitaus relevanter als CPU-Anweisungen. Cache-Speicher können verschiedene Ausrichtungsanforderungen haben. Sie bevorzugen möglicherweise eine einfache Schleife, oder sie bevorzugen 32-Bit ausgerichtete Chunks. Ich bin kein Experte auf diesem Gebiet, deshalb vermeide ich vorzeitige Optimierung und überlasse es dem Compiler, der hoffentlich mehr über Cache-Speicher weiß als ich.
Dann gibt es eine CPU-Verzweigungsvorhersage und eine Befehlsleitung. Dieser spezielle Code ist ziemlich deterministisch, daher ist dies möglicherweise kein Problem. Aber als Faustregel gilt: Einfacher Code liefert eine effektivere Verzweigungsvorhersage als komplexer Code.
Außerdem gibt es eine Aufteilung, die bei vielen CPU-Architekturen langsam ist. Abhängig von der zu kopierenden Datenmenge können die Divisionen dazu führen, dass das Memcpy wesentlich langsamer ist.
Um es zusammenzufassen: Die manuelle Optimierung ist ziemlich komplex und erfordert ein gründliches Wissen über die CPU und die Hardware. Sie können und sollten nicht "für eine 32-Bit-CPU optimieren", Sie müssen die Besonderheiten kennen. In den meisten Fällen wird der Compiler den Code viel effektiver optimieren als Sie. Die Bibliothek memcpy () wird oft in Inline-Assembler geschrieben, optimiert für das spezifische Ziel.