Warum ist malloc+memset langsamer als calloc?

Lesezeit: 11 Minuten

Benutzeravatar von kingkai
Königkai

Das ist bekannt calloc ist anders als malloc , dass es den zugeordneten Speicher initialisiert. Mit calloc, wird der Speicher auf Null gesetzt. Mit mallocder Speicher wird nicht gelöscht.

Also im Arbeitsalltag betrachte ich calloc wie malloc+memset. Übrigens habe ich aus Spaß folgenden Code für einen Benchmark geschrieben.

Das Ergebnis ist verwirrend.

Code 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)calloc(1,BLOCK_SIZE);
                i++;
        }
}

Ausgabe von Code 1:

time ./a.out  
**real 0m0.287s**  
user 0m0.095s  
sys 0m0.192s  

Code 2:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)malloc(BLOCK_SIZE);
                memset(buf[i],'\0',BLOCK_SIZE);
                i++;
        }
}

Ausgabe von Code 2:

time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s  

Ersetzen memset mit bzero(buf[i],BLOCK_SIZE) in Code 2 führt zum gleichen Ergebnis.

Meine Frage ist: Warum ist malloc+memset so viel langsamer als calloc? Wie kann calloc TU das?

Benutzeravatar von Dietrich Epp
Dietrich Ep

Die Kurzversion: Immer verwenden calloc() Anstatt von malloc()+memset(). In den meisten Fällen werden sie gleich sein. In manchen Fällen, calloc() macht weniger Arbeit, weil es überspringen kann memset() völlig. In anderen Fällen, calloc() kann sogar schummeln und keinen Speicher zuweisen! Jedoch, malloc()+memset() wird immer die volle Arbeit leisten.

Um dies zu verstehen, ist ein kurzer Rundgang durch das Gedächtnissystem erforderlich.

Kurzer Rundgang durch die Erinnerung

Hier gibt es vier Hauptteile: Ihr Programm, die Standardbibliothek, den Kernel und die Seitentabellen. Du kennst dein Programm bereits, also…

Speicherzuordner wie malloc() und calloc() sind meistens dazu da, kleine Zuweisungen (alles von 1 Byte bis zu 100 KB) zu nehmen und sie in größeren Speicherpools zu gruppieren. Wenn Sie beispielsweise 16 Byte zuweisen, malloc() wird zuerst versuchen, 16 Bytes aus einem seiner Pools herauszuholen, und dann mehr Speicher vom Kernel anfordern, wenn der Pool leer ist. Da das Programm, nach dem Sie fragen, jedoch eine große Menge an Speicher auf einmal zuweist, malloc() und calloc() fragt einfach direkt vom Kernel nach diesem Speicher. Der Schwellenwert für dieses Verhalten hängt von Ihrem System ab, aber ich habe gesehen, dass 1 MiB als Schwellenwert verwendet wird.

Der Kernel ist dafür verantwortlich, jedem Prozess tatsächlichen RAM zuzuweisen und sicherzustellen, dass Prozesse den Speicher anderer Prozesse nicht stören. Das nennt man Speicherschutz, Es ist seit den 1990er Jahren weit verbreitet und der Grund, warum ein Programm abstürzen kann, ohne das gesamte System zum Absturz zu bringen. Wenn also ein Programm mehr Speicher benötigt, kann es den Speicher nicht einfach nehmen, sondern fragt den Speicher stattdessen mit einem Systemaufruf wie beim Kernel ab mmap() oder sbrk(). Der Kernel gibt jedem Prozess RAM, indem er die Seitentabelle modifiziert.

Die Seitentabelle bildet Speicheradressen auf tatsächliches physisches RAM ab. Die Adressen Ihres Prozesses, 0x00000000 bis 0xFFFFFFFF auf einem 32-Bit-System, sind kein echter Speicher, sondern Adressen darin virtueller Speicher. Der Prozessor unterteilt diese Adressen in 4-KiB-Seiten, und jede Seite kann einem anderen Teil des physischen RAM zugewiesen werden, indem die Seitentabelle geändert wird. Nur der Kernel darf die Seitentabelle ändern.

Wie es nicht funktioniert

