¿Malloc personalizado para muchos bloques pequeños de tamaño fijo?

Question

Necesito asignar, y liberar muchos bloques de tamaño fijo, pequeños (16 bytes) de memoria, en un orden no fijo. Podría llamar malloc y gratis para cada uno, pero probablemente sea muy ineficiente. Una mejor solución probablemente sería llamar a malloc y liberar bloques más grandes, y manejar la asignación dentro de esos bloques.

La pregunta es, ¿cuál es la mejor manera de hacerlo?

Parece que esto no debería ser un problema muy raro o un problema raro, y que debería haber sido "resuelto", pero parece que no puedo encontrar nada. ¿Alguna sugerencia?

Para aclarar, soy consciente de que las bibliotecas del grupo de memoria, y lo que no existe, pero también tienen un parámetro de tamaño. Si el tamaño es constante, existen diferentes opciones para algoritmos más eficientes, ¿hay alguna implementación de estos?

Answer 1

Antes de emprender la onerosa tarea de volver a escribir malloc, se aplica la recomendación estándar. ¡Haz un perfil de tu código y asegúrate de que esto sea realmente un problema!

Answer 2

La mejor manera de hacerlo es no asumir que será ineficiente. En cambio, pruebe la solución con malloc, mida el rendimiento y demuestre que es eficiente o no. Entonces, una vez que se proporciona para ser ineficiente (probablemente no lo será) es el único momento en que debe pasar a un asignador personalizado. Sin la prueba, nunca sabrá si su solución es realmente más rápida o no.

Answer 3

Lo que está buscando se llama grupo de memoria. Existen implementaciones existentes, aunque no es difícil (y una buena práctica) hacer las suyas propias.

La implementación más simple para un conjunto de datos del mismo tamaño es simplemente un contenedor que contiene un búfer de n * tamaño y una pila de n punteros. "malloc" del grupo muestra el puntero en la parte superior. "libre" para el grupo coloca el puntero en la pila.

Answer 4

para su requisito su asignador personalizado sería realmente simple. simplemente actualice una memoria de matriz grande

calloc(N * 16) 

y luego puede simplemente distribuir las entradas de la matriz. para poder rastrear qué ubicaciones de las matrices están en uso, puede usar un mapa de bits simple y luego, con algunas operaciones de bits inteligentes y la substracción del puntero, sus operaciones personalizadas de malloc/free deberían ser bastante fáciles. si se queda sin espacio puede simplemente realloc un poco más, pero tener un valor predeterminado fijo adecuado sería un poco más fácil.

aunque en realidad solo deberías usar malloc primero. malloc crea grupos de bloques de memoria libres de diferentes tamaños, apostaría a que hay un grupo para bloques de memoria de 16 bytes (diferentes implementaciones pueden o no hacer esto pero es una optimización bastante común) y dado que todas las asignaciones son del mismo tamaño de fragmentación no debería ser un problema. (además de la depuración de su asignador podría ser un poco una pesadilla.)

Answer 5

Tienes razón, es un problema común [Es decir: cómo hacer la asignación de tamaño fijo, quiero decir. "malloc está ralentizando mi aplicación" es menos común de lo que crees].

Si su código es demasiado lento y malloc es un culpable plausible, entonces un simple asignador de celda (o "grupo de memoria") podría mejorar las cosas. Casi con certeza puede encontrar uno en alguna parte, o es fácil de escribir:

Asigne un bloque grande y coloque un nodo de lista enlazado individualmente al comienzo de cada celda de 16 bytes. Enlazarlos a todos juntos.Para asignar, quitar el encabezado de la lista y devolverlo. Para liberar, agregue la celda al encabezado de la lista. Por supuesto, si intentas asignar y la lista está vacía, entonces debes asignar un nuevo bloque grande, dividirlo en celdas y agregarlas a la lista libre.

Puede evitar ese gran trabajo por adelantado si lo desea. Cuando asigna un bloque grande, simplemente almacene un puntero hasta el final. Para asignar, mueva su puntero hacia atrás 16 bytes a través del bloque y devuelva el nuevo valor. A menos que ya estuviera al comienzo del bloque [*], por supuesto. Si eso sucede, y la lista gratuita también está vacía, necesita un nuevo bloque grande. Gratis no cambia: solo agrega el nodo a la lista gratuita.

Tiene la opción de tratar primero el bloque y consultar la lista gratuita si está agotada, o consultar primero la lista gratuita y ocuparse del bloque si está vacío. No sé cuál tiende a ser más rápido: lo bueno de la lista gratuita de último en entrar es que es compatible con el caché, ya que está usando memoria que se usó recientemente, así que probablemente lo intente. primero.

Tenga en cuenta que el nodo de la lista no es necesario mientras la celda está asignada, por lo que esencialmente hay cero sobrecarga por celda. Aparte de la velocidad, es probable que sea una ventaja sobre malloc, u otros asignadores de propósito general.

