Schnellerer Weg zum Nullspeicher als mit memset?

Lesezeit: 11 Minuten

Benutzeravatar von maep
Maep

Ich habe das gelernt memset(ptr, 0, nbytes) ist wirklich schnell, aber gibt es einen schnelleren Weg (zumindest auf x86)?

Ich gehe davon aus, dass memset verwendet wird movjedoch verwenden die meisten Compiler beim Nullen des Speichers xor da es schneller ist, richtig? edit1: Falsch, wie GregS darauf hinwies, dass das nur mit Registern funktioniert. Was dachte ich?

Außerdem bat ich eine Person, die mehr über Assembler wusste als ich, sich die stdlib anzusehen, und er sagte mir, dass Memset auf x86 die 32 Bit breiten Register nicht voll ausnutzt. Allerdings war ich damals sehr müde, also bin ich mir nicht ganz sicher, ob ich es richtig verstanden habe.

bearbeiten2: Ich habe dieses Problem erneut aufgegriffen und ein wenig getestet. Folgendes habe ich getestet:

    #include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    #include <sys/time.h>

    #define TIME(body) do {                                                     \
        struct timeval t1, t2; double elapsed;                                  \
        gettimeofday(&t1, NULL);                                                \
        body                                                                    \
        gettimeofday(&t2, NULL);                                                \
        elapsed = (t2.tv_sec - t1.tv_sec) * 1000.0 + (t2.tv_usec - t1.tv_usec) / 1000.0; \
        printf("%s\n --- %f ---\n", #body, elapsed); } while(0)                 \


    #define SIZE 0x1000000

    void zero_1(void* buff, size_t size)
    {
        size_t i;
        char* foo = buff;
        for (i = 0; i < size; i++)
            foo[i] = 0;

    }

    /* I foolishly assume size_t has register width */
    void zero_sizet(void* buff, size_t size)
    {
        size_t i;
        char* bar;
        size_t* foo = buff;
        for (i = 0; i < size / sizeof(size_t); i++)
            foo[i] = 0;

        // fixes bug pointed out by tristopia
        bar = (char*)buff + size - size % sizeof(size_t);
        for (i = 0; i < size % sizeof(size_t); i++)
            bar[i] = 0;
    }

    int main()
    {
        char* buffer = malloc(SIZE);
        TIME(
            memset(buffer, 0, SIZE);
        );
        TIME(
            zero_1(buffer, SIZE);
        );
        TIME(
            zero_sizet(buffer, SIZE);
        );
        return 0;
    }

Ergebnisse:

zero_1 ist die langsamste, mit Ausnahme von -O3. zero_sizet ist die schnellste mit ungefähr gleicher Leistung über -O1, -O2 und -O3. memset war immer langsamer als zero_sizet. (doppelt so langsam für -O3). Interessant ist, dass bei -O3 zero_1 gleich schnell war wie zero_sizet. Die disassemblierte Funktion hatte jedoch ungefähr viermal so viele Anweisungen (ich denke, verursacht durch das Abrollen der Schleife). Außerdem habe ich versucht, zero_sizet weiter zu optimieren, aber der Compiler hat mich immer übertroffen, aber hier keine Überraschung.

Für jetztige Memset-Gewinne wurden frühere Ergebnisse durch den CPU-Cache verzerrt. (Alle Tests wurden unter Linux ausgeführt) Weitere Tests erforderlich. Ich werde es als nächstes mit Assembler versuchen 🙂

edit3: Fehler im Testcode behoben, Testergebnisse sind nicht betroffen

edit4: Beim Stöbern in der zerlegten VS2010 C-Laufzeitumgebung ist mir das aufgefallen memset hat eine SSE-optimierte Routine für Null. Das wird schwer zu schlagen sein.

  • Anstatt das anzunehmen memset Verwendet mov, warum versuchen Sie nicht, die Ausgabe Ihres Compilers zu zerlegen? Unterschiedliche Compiler werden unterschiedliche Dinge tun. Wenn xor auf einer gegebenen Architektur schneller ist, dann wäre es nicht verwunderlich, wenn einige Compiler optimieren memset(ptr, 0, nbytes) hinein xor Anweisungen.

    – Laurence Gonsalves

    6. September 2010 um 23:57 Uhr

  • Mir ist kein Compiler bekannt, der XOR verwendet, um den Speicher auf Null zu setzen. Vielleicht ein Register, aber kein Speicher. Um XOR zum Nullen des Speichers zu verwenden, müssen Sie zuerst den Speicher lesen, dann XOR und dann den Speicher schreiben.

    – Präsident James K. Polk

    7. September 2010 um 0:00 Uhr

  • Gegebenenfalls, calloc praktisch kostenlos sein, da die Implementierung Seiten im Voraus nullen könnte, während die CPU ansonsten im Leerlauf ist. Zählt das? 😉

    – Steve Jessop

    7. September 2010 um 0:01 Uhr


  • @aaa Karpfen, GregS hat Recht, dass die Verwendung eines XOR zum Löschen des Speichers fast nie die richtige Antwort sein wird. Die Ausnahme, die einem in den Sinn kommt, sind die kleinsten PIC-CPUs von Microchip, bei denen der gesamte verfügbare RAM wirklich nur ein großes Feld von Allzweckregistern ist. Das Löschen eines Registers mit einem XOR ist in CISC-Architekturen üblich. Einige RISC-Architekturen umfassen effektiv ein Allzweckregister, das so fest verdrahtet ist, dass es nur für diesen Zweck Null hält.

    – RBerteig

    7. September 2010 um 2:09 Uhr

  • @TravisGockel Auch höchst unklug: madvise() kann nur ein no-op sein. Es könnte bei einem funktionieren bestimmte Kernel- und libc-Versionaber es hört sich so an, als könnte es bei einem Upgrade leicht kaputt gehen.

    – tc.

    14. Mai 2013 um 15:18 Uhr


x86 ist eine ziemlich breite Palette von Geräten.

Für ein völlig generisches x86-Ziel könnte ein Assemblerblock mit “rep movsd” Nullen in 32-Bit-Speicher auf einmal sprengen. Versuchen Sie sicherzustellen, dass der Großteil dieser Arbeit DWORD-ausgerichtet ist.

Bei Chips mit mmx könnte eine Assembly-Schleife mit movq 64 Bit gleichzeitig treffen.

Möglicherweise können Sie einen C/C++-Compiler dazu bringen, einen 64-Bit-Schreibvorgang mit einem Zeiger auf long long oder _m64 zu verwenden. Das Ziel muss für die beste Leistung auf 8 Byte ausgerichtet sein.

für Chips mit sse ist movaps schnell, aber nur wenn die Adresse auf 16 Byte ausgerichtet ist, verwenden Sie also ein movsb, bis es ausgerichtet ist, und schließen Sie dann Ihren Löschvorgang mit einer Schleife von movaps ab

Win32 hat “ZeroMemory()”, aber ich vergesse, ob das ein Makro für Memset oder eine tatsächliche “gute” Implementierung ist.

  • 10 Jahre alte Antwort, aber ZeroMemory ist ein Makro für Memset: D

    – Hypervisor

    17. Dezember 2020 um 23:06 Uhr

Benutzeravatar von Ben Zotto
Ben Zotto

memset ist generell sehr sehr schnell ausgelegt allgemeiner Zweck Einstell-/Nullcode. Es verarbeitet alle Fälle mit unterschiedlichen Größen und Ausrichtungen, die sich auf die Arten von Anweisungen auswirken, die Sie für Ihre Arbeit verwenden können. Je nachdem, auf welchem ​​​​System Sie sich befinden (und von welchem ​​​​Anbieter Ihre stdlib stammt), kann die zugrunde liegende Implementierung in Assembler sein, der für diese Architektur spezifisch ist, um die nativen Eigenschaften zu nutzen. Es kann auch interne Sonderfälle geben, um den Fall des Nullsetzens zu behandeln (im Gegensatz zum Setzen eines anderen Werts).

Das heißt, wenn Sie ein sehr spezifisches, sehr leistungskritisches Memory Zeroing durchführen müssen, ist es sicherlich möglich, dass Sie ein bestimmtes schlagen könnten memset Umsetzung durch Eigenleistung. memset und seine Freunde in der Standardbibliothek sind immer unterhaltsame Ziele für die Programmierung mit einem Vorsprung. 🙂

  • Außerdem: memset könnte theoretisch einen Sonderfall für 0 haben, der zur Kompilierzeit ausgewählt wird (entweder durch Inlining oder als intrinsische Operation), wenn dieses Argument ein Literal ist. Weiß nicht, ob es jemand tut oder nicht.

    – Steve Jessop

    6. September 2010 um 23:58 Uhr


  • @Steve Jessop: Interessante Idee (insbesondere, dass es Kompilierzeit sein könnte). Ich erinnere mich, dass ich einmal die Maverick-Implementierung von Memset von jemandem gelesen habe, die Sonderfälle für fast alles hatte, wofür Sie Memset tatsächlich verwenden würden.

    – Ben Zotto

    7. September 2010 um 0:05 Uhr

  • gcc verwendet normalerweise eine eingebaute Inline-Implementierung von memset(). Lustigerweise erinnere ich mich, etwas über eine fehlerhafte Implementierung von gelesen zu haben memset() die den Wert immer auf 0 setzen – und das wurde nicht bemerkt Jahreweil anscheinend die überwiegende Mehrheit der Zeit memset() wird verwendet, um auf Null zu setzen!

    – Café

    7. September 2010 um 0:50 Uhr

  • memset ist im Allgemeinen als sehr, sehr schnelles Allzweck-Setzen/Nullstellen von Codes konzipiert…” – Das finde ich nicht ganz richtig. Es gibt keine Garantien memset wird den Optimierungsdurchgang überstehen, sodass eine Nullung möglicherweise nicht auftritt. memset_s macht diese Garantie, aber die Glibc-Leute lehnen es ab, sie zu geben. Siehe auch Problem 17879: In der Bibliothek fehlen memset_s.

    – jww

    27. Februar 2016 um 13:41 Uhr


Heutzutage sollte Ihr Compiler die ganze Arbeit für Sie erledigen. Zumindest soweit ich weiß, ist gcc sehr effizient bei der Optimierung von Anrufen memset entfernt (überprüfen Sie jedoch besser den Assembler).

Dann auch vermeiden memset wenn es nicht sein muss:

  • Verwenden Sie calloc für Heap-Speicher
  • Verwenden Sie die richtige Initialisierung (... = { 0
    }
    ) für Stapelspeicher

Und für richtig große Brocken zu gebrauchen mmap Wenn du es hast. Dadurch wird “kostenlos” nur null initialisierter Speicher vom System abgerufen.

  • Nein, als ich das letzte Mal nachgesehen habe, war gcc nicht dabei. Allerdings optimiert g++ einen Aufruf an std::fill (es sei denn, es gibt eine Optimierung -ftree-loop-distribute-patterns aktiviert, in diesem Fall wird es auch ein Aufruf an memset)das ein C++-Analogon von Memset ist.

    – Hallo Engel

    26. September 2015 um 16:08 Uhr


  • Vielleicht noch eine Erwähnung wert: Ich habe gerade einen Test gemacht und eine wunderbare Sache gefunden: mit der -ftree-loop-distribute-patternswas sich ändert std∷fill zu memset das Programm x10 (!) Mal schneller als ohne, dh wann std∷fill ist von g ++ eingebettet, und selbst wenn ich hinzufüge march=native. Daher ist gcc-4.9.2 nicht so gut in Optimierungen, weil das bedeutet, dass es eine Möglichkeit zur Optimierung gibt std∷fill sogar mehr. Übrigens, ich habe auch einen Test mit Clang gemacht, und ich fand, dass es schlechter optimiert ist – mit -O3 Ebene entfernt es nicht einmal push-pop aus dem Code.

    – Hallo Engel

    26. September 2015 um 17:12 Uhr


  • Nun, der Kommentar “kostenlos” ist nicht ganz richtig. Die Initialisierung des Speichers auf Null erfolgt einfach im Betriebssystem und nicht unter Ihrer Programmsteuerung. Wer weiß, wer die mmap-Funktion geschrieben hat und ob sie IT-effizient ist? Wenn Zeitkritik wichtig ist, ist es besser, das nicht initialisierte Speicher zu erhalten, als es selbst mit einer Assembler-Routine zu löschen.

    – Cooler Speer

    25. Februar 2017 um 1:44 Uhr

  • Der Compiler bietet Intrinsics für die meisten grundlegenden Funktionen, einschließlich dieser. Von Bibliotheksfunktionen wird erwartet, dass sie die systeminternen Funktionen des Compilers verwenden, sofern verfügbar.

    – Igor Stoppa

    18. September 2018 um 13:55 Uhr

Wenn ich mich richtig erinnere (vor ein paar Jahren), sprach einer der leitenden Entwickler über einen schnellen Weg zu bzero() auf PowerPC (Spezifikationen besagten, dass wir fast den gesamten Speicher beim Einschalten auf Null setzen müssten). Es ist möglicherweise nicht gut (wenn überhaupt) auf x86 übersetzbar, aber es könnte sich lohnen, es zu erkunden.

Die Idee war, eine Daten-Cache-Zeile zu laden, diese Daten-Cache-Zeile zu löschen und dann die gelöschte Daten-Cache-Zeile zurück in den Speicher zu schreiben.

Für das, was es wert ist, hoffe ich, dass es hilft.

Wenn Sie keine besonderen Anforderungen haben oder wissen, dass Ihr Compiler/stdlib schlecht ist, bleiben Sie bei memset. Es ist universell einsetzbar und sollte im Allgemeinen eine anständige Leistung haben. Außerdem haben es Compiler möglicherweise leichter, memset() zu optimieren/inlining, da es eine intrinsische Unterstützung dafür haben kann.

Zum Beispiel generiert Visual C++ oft Inline-Versionen von memcpy/memset, die sind so klein wie ein Anruf an die Bibliotheksfunktion, wodurch Push/Call/Ret-Overhead vermieden wird. Und es gibt weitere mögliche Optimierungen, wenn der Größenparameter zur Kompilierzeit ausgewertet werden kann.

Das heißt, wenn Sie haben Spezifisch Bedürfnisse (wobei Größe immer sein wird sehr klein *oder* riesig), können Sie Geschwindigkeitsschübe erhalten, indem Sie auf die Montageebene herunterfallen. Verwenden Sie beispielsweise Write-Through-Vorgänge, um große Speicherblöcke auf Null zu setzen, ohne Ihren L2-Cache zu verschmutzen.

Aber es hängt alles davon ab – und für normale Sachen bleib bitte bei memset/memcpy 🙂

  • Sogar alte gcc-Implementierungen auf Sparc ersetzt memcpy und memset ruft mith mov instructions wenn die Größen zur Kompilierzeit bekannt und nicht zu groß waren.

    – Patrick Schlüter

    11. Juli 2011 um 13:41 Uhr

Benutzeravatar von bta
bta

Die Memset-Funktion ist so konzipiert, dass sie flexibel und einfach ist, auch auf Kosten der Geschwindigkeit. In vielen Implementierungen handelt es sich um eine einfache While-Schleife, die den angegebenen Wert Byte für Byte über die angegebene Anzahl von Bytes kopiert. Wenn Sie ein schnelleres Memset (oder memcpy, memmove usw.) wünschen, ist es fast immer möglich, selbst eines zu programmieren.

Die einfachste Anpassung wäre, Single-Byte-Set-Operationen durchzuführen, bis die Zieladresse 32- oder 64-Bit-ausgerichtet ist (was auch immer der Architektur Ihres Chips entspricht), und dann mit dem Kopieren eines vollständigen CPU-Registers auf einmal zu beginnen. Möglicherweise müssen Sie am Ende ein paar Einzelbyte-Set-Operationen ausführen, wenn Ihr Bereich nicht an einer ausgerichteten Adresse endet.

Abhängig von Ihrer speziellen CPU haben Sie möglicherweise auch einige Streaming-SIMD-Anweisungen, die Ihnen helfen können. Diese funktionieren in der Regel besser bei ausgerichteten Adressen, sodass die obige Technik zur Verwendung ausgerichteter Adressen auch hier nützlich sein kann.

Beim Nullen großer Speicherabschnitte können Sie auch einen Geschwindigkeitsschub feststellen, indem Sie den Bereich in Abschnitte aufteilen und jeden Abschnitt parallel verarbeiten (wobei die Anzahl der Abschnitte mit Ihrer Anzahl oder Kernen/Hardware-Threads identisch ist).

Am wichtigsten ist, dass es keine Möglichkeit gibt zu sagen, ob irgendetwas davon hilft, es sei denn, Sie versuchen es. Sehen Sie sich zumindest an, was Ihr Compiler für jeden Fall ausgibt. Sehen Sie sich auch an, was andere Compiler für ihr Standard-Memset ausgeben (ihre Implementierung ist möglicherweise effizienter als die Ihres Compilers).

  • Sogar alte gcc-Implementierungen auf Sparc ersetzt memcpy und memset ruft mith mov instructions wenn die Größen zur Kompilierzeit bekannt und nicht zu groß waren.

    – Patrick Schlüter

    11. Juli 2011 um 13:41 Uhr

Benutzeravatar von Chris
Chris

Es gibt einen fatalen Fehler in diesem ansonsten großartigen und hilfreichen Test: Da memset die erste Anweisung ist, scheint es einen gewissen “Speicher-Overhead” zu geben, der es extrem langsam macht. Das Verschieben des Timings von Memset auf den zweiten Platz und etwas anderes auf den ersten Platz oder einfach das Timing von Memset zweimal macht Memset zum schnellsten aller Kompilierungsschalter !!!

  • Danke für den Hinweis. Ich habe den Test ursprünglich auf einem Atom durchgeführt, aber jetzt habe ich nur Zugriff auf einen PPC. Zumindest bei dieser Maschine kann ich deine Aussage bestätigen. Ich vermute, dass der Cache seine Magie ausübt. Ich denke, ich muss jetzt zu Assembler wechseln.

    – Mäp

    19. August 2011 um 14:05 Uhr

1417040cookie-checkSchnellerer Weg zum Nullspeicher als mit memset?

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

Privacy policy