suggerimenti per migliorare un'implementazione dell'algoritmo allocatore

Question

Ho un'applicazione Visual Studio 2008 C++ in cui sto utilizzando un allocatore personalizzato per contenitori standard in modo che la loro memoria provenga da un file mappato in memoria anziché dall'heap. Questo allocatore è usato per 4 casi d'uso differenti:

1. 104-byte struttura di dimensioni fisse std::vector< SomeType, MyAllocator<SomeType> > foo;
2. 200 byte dimensione fissa struttura
3. 304 byte struttura dimensione fissa
4. stringhe n byte std::basic_string< char, std::char_traits<char>, MyAllocator<char> > strn;

Devo essere in grado di allocare circa 32 MB totali per ciascuno di questi.

L'allocatore tiene traccia dell'utilizzo della memoria utilizzando un std::map di puntatori alle dimensioni di allocazione. typedef std::map< void*, size_t > SuperBlock; Ogni SuperBlock rappresenta 4MB di memoria.

C'è uno std::vector<SuperBlock> di questi nel caso in cui un SuperBlock non sia abbastanza spazio.

L'algoritmo utilizzato per l'allocatore è questa:

1. Per ogni SuperBlock: C'è spazio alla fine del superblocco? mettere l'assegnazione lì. (veloce)
2. In caso contrario, cercare all'interno di ciascun SuperBlock uno spazio vuoto di dimensioni sufficienti e collocare l'allocazione lì. (lento)
3. Ancora niente? allocare un altro SuperBlock e inserire l'allocazione all'inizio del nuovo SuperBlock.

Sfortunatamente, il passaggio 2 può diventare MOLTO lento dopo un po '. Man mano che le copie degli oggetti vengono create e le variabili temporanee distrutte, ottengo molta frammentazione. Ciò causa molte ricerche approfondite all'interno della struttura della memoria. La frammentazione è in discussione perché ho una quantità limitata di memoria con cui lavorare (vedi nota sotto)

