¿Eficiente gestor de pilas para grandes cambios, pequeñas asignaciones?

Question

Estoy buscando ideas para que un administrador de montón maneje una situación muy específica: muchas y muchas asignaciones muy pequeñas, que van de 12 a 64 bytes cada una. Algo más grande, lo pasaré al administrador de pilas habitual, por lo que solo será necesario atender a pequeños bloques. Solo se necesita una alineación de 4 bytes.

Mis principales preocupaciones son

1. Overhead. La pila regular de libc generalmente redondeará una asignación a un múltiplo de 16 bytes, luego agregará otro encabezado de 16 bytes, lo que significa una sobrecarga de más del 50% en una asignación de 20 bytes, lo que apesta.
2. Rendimiento

Un aspecto útil es que Lua (que es el usuario de este montón) le dirá el tamaño del bloque que está liberando cuando llama a free (), esto puede permitir ciertas optimizaciones.

Publicaré mi enfoque actual, que funciona bien, pero me gustaría mejorarlo si es posible. ¿Alguna idea?

Answer 1

Es posible crear un administrador de almacenamiento dinámico que sea muy eficiente para objetos que sean todos del mismo tamaño. Puede crear uno de estos montones para cada tamaño de objeto que necesite, o si no le importa usar un poco de espacio, cree uno para objetos de 16 bytes, uno para 32 y otro para 64. La sobrecarga máxima sería 31 bytes para una asignación de 33 bytes (que iría en el montón de tamaño de bloque de 64).

Answer 2

Para ampliar lo que dice Greg Hewgill, una forma de hacer un montón de tamaño fijo ultra eficiente es:

1. Divide un búfer grande en nodos. El tamaño del nodo debe ser al menos sizeof (void *).
2. Encadéntelos en una lista enlazada individualmente (la "lista libre"), usando los primeros bytes sizeof (void *) de cada nodo libre como un puntero de enlace. Los nodos asignados no necesitarán un puntero de enlace, por lo que la sobrecarga por nodo es 0.
3. Asigne eliminando el encabezado de la lista y devolviéndolo (2 cargas, 1 tienda).
4. Gratis insertando al principio de la lista (1 carga, 2 tiendas).

Obviamente, el paso 3 también tiene que verificar si la lista está vacía, y si es así, hacer un montón de trabajo para obtener un nuevo búfer grande (o fallar).

Incluso más eficiente, como dicen Greg D y hazzen, es asignar incrementando o disminuyendo un puntero (1 carga, 1 tienda), y no ofrecer una forma de liberar un solo nodo en absoluto.

Editar: En ambos casos, Free puede lidiar con la complicación " cualquier cosa más grande que le pase al administrador de pilas habitual " por el hecho útil de que obtiene el tamaño de nuevo en la llamada para liberar. De lo contrario, estaría viendo una bandera (sobrecarga probablemente de 4 bytes por nodo) o una búsqueda en algún tipo de registro de los búferes que haya utilizado.

Answer 3

La respuesta puede depender de los patrones de vida útil de estos objetos. Si todos los objetos se crean instancias a medida que avanza, y luego todos se eliminan de un solo golpe, puede tener sentido crear un administrador de pila muy simple que asigne memoria simplemente incrementando un puntero. Luego, cuando haya terminado, sople todo el montón.

Raymond Chen hizo un publicación interesante que puede ayudar a inspirarte. :)

Answer 4

Me gusta la respuesta onebyones.

También puede considerar el sistema de amigos para sus conjuntos de montones de tamaño fijo.

Answer 5

Si se asigna, utiliza y libera un montón de memoria antes de pasar a la siguiente ronda de asignación, sugeriría usar el asignador más simple posible:

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}

Answer 6

Utilizo un gestor de memoria de bloques pequeños (SBMM) en su mayoría O (1). Básicamente funciona de esta manera:

1) Asigna SuperBlocks más grandes desde el sistema operativo y rastrea las Direcciones de Inicio y Fin como un rango. El tamaño del SuperBlock es ajustable pero 1MB tiene un tamaño bastante bueno.

2) Los SuperBlocks se dividen en bloques (también de tamaño ajustable ... 4K-64K es bueno dependiendo de su aplicación). Cada uno de estos Bloques maneja las asignaciones de un tamaño específico y almacena todos los elementos en el Bloque como una lista enlazada individualmente. Cuando asignas un SuperBlock, creas una lista enlazada de Free Blocks.

3) Asignar un artículo significa A) Comprobar si hay un bloque con elementos libres que se encarguen de ese tamaño, y si no, asignar un nuevo bloque desde los SuperBlocks. B) Eliminando el artículo de la lista libre del bloque.

4) Liberar un Elemento por dirección significa A) Buscar SuperBlock que contiene la dirección (*) B) Encontrar Bloque en SuperBlock (restar SuperBlock dirección de inicio y dividir por tamaño de Bloque) C) Presionar el elemento nuevamente en la lista de Elementos Libres del Bloque.

Como dije, este SBMM es muy rápido ya que se ejecuta con O (1) rendimiento (*). En la versión que he implementado, uso un AtomicSList (similar a SLIST en Windows) para que no sea solo el rendimiento O (1) sino también ThreadSafe y LockFree en la implementación. Realmente podría implementar el algoritmo utilizando Win32 SLIST si quisiera.

Curiosamente, el algoritmo para asignar Bloques desde los SuperBlocks o Elementos desde los Bloques da como resultado un código casi idéntico (ambos son asignaciones O (1) de una Lista Libre).

(*) Los SuperBlocks se organizan en un rangemap con un rendimiento promedio de O (1) (pero un potencial de O (Lg N) para el peor de los casos donde N es el número de SuperBlocks). El ancho del mapa de rango depende de saber aproximadamente la cantidad de memoria que se necesitará para obtener el rendimiento O (1). Si se excede, desperdiciará un poco de memoria pero seguirá obteniendo el rendimiento O (1). Si subestima, se acercará al rendimiento de O (Lg N), pero la N es para el conteo de SuperBlock, no para el conteo de elementos. Dado que el recuento de SuperBlock es muy bajo en comparación con el recuento de elementos (en aproximadamente 20 órdenes binarias de magnitud en mi código), no es tan crítico como el resto del asignador.