Warum ist malloc + memset langsamer als calloc?

256

Es ist bekannt, dass dies callocanders ist als mallocdarin, dass der zugewiesene Speicher initialisiert wird. Mit callocwird der Speicher auf Null gesetzt. Mit mallocwird der Speicher nicht gelöscht.

In der täglichen Arbeit betrachte ich also callocals malloc+ memset. Übrigens habe ich zum Spaß den 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  

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

Meine Frage ist: Warum ist malloc+ memsetso viel langsamer als calloc? Wie kann das callocgehen?

Kingkai
quelle

Antworten:

455

Die Kurzversion: Immer verwenden calloc()statt malloc()+memset(). In den meisten Fällen sind sie gleich. In einigen Fällen calloc()wird weniger Arbeit erledigt, da es memset()vollständig überspringen kann . In anderen Fällen calloc()kann sogar betrügen und kein Speicher zugewiesen werden! Allerdings malloc()+memset()wird der volle Betrag der Arbeit immer tun.

Um dies zu verstehen, ist eine kurze Einführung in das Speichersystem erforderlich.

Schnelle Tour durch die Erinnerung

Hier gibt es vier Hauptteile: Ihr Programm, die Standardbibliothek, den Kernel und die Seitentabellen. Sie kennen Ihr Programm bereits, also ...

Speicherzuordnungen mögen malloc()und calloc()sind meistens dazu da, kleine Zuordnungen (von 1 Byte bis 100 KB) zu nehmen und sie in größere Speicherpools zu gruppieren. Wenn Sie beispielsweise 16 Bytes zuweisen, malloc()versuchen Sie zunächst, 16 Bytes aus einem seiner Pools herauszuholen, und fordern Sie dann mehr Speicher vom Kernel an, wenn der Pool trocken läuft. Da das Programm, nach dem Sie fragen, jedoch gleichzeitig eine große Menge an Speicher reserviert malloc()und calloc()nur direkt vom Kernel nach diesem Speicher fragt. 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 den tatsächlichen RAM zuzuweisen und sicherzustellen, dass Prozesse den Speicher anderer Prozesse nicht beeinträchtigen. Dies wird als Speicherschutz bezeichnet, ist seit den 1990er Jahren häufig anzutreffen und der Grund, warum ein Programm abstürzen kann, ohne das gesamte System herunterzufahren. Wenn ein Programm also mehr Speicher benötigt, kann es nicht nur den Speicher belegen, sondern fordert den Speicher mithilfe eines Systemaufrufs wie mmap()oder vom Kernel an sbrk(). Der Kernel gibt jedem Prozess RAM, indem er die Seitentabelle ändert.

Die Seitentabelle ordnet Speicheradressen dem tatsächlichen physischen RAM zu. Die Adressen Ihres Prozesses, 0x00000000 bis 0xFFFFFFFF auf einem 32-Bit-System, sind kein realer Speicher, sondern Adressen im virtuellen Speicher. Der Prozessor unterteilt diese Adressen in 4 KiB-Seiten, und jede Seite kann durch Ändern der Seitentabelle einem anderen physischen RAM zugewiesen werden. Nur der Kernel darf die Seitentabelle ändern.

Wie es nicht funktioniert