Qualcuno può suggerire miglioramenti a questo algoritmo che velocizzerebbe il processo? Ho bisogno di due algoritmi separati (1 per le allocazioni a dimensione fissa e uno per l'allocatore di stringhe)?

Nota: Per coloro che hanno bisogno di una ragione: sto usando questo algoritmo in Windows Mobile, dove c'è un limite di slot processo di 32MB al mucchio. Quindi, il solito std::allocator non lo taglierà. Devo mettere le allocazioni nell'area di memoria grande da 1 GB per avere spazio sufficiente e questo è ciò che fa.

Answer 1

Per gli oggetti di dimensioni fisse, è possibile creare un allocatore di dimensioni fisse. Fondamentalmente si assegnano blocchi, si partizionano in blocchi secondari della dimensione appropriata e si crea un elenco collegato con il risultato. L'allocazione da tale blocco è O (1) se c'è memoria disponibile (basta rimuovere il primo elemento dall'elenco e restituire un puntatore ad esso) come è deallocation (aggiungi il blocco alla lista libera). Durante l'allocazione, se l'elenco è vuoto, acquisisci un nuovo superblocco, partizione e aggiungi tutti i blocchi nell'elenco.

Per l'elenco di dimensioni variabili, è possibile semplificarlo nel blocco di dimensioni fisse allocando solo blocchi di dimensioni note: 32 byte, 64 byte, 128 byte, 512 byte. Dovrai analizzare l'utilizzo della memoria per trovare i diversi bucket in modo da non sprecare troppa memoria. Per oggetti di grandi dimensioni, è possibile tornare a un modello di allocazione di dimensioni dinamiche, che sarà lento, ma si spera che la quantità di oggetti di grandi dimensioni sia limitata.

Answer 2

È possibile disporre di un pool di allocazione di memoria separato per ogni tipo di dimensione fissa che si sta allocando? In questo modo non ci sarà alcuna frammentazione, perché gli oggetti allocati si allineano sempre sui confini di byte. Ciò non aiuta per le stringhe di lunghezza variabile, ovviamente.

C'è un esempio di allocazione di piccoli oggetti in Alexandrescu Modern C++ design che illustra questo principio e può darvi alcune idee.

Answer 3

Per le dimensioni fisse, è possibile utilizzare facilmente un tipo di allocatore di allocatori di memoria di piccole dimensioni in cui si assegna un blocco grande suddiviso in blocchi di dimensioni fisse. Quindi si crea un vettore di puntatori su blocchi disponibili e pop/push mentre si assegna/libera. Questo è molto veloce.

Per articoli di lunghezza variabile, è più difficile: devi occuparti della ricerca di uno spazio contiguo disponibile o utilizzare un altro approccio. Potresti considerare di mantenere un'altra mappa di tutti i nodi liberi ordinati per dimensione del blocco, in modo da poter ridurre la mappa e se il prossimo nodo disponibile dice solo il 5% di ritorno troppo grande invece di cercare di trovare lo spazio disponibile utilizzabile della dimensione esatta.

Answer 4

La mia inclinazione per elementi di dimensioni variabili sarebbe, se possibile, evitare di tenere puntatori diretti ai dati e conservare invece le maniglie. Ogni handle sarebbe un indice di un superblocco e un indice di un elemento all'interno del superblocco. Ogni superblocco avrebbe una lista articoli allocata dall'alto in basso e gli articoli allocati dal basso verso l'alto. L'allocazione di ogni articolo sarebbe preceduta dalla sua lunghezza e dall'indice dell'elemento che rappresenta; usa un bit dell'indice per indicare se un oggetto è "appuntato".

Se un articolo si adatta dopo l'ultimo elemento assegnato, è sufficiente assegnarlo. Se dovesse colpire un oggetto bloccato, sposta il segno di allocazione successiva oltre l'oggetto appuntato, trova il successivo oggetto appuntato più in alto e prova di nuovo l'allocazione. Se l'oggetto si scontrerà con la lista degli oggetti ma c'è abbastanza spazio libero da qualche parte, compacifichi il contenuto del blocco (se uno o più oggetti sono bloccati, potrebbe essere meglio usare un altro superblocco se ne è disponibile uno). A seconda dei modelli di utilizzo, può essere desiderabile iniziare solo con la compattazione delle cose che sono state aggiunte dall'ultima raccolta; se questo non fornisce abbastanza spazio, allora compacifica tutto.

Ovviamente, se solo si dispone di poche dimensioni discrete di elementi, è possibile utilizzare semplici allocatori di blocchi di dimensioni fisse.

Answer 5

Concordo con Tim: utilizzare i lotti di memoria per evitare la frammentazione.

Tuttavia, è possibile evitare un po 'di sfasamento memorizzando puntatori anziché oggetti nei propri vettori, forse ptr_vector?

Answer 6

Sulla base della risposta di Tim, personalmente utilizzerei qualcosa di simile a BiBOP.

L'idea di base è semplice: utilizzare piscine di dimensioni fisse.

Ci sono alcuni perfezionamenti a questo.

In primo luogo, la dimensione dei pool è generalmente fissa. Dipende dalla routine di allocazione, in genere se si conosce il sistema operativo su cui si lavora sulla mappa almeno 4 KB in una sola volta quando si utilizza malloc, quindi si utilizza tale valore. Per un file mappato in memoria, potresti essere in grado di aumentarlo.

Il vantaggio dei pool di dimensioni fisse è che combatte piacevolmente la frammentazione. Tutte le pagine hanno le stesse dimensioni, è possibile riciclare facilmente una pagina vuota da 256 byte in una pagina da 128-byte.

Esiste ancora una certa frammentazione per oggetti di grandi dimensioni, che in genere vengono allocati all'esterno di questo sistema. Ma è basso, soprattutto se si inseriscono oggetti di grandi dimensioni in un multiplo delle dimensioni della pagina, in questo modo la memoria sarà facile da riciclare.

In secondo luogo, come gestire le piscine? Utilizzo di elenchi collegati.

Le pagine sono tipicamente non tipizzate (da sole), quindi è disponibile una lista di pagine in cui preparare nuove pagine e inserire pagine "riciclate".

Per ciascuna categoria di dimensioni è disponibile un elenco di pagine "occupate", in cui è stata allocata memoria. Per ogni pagina si mantiene:

• la dimensione di allocazione (per questa pagina)
• il numero di oggetti allocati (per verificare la presenza di vuoto)
• un puntatore alla prima cella libera
• un puntatore a la pagina precedente e quella successiva (potrebbe indicare la "testa" dell'elenco)

Ogni cella libera è essa stessa un puntatore (o indice, a seconda della dimensione che si ha) alla successiva cella libera.

L'elenco delle pagine "occupati" di una certa dimensione è semplicemente gestito:

• sulla eliminazione: se si svuota il pagina, quindi rimuoverlo dalla lista e spingerlo nelle pagine riciclati, in caso contrario, aggiorna l'elenco di celle libere di questa pagina (nota: trovare l'inizio della pagina corrente di solito è un'operazione semplice modulo sull'indirizzo)
• all'inserimento: cerca a partire da capo, non appena trovi una pagina non piena , spostalo davanti all'elenco (se non lo è già) e inserisci il tuo articolo

Questo schema è davvero performante in termini di memoria, con solo una singola pagina riservata per l'indicizzazione.

Per applicazioni multi-threaded/multi-processi, è necessario aggiungere la sincronizzazione (un mutex per pagina in genere), nel caso in cui si possa trarre ispirazione da tcmalloc di Google (cercare e trovare un'altra pagina invece di bloccare, utilizzare un cache locale dei thread per ricordare quale pagina hai usato per l'ultima volta).

Detto questo, hai provato Boost.Interprocess? Fornisce allocatori.