So funktioniert die Zuweisung von 256 MiB nicht Arbeit:

  1. Ihr Prozess ruft calloc() und fragt nach 256 MiB.

  2. Die Standardbibliothek ruft auf mmap() und fragt nach 256 MiB.

  3. Der Kernel findet 256 MiB ungenutzten RAM und gibt ihn Ihrem Prozess, indem er die Seitentabelle modifiziert.

  4. Die Standardbibliothek nullt den Arbeitsspeicher mit memset() und Rücksendungen von calloc().

  5. Ihr Prozess wird schließlich beendet und der Kernel beansprucht den Arbeitsspeicher zurück, damit er von einem anderen Prozess verwendet werden kann.

Wie es tatsächlich funktioniert

Der obige Prozess würde funktionieren, aber es passiert einfach nicht auf diese Weise. Es gibt drei große Unterschiede.

  • Wenn Ihr Prozess neuen Speicher vom Kernel erhält, wurde dieser Speicher wahrscheinlich zuvor von einem anderen Prozess verwendet. Dies ist ein Sicherheitsrisiko. Was ist, wenn dieser Speicher Passwörter, Verschlüsselungsschlüssel oder geheime Salsa-Rezepte enthält? Um zu verhindern, dass vertrauliche Daten durchsickern, löscht der Kernel immer den Speicher, bevor er ihn an einen Prozess weitergibt. Wir könnten den Speicher genauso gut löschen, indem wir ihn auf Null setzen, und wenn ein neuer Speicher auf Null gesetzt wird, können wir ihn genauso gut zu einer Garantie machen, also mmap() garantiert, dass der neue Speicher, den es zurückgibt, immer auf Null gesetzt ist.

  • Es gibt viele Programme, die Speicher zuweisen, aber nicht sofort verwenden. Manchmal wird Speicher zugewiesen, aber nie verwendet. Der Kernel weiß das und ist faul. Wenn Sie neuen Speicher zuweisen, berührt der Kernel die Seitentabelle überhaupt nicht und gibt Ihrem Prozess keinen RAM. Stattdessen findet es einen Adressraum in Ihrem Prozess, notiert sich, was dorthin gehen soll, und verspricht, dass es RAM dort platzieren wird, wenn Ihr Programm es jemals tatsächlich verwendet. Wenn Ihr Programm versucht, von diesen Adressen zu lesen oder zu schreiben, löst der Prozessor a aus Seitenfehler und der Kernel greift ein, um diesen Adressen RAM zuzuweisen, und setzt Ihr Programm fort. Wenn Sie den Speicher nie verwenden, tritt der Seitenfehler nie auf und Ihr Programm erhält nie wirklich den Arbeitsspeicher.

  • Einige Prozesse weisen Speicher zu und lesen daraus, ohne ihn zu ändern. Dies bedeutet, dass viele Seiten im Speicher über verschiedene Prozesse hinweg mit ursprünglichen Nullen gefüllt werden können, von denen zurückgegeben wird mmap(). Da diese Seiten alle gleich sind, lässt der Kernel alle diese virtuellen Adressen auf eine einzelne gemeinsam genutzte 4-KiB-Speicherseite zeigen, die mit Nullen gefüllt ist. Wenn Sie versuchen, in diesen Speicher zu schreiben, löst der Prozessor einen weiteren Seitenfehler aus, und der Kernel springt ein, um Ihnen eine neue Seite mit Nullen zu geben, die nicht mit anderen Programmen geteilt wird.

Der finale Prozess sieht eher so aus:

  1. Ihr Prozess ruft calloc() und fragt nach 256 MiB.

  2. Die Standardbibliothek ruft auf mmap() und fragt nach 256 MiB.

  3. Der Kernel findet 256 MiB ungenutzt Adressraum, macht eine Notiz darüber, wofür dieser Adressraum jetzt verwendet wird, und kehrt zurück.

  4. Die Standardbibliothek kennt das Ergebnis von mmap() ist immer mit Nullen gefüllt (bzw wird sein sobald es tatsächlich etwas RAM erhält), so dass es den Speicher nicht berührt, sodass es keinen Seitenfehler gibt und der RAM niemals an Ihren Prozess übergeben wird.

  5. Ihr Prozess wird schließlich beendet, und der Kernel muss den Arbeitsspeicher nicht zurückfordern, da er überhaupt nie zugewiesen wurde.