So funktioniert das Zuweisen von 256 MiB nicht :

  1. Ihr Prozess ruft an calloc()und fordert 256 MiB an.

  2. Die Standardbibliothek ruft an mmap()und fordert 256 MiB an.

  3. Der Kernel findet 256 MiB nicht verwendeten RAM und gibt ihn durch Ändern der Seitentabelle an Ihren Prozess weiter.

  4. Die Standardbibliothek setzt den RAM auf Null memset()und kehrt von zurück 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 so. Es gibt drei Hauptunterschiede.

  • 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 verloren gehen, bereinigt der Kernel immer den Speicher, bevor er an einen Prozess übergeben wird. Wir können den Speicher genauso gut bereinigen, indem wir ihn auf Null setzen, und wenn der neue Speicher auf Null gesetzt wird, können wir ihn auch als Garantie festlegen, um mmap()sicherzustellen, dass der neue Speicher, den er zurückgibt, immer auf Null gesetzt wird.

  • Es gibt viele Programme, die Speicher zuweisen, den Speicher jedoch 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, was dorthin gehen soll, und verspricht, dass RAM dort abgelegt wird, falls Ihr Programm ihn jemals tatsächlich verwendet. Wenn Ihr Programm versucht, von diesen Adressen zu lesen oder zu schreiben, löst der Prozessor einen Seitenfehler aus, und der Kernel weist diesen Adressen RAM zu und setzt Ihr Programm fort. Wenn Sie den Speicher nie verwenden, tritt der Seitenfehler nie auf und Ihr Programm erhält nie den RAM.

  • Einige Prozesse weisen Speicher zu und lesen ihn dann aus, ohne ihn zu ändern. Dies bedeutet, dass viele Seiten im Speicher über verschiedene Prozesse hinweg mit makellosen Nullen gefüllt sein 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-KB-Speicherseite verweisen, 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 greift ein, um eine neue Seite mit Nullen zu erhalten, die nicht mit anderen Programmen geteilt wird.

Der letzte Prozess sieht eher so aus:

  1. Ihr Prozess ruft an calloc()und fordert 256 MiB an.

  2. Die Standardbibliothek ruft an mmap()und fordert 256 MiB an.

  3. Der Kernel findet 256 MiB nicht verwendeten Adressraums, notiert, wofür dieser Adressraum jetzt verwendet wird, und gibt ihn zurück.

  4. Die Standardbibliothek weiß, dass das Ergebnis von mmap()immer mit Nullen gefüllt ist (oder wird, sobald es tatsächlich RAM erhält), so dass es den Speicher nicht berührt, so dass kein Seitenfehler vorliegt 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 nicht zugewiesen wurde.

Wenn Sie memset()die Seite auf Null setzen, memset()wird der Seitenfehler ausgelöst, der RAM wird zugewiesen und dann auf Null gesetzt, obwohl er bereits mit Nullen gefüllt ist. Dies ist eine enorme Menge an zusätzlicher Arbeit und erklärt, warum calloc()es schneller als malloc()und ist memset(). Wenn am Ende sowieso der Speicher verwendet wird, 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 haben 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 anspruchsvolle Speicherverwaltungseinheit einfach zu klein sind.

Dies funktioniert auch bei kleineren Zuordnungen nicht immer. Ruft bei kleineren Zuordnungen calloc()Speicher aus einem gemeinsam genutzten Pool ab, anstatt direkt zum Kernel zu wechseln. Im Allgemeinen werden im gemeinsam genutzten Pool möglicherweise Junk-Daten aus dem alten Speicher gespeichert, der verwendet und freigegeben free()wurde. calloc()Daher kann dieser Speicher verwendet und aufgerufen werden memset(), um ihn zu löschen. Bei allgemeinen Implementierungen wird nachverfolgt, welche Teile des gemeinsam genutzten Pools makellos und immer noch mit Nullen gefüllt sind. Dies ist jedoch nicht bei allen Implementierungen der Fall.

Einige falsche Antworten zerstreuen

Abhängig vom Betriebssystem kann der Kernel in seiner Freizeit den Arbeitsspeicher auf Null setzen oder nicht, falls Sie später einen auf Null gesetzten Speicher benötigen. Linux stellt den Speicher nicht im Voraus auf Null, und Dragonfly BSD hat diese Funktion kürzlich ebenfalls aus dem Kernel entfernt . Einige andere Kernel haben jedoch vorzeitig keinen Speicherplatz. Das Nullstellen von Seiten im Leerlauf reicht ohnehin nicht aus, um die großen Leistungsunterschiede zu erklären.

Die calloc()Funktion verwendet keine spezielle speicherausgerichtete Version von memset(), und das würde sie sowieso nicht viel schneller machen. Die meisten memset()Implementierungen für moderne Prozessoren sehen ungefähr 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

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

