Heap-manager efficiente per churn pesanti, piccoli allci?

Question

Sto cercando idee per un heap-manager per gestire una situazione molto specifica: molte e molte allocazioni molto piccole, che vanno da 12 a 64 byte ciascuna. Qualcosa di più grande, passerò al normale gestore di heap, quindi dovranno essere soddisfatti solo piccoli blocchi. È necessario solo un allineamento a 4 byte.

Le mie preoccupazioni principali sono

1. Overhead. L'heap di libc normale in genere arrotonda un'allocazione a un multiplo di 16 byte, quindi aggiunge un'altra intestazione di 16 byte - questo significa un overhead del 50% su un'allocazione di 20 byte, che fa schifo.
2. Prestazioni

Un aspetto utile è che Lua (che è l'utente di questo heap) ti dirà la dimensione del blocco che sta liberando quando chiama free () - questo potrebbe abilitare alcune ottimizzazioni.

Pubblicherò il mio approccio attuale, che funziona bene, ma mi piacerebbe migliorarlo se possibile. Qualche idea?

Answer 1

È possibile creare un gestore di heap molto efficiente per oggetti della stessa dimensione. Puoi creare uno di questi heap per ogni dimensione di oggetto di cui hai bisogno o, se non ti dispiace usare un po 'di spazio, crearne uno per oggetti a 16 byte, uno per 32 e uno per 64. Il sovraccarico massimo sarebbe 31 byte per un'allocazione di 33 byte (che andrebbe sull'heap a 64 blocchi).

Answer 2

Per espandere ciò che dice Greg Hewgill, un modo per fare un heap a dimensione fissa ultra efficiente è:

1. Dividi un grosso buffer in nodi. La dimensione del nodo deve essere almeno sizeof (void *).
2. Stringili insieme in un elenco collegato singolarmente ("elenco libero"), usando i primi byte size (void *) di ciascun nodo libero come puntatore di collegamento. I nodi allocati non avranno bisogno di un puntatore di collegamento, quindi l'overhead per nodo è 0.
3. Allocare rimuovendo la testa dell'elenco e restituendola (2 carichi, 1 negozio).
4. Gratuito inserendo in testa all'elenco (1 caricamento, 2 negozi).

Ovviamente anche il passaggio 3 deve verificare se l'elenco è vuoto e in tal caso un sacco di lavoro ottiene un nuovo buffer di grandi dimensioni (o fallisce).

Ancora più efficiente, come dicono Greg D e hazzen, è quello di allocare incrementando o decrementando un puntatore (1 caricamento, 1 archivio) e non offrire affatto un modo per liberare un singolo nodo.

Modifica: in entrambi i casi, gratuito può gestire la complicazione "qualsiasi cosa più grande che passo sul normale gestore di heap" dal fatto utile che si ottiene gratuitamente la dimensione della chiamata. Altrimenti guarderesti una bandiera (sovraccarico probabilmente 4 byte per nodo) oppure una ricerca in una specie di record del buffer che hai usato.

Answer 3

La risposta può dipendere dai modelli di durata di questi oggetti. Se gli oggetti vengono tutti istanziati mentre procedi, e poi tutti rimossi in un colpo solo, può avere senso creare un gestore heap molto semplice che alloca la memoria semplicemente incrementando un puntatore. Quindi, quando hai finito, soffia via l'intero mucchio.

Raymond Chen ha pubblicato un post interessante che può aiutarti a ispirarti. :)

Answer 4

Mi piace la risposta di onebyones.

Potresti anche prendere in considerazione il buddy system per i tuoi set di heap di dimensioni fisse.

Answer 5

Se un gruppo di memoria viene allocato, utilizzato e liberato prima di passare al prossimo round di allocazione, suggerirei di utilizzare l'allocatore più semplice possibile:

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

Uso principalmente un O (1) Small Block Memory Manager (SBMM). Fondamentalmente funziona in questo modo:

1) Alloca i SuperBlock più grandi dal sistema operativo e tiene traccia degli indirizzi Start + End come intervallo. La dimensione del SuperBlock è regolabile, ma 1 MB rende abbastanza buona.

2) I Superblocchi sono suddivisi in Blocchi (anche regolabili in dimensioni ... 4K-64K è buono a seconda della tua app). Ciascuno di questi blocchi gestisce le allocazioni di una dimensione specifica e memorizza tutti gli elementi nel blocco come un elenco collegato singolarmente. Quando si assegna un SuperBlock, si crea un elenco collegato di blocchi gratuiti.

3) Allocare un Articolo significa A) Controllare per vedere se c'è un Blocco con Oggetti Gratis che gestisce quella dimensione - e in caso contrario, allocare un nuovo Blocco dai Superblocchi. B) Rimozione dell'elemento dall'elenco gratuito del blocco.

4) Liberare un oggetto per indirizzo significa A) Trovare SuperBlock contenente l'indirizzo (*) B) Trovare il blocco in SuperBlock (sottrarre l'indirizzo iniziale del SuperBlock e dividerlo per dimensione del blocco) C) Riportare l'elemento nell'elenco di oggetti liberi del blocco.

/ p>

Come ho detto, questo SBMM è molto veloce in quanto funziona con prestazioni O (1) (*). Nella versione che ho implementato, utilizzo AtomicSList (simile a SLIST in Windows) in modo che non siano solo le prestazioni O (1), ma anche ThreadSafe e LockFree nell'implementazione. In realtà potresti implementare l'algoritmo usando Win32 SLIST se lo desideri.

È interessante notare che l'algoritmo per l'allocazione di blocchi dai Superblocchi o elementi dai blocchi produce un codice quasi identico (entrambi sono allocazioni O (1) da un elenco gratuito).

(*) I Superblocchi sono disposti in una mappa di mappe con prestazioni medie O (1) (ma una potenziale O (Lg N) per il peggior caso in cui N è il numero di Superblocchi). L'ampiezza della gamma di mappe dipende dalla conoscenza approssimativa della quantità di memoria necessaria per ottenere le prestazioni O (1). Se si supera, si spreca un po 'di memoria ma si ottengono comunque prestazioni O (1). Se effettui il downhoot, ti avvicinerai alle prestazioni di O (Lg N) ma N è per il conteggio di SuperBlock, non per il conteggio degli oggetti. Poiché il conteggio di SuperBlock è molto basso rispetto al conteggio degli oggetti (di circa 20 ordini binari di grandezza nel mio codice), non è così critico come il resto dell'allocatore.