¿Qué tan eficiente es malloc y cómo difieren las implementaciones?

Si lo uso malloc, ¿ mallocusa siempre el mismo algoritmo independientemente de lo que esté asignando o mira los datos y selecciona un algoritmo apropiado?

¿Podemos hacer malloc más rápido o más inteligente eligiendo un algoritmo más eficiente? En mis pruebas, el sistema oficial incorporado mallocde Ubuntu es 10 veces más lento que un proyecto escolar si los resultados de mi prueba son correctos. ¿Cuál es la trampa? Me sorprende que haya mallocfuncionado tan mal en las pruebas porque debería optimizarse. ¿Utiliza siempre el mismo algoritmo? ¿Hay una implementación de referencia de malloc? Si quiero ver la fuente malloc, ¿cuál debo mirar? Las pruebas que ejecuto son las siguientes:

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

¿Está bien la prueba? También uso esta prueba:

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

• actualizar

De acuerdo con el comentario, debería hacer trozos de tamaño variable y libres en un orden diferente al de asignación, así que intento:

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

Entonces mi malloc personalizado ya no es más rápido:

$ 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

El algoritmo que utilicé fue:

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

Existen múltiples implementaciones de mallocy pueden usar algoritmos muy diferentes. Dos implementaciones muy utilizadas son jemalloc y dlmalloc . En ambos casos, los enlaces tienen mucha información sobre el proceso de pensamiento y las compensaciones realizadas en un asignador de propósito general.

Tenga en cuenta que una mallocimplementación tiene muy poca información para continuar, solo el tamaño de la asignación solicitada. Una freeimplementación solo tiene el puntero y cualquier dato que 'malloc' pueda haberle asignado en secreto. Como tal, termina habiendo una buena cantidad de heurísticas, es decir, conjeturas inspiradas al decidir cómo asignar y desasignar.

Algunos problemas que un asignador necesita abordar son:

1. alineación: algunas alineaciones de memoria son más rápidas que otras
2. fragmentación: la asignación ingenua y la liberación pueden dejar agujeros que causan hinchazón
3. rendimiento: volver al sistema operativo para obtener más memoria puede ser costoso
4. Solicitudes comunes: en la práctica, las aplicaciones (especialmente C ++) a menudo hacen muchas asignaciones pequeñas, por lo que hacerlas eficientes puede ayudar mucho

Teniendo todo esto en cuenta, lo que encontrará es que los asignadores tienden a ser piezas complejas de software para que, en general, funcionen bien. Sin embargo, en casos específicos, puede ser mejor administrar la memoria fuera del asignador si sabe mucho más sobre la estructura de los datos. Obviamente, el inconveniente es que debe hacer el trabajo usted mismo.

Si solo le importa la eficiencia, aquí hay una implementación estándar y muy eficiente :

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

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

Estoy bastante seguro de que no encontrarás más rápido malloc.

Pero si bien sigue cumpliendo con el estándar, esa implementación es inútil (nunca asigna con éxito ninguna memoria de almacenamiento dinámico). Es una implementación de broma.

Esto ilustra que en el mundo real, mallocy las freeimplementaciones necesitan hacer compensaciones . Y varias implementaciones están haciendo varias compensaciones. Encontrarás muchos tutoriales sobre implementaciones de malloc . Para depurar fugas de memoria en sus programas en C, querrá usar valgrind .

Tenga en cuenta que al menos en los sistemas Linux, (casi) todas las bibliotecas estándar de C son software libre , por lo que puede estudiar su código fuente (en particular, el de malloc& free). musl-libc tiene un código fuente muy legible.

Por cierto, el código en su pregunta es incorrecto (y se bloqueará con mi mallocanterior). Cada llamada a malloc puede fallar, y debe probar eso.

Es posible que desee leer la Programación avanzada de Linux y algunos materiales más generales sobre los sistemas operativos, por ejemplo , Sistemas operativos: tres piezas fáciles .

Probablemente debería leer algo sobre la recolección de basura , al menos para obtener los conceptos principales y la terminología; quizás leyendo el manual de GC . Tenga en cuenta que el recuento de referencias se puede ver como una forma de GC (una pobre, que no maneja bien los ciclos de referencia o los gráficos cíclicos ...).

