Zurücksetzen des C int-Arrays auf Null: der schnellste Weg?

Lesezeit: 10 Minuten

Vincents Benutzeravatar
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, 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

Benutzeravatar von Matteo Italia
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

Benutzeravatar von Benjamin
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.

clang 3.8 (unter Verwendung des clang-cl-Frontends, Optimierungs-Flags = /OX /arch:AVX /Oi /Ot)

int:
memset:      99
fill:        97
ZERO:        98
intrin_ZERO: 90

long long:
memset:      285
fill:        286
ZERO:        285
intrin_ZERO: 188

gcc 5.1.0 (Optimierungs-Flags: -O3 -march=native -mtune=native -mavx):

int:
memset:      268
fill:        268
ZERO:        268
intrin_ZERO: 91
long long:
memset:      402
fill:        399
ZERO:        400
intrin_ZERO: 185

msvc 2015 (Optimierungsflags: /OX /arch:AVX /Oi /Ot):

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.

    – Wychmeister

    5. März 2020 um 11:41 Uhr

Aus memset():

memset(myarray, 0, sizeof(myarray));

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 mit Russlands Benutzer-Avatar
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

#define ARRAY_SIZE(a) (sizeof (a) / sizeof *(a))
#define ZERO_ANY_A(T, a) ZERO_ANY(T, (a), ARRAY_SIZE(a))

In Ihrem Beispiel würde es als angewendet werden

int a[100];

ZERO_ANY(int, a, 100);
// or
ZERO_ANY_A(int, a);

Es ist auch erwähnenswert, dass man speziell für Objekte von skalaren Typen ein typunabhängiges Makro implementieren kann

#define ZERO(a, n) do{\
   size_t i_ = 0, n_ = (n);\
   for (; i_ < n_; ++i_)\
     (a)[i_] = 0;\
} while (0)

und

#define ZERO_A(a) ZERO((a), ARRAY_SIZE(a))

Drehen Sie das obige Beispiel in

 int a[100];

 ZERO(a, 100);
 // or
 ZERO_A(a);

Benutzeravatar von Bruno Soares
Bruno Soares

Für die statische Deklaration könnten Sie Folgendes verwenden:

T myarray[100] = {0};

Für die dynamische Deklaration schlage ich den gleichen Weg vor: memset

  • Die Frage lautet: “Nicht nur zur Initialisierung”.

    – Ben Voigt

    15. Juni 2013 um 22:54 Uhr

zero(myarray); ist alles, was Sie in C++ brauchen.

Fügen Sie dies einfach zu einer Kopfzeile hinzu:

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}

  • Die Frage lautet: “Nicht nur zur Initialisierung”.

    – Ben Voigt

    15. Juni 2013 um 22:54 Uhr

Hier ist die Funktion, die ich verwende:

template<typename T>
static void setValue(T arr[], size_t length, const T& val)
{
    std::fill(arr, arr + length, val);
}

template<typename T, size_t N>
static void setValue(T (&arr)[N], const T& val)
{
    std::fill(arr, arr + N, val);
}

Du kannst es so nennen:

//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

1422740cookie-checkZurücksetzen des C int-Arrays auf Null: der schnellste Weg?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy