Ist memset() effizienter als die for-Schleife in C?

Lesezeit: 9 Minuten

Davids Benutzeravatar
David

Ist memset() effizienter als for Schleife.

In Anbetracht dieses Codes:

char x[500];
memset(x,0,sizeof(x));

Und das hier:

char x[500];
for(int i = 0 ; i < 500 ; i ++) x[i] = 0;

Welche ist effizienter und warum? Gibt es eine spezielle Anweisung in der Hardware, um eine Initialisierung auf Blockebene durchzuführen?

  • Ja. Nein, vielleicht. Es hängt davon ab, ob. Die einzige Möglichkeit, eine nützliche Antwort zu erhalten, besteht darin, sie zu analysieren und zu profilieren in deiner Umgebung. Welches auf meinem Compiler, in meinem Programm, auf meinem Computer schneller ist, sagt Ihnen nichts Nützliches.

    – Robᵩ

    9. September 2011 um 21:34 Uhr

  • Warum sich die Mühe machen, Nachforschungen anzustellen? Sofern es keine Daten gibt, die etwas anderes belegen (Sie verfehlen Ihre Leistungsziele und die Untersuchung weist auf diesen Codeabschnitt hin), ist dieser Codeabschnitt wahrscheinlich kein Hotspot, und Sie sollten sich einfach für einen möglichst einfachen, lesbaren und wartbaren Code entscheiden.

    – Michael

    9. September 2011 um 21:54 Uhr

  • Wenn Sie einen Compiler haben, der diese Schleife nicht durch memset() ersetzt, sollten Sie einen anderen Compiler finden.

    – Hans Passant

    9. September 2011 um 22:00 Uhr

  • @Chris: Ähmmm … dann sollten sie es wahrscheinlich lernen. Ich schätze, ich bin ein 27-jähriger Dinosaurier, aber ich habe ein Problem mit sogenannten “Ingenieuren”, die die grundlegende Assemblierung nicht lesen können … Ich will damit nicht sagen, dass man keinen Profiler verwenden sollte, aber für einen so trivialen Vergleich sollte es unnötig sein.

    – Ed S.

    9. September 2011 um 22:07 Uhr


  • @Chris: Und das ist der Grund, warum so viele Web-Jungs (und -Mädels), mit denen ich in Kontakt gekommen bin, Schreibanwendungen geschrieben haben, die viel langsamer sind, als sie sein sollten. Nicht unbedingt, weil sie Assembler nicht lesen können, sondern weil sie nie wirklich die Leistungsmerkmale der von ihnen verwendeten Datenstrukturen gelernt haben und wie ihr High-Level-Code ausgeführt werden kann, wenn er in Maschinencode umgewandelt wird. Ich schweife jedoch ab, das ist eine Diskussion für einen anderen Ort und eine andere Zeit.

    – Ed S.

    9. September 2011 um 22:11 Uhr


Benutzeravatar von Diego Sevilla
Diego Sevilla

Höchstwahrscheinlich, memset wird viel schneller sein als diese Schleife. Beachten Sie, wie Sie einen behandeln Charakter gleichzeitig, aber diese Funktionen sind so optimiert, dass sie mehrere Bytes gleichzeitig setzen, sogar unter Verwendung, wenn verfügbar, von MMX- und SSE-Anweisungen.

Ich denke, das paradigmatische Beispiel für diese Optimierungen, die normalerweise unbemerkt bleiben, ist die GNU C-Bibliothek strlen Funktion. Man würde denken, dass es mindestens O(n) Leistung hat, aber es hat tatsächlich O(n/4) oder O(n/8) je nach Architektur (ja, ich weiß, in Big O() wird es dasselbe sein , aber du bekommst tatsächlich eine achte der ganzen Zeit). Wie? Schwierig, aber schön: Strlen.

  • Jeder optimierende Compiler ersetzt die for-Schleife durch eine optimale Sequenz (die ein Aufruf von memset sein kann).

    – Stefan Kanon

    9. September 2011 um 21:42 Uhr

  • Es ist auch nicht garantiert, dass es “viel schneller” ist, selbst wenn der Compiler suboptimalen Code für die Schleife ausgibt. 500 ist nicht wirklich eine so hohe Zahl, und wenn ein weicher oder harter Seitenfehler auftritt, wird dies die Kosten der Schleife selbst bei weitem aufwiegen.

    – Michael

    9. September 2011 um 21:45 Uhr

  • @Stephen Canon: Heh. Ich habe eine C-Bibliothek mit Clang/LLVM kompiliert und die Memset-For-Schleife der Bibliothek durch einen Aufruf von Memset ersetzt. Hoppla! Tiefe Rekursion.

    – Richard Pennington

    9. September 2011 um 21:51 Uhr

  • @Diego, es geht nicht darum, dass 500/8-Zuweisungen langsamer oder schneller als 500-Zuweisungen zu 0 sind. Mikro-Benchmarks wie diese sind aufgrund anderer Effekte im System selten nützlich. Bei einem modernen Prozessor liegt der Unterschied zwischen nur den Vergleichen wahrscheinlich in der Größenordnung von 62 Zyklen gegenüber 500 Zyklen. Was ich vorschlage, ist, wenn Sie beim Ausführen des Codes einen harten Seitenfehler in der Größenordnung von 10 Millionen Zyklen erleiden, sind die 438 Zyklen, die Sie eingespart haben, nur Rauschen.

    – Michael

    9. September 2011 um 22:00 Uhr

  • @ Richard Pennington: -fno-builtin-memset.

    – Stefan Kanon

    9. September 2011 um 22:30 Uhr

Benutzeravatar von Ed S
Ed S.

Nun, warum werfen wir nicht einen Blick auf den generierten Assembler-Code, vollständige Optimierung unter VS 2010.

char x[500];
char y[500];
int i;      

memset(x, 0, sizeof(x) );   
  003A1014  push        1F4h  
  003A1019  lea         eax,[ebp-1F8h]  
  003A101F  push        0  
  003A1021  push        eax  
  003A1022  call        memset (3A1844h)  

Und deine Schleife…

char x[500];
char y[500];
int i;    

for( i = 0; i < 500; ++i )
{
    x[i] = 0;

      00E81014  push        1F4h  
      00E81019  lea         eax,[ebp-1F8h]  
      00E8101F  push        0  
      00E81021  push        eax  
      00E81022  call        memset (0E81844h)  

      /* note that this is *replacing* the loop, 
         not being called once for each iteration. */
}

Unter diesem Compiler ist der generierte Code also genau derselbe. memset ist schnell, und der Compiler ist intelligent genug, um zu wissen, dass Sie dasselbe tun wie beim Aufrufen memset einmal sowieso, also erledigt es das für dich.

Wenn der Compiler die Schleife tatsächlich so verlassen hat, wie sie ist, wäre sie wahrscheinlich langsamer, da Sie Blöcke mit mehr als einer Bytegröße gleichzeitig festlegen können (dh Sie könnten Ihre Schleife mindestens ein wenig entrollen. Sie können davon ausgehen memset wird sein wenigstens so schnell wie eine naive Implementierung wie die Schleife. Probieren Sie es unter einem Debug-Build aus und Sie werden feststellen, dass die Schleife nicht ersetzt wird.

Das heißt, es hängt davon ab, was der Compiler für Sie tut. Ein Blick auf die Demontage ist immer eine gute Möglichkeit, genau zu wissen, was los ist.

  • Interessanterweise hat meine Version nicht dazu geführt, dass die Schleife in Memset konvertiert wurde, aber das liegt wahrscheinlich daran, dass die Schleife für meinen Test auf einem globalen operierte (ansonsten wurde die gesamte Schleife als unnötig entfernt.)

    – Michael

    9. September 2011 um 21:53 Uhr

  • @Michael: Ich habe ein paar Anrufe hinzugefügt printf verwenden x und y um sicherzustellen, dass sie nicht vollständig wegoptimiert wurden, da sie nicht verwendet werden. Es ist natürlich bis zu einem gewissen Grad Compiler- und Plattformabhängig, aber jeder halbwegs anständige optimierende Compiler sollte die Schleife mit eingeschalteten Optimierungen loswerden.

    – Ed S.

    9. September 2011 um 22:06 Uhr


  • sogar memset() vs. Array-Initialisierung (Bsp.: a[n]={0}) nimmt denselben Code wie er aussieht. Der Vorteil von memset ist, dass die Array-Größe eine Variable sein kann, was bei der Initialisierung nicht möglich ist. Habe ich recht?

    – Rajesh

    21. Juni 2020 um 12:39 Uhr

  • Wie prüft man die “Demontage”.

    – young_souflaki

    22. Oktober 2020 um 3:36 Uhr

  • @young_souflaki: In VS? docs.microsoft.com/en-us/visualstudio/debugger/…

    – Ed S.

    13. November 2020 um 17:29 Uhr

Es hängt wirklich vom Compiler und der Bibliothek ab. Für ältere Compiler oder einfache Compiler kann Memset in einer Bibliothek implementiert werden und würde nicht besser funktionieren als eine benutzerdefinierte Schleife.

Für fast alle Compiler, die es wert sind, verwendet zu werden, ist memset eine intrinsische Funktion, und der Compiler generiert dafür optimierten Inline-Code.

Andere haben vorgeschlagen, Profile zu erstellen und zu vergleichen, aber ich würde mich nicht darum kümmern. Verwenden Sie einfach memset. Code ist einfach und leicht zu verstehen. Machen Sie sich keine Sorgen, bis Ihre Benchmarks Ihnen sagen, dass dieser Teil des Codes ein Leistungs-Hotspot ist.

Benutzeravatar von Bobby Powers
Bobby Powers

Die Antwort ist “es kommt darauf an”. memset KANN effizienter sein oder intern eine for-Schleife verwenden. Mir fällt kein Fall ein wo memset wird weniger effizient sein. In diesem Fall kann es zu einer effizienteren for-Schleife werden: Ihre Schleife wird 500 Mal durchlaufen und setzt jedes Mal einen Wert von Bytes des Arrays auf 0. Auf einem 64-Bit-Rechner könnten Sie eine Schleife durchlaufen, 8 Bytes (ein langes langes) auf einmal setzen, was fast 8-mal schneller wäre, und sich am Ende nur mit den verbleibenden 4 Bytes (500% 8) befassen.

BEARBEITEN:

in der Tat ist dies was memset macht in glibc:

http://repo.or.cz/w/glibc.git/blob/HEAD:/string/memset.c

Wie Michael betonte, kann der C-Compiler in bestimmten Fällen (in denen die Array-Länge zur Kompilierzeit bekannt ist) inline arbeiten memset, um den Overhead des Funktionsaufrufs loszuwerden. Glibc hat auch für Assembly optimierte Versionen von memset für die meisten großen Plattformen, wie amd64:

http://repo.or.cz/w/glibc.git/blob/HEAD:/sysdeps/x86_64/memset.S

Gute Compiler erkennen die for-Schleife und ersetzen sie entweder durch eine optimale Inline-Sequenz oder einen Aufruf von memset. Sie werden Memset auch durch eine optimale Inline-Sequenz ersetzen, wenn die Puffergröße klein ist.

In der Praxis ist mit einem optimierenden Compiler der generierte Code (und damit die Leistung) identisch.

  • Können Sie ein Zitat angeben?

    – Translunar

    10. Dezember 2015 um 16:24 Uhr

  • Probieren Sie es aus und sehen Sie mit jedem guten optimierenden Compiler (z goo.gl/2mWsxq). Ich bin mir nicht sicher, was ich hier “zitieren” soll.

    – Stefan Kanon

    10. Dezember 2015 um 17:50 Uhr


  • Wissenschaftliche Zitate sind immer wichtig, auch wenn es nur graue Literatur ist.

    – Patrick

    18. Januar 2020 um 11:08 Uhr

Benutzeravatar von beetree
Bienenbaum

Stimme oben zu. Es hängt davon ab, ob. Aber sicher ist memset schneller oder gleich der for-Schleife. Wenn Sie sich Ihrer Umgebung nicht sicher sind oder zu faul zum Testen, gehen Sie den sicheren Weg und entscheiden Sie sich für memset.

  • Können Sie ein Zitat angeben?

    – Translunar

    10. Dezember 2015 um 16:24 Uhr

  • Probieren Sie es aus und sehen Sie mit jedem guten optimierenden Compiler (z goo.gl/2mWsxq). Ich bin mir nicht sicher, was ich hier “zitieren” soll.

    – Stefan Kanon

    10. Dezember 2015 um 17:50 Uhr


  • Wissenschaftliche Zitate sind immer wichtig, auch wenn es nur graue Literatur ist.

    – Patrick

    18. Januar 2020 um 11:08 Uhr

Andere Techniken wie Schleife abrollen die die Anzahl der Schleifen reduzieren, können ebenfalls verwendet werden. Der Code von memset() kann das berühmte nachahmen Duffs Gerät:

void *duff_memset(char *to, int c, size_t count)
{
    size_t n;
    char *p = to;
    n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *p++ = c;
    case 7:      *p++ = c;
    case 6:      *p++ = c;
    case 5:      *p++ = c;
    case 4:      *p++ = c;
    case 3:      *p++ = c;
    case 2:      *p++ = c;
    case 1:      *p++ = c;
            } while (--n > 0);
    }
    return to;
}

Diese Tricks wurden früher verwendet, um die Ausführungsgeschwindigkeit zu erhöhen. Auf modernen Architekturen erhöht dies jedoch tendenziell die Codegröße und erhöht Cache-Fehler.

Es ist also ziemlich unmöglich zu sagen, welche Implementierung schneller ist, da dies von der Qualität der Compiler-Optimierungen, der Fähigkeit der C-Bibliothek, spezielle Hardwareanweisungen zu nutzen, der Datenmenge, mit der Sie arbeiten, und den Funktionen der zugrundeliegendes Betriebssystem (Seitenfehlerverwaltung, TLB-Fehler, Copy-On-Write).

Beispielsweise in der glibc die Implementierung von memset() sowie diverse andere “Kopieren/Setzen”-Funktionen wie z bnull() oder strcpy() architekturabhängig sind, um verschiedene optimierte Hardwareanweisungen zu nutzen, wie z SSE oder AVX.

1412370cookie-checkIst memset() effizienter als die for-Schleife in C?

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

Privacy policy