Come posso implementare in modo efficiente l'allocazione dei lotti in una lista freelance?

Question

Come posso implementare in modo efficiente l'allocazione dei lotti in una lista freelance?

#1 da (1 voti)

3

Ho implementato gli allocatori di Andrei Alexandrescu come esercizio, ma mi sono bloccato sul suo Freelist . Il% co_de di Andrei è simile al seguente:

template<class BaseAllocator,
    std::size_t kMinSize,
    std::size_t kMaxSize /* Actual size of each block on the freelist */,
    std::size_t kBatchSize,
    std::size_t kMaxRemembered>
class Freelist
{
    // ...
};

Tutto tranne il Freelist ha un'implementazione chiara per me. Facciamo un esempio specifico:

Freelist<A, 8, 8, 8, someLargeNumber>

In sostanza, una freelist che memorizza blocchi di dimensioni kBatchSize nel suo elenco, ma alloca 8 byte dall'allocatore principale quando viene richiesto di allocare 8*8=64 , inserendo i byte rimanenti nella lista dei risultati.

Alcuni dei miei pensieri su come implementare questo sono i seguenti (supponiamo che 8 sia il numero di blocchi sull'elencare):

Unisciti ai blocchi di memoria adiacenti quando aggiungi blocchi gratuiti alla lista dei preferiti. Questo perde la complessità di n che avevamo in precedenza, e ha anche il problema che è possibile unire blocchi che provengono effettivamente da allocazioni differenti.
Potrei modificare la tecnica precedente per allocare sempre la memoria allineata alla dimensione del batch. Quindi, potrei usare l'allineamento per determinare se due blocchi provengono da allocazioni differenti. Questo ha ancora il problema di complessità e limita O(1) e kMaxSize a potenze di due (come l'allineamento deve essere una potenza di due)
Potrei avere un kBatchSize per memorizzare ulteriori informazioni su un determinato batch. Non mi piace questa idea perché modifica il requisito di memoria da std::vector<Batch, BaseAllocator> a O(1) . I liberi professionisti senza allocazione batch possono essere implementati in quasi nessuna memoria aggiuntiva (un puntatore all'inizio e forse una dimensione dell'elenco)
Potrei richiedere O(n) per essere ciò che chiamerei un "allocatore segmentabile"; cioè, i segmenti di un blocco possono essere deallocati separatamente, o uniti e deallocati insieme. Sebbene ciò renderebbe insignificante l'implementazione di BaseAllocator , questo sembra un requisito troppo grande da inserire in Freelist

Nessuno di questi approcci mi sembra giusto. Se l'allocazione in lotti è una valida ottimizzazione per un elenco a dominio libero, sembra che dovrebbe esserci un modo per implementarlo in BaseAllocator di spazio e tempo.

design c++ memory allocation

posta Justin 13.06.2017 - 20:34

fonte

1 risposta

Leggi altre domande sui tag design c++ memory allocation

Come dovrei unità testare una funzione impura che chiama una serie di metodi? Assegnare un nome a una classe vista

score 1 · Answer 1

Per me, se aggiungerai il supporto "batch" a una lista libera che può anche allocare blocchi più piccoli, il punto non è di allocare il batch più rapidamente dell'assegnazione di kBatchSize elementi individualmente attraverso la lista libera. È avere garanzie di contiguità sul risultato, in quanto sarebbe necessario implementare una piccola sequenza contigua usando ad esempio,

Il lavoro richiesto per l'allocazione e la liberazione da una lista libera è già così banale che non ci sono miglioramenti ragionevoli della velocità per il batching, ma allocare individualmente singoli elementi da una lista libera non ti dà quelle garanzie di contiguità .

Per quanto riguarda l'implementazione ottimale, non posso dirlo, ma potrebbe essere un suggerimento importante. Personalmente preferirei utilizzare l'allocatore principale in questi casi o semplicemente utilizzare una lista separata separata progettata per allocare kMaxSize*kBatchSize byte chunk.

A mio modesto parere, Alexandrescu è un tipo di successo, come nel caso di molti geniali pionieri che spingono i confini di un linguaggio di programmazione. Le sue idee vanno da quelle brillanti e ampiamente applicabili a quelle poco pratiche e poco pratiche. Se dovessi considerare il supporto batch per una lista libera, la prima cosa che considererei è un'altra lista libera o un allocatore diverso a titolo definitivo. Oltre a ciò, un allocatore con 5 parametri di modello è già piuttosto ingombrante da usare. L'idea di poter specificare gli allocatori principali è un'idea meravigliosa che voglio rubare. Non sono così sicuro di specificare dimensioni min / max, dimensioni batch e limiti superiori. Boh, forse mi sbalordirà dimostrando una implementazione super efficiente e semplice che mi sfugge per questo. Al momento non riesco a vederne uno, e ci ho pensato per un'ora da quando ho risposto per la prima volta.

Gran parte della semplicità e dell'enorme velocità delle liste libere derivano dal presupposto restrittivo che si tratta di allocatori a dimensione fissa, non di dimensioni variabili, e che ogni blocco può fungere da unione di memoria utilizzata per l'elemento specifico digita o un puntatore a elenco collegato singolarmente al prossimo blocco libero (per il quale è fondamentale che i blocchi siano della stessa dimensione per banalizzare la logica di deallocation pur consentendo comunque di recuperare la memoria liberata nella sua interezza su allocazioni successive). La capacità di allocare in lotti getta una chiave inglese nel concetto per il quale non penso ci sia alcuna soluzione che possa raggiungere la stessa velocità per tutti i casi di input.

Tentativo

Uffa, questa domanda mi ha fatto riflettere a lungo su di esso oltre a visitare la lavagna e buttare via un'idea dopo idea.

Le uniche idee che ho avuto finora che si avvicinano a essere in grado di raggiungere tutte le operazioni desiderate in un tempo costante con il supporto di allocazione batch in là richiede che i metadati siano associati all'assegnazione e che alcune ipotesi siano fatte su esattamente come la memoria raggruppa i blocchi di lotti da allineare (con enormi allineamenti usati per i pool) per permetterci di passare da un puntatore al blocco verso il pool per ottenere l'accesso ai metadati usando alcune operazioni aritmetiche.

Il sovraccarico della memoria può essere molto piccolo, meno di 1 byte per chunk (solo la lunghezza del batch) a meno che kBatchSize sia enorme (che non dovrebbe essere comunque o dovremmo probabilmente usare l'allocatore principale), ma Richiederà anche un array di kBatchSize di puntatori a testa libera da memorizzare nell'allocatore stesso.

Posso quasi immaginare la soluzione, ma non mi piace dove è diretta perché fornire un supporto batch a una lista libera non è un caso d'uso abbastanza pratico per giustificare tutto questo lavoro (sia mentalmente che computazionalmente) a meno che non ci sia qualcosa di magicamente semplice e bella soluzione che ci elude, che comporta costi zero per i casi comuni.