Wenn du benutzt memset() um die Seite zu nullen, memset() wird den Seitenfehler auslösen, dafür sorgen, dass der RAM zugewiesen wird, und ihn dann auf Null setzen, obwohl er bereits mit Nullen gefüllt ist. Dies ist eine enorme Menge an zusätzlicher Arbeit und erklärt warum calloc() ist schneller als malloc() und memset(). Wenn Sie den Speicher trotzdem verwenden, calloc() ist immer noch schneller als malloc() und memset() aber der Unterschied ist nicht ganz so lächerlich.


Das funktioniert nicht immer

Nicht alle Systeme verfügen über ausgelagerten virtuellen Speicher, daher können nicht alle Systeme diese Optimierungen verwenden. Dies gilt sowohl für sehr alte Prozessoren wie den 80286 als auch für eingebettete Prozessoren, die für eine ausgeklügelte Speicherverwaltungseinheit einfach zu klein sind.

Dies funktioniert auch nicht immer mit kleineren Allokationen. Bei kleineren Zuteilungen calloc() erhält Speicher aus einem gemeinsam genutzten Pool, anstatt direkt zum Kernel zu gehen. Im Allgemeinen enthält der gemeinsam genutzte Pool möglicherweise Junk-Daten aus altem Speicher, der verwendet und freigegeben wurde free()Also calloc() könnte diese Erinnerung nehmen und anrufen memset() um es auszuräumen. Gängige Implementierungen verfolgen, welche Teile des gemeinsam genutzten Pools unberührt und noch mit Nullen gefüllt sind, aber nicht alle Implementierungen tun dies.

Zerstreuen einige falsche Antworten

Abhängig vom Betriebssystem kann der Kernel in seiner Freizeit Speicher auf Null setzen oder auch nicht, falls Sie später etwas auf Null gesetzten Speicher benötigen. Linux setzt den Speicher nicht vorzeitig auf Null, und Dragonfly BSD hat diese Funktion kürzlich ebenfalls aus ihrem Kernel entfernt. Einige andere Kernel machen jedoch im Voraus null Speicher. Das Nullen von Seiten im Idle reicht ohnehin nicht aus, um die großen Leistungsunterschiede zu erklären.

Das calloc() Funktion verwendet keine spezielle speicherausgerichtete Version von memset(), und das würde es sowieso nicht viel schneller machen. Die meisten memset() Implementierungen für moderne Prozessoren sehen etwa so aus:

function memset(dest, c, len)
    // one byte at a time, until the dest is aligned...
    while (len > 0 && ((unsigned int)dest & 15))
        *dest++ = c
        len -= 1
    // now write big chunks at a time (processor-specific)...
    // block size might not be 16, it's just pseudocode
    while (len >= 16)
        // some optimized vector code goes here
        // glibc uses SSE2 when available
        dest += 16
        len -= 16
    // the end is not aligned, so one byte at a time
    while (len > 0)
        *dest++ = c
        len -= 1

Du kannst also sehen, memset() ist sehr schnell und Sie werden nichts Besseres für große Speicherblöcke bekommen.

Die Tatsache, dass memset() Das Nullen von Speicher, der bereits auf Null gesetzt ist, bedeutet zwar, dass der Speicher zweimal auf Null gesetzt wird, aber das erklärt nur einen 2-fachen Leistungsunterschied. Der Leistungsunterschied ist hier viel größer (ich habe mehr als drei Größenordnungen auf meinem System zwischen gemessen malloc()+memset() und calloc()).

Partytrick

Anstatt 10 Schleifen zu durchlaufen, schreiben Sie ein Programm, das Speicher bis zuweist malloc() oder calloc() gibt NULL zurück.