Tenga en cuenta que soltar todo el asignador es prácticamente la única forma de liberar memoria al sistema, por lo que los usuarios que planean asignar una gran cantidad de celdas, usarlas y liberarlas, deben crear su propia asignador, úsalo y luego destrúyelo. Tanto para el rendimiento (no es necesario liberar todas las celdas) como para evitar el efecto de fragmentación en el que se debe mantener un bloque completo si alguna de sus celdas está en uso. Si no puede hacer esto, su uso de la memoria será la marca máxima del tiempo que su programa ha estado funcionando. Para algunos programas, eso es un problema (por ejemplo, un programa de larga ejecución con ocasionales picos grandes en el uso de memoria, en un sistema donde la memoria está restringida). Para otros, está absolutamente bien (por ejemplo, si la cantidad de células en uso aumenta hasta casi el final del programa, o fluctúa dentro de un rango en el que realmente no te importa que uses más memoria de la que estrictamente puedes). Para algunos es activamente deseable (si sabes cuánta memoria usarás, puedes asignarla por adelantado y no tener que preocuparte por los fallos). Para el caso, algunas implementaciones de malloc tienen dificultades para liberar memoria del proceso al sistema operativo.

[*] Donde "inicio del bloque" probablemente signifique "el inicio del bloque, más el tamaño de un nodo utilizado para mantener una lista de todos los bloques, para que todos puedan liberarse cuando el asignador de celda sea destruido".

Answer 6

Puede intentar anular malloc/free with an alternative implementation adecuado para muchas asignaciones pequeñas.

Answer 7

Wilson, Johnstone, Neely y Boles escribieron a nice paper surveying all sorts of different allocators.

En mi experiencia, el rendimiento y la diferencia entre los gastos generales de una piscina de buen asignador fijo y sólo confiar en dlmalloc puede ser masiva en los casos en que está haciendo montones y montones de pequeñas asignaciones de corta duración en un espacio de direcciones limitado (como un sistema sin archivo de página). En la aplicación en la que estoy trabajando en este momento, nuestro bucle principal salta de 30ms a> 100ms si reemplazo nuestro asignador de bloque con llamadas simples al malloc() (y eventualmente falla debido a la fragmentación).

Answer 8

El siguiente código es bastante feo, pero el objetivo no es la belleza, sino averiguar qué tan grande es el bloque asignado por malloc.
Pedí 4 bytes, y malloc solicitó y recibió 135160 bytes del sistema operativo.

#include <stdio.h> 
#include <malloc.h> 


int main() 
{ 
    int* mem = (int*) malloc(sizeof(int)) ; 
    if(mem == 0) return 1; 
    long i=1L; 

    while(i) 
    { 
     mem[i-1] = i; 
     printf("block is %d bytes\n", sizeof(int) * i++); 
    }//while 

    free(mem); 
    return 0 ; 
} 

$ g ++ -o file.cpp archivo
$ ./file
...
bloque es 135144 bytes
bloque es 135148 bytes
bloque es 135152 bytes
bloque es 135156 bytes
bloque es 135160 bytes
falla Segmentación

Esta ma lloc es un asunto serio.
realloc no realiza ninguna llamada al sistema si el tamaño solicitado es menor que el disponible debido a la agrupación interna.
Después de que realloc copió la memoria en una zona más grande, no destruye el bloque anterior, no lo devuelve al sistema inmediatamente. Esto todavía se puede acceder (por supuesto totalmente inseguro). Con todo esto, no tiene sentido para mí, alguien necesitaría un grupo de memoria adicional.

Answer 9

Debido al interés académico estaba trabajando en una solución a ese problema hace unos días. La implementación es muy simple pero completa y mencionó que está buscando un reemplazo directo, por lo que creo que mi implementación podría funcionar para usted.

Básicamente funciona como describe patros, excepto que automáticamente solicita más memoria si ya no hay bloques libres. El código fue probado con una gran lista vinculada (alrededor de 6 millones de nodos, cada uno de 16 bytes de tamaño) frente a un esquema ingenuo de malloc()/free() y se realizó aproximadamente un 15% más rápido que eso. Entonces supuestamente es útil para tu intención. Es fácil ajustarlo a diferentes tamaños de bloque, ya que el tamaño de bloque especificado al crear una gran cantidad de memoria.

El código está disponible en GitHub: challoc

Ejemplo de uso:

int main(int argc, char** argv) { 
    struct node { 
      int data; 
     struct node *next, *prev; 
    }; 
    // reserve memory for a large number of nodes 
    // at the moment that's three calls to malloc() 
    ChunkAllocator* nodes = chcreate(1024 * 1024, sizeof(struct node)); 

    // get some nodes from the buffer 
    struct node* head = challoc(nodes); 
    head->data = 1; 
    struct node* cur = NULL; 
    int i; 
    // this loop will be fast, since no additional 
    // calls to malloc are necessary 
    for (i = 1; i < 1024 * 1024; i++) { 
      cur = challoc(nodes); 
     cur->data = i; 
     cur = cur->next; 
    } 

    // the next call to challoc(nodes) will 
    // create a new buffer to hold double 
    // the amount of `nodes' currently holds 

    // do something with a few nodes here 

    // put a single node back into the buffer 
    chfree(nodes,head); 

    // mark the complete buffer as `empty' 
    // this also affects any additional 
    // buffers that have been created implicitly 
    chclear(nodes); 

    // give all memory back to the OS 
    chdestroy(nodes); 

    return 0; 
}