Wie effizient ist malloc und wie unterscheiden sich Implementierungen?

Wenn ich verwende malloc, wird mallocimmer derselbe Algorithmus verwendet, unabhängig davon, was zugewiesen wird, oder werden die Daten überprüft und ein geeigneter Algorithmus ausgewählt?

Können wir Malloc schneller oder intelligenter machen, indem wir einen effizienteren Algorithmus wählen? In meinen Tests ist das eingebaute offizielle System mallocvon Ubuntu zehnmal langsamer als ein Schulprojekt, wenn meine Testergebnisse korrekt sind. Was ist der Haken? Ich bin überrascht, dass mallocdie Tests so schlecht abschnitten, weil sie optimiert werden sollten. Verwendet es immer den gleichen Algorithmus? Gibt es eine Referenzimplementierung von malloc? Wenn ich nach der Quelle suchen möchte, nach mallocwelcher sollte ich suchen? Die Tests, die ich durchführe, sind die folgenden:

/* returns an array of arrays of char*, all of which NULL */
char ***alloc_matrix(unsigned rows, unsigned columns) {
    char ***matrix = malloc(rows * sizeof(char **));
    unsigned row = 0;
    unsigned column = 0;
    if (!matrix) abort();

    for (row = 0; row < rows; row++) {
        matrix[row] = calloc(columns, sizeof(char *));
        if (!matrix[row]) abort();
        for (column = 0; column < columns; column++) {
            matrix[row][column] = NULL;
        }
    }
    return matrix;
}

/* deallocates an array of arrays of char*, calling free() on each */
void free_matrix(char ***matrix, unsigned rows, unsigned columns) {
    unsigned row = 0;
    unsigned column = 0;
    for (row = 0; row < rows; row++) {
        for (column = 0; column < columns; column++) {
            /*    printf("column %d row %d\n", column, row);*/
            free(matrix[row][column]);
        }
        free(matrix[row]);
    }
    free(matrix);
}


int main(int agrc, char **argv) {

    int x = 10000;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Ist der Test in Ordnung? Ich benutze auch diesen Test:

   for (i = 0; i < 1000000; i++) {
        void *p = malloc(1024 * 1024 * 1024);
        free(p);
   }

• aktualisieren

Dem Kommentar zufolge sollte ich Stücke mit variabler Größe erstellen und in einer anderen Reihenfolge als der Zuweisung freigeben. Deshalb versuche ich:

int main(int agrc, char **argv) {
     int i;
    srand(time(NULL));
    int randomnumber;
    int size = 1024;
    void *p[size];
    for (i = 0; i < size; i++) {
        randomnumber = rand() % 10;
        p[i] = malloc(1024 * 1024 * randomnumber);
    }

    for (i = size-1; i >= 0; i--) {
        free(p[i]);
    }

    int x = 1024;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Dann ist mein benutzerdefiniertes Malloc nicht mehr schneller:

$ time ./gb_quickfit 

real    0m0.154s
user    0m0.008s
sys 0m0.144s
dac@dac-Latitude-E7450:~/ClionProjects/omalloc/openmalloc/overhead$ time ./a.out 

real    0m0.014s
user    0m0.008s
sys 0m0.004s

Der von mir verwendete Algorithmus war:

void *malloc_quick(size_t nbytes) {

    Header *moreroce(unsigned);
    int index, i;
    index = qindex(nbytes);

    /* 
     * Use another strategy for too large allocations. We want the allocation
     * to be quick, so use malloc_first().
     */

    if (index >= NRQUICKLISTS) {
        return malloc_first(nbytes);
    }

    /* Initialize the quick fit lists if this is the first run. */
    if (first_run) {
        for (i = 0; i < NRQUICKLISTS; ++i) {
            quick_fit_lists[i] = NULL;
        }
        first_run = false;
    }


    /*
     * If the quick fit list pointer is NULL, then there are no free memory
     * blocks present, so we will have to create some before continuing.
     */

    if (quick_fit_lists[index] == NULL) {
        Header* new_quick_fit_list = init_quick_fit_list(index);
        if (new_quick_fit_list == NULL) {
            return NULL;
        } else {
            quick_fit_lists[index] = new_quick_fit_list;
        }
    }

    /*
     * Now that we know there is at least one free quick fit memory block,
     * let's use return that and also update the quick fit list pointer so that
     * it points to the next in the list.
     */

    void* pointer_to_return = (void *)(quick_fit_lists[index] + 1);
    quick_fit_lists[index] = quick_fit_lists[index]->s.ptr;
   /* printf("Time taken %d seconds %d milliseconds", msec/1000, msec%1000);*/
    return pointer_to_return;
}

Es gibt mehrere Implementierungen von mallocund sie können sehr unterschiedliche Algorithmen verwenden. Zwei sehr weit verbreitete Implementierungen sind jemalloc und dlmalloc . In beiden Fällen enthalten die Links viele Informationen über den Denkprozess und die Kompromisse, die bei einem Allzweck-Allokator eingegangen werden.

Bedenken Sie, dass eine mallocImplementierung nur sehr wenige Informationen enthält, nur die Größe der angeforderten Zuweisung. Eine freeImplementierung hat nur den Zeiger und alle Daten, die 'malloc' möglicherweise heimlich angehängt hat. Als solches gibt es eine ganze Reihe von Heuristiken, dh inspirierte Vermutungen bei der Entscheidung, wie zuzuweisen und die Zuordnung aufzuheben.

Einige Probleme, die ein Allokator angehen muss, sind:

1. Ausrichtung - Einige Speicherausrichtungen sind schneller als andere
2. Fragmentierung - naive Zuordnung und Befreiung können Löcher hinterlassen, die Aufblähen verursachen
3. Leistung - Die Rückkehr zum Betriebssystem für mehr Speicher kann teuer sein
4. Häufige Anforderungen - In der Praxis führen Anwendungen (insbesondere C ++) häufig viele kleine Zuweisungen durch, sodass es sehr hilfreich sein kann, diese effizient zu gestalten

Wenn Sie all dies berücksichtigen, werden Sie feststellen, dass die Allokatoren in der Regel komplexe Softwareteile sind, sodass sie im allgemeinen Gebrauch eine gute Leistung erbringen. In bestimmten Fällen ist es jedoch möglicherweise besser, den Speicher außerhalb des Allokators zu verwalten, wenn Sie viel mehr über die Struktur der Daten wissen. Offensichtlich ist der Nachteil, dass Sie die Arbeit selbst erledigen müssen.

Wenn Sie sich nur für Effizienz interessieren , finden Sie hier eine standardkonforme und sehr effiziente Implementierung :

void* malloc(size_t sz) {
  errno = ENOMEM;
  return NULL;
}

void free(void*p) {
  if (p != NULL) abort();
}

Ich bin mir ziemlich sicher, dass Sie nicht schneller finden werden malloc.

Diese Implementierung entspricht zwar weiterhin dem Standard, ist jedoch nutzlos (sie weist niemals erfolgreich Heapspeicher zu). Es ist eine Scherzimplementierung.

Dies zeigt, dass in der realen Welt malloc& freeImplementierungen Kompromisse eingehen müssen . Und verschiedene Implementierungen machen verschiedene Kompromisse. Sie finden viele Tutorials zu Malloc-Implementierungen . Um Speicherlecks in Ihren C-Programmen zu beheben , sollten Sie valgrind verwenden .

Beachten Sie, dass auf Linux - Systemen zumindest, (fast) alle C - Standardbibliotheken sind freie Software , so dass Sie studieren , ihren Quellcode (insbesondere eine für malloc& free). musl-libc hat einen sehr gut lesbaren Quellcode.

Übrigens ist der Code in Ihrer Frage falsch (und stürzt mit meinem mallocoben genannten ab). Jeder Aufruf von malloc kann fehlschlagen, und das sollten Sie testen.

Vielleicht möchten Sie Advanced Linux Programming und etwas allgemeineres Material über Betriebssysteme lesen , z. B. Betriebssysteme: drei einfache Teile .

Sie sollten wahrscheinlich etwas über die Speicherbereinigung lesen , um zumindest die wichtigsten Konzepte und Begriffe zu erhalten. Vielleicht durch Lesen des GC-Handbuchs . Beachten Sie, dass die Referenzzählung als eine Form der GC angesehen werden kann (eine schlechte, die Referenzzyklen oder zyklische Diagramme nicht gut handhabt ...).

Vielleicht möchten Sie in Ihrem C-Programm den konservativen Garbage Collector von Boehm verwenden : Sie würden dann GC_MALLOC(oder für Daten ohne Zeiger wie Zeichenfolgen oder numerische Arrays GC_MALLOC_ATOMIC) anstelle von verwenden mallocund Sie werden sich nicht mehr darum kümmern, aufzurufen free. Bei der Verwendung von Boehms GC gibt es einige Einschränkungen. Sie könnten andere GC-Schemata oder Bibliotheken in Betracht ziehen ...

NB: Um den Fehler von malloc auf einem Linux-System zu testen ( mallocmanchmal werden die Systemaufrufe mmap (2) und / oder sbrk (2) unter Linux aufgerufen , um den virtuellen Adressraum zu vergrößern , aber meistens wird versucht, zuvor freed-Speicher wiederzuverwenden ). Sie können setrlimit (2) entsprechend mit RLIMIT_ASund / oder RLIMIT_DATAhäufig über die ulimitin Ihrer Terminal-Shell integrierte Bash aufrufen. Verwenden Sie strace (1) , um die Systemaufrufe herauszufinden, die von Ihrem (oder einem anderen) Programm ausgeführt werden.

Erstens arbeiten Malloc und Free zusammen, sodass es irreführend ist, Malloc selbst zu testen . Zweitens, egal wie gut sie sind, können sie leicht die dominierenden Kosten in jeder Anwendung sein, und die beste Lösung dafür ist, sie weniger zu nennen. Weniger zu nennen ist fast immer der beste Weg, um Programme zu reparieren, die malloc-begrenzt sind . Ein üblicher Weg, dies zu tun, besteht darin, gebrauchte Objekte zu recyceln. Wenn Sie mit einem Block fertig sind, anstatt frei es -ing, ketten Sie es auf einem verwendeten Blockstapel und wiederverwenden es das nächste Mal , wenn Sie ein benötigen.

Das Hauptproblem bei Ihrer malloc_quick()Implementierung ist, dass sie nicht threadsicher ist. Und ja, wenn Sie die Thread-Unterstützung in Ihrem Allokator weglassen, können Sie einen signifikanten Leistungsgewinn erzielen. Ich habe eine ähnliche Beschleunigung mit meinem eigenen nicht threadsicheren Allokator gesehen.

Eine Standardimplementierung muss jedoch threadsicher sein. Es muss Folgendes berücksichtigen:

• Verschiedene Threads verwenden malloc()und free()gleichzeitig. Dies bedeutet, dass die Implementierung ohne interne Synchronisierung nicht auf den globalen Status zugreifen kann.

  Da Sperren sehr teuer sind, malloc()versuchen typische Implementierungen, die Verwendung des globalen Status so weit wie möglich zu vermeiden, indem für fast alle Anforderungen threadlokaler Speicher verwendet wird.

• Ein Thread, der einen Zeiger zuweist, ist nicht unbedingt der Thread, der ihn freigibt. Dafür muss gesorgt werden.

• Ein Thread kann ständig Speicher zuweisen und ihn an einen anderen Thread weitergeben, um ihn freizugeben. Dies erschwert die Behandlung des letzten Punkts erheblich, da sich freie Blöcke in jedem threadlokalen Speicher ansammeln können. Dies zwingt die malloc()Implementierung dazu, Mittel für die Threads bereitzustellen, um freie Blöcke auszutauschen, und erfordert wahrscheinlich von Zeit zu Zeit das Ergreifen von Sperren.

Wenn Sie sich nicht für Threads interessieren, sind all diese Punkte überhaupt keine Probleme, sodass ein nicht threadsicherer Allokator nicht für die Behandlung mit Leistung bezahlen muss. Aber wie gesagt, eine Standardimplementierung kann diese Probleme nicht ignorieren und muss folglich für ihre Behandlung bezahlen.

Ich denke, dass die beiden SUT keine direkten Vergleiche sind. Ich wäre nicht überrascht über einen vergleichbaren Unterschied, wenn Sie alle Variablen berücksichtigen: Speicherherstellung, Motherboard-Architektur, Compiler-Version (das kompilierte Malloc), wie die Speicherplatzanwendung auf dem SUT zu der Zeit aussieht, etc etc etc ... .... Versuchen Sie, Ihr Testkabel zu verwenden, um repräsentativer zu sein, wie Sie Speicher in einem realen Projekt verwenden würden - mit einigen großen / kleinen Zuordnungen und einigen Anwendungen, die lange gehalten wurden, und einigen, die kurz nach der Aufnahme freigegeben wurden.

Wenn Sie eine echte Malloc-Implementierung mit einem Schulprojekt vergleichen, müssen Sie berücksichtigen, dass ein echtes Malloc Zuweisungen, Neuzuweisungen und die Freigabe von Speicher in sehr unterschiedlichen Größen verwalten muss. Dies funktioniert ordnungsgemäß, wenn Zuweisungen auf verschiedenen Threads gleichzeitig erfolgen und die Neuzuweisung und Freigabe von Speicher auf verschiedenen Threads erfolgen . Sie möchten auch sicherstellen, dass jeder Versuch, Speicher freizugeben, der nicht mit malloc zugewiesen wurde, abgefangen wird. Stellen Sie schließlich sicher, dass Sie nicht mit einer Debugging-Malloc-Implementierung vergleichen.