Was passiert, wenn Sie hinzufügen memset()?

  • @Dietrich: Die Erklärung des virtuellen Speichers von Dietrich über das OS, das mehrmals dieselbe mit Nullen gefüllte Seite für calloc zuweist, ist leicht zu überprüfen. Fügen Sie einfach eine Schleife hinzu, die Junk-Daten in jede zugewiesene Speicherseite schreibt (das Schreiben eines Bytes alle 500 Bytes sollte ausreichen). Das Gesamtergebnis sollte dann viel enger werden, da das System gezwungen wäre, in beiden Fällen wirklich unterschiedliche Seiten zuzuweisen.

    – kriss

    22. April 2010 um 6:43 Uhr

  • @kriss: in der Tat, obwohl ein Byte alle 4096 auf den meisten Systemen ausreicht

    – Dietrich Ep

    22. April 2010 um 6:46 Uhr

  • @mirabilos: Tatsächlich sind Implementierungen in der Regel noch ausgefeilter. Speicher zugewiesen von mmap() wird in großen Stücken zugeteilt, so dass die malloc() / calloc() Die Implementierung kann verfolgen, welche Blöcke noch makellos und voller Nullen sind. So calloc() kann vermeiden, Speicher zu berühren, selbst wenn er den Speicher nicht bekommt mmap()dh es war bereits Teil des Haufens, wurde aber noch nicht verwendet.

    – Dietrich Ep

    31. März 2014 um 20:49 Uhr


  • @mirabilos: Ich habe auch Implementierungen mit einer “Hochwassermarke” gesehen, bei denen Adressen über einen bestimmten Punkt hinaus auf Null gesetzt werden. Ich bin mir nicht sicher, was Sie mit „fehleranfällig“ meinen. Wenn Sie sich Sorgen darüber machen, dass Anwendungen in nicht zugeordneten Speicher schreiben, können Sie nur sehr wenig tun, um heimtückische Fehler zu verhindern, außer das Programm mit Mudflap zu instrumentieren.

    – Dietrich Ep

    31. März 2014 um 21:24 Uhr

  • Auch wenn es nicht geschwindigkeitsabhängig ist, calloc ist auch weniger fehleranfällig. Das ist wo large_int * large_int würde zu einem Überlauf führen, calloc(large_int, large_int) kehrt zurück NULLaber malloc(large_int * large_int) ist ein undefiniertes Verhalten, da Sie die tatsächliche Größe des zurückgegebenen Speicherblocks nicht kennen.

    – Dünen

    23. März 2018 um 9:41 Uhr

Denn auf vielen Systemen setzt das Betriebssystem in freier Verarbeitungszeit den freien Speicher selbst auf Null und markiert ihn als sicher calloc()also wenn du anrufst calloc()verfügt es möglicherweise bereits über freien, auf Null gesetzten Speicher, den Sie erhalten können.

  • Bist du dir sicher? Welche Systeme machen das? Ich dachte, dass die meisten Betriebssysteme den Prozessor einfach herunterfahren, wenn sie sich im Leerlauf befinden, und den Speicher bei Bedarf für die zugewiesenen Prozesse auf Null setzen, sobald sie in diesen Speicher schreiben (aber nicht, wenn sie ihn zuweisen).

    – Dietrich Ep

    22. April 2010 um 6:00 Uhr

  • @Dietrich – Nicht sicher. Ich habe es einmal gehört und es schien eine vernünftige (und einigermaßen einfache) Art zu sein calloc() effizienter.

    – Chris Lutz

    22. April 2010 um 6:06 Uhr


  • @Pierreten – Ich kann keine guten Informationen finden calloc()-spezifische Optimierungen und ich habe keine Lust, den libc-Quellcode für das OP zu interpretieren. Können Sie irgendetwas nachschlagen, um zu zeigen, dass diese Optimierung nicht existiert / nicht funktioniert?

    – Chris Lutz

    22. April 2010 um 6:13 Uhr


  • @Dietrich: FreeBSD soll Seiten in Leerlaufzeiten mit Nullen füllen: Siehe die Einstellung vm.idlezero_enable.

    – Zan Luchs

    7. März 2011 um 21:47 Uhr

  • @DietrichEpp Entschuldigung an Necro, aber zum Beispiel Windows tut dies.

    – Andreas Grapentin

    11. November 2014 um 19:37 Uhr


Auf einigen Plattformen in einigen Modi initialisiert malloc den Speicher auf einen Wert, der normalerweise nicht Null ist, bevor er ihn zurückgibt, sodass die zweite Version den Speicher durchaus zweimal initialisieren könnte

1426760cookie-checkWarum ist malloc+memset langsamer als calloc?

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

Privacy policy