Die Tatsache, memset()dass der bereits auf Null gesetzte Speicher auf Null gesetzt wird, bedeutet, dass der Speicher zweimal auf Null gesetzt wird, was jedoch nur einen zweifachen Leistungsunterschied erklärt. Der Leistungsunterschied ist hier viel größer (ich habe auf meinem System zwischen malloc()+memset()und mehr als drei Größenordnungen gemessen calloc()).

Partytrick

Schreiben Sie statt einer 10-fachen Schleife ein Programm, das Speicher bis malloc()oder calloc()NULL zurückgibt.

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

Dietrich Epp
quelle
7
@Dietrich: Die Erklärung des virtuellen Speichers von Dietrich über das Betriebssystem, das dieselbe mit Null gefüllte Seite mehrmals 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 näher kommen, da das System in beiden Fällen gezwungen wäre, wirklich unterschiedliche Seiten zuzuweisen.
kriss
1
@kriss: in der Tat, obwohl ein Byte pro 4096 auf der überwiegenden Mehrheit der Systeme ausreicht
Dietrich Epp
Tatsächlich calloc()ist es oft Teil der mallocImplementierungssuite und daher so optimiert, dass beim Abrufen von Speicher kein Aufruf erfolgt . bzerommap
Mirabilos
1
Vielen Dank für die Bearbeitung, fast das hatte ich mir vorgestellt. Früh geben Sie an, immer Calloc anstelle von Malloc + Memset zu verwenden. Bitte geben Sie 1. Standardwert für malloc an. 2. Wenn ein kleiner Teil des Puffers auf Null gesetzt werden muss, setzen Sie diesen Teil 3 in ein Memet. Andernfalls verwenden Sie Calloc. Insbesondere NICHT malloc + memset die gesamte Größe (verwenden Sie dazu calloc) und standardmäßig NICHT alles aufrufen, da dies Dinge wie Valgrind und statische Code-Analysatoren behindert (der gesamte Speicher wird plötzlich initialisiert). Davon abgesehen denke ich, dass das in Ordnung ist.
Mitarbeiter des Monats
5
Obwohl nicht geschwindigkeitsbezogen, callocist es auch weniger fehleranfällig. Das heißt, wo large_int * large_intdies zu einem Überlauf führen würde, wird calloc(large_int, large_int)zurückgegeben NULL, ist jedoch malloc(large_int * large_int)ein undefiniertes Verhalten, da Sie die tatsächliche Größe des zurückgegebenen Speicherblocks nicht kennen.
Dünen
12

Da das Betriebssystem auf vielen Systemen in der freien Verarbeitungszeit den freien Speicher selbstständig auf Null setzt und ihn als sicher markiert, verfügt es calloc()beim Aufrufen calloc()möglicherweise bereits über freien, auf Null gesetzten Speicher.

Chris Lutz
quelle
2
Bist du sicher? Welche Systeme machen das? Ich dachte, dass die meisten Betriebssysteme den Prozessor nur im Leerlauf herunterfahren 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 Epp
@ Dietrich - Ich bin mir nicht sicher. Ich habe es einmal gehört und es schien ein vernünftiger (und einigermaßen einfacher) Weg zu sein, calloc()effizienter zu werden.
Chris Lutz
@Pierreten - Ich kann keine guten Informationen zu calloc()spezifischen Optimierungen finden und habe keine Lust, den libc-Quellcode für das OP zu interpretieren. Können Sie etwas nachschlagen, um zu zeigen, dass diese Optimierung nicht existiert / nicht funktioniert?
Chris Lutz
13
@Dietrich: FreeBSD soll Seiten in Leerlaufzeit auf Null setzen: Siehe die Einstellung vm.idlezero_enable.
Zan Lynx
1
@DietrichEpp Entschuldigung für Necro, aber zum Beispiel macht Windows dies.
Andreas Grapentin
1

Auf einigen Plattformen in einigen Modi initialisiert malloc den Speicher vor der Rückgabe auf einen Wert ungleich Null, sodass die zweite Version den Speicher möglicherweise zweimal initialisieren kann

Stewart
quelle