Zurücksetzen des C int-Arrays auf Null: der schnellste Weg?
Lesezeit: 10 Minuten
Vinzenz
Angenommen wir haben a T myarray[100] mit T = int, unsigned int, long long int oder unsigned long long int, was ist der schnellste Weg, um den gesamten Inhalt auf Null zurückzusetzen (nicht nur zur Initialisierung, sondern um den Inhalt mehrmals in meinem Programm zurückzusetzen)? Vielleicht mit memset?
Dieselbe Frage für ein dynamisches Array wie T *myarray = new T[100].
@BoPersson: Nun, newist C++…
– Matteo Italien
5. Februar 2012 um 20:06 Uhr
@Matteo – na ja. Hat die Antworten nicht sehr beeinflusst (bis jetzt :-).
– Bo Persson
5. Februar 2012 um 20:12 Uhr
@BoPersson: Ich fühlte mich schlecht, wenn ich nur darüber redete memset wenn C++ irgendwie involviert ist … 🙂
– Matteo Italien
5. Februar 2012 um 20:15 Uhr
Auf einem modernen Compiler ist ein einfacher nicht zu übertreffen for Schleife. Aber überraschenderweise können Sie viel Schlimmeres erreichen, wenn Sie versuchen, schlau zu sein.
– David Schwartz
21. September 2015 um 8:58 Uhr
Verwenden Sie eine Struktur und stecken Sie ein Array hinein. Erstellen Sie eine Instanz, die nur aus Nullen besteht. Verwenden Sie dies, um andere, die Sie erstellen, auf Null zu setzen. Es funktioniert gut. Keine Includes, keine Funktionen, ziemlich schnell.
– Xofo
5. März 2019 um 8:24 Uhr
Matteo Italien
memset (aus <string.h>) ist wahrscheinlich der schnellste Standardweg, da es sich normalerweise um eine Routine handelt, die direkt in Assembler geschrieben und von Hand optimiert wird.
memset(myarray, 0, sizeof(myarray)); // for automatically-allocated arrays
memset(myarray, 0, N*sizeof(*myarray)); // for heap-allocated arrays, where N is the number of elements
Übrigens, in C++ wäre der idiomatische Weg zu verwenden std::fill (aus <algorithm>):
std::fill(myarray, myarray+N, 0);
die kann automatisch optimiert werden in a memset; Ich bin mir ziemlich sicher, dass es so schnell wie möglich funktionieren wird memset zum ints, während es bei kleineren Typen etwas schlechter abschneiden kann, wenn der Optimierer nicht schlau genug ist. Im Zweifelsfall aber Profil.
Ab dem ISO C-Standard von 1999 war dies nicht wirklich garantiert memset würde eine Ganzzahl auf 0 setzen; Es gab keine spezifische Aussage, dass All-Bits-Zero eine Darstellung von ist 0. Ein Technical Corrigendum fügte eine solche Garantie hinzu, die im ISO C-Standard 2011 enthalten ist. Ich glaube, dass alle Bits-Null ist eine gültige Darstellung von 0 für alle Integer-Typen in allen bestehenden C- und C++-Implementierungen, weshalb das Komitee diese Anforderung hinzufügen konnte. (Für Fließkomma- oder Zeigertypen gibt es keine ähnliche Garantie.)
– Keith Thompson
16. Juni 2013 um 0:17 Uhr
Ergänzung zum Kommentar von @KeithThompson: Diese Garantie wurde in TC2 (2004) im Klartext zu 6.2.6.2/5 hinzugefügt; Wenn es jedoch keine Füllbits gibt, haben 6.2.6.2/1 und /2 bereits garantiert, dass alle Bits Null waren 0. (Bei Füllbits besteht die Möglichkeit, dass alle Bits Null eine Trap-Darstellung sein könnten). Aber in jedem Fall soll der TC fehlerhaften Text anerkennen und ersetzen, also sollten wir ab 2004 so tun, als ob C99 diesen Text immer enthalten hätte.
– MM
29. Mai 2015 um 11:02 Uhr
In C, wenn Sie das dynamische Array zugewiesen haben korrekt, dann gibt es keinen Unterschied zwischen den beiden Memsets. Korrekte dynamische Zuordnung wäre int (*myarray)[N] = malloc(sizeof(*myarray));.
– Ludin
21. September 2015 um 9:04 Uhr
@Lundin: natürlich – wenn Sie zur Kompilierzeit wissen, wie groß N ist, aber in den allermeisten Fällen, wenn Sie verwendet werden malloc Sie wussten es nur zur Laufzeit.
– Matteo Italien
21. September 2015 um 9:12 Uhr
@MatteoItalia Wir haben VLAs seit dem Jahr 1999.
– Ludin
21. September 2015 um 9:15 Uhr
Benjamin
Obwohl diese Frage ziemlich alt ist, braucht sie einige Benchmarks, da sie nicht nach der idiomatischsten Art oder der Art und Weise fragt, die in der geringsten Anzahl von Zeilen geschrieben werden kann, sondern nach der am schnellsten Weg. Und es ist dumm, diese Frage ohne tatsächliche Tests zu beantworten. Also habe ich vier Lösungen verglichen, memset vs. std::fill vs. ZERO of AnTs Antwort vs. eine Lösung, die ich mit AVX-Intrinsics erstellt habe.
Beachten Sie, dass diese Lösung nicht generisch ist, sie funktioniert nur mit Daten von 32 oder 64 Bit. Bitte kommentieren Sie, wenn dieser Code etwas falsch macht.
#include<immintrin.h>
#define intrin_ZERO(a,n){\
size_t x = 0;\
const size_t inc = 32 / sizeof(*(a));/*size of 256 bit register over size of variable*/\
for (;x < n-inc;x+=inc)\
_mm256_storeu_ps((float *)((a)+x),_mm256_setzero_ps());\
if(4 == sizeof(*(a))){\
switch(n-x){\
case 3:\
(a)[x] = 0;x++;\
case 2:\
_mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
case 1:\
(a)[x] = 0;\
break;\
case 0:\
break;\
};\
}\
else if(8 == sizeof(*(a))){\
switch(n-x){\
case 7:\
(a)[x] = 0;x++;\
case 6:\
(a)[x] = 0;x++;\
case 5:\
(a)[x] = 0;x++;\
case 4:\
_mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
case 3:\
(a)[x] = 0;x++;\
case 2:\
((long long *)(a))[x] = 0;break;\
case 1:\
(a)[x] = 0;\
break;\
case 0:\
break;\
};\
}\
}
Ich werde nicht behaupten, dass dies die schnellste Methode ist, da ich kein Low-Level-Optimierungsexperte bin. Vielmehr ist es ein Beispiel für eine korrekte architekturabhängige Implementierung, die schneller als Memset ist.
Nun zu den Ergebnissen. Ich habe die Leistung für Arrays der Größe 100 int und long long berechnet, sowohl statisch als auch dynamisch zugewiesen, aber mit Ausnahme von msvc, das eine Eliminierung von totem Code bei statischen Arrays durchführte, waren die Ergebnisse äußerst vergleichbar, sodass ich nur die Leistung dynamischer Arrays zeigen werde. Zeitmarkierungen sind ms für 1 Million Iterationen, wobei die Uhrfunktion mit niedriger Genauigkeit von time.h verwendet wird.
int
memset: 196
fill: 613
ZERO: 221
intrin_ZERO: 95
long long:
memset: 273
fill: 559
ZERO: 376
intrin_ZERO: 188
Hier passiert eine Menge Interessantes: llvm tötet gcc, MSVCs typische fleckige Optimierungen (es führt eine beeindruckende Eliminierung von totem Code auf statischen Arrays durch und hat dann eine schreckliche Leistung zum Füllen). Obwohl meine Implementierung erheblich schneller ist, kann dies nur daran liegen, dass sie erkennt, dass das Löschen von Bits viel weniger Overhead hat als jede andere Setzoperation.
Die Implementierung von Clang verdient eine genauere Betrachtung, da sie erheblich schneller ist. Einige zusätzliche Tests zeigen, dass sein Memset tatsächlich auf Null spezialisiert ist – Nicht-Null-Memsets für 400-Byte-Arrays sind viel langsamer (~ 220 ms) und mit gcc vergleichbar. Die Mem-Einstellung ungleich Null mit einem 800-Byte-Array macht jedoch keinen Geschwindigkeitsunterschied, weshalb ihr Memset in diesem Fall wahrscheinlich eine schlechtere Leistung als meine Implementierung aufweist – die Spezialisierung gilt nur für kleine Arrays, und der Cuttoff liegt genau bei 800 Byte. Beachten Sie auch, dass gcc ‘fill’ und ‘ZERO’ nicht für Memset optimiert werden (mit Blick auf generierten Code), gcc generiert einfach Code mit identischen Leistungsmerkmalen.
Fazit: memset ist für diese Aufgabe nicht so optimiert, wie es die Leute vorgeben würden (andernfalls hätten gcc und msvc und llvms memset die gleiche Leistung). Wenn es auf die Leistung ankommt, sollte Memset keine endgültige Lösung sein, insbesondere für diese umständlichen Arrays mittlerer Größe, da es nicht auf das Löschen von Bits spezialisiert ist und nicht besser von Hand optimiert ist, als es der Compiler alleine tun könnte.
Ein Benchmark ohne Code und ohne Nennung der Compiler-Version und der verwendeten Optionen? Hmm…
– Marc Glisse
21. September 2015 um 20:57 Uhr
Ich hatte bereits die Compiler-Versionen (sie waren nur ein wenig versteckt) und nur die entsprechenden Optionen verwendet.
– Benjamin
22. September 2015 um 22:31 Uhr
Ungültiges Typargument von unärem ‘*’ (hat ‘size_t {aka unsigned int}’)|
– Piotr Wasilewicz
25. Juni 2017 um 8:08 Uhr
Wenn Sie so großzügig sind, Ihre eigene optimierte Nullungsmethode zu schreiben – könnten Sie bitte ein paar Worte darüber verlieren, WIE es funktioniert und WARUM es schneller ist? Der Code ist alles andere als selbsterklärend.
– Motti Schoner
31. Dezember 2019 um 14:15 Uhr
@MottiShneor Es sieht komplizierter aus als es ist. Ein AVX-Register hat eine Größe von 32 Bytes. Also berechnet er, wie viele Werte von a in ein Register passen. Danach durchläuft er alle 32-Byte-Blöcke, die mit Zeigerarithmetik vollständig überschrieben werden sollen ((float *)((a)+x)). Die beiden Intrinsics (beginnend mit _mm256) erstellen Sie einfach ein mit Null initialisiertes 32-Byte-Register und speichern Sie es im aktuellen Zeiger. Das sind die ersten 3 Zeilen. Der Rest behandelt nur alle Sonderfälle, in denen der letzte 32-Byte-Block nicht vollständig überschrieben werden soll. Aufgrund der Vektorisierung ist es schneller. – Ich hoffe das hilft.
Sie können verwenden sizeof(myarray) wenn die Größe von myarray ist zur Kompilierzeit bekannt. Andernfalls, wenn Sie ein Array mit dynamischer Größe verwenden, wie es beispielsweise über erhalten wird malloc oder newmüssen Sie die Länge im Auge behalten.
sizeof funktioniert auch dann, wenn die Größe des Arrays zur Kompilierzeit nicht bekannt ist. (natürlich nur wenn es sich um ein Array handelt)
– asaelr
5. Februar 2012 um 2:28 Uhr
@asaelr: In C++, sizeof wird immer zur Kompilierzeit ausgewertet (und kann nicht mit VLAs verwendet werden). In C99 kann es sich bei VLAs um einen Laufzeitausdruck handeln.
– Ben Voigt
15. Juni 2013 um 22:53 Uhr
@BenVoigt Nun, die Frage betrifft beides c und c++. Ich habe die Antwort von Alex kommentiert, die besagt: “Sie können sizeof (myarray) verwenden, wenn die Größe von myarray zur Kompilierzeit bekannt ist”.
– asaelr
15. Juni 2013 um 23:44 Uhr
@asaelr: Und in C++ hat er völlig recht. Ihr Kommentar sagte nichts über C99 oder VLAs, also wollte ich es klarstellen.
– Ben Voigt
16. Juni 2013 um 0:27 Uhr
AnT steht zu Russland
Sie können verwenden memsetaber nur, weil sich unsere Typenauswahl auf ganzzahlige Typen beschränkt.
Im Allgemeinen ist es in C sinnvoll, ein Makro zu implementieren
#define ZERO_ANY(T, a, n) do{\
T *a_ = (a);\
size_t n_ = (n);\
for (; n_ > 0; --n_, ++a_)\
*a_ = (T) { 0 };\
} while (0)
Dadurch erhalten Sie eine C++-ähnliche Funktionalität, mit der Sie ein Array von Objekten beliebigen Typs “auf Null zurücksetzen” können, ohne auf Hacks wie zurückgreifen zu müssen memset. Im Grunde ist dies ein C-Analogon der C++-Funktionsvorlage, außer dass Sie das Typargument explizit angeben müssen.
Darüber hinaus können Sie eine “Vorlage” für nicht verfallene Arrays erstellen
//fixed arrays
int a[10];
setValue(a, 0);
//dynamic arrays
int *d = new int[length];
setValue(d, length, 0);
Oben ist mehr C ++ 11-Weg als die Verwendung von Memset. Außerdem erhalten Sie einen Kompilierzeitfehler, wenn Sie ein dynamisches Array mit Angabe der Größe verwenden.
Die ursprüngliche Frage bezieht sich auf C, nicht auf C++, daher kann std::fill keine richtige Antwort sein
– Motti Schoner
31. Dezember 2019 um 13:42 Uhr
14227400cookie-checkZurücksetzen des C int-Arrays auf Null: der schnellste Weg?yes
@BoPersson: Nun,
new
ist C++…– Matteo Italien
5. Februar 2012 um 20:06 Uhr
@Matteo – na ja. Hat die Antworten nicht sehr beeinflusst (bis jetzt :-).
– Bo Persson
5. Februar 2012 um 20:12 Uhr
@BoPersson: Ich fühlte mich schlecht, wenn ich nur darüber redete
memset
wenn C++ irgendwie involviert ist … 🙂– Matteo Italien
5. Februar 2012 um 20:15 Uhr
Auf einem modernen Compiler ist ein einfacher nicht zu übertreffen
for
Schleife. Aber überraschenderweise können Sie viel Schlimmeres erreichen, wenn Sie versuchen, schlau zu sein.– David Schwartz
21. September 2015 um 8:58 Uhr
Verwenden Sie eine Struktur und stecken Sie ein Array hinein. Erstellen Sie eine Instanz, die nur aus Nullen besteht. Verwenden Sie dies, um andere, die Sie erstellen, auf Null zu setzen. Es funktioniert gut. Keine Includes, keine Funktionen, ziemlich schnell.
– Xofo
5. März 2019 um 8:24 Uhr