Es posible que desee utilizar en su programa C el recolector de basura conservador de Boehm : luego usaría GC_MALLOC(o, para datos sin punteros como cadenas o matrices numéricas GC_MALLOC_ATOMIC) en lugar de mallocy no se molestará freemás en llamar . Hay algunas advertencias al usar el GC de Boehm. Puede considerar otros esquemas o bibliotecas de GC ...

NB: para probar el error de malloc en un sistema Linux (a mallocveces se llama a las llamadas del sistema mmap (2) y / o sbrk (2) en Linux para aumentar el espacio de direcciones virtuales , pero la mayoría de las veces trata de reutilizar freed memoria anteriormente ) , puede llamar a setrlimit (2) adecuadamente con RLIMIT_ASy / o RLIMIT_DATA, a menudo a través del ulimitbash incorporado de su terminal. Use strace (1) para averiguar las llamadas al sistema realizadas por su (o algún otro) programa.

Primero, malloc y free trabajan juntos, por lo que probar malloc por sí solo es engañoso. En segundo lugar, no importa cuán buenos sean, pueden ser fácilmente el costo dominante en cualquier aplicación, y la mejor solución es llamarlos menos. Llamarlos menos es casi siempre la forma ganadora de arreglar programas que están limitados por malloc . Una forma común de hacer esto es reciclar objetos usados. Cuando haya terminado con un bloque, en lugar de liberarlo , lo encadenará en una pila de bloques usados ​​y lo reutilizará la próxima vez que lo necesite.

El principal problema con su malloc_quick()implementación es que no es seguro para subprocesos. Y sí, si omite el soporte de subprocesos de su asignador, puede lograr una ganancia de rendimiento significativa. He visto una aceleración similar con mi propio asignador no seguro para subprocesos.

Sin embargo, una implementación estándar debe ser segura para subprocesos. Debe tener en cuenta todo lo siguiente:

• Diferentes hilos de uso malloc()y al free()mismo tiempo. Eso significa que la implementación no puede acceder al estado global sin sincronización interna.

  Dado que los bloqueos son realmente caros, las malloc()implementaciones típicas intentan evitar el uso del estado global tanto como sea posible mediante el uso de almacenamiento local de subprocesos para casi todas las solicitudes.

• Un hilo que asigna un puntero no es necesariamente el hilo que lo libera. Esto tiene que ser atendido.

• Un subproceso puede asignar memoria constantemente y pasarlo a otro subproceso para liberarlo. Esto hace que el manejo del último punto sea mucho más difícil, porque significa que pueden acumularse bloques libres dentro de cualquier almacenamiento local de subprocesos. Esto obliga a la malloc()implementación a proporcionar medios para que los subprocesos intercambien bloques libres, y probablemente requiera agarrar los bloqueos de vez en cuando.

Si no le importan los subprocesos, todos estos puntos no son ningún problema, por lo que un asignador no seguro para subprocesos no tiene que pagar por su manejo con rendimiento. Pero, como dije, una implementación estándar no puede ignorar estos problemas y, en consecuencia, tiene que pagar por su manejo.

Creo que los dos SUT no son comparaciones directas. No me sorprendería ninguna diferencia comparable si considera todas las variables: fabricación de memoria, arquitectura de la placa base, versión del compilador (que compiló malloc), cómo es la aplicación de espacio de memoria en el SUT en ese momento, etc., etc. .... Intente usar su arnés de prueba para ser más representativo de cómo usaría la memoria en un proyecto real, con algunas asignaciones grandes / pequeñas, y algunas aplicaciones retenidas durante mucho tiempo y algunas liberadas poco después de ser tomadas.

Si compara una implementación real de malloc con un proyecto escolar, considere que un malloc real debe administrar asignaciones, reasignaciones y liberar memoria de tamaños muy diferentes, funcionando correctamente si las asignaciones ocurren en diferentes hilos simultáneamente, y la reasignación y la liberación de memoria ocurren en diferentes hilos . También debe asegurarse de que cualquier intento de liberar memoria que no se asignó con malloc queda atrapado. Y finalmente, asegúrese de no compararlo con una implementación de depuración de malloc.