Quanto è efficiente Malloc e in che modo differiscono le implementazioni?

7

Se utilizzo malloc , malloc usa sempre lo stesso algoritmo indipendentemente da ciò che sta allocando o guarda i dati e seleziona un algoritmo appropriato?

Possiamo rendere malloc più veloce o più intelligente scegliendo un algoritmo più efficiente? Nei miei test, il sistema ufficiale incorporato malloc di Ubuntu è 10 volte più lento di un progetto scolastico se i miei risultati dei test sono corretti. Qual è il trucco? Sono sorpreso che malloc abbia funzionato così male nei test perché dovrebbe essere ottimizzato. Utilizza sempre lo stesso algoritmo? Esiste un'implementazione di riferimento di malloc ? Se voglio dare un'occhiata all'origine per malloc , quale dovrei considerare? I test che eseguo sono i seguenti:

/* 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);
}

Il test va bene? Anche io uso questo test:

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

Secondo il commento, dovrei creare blocchi di dimensioni variabili e liberi in ordine diverso da quello di allocazione, quindi provo:

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);
}

Quindi il mio malloc personalizzato non è più veloce:

$ 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

L'algoritmo che ho usato era:

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;
}
    
posta Niklas Rosencrantz 20.05.2016 - 05:53
fonte

6 risposte

11

Esistono più implementazioni di malloc e possono utilizzare algoritmi molto diversi. Due implementazioni molto diffuse sono jemalloc e dlmalloc . In entrambi i casi i collegamenti contengono molte informazioni sul processo di pensiero e sui trade-off effettuati in un allocatore generale.

Ricorda che un'implementazione malloc ha pochissime informazioni da seguire, solo la dimensione dell'allocazione richiesta. Un'implementazione di free ha solo il puntatore e qualsiasi dato "malloc" potrebbe esservi collegato segretamente. In quanto tale, finisce per essere una buona dose di euristiche, vale a dire ispirate congetture nel decidere come allocare e deallocare.

Alcuni problemi che un allocatore deve risolvere sono:

  1. allineamento: alcuni allineamenti di memoria sono più veloci di altri
  2. frammentazione - l'allocazione ingenua e la liberazione possono lasciare buchi che causano ingigantire
  3. prestazioni: tornare al sistema operativo per più memoria può essere costoso
  4. Richieste comuni: in pratica le applicazioni (specialmente il C ++) fanno un sacco di piccole allocazioni, quindi renderle efficienti possono aiutare molto

Tenendo conto di tutto ciò, ciò che scoprirai è che gli allocatori tendono a essere pezzi complessi di software in modo che, nell'uso generale, si comportano bene. Tuttavia, in casi specifici, potrebbe essere meglio gestire la memoria al di fuori dell'allocazione se si conosce molto di più sulla struttura dei dati. Ovviamente il lato negativo è che devi fare il lavoro da solo.

    
risposta data 20.05.2016 - 14:24
fonte
17

Se ti interessa solo in termini di efficienza, ecco una implementazione conforme e molto efficiente :

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

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

Sono abbastanza sicuro che non troverai più velocemente malloc .

Ma pur rimanendo conforme allo standard, quell'implementazione è inutile (non assegna mai correttamente memoria heap). È un'implementazione di scherzo.

Questo dimostra che nel mondo reale, malloc & Le implementazioni free devono rendere trade-off . E varie implementazioni stanno facendo vari compromessi. Troverai molti tutorial su implementazioni malloc . Per eseguire il debug di perdite di memoria nei tuoi programmi in C, ti consigliamo di utilizzare valgrind .

Si noti che su sistemi Linux almeno, (quasi) tutte le librerie standard C sono software gratuito , così puoi studiare il loro codice sorgente (in particolare quello per malloc e free ). musl-libc ha un codice sorgente molto leggibile.

BTW, il codice nella tua domanda è sbagliato (e si bloccherà con il mio malloc sopra). Ogni chiamata a malloc può fallire, e dovresti testarlo.

Puoi leggere Programmazione Linux avanzata e materiale più generale sui sistemi operativi, ad es. Sistemi operativi: tre pezzi facili .

Probabilmente dovresti leggere qualcosa su garbage collection , almeno per ottenere i concetti principali & terminologia; magari leggendo il manuale GC . Nota che il conteggio dei riferimenti può essere visualizzato come una forma di GC (uno scarso, che non gestisce bene riferimento cicli o grafici ciclici ...).

Potresti volerlo usare nel tuo programma C Garbage collector conservatore di Boehm : dovresti usare GC_MALLOC (o, per i dati senza puntatori come stringhe o matrici numeriche, GC_MALLOC_ATOMIC ) invece di malloc e non ti preoccuperai più di chiamare free più. Ci sono alcuni avvertimenti quando si utilizza il GC di Boehm. Potresti prendere in considerazione altri schemi o librerie GC ...

NB: per testare l'errore di malloc su un sistema Linux ( malloc a volte chiama mmap (2) e / o sbrk (2) chiamate di sistema su Linux per far crescere lo spazio di indirizzi virtuali , ma molto spesso cerca di riutilizzare la memoria precedente free d), potresti chiama setrlimit (2) in modo appropriato con RLIMIT_AS e / o RLIMIT_DATA , spesso attraverso il ulimit bash incorporato nella tua shell di terminale. Usa strace (1) per scoprire le chiamate di sistema fatte dal tuo (o da qualche altro ).

    
risposta data 20.05.2016 - 15:53
fonte
4

Innanzitutto, malloc e free funzionano insieme, quindi testare malloc di per sé è fuorviante. In secondo luogo, non importa quanto siano validi, possono facilmente essere il costo dominante in qualsiasi applicazione e la soluzione migliore è chiamarli di meno. Chiamarli di meno è quasi sempre il modo vincente per sistemare programmi malloc -limitati. Un modo comune per farlo è riciclare oggetti usati. Quando hai finito con un blocco, piuttosto che gratuito , lo fai in una pila di blocchi usati e riutilizzalo la prossima volta che ne hai bisogno.

    
risposta data 20.05.2016 - 15:25
fonte
3

Il problema principale con la tua implementazione di malloc_quick() è che non è thread-safe. E sì, se si omette il supporto del thread dal proprio allocatore, è possibile ottenere un significativo aumento delle prestazioni. Ho visto una simile accelerazione con il mio allocatore non thread-safe.

Tuttavia, un'implementazione standard deve essere thread-safe. Deve tenere conto di quanto segue:

  • Diversi thread utilizzano malloc() e free() contemporaneamente. Ciò significa che l'implementazione non può accedere allo stato globale senza sincronizzazione interna.

    Poiché i blocchi sono molto costosi, le tipiche implementazioni malloc() cercano di evitare l'utilizzo dello stato globale il più possibile utilizzando l'archiviazione locale dei thread per quasi tutte le richieste.

  • Un thread che alloca un puntatore non è necessariamente il thread che lo libera. Questo deve essere curato.

  • Un thread può costantemente allocare memoria e passarlo a un altro thread per liberarlo. Ciò rende molto più difficile la gestione dell'ultimo punto, poiché significa che i blocchi liberi possono accumularsi all'interno di qualsiasi storage locale thread. Ciò impone l'implementazione di malloc() per fornire mezzi per i thread per lo scambio di blocchi liberi e, probabilmente, richiede l'acquisizione di blocchi di volta in volta.

Se non ti preoccupi dei thread, tutti questi punti non sono affatto problemi, quindi un allocatore non thread-safe non deve pagare per la loro gestione con le prestazioni. Ma, come ho detto, un'implementazione standard non può ignorare questi problemi e, di conseguenza, deve pagare per la loro gestione.

    
risposta data 21.05.2016 - 10:46
fonte
2

Penso che i due SUT non siano confronti diretti. Non sarei sorpreso di nessuna differenza comparabile considerando tutte le variabili: produzione della memoria, architettura della scheda madre, versione del compilatore (che ha compilato malloc), quale è l'applicazione dello spazio di memoria sul SUT al momento, ecc ecc ecc ... .... Prova a usare la tua imbracatura di test per essere più rappresentativo di come useresti la memoria in un progetto reale - con alcune allocazioni grandi / piccole e alcune applicazioni mantenute per un lungo periodo di tempo e alcune subito dopo essere state riprese.

    
risposta data 20.05.2016 - 09:34
fonte
1

Se si confronta un'implementazione di malloc con un progetto scolastico, si consideri che un malloc reale deve gestire allocazioni, riallocazioni e liberare memoria di dimensioni estremamente diverse, funzionare correttamente se le allocazioni si verificano su thread diversi simultaneamente e la riallocazione e la liberazione della memoria avvengono su fili diversi Si vuole anche essere sicuri che qualsiasi tentativo di liberare memoria non allocata con malloc venga catturato. Infine, assicurati di non confrontare con un'implementazione di malloc di debug.

    
risposta data 20.05.2016 - 19:19
fonte

Leggi altre domande sui tag