Esempi convincenti di allocatori C ++ personalizzati?
https://stackoverflow.com/questions/826569
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quali sono alcuni dei buoni motivi per abbandonare std :: allocator a favore di una soluzione personalizzata? Hai mai incontrato situazioni in cui era assolutamente necessario per correttezza, prestazioni, scalabilità, ecc.? Qualche esempio davvero intelligente?
Gli allocatori personalizzati sono sempre stati una caratteristica della libreria standard di cui non ho avuto molto bisogno. Mi stavo solo chiedendo se qualcuno qui su SO potesse fornire alcuni esempi convincenti per giustificare la sua esistenza.
Soluzione
Come menziono qui , ho visto la STL personalizzata di Intel TBB l'allocatore migliora significativamente le prestazioni di un'app multithread semplicemente cambiando una singola
std::vector<T>
a
std::vector<T,tbb::scalable_allocator<T> >
(questo è un modo rapido e conveniente di commutare l'allocatore per usare gli heap di thread-nifty privati ??di TBB; vedi pagina 7 in questo documento )
Altri suggerimenti
Un'area in cui gli allocatori personalizzati possono essere utili è lo sviluppo del gioco, in particolare sulle console di gioco, in quanto hanno solo una piccola quantità di memoria e nessuno scambio. Su tali sistemi si desidera assicurarsi di avere uno stretto controllo su ciascun sottosistema, in modo che un sistema non critico non possa rubare la memoria da uno critico. Altre cose come gli allocatori di pool possono aiutare a ridurre la frammentazione della memoria. Puoi trovare un lungo documento dettagliato sull'argomento su:
Sto lavorando su un allocatore mmap che consente ai vettori di utilizzare la memoria da un file mappato in memoria. L'obiettivo è quello di avere vettori che utilizzano tale archiviazione sono direttamente nella memoria virtuale mappata da mmap. Il nostro problema è migliora la lettura di file di grandi dimensioni (> 10 GB) in memoria senza copia sovraccarico, quindi ho bisogno di questo allocatore personalizzato.
Finora ho lo scheletro di un allocatore personalizzato (che deriva da std :: allocator), penso che sia un buon inizio punto per scrivere i propri allocatori. Sentiti libero di usare questo codice nel modo che desideri:
#include <memory>
#include <stdio.h>
namespace mmap_allocator_namespace
{
// See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
template <typename T>
class mmap_allocator: public std::allocator<T>
{
public:
typedef size_t size_type;
typedef T* pointer;
typedef const T* const_pointer;
template<typename _Tp1>
struct rebind
{
typedef mmap_allocator<_Tp1> other;
};
pointer allocate(size_type n, const void *hint=0)
{
fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
return std::allocator<T>::allocate(n, hint);
}
void deallocate(pointer p, size_type n)
{
fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
return std::allocator<T>::deallocate(p, n);
}
mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
template <class U>
mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
~mmap_allocator() throw() { }
};
}
Per utilizzare questo, dichiarare un contenitore STL come segue:
using namespace std;
using namespace mmap_allocator_namespace;
vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());
Può essere usato ad esempio per registrare ogni volta che viene allocata la memoria. Cosa è necessario è la struttura di rebind, altrimenti il ??contenitore vettoriale utilizza le superclassi allocate / deallocate metodi.
Aggiornamento: l'allocatore della mappatura della memoria è ora disponibile all'indirizzo https://github.com/johannesthoma/mmap_allocator ed è LGPL. Sentiti libero di usarlo per i tuoi progetti.
Sto lavorando con un motore di archiviazione MySQL che utilizza c ++ per il suo codice. Stiamo utilizzando un allocatore personalizzato per utilizzare il sistema di memoria MySQL anziché competere con MySQL per la memoria. Ci consente di assicurarci di utilizzare la memoria come l'utente ha configurato MySQL per l'uso e non "extra".
Può essere utile utilizzare allocatori personalizzati per utilizzare un pool di memoria anziché l'heap. Questo è un esempio tra molti altri.
Nella maggior parte dei casi, si tratta sicuramente di un'ottimizzazione prematura. Ma può essere molto utile in determinati contesti (dispositivi integrati, giochi, ecc.).
Non ho scritto codice C ++ con un allocatore STL personalizzato, ma posso immaginare un server web scritto in C ++, che utilizza un allocatore personalizzato per l'eliminazione automatica dei dati temporanei necessari per rispondere a una richiesta HTTP. L'allocatore personalizzato può liberare tutti i dati temporanei una volta che la risposta è stata generata.
Un altro possibile caso d'uso per un allocatore personalizzato (che ho usato) è scrivere un unit test per dimostrare che il comportamento di una funzione non dipende da una parte del suo input. L'allocatore personalizzato può riempire l'area di memoria con qualsiasi modello.
Quando si lavora con GPU o altri coprocessori è talvolta utile allocare le strutture di dati nella memoria principale in modo speciale . Questo modo speciale di allocare memoria può essere implementato in modo conveniente in un allocatore personalizzato.
Il motivo per cui l'allocazione personalizzata tramite il runtime dell'acceleratore può essere utile quando si utilizzano gli acceleratori è il seguente:
- tramite allocazione personalizzata il runtime dell'acceleratore o il driver vengono informati del blocco di memoria
- inoltre il sistema operativo può assicurarsi che il blocco di memoria allocato sia bloccato nella pagina (alcuni chiamano questa memoria appuntata ), cioè il sottosistema di memoria virtuale del sistema operativo potrebbe non muoversi o rimuovere la pagina all'interno o dalla memoria
- se 1. e 2. hold e viene richiesto un trasferimento di dati tra un blocco di memoria bloccato in una pagina e un acceleratore, il runtime può accedere direttamente ai dati nella memoria principale poiché sa dove si trova e può essere sicuro del funzionamento il sistema non lo ha spostato / rimosso
- questo salva una copia della memoria che si verificherebbe con la memoria allocata in modo non bloccato: i dati devono essere copiati nella memoria principale in un'area di gestione temporanea bloccata da pagina con l'acceleratore in grado di inizializzare il trasferimento dei dati (tramite DMA)
Sto usando allocatori personalizzati qui; potresti persino dire che avrebbe funzionato in giro altra gestione dinamica della memoria personalizzata.
Background: abbiamo sovraccarichi per malloc, calloc, free e le varie varianti dell'operatore new ed delete, e il linker fa felicemente che STL li usi per noi. Questo ci consente di eseguire operazioni come pooling automatico di piccoli oggetti, rilevamento perdite, riempimento allocazione, riempimento gratuito, allocazione di riempimento con sentinelle, allineamento della cache-line per determinati allocati e ritardo gratuito.
Il problema è che stiamo funzionando in un ambiente incorporato - non c'è abbastanza memoria in giro per fare correttamente la contabilità del rilevamento delle perdite per un lungo periodo. Almeno, non nella RAM standard: c'è un altro mucchio di RAM disponibile altrove, attraverso le funzioni di allocazione personalizzate.
Soluzione: scrivere un allocatore personalizzato che utilizza l'heap esteso e utilizzarlo solo all'interno dell'architettura di tracciamento delle perdite di memoria ... Tutto il resto viene impostato sui normali sovraccarichi nuovi / eliminati che presentano tracciamento delle perdite. Questo evita il tracciamento del tracker stesso (e fornisce anche un po 'di funzionalità di imballaggio extra, conosciamo le dimensioni dei nodi del tracker).
Lo usiamo anche per conservare i dati di profilazione dei costi delle funzioni, per lo stesso motivo; scrivere una voce per ogni chiamata di funzione e ritorno, così come gli interruttori di thread, può diventare costoso velocemente. L'allocatore personalizzato ci fornisce di nuovo allocati più piccoli in un'area di memoria di debug più ampia.
Sto usando un allocatore personalizzato per contare il numero di allocazioni / deallocazioni in una parte del mio programma e misurare quanto tempo impiega. Ci sono altri modi per raggiungere questo obiettivo, ma questo metodo è molto conveniente per me. È particolarmente utile poter utilizzare l'allocatore personalizzato solo per un sottoinsieme dei miei contenitori.
Una situazione essenziale: quando si scrive codice che deve funzionare oltre i limiti del modulo (EXE / DLL), è essenziale mantenere le allocazioni e le eliminazioni in un solo modulo.
Dove mi sono imbattuto in questa era un'architettura Plugin su Windows. È essenziale, ad esempio, se si passa una stringa std :: string attraverso il limite della DLL, che qualsiasi riallocazione della stringa si verifichi dall'heap da cui proviene, NON dall'heap nella DLL che potrebbe essere diverso *.
* In realtà è più complicato di così, come se si stesse collegando dinamicamente al CRT questo potrebbe funzionare comunque. Ma se ogni DLL ha un collegamento statico al CRT, ti stai dirigendo verso un mondo di dolore, in cui si verificano continuamente errori di allocazione fantasma.
Un esempio di I time che ho usato questi stava lavorando con sistemi embedded molto limitati dalle risorse. Diciamo che hai 2k di RAM libera e che il tuo programma deve usare un po 'di quella memoria. Devi archiviare diciamo 4-5 sequenze da qualche parte che non sono nello stack e inoltre devi avere un accesso molto preciso su dove vengono archiviate queste cose, questa è una situazione in cui potresti voler scrivere il tuo allocatore. Le implementazioni predefinite possono frammentare la memoria, questo potrebbe essere inaccettabile se non si dispone di memoria sufficiente e non è possibile riavviare il programma.
Un progetto a cui stavo lavorando era l'utilizzo di AVR-GCC su alcuni chip a bassa potenza. Abbiamo dovuto memorizzare 8 sequenze di lunghezza variabile ma con un massimo noto. La l'implementazione standard della libreria della gestione della memoria è un involucro sottile malloc / free che tiene traccia di dove posizionare gli oggetti anteponendo ogni blocco allocato di memoria con un puntatore appena oltre la fine di quel pezzo di memoria allocato. Quando si alloca un nuovo pezzo di memoria, l'allocatore standard deve camminare su ciascuno dei pezzi di memoria per trovare il blocco successivo disponibile dove si adatterà la dimensione della memoria richiesta. Su una piattaforma desktop questo sarebbe molto veloce per questi pochi elementi, ma devi tenere presente che alcuni di questi microcontrollori sono molto lenti e primitivi in ??confronto. Inoltre, il problema della frammentazione della memoria era un problema enorme che significava che non avevamo altra scelta che adottare un approccio diverso.
Quindi quello che abbiamo fatto è stato implementare il nostro pool di memoria . Ogni blocco di memoria era abbastanza grande da adattarsi alla sequenza più grande di cui avremmo bisogno. Questo ha assegnato in anticipo blocchi di memoria di dimensioni fisse e contrassegnato quali blocchi di memoria erano attualmente in uso. Lo abbiamo fatto mantenendo un numero intero a 8 bit dove ogni bit rappresentava se veniva usato un certo blocco. Abbiamo scambiato l'utilizzo della memoria qui per tentare di rendere l'intero processo più veloce, il che nel nostro caso era giustificato mentre spingevamo questo chip microcontrollore vicino alla sua massima capacità di elaborazione.
Altre volte vedo scrivere il proprio allocatore personalizzato nel contesto dei sistemi embedded, ad esempio se la memoria per la sequenza non è nella RAM principale come spesso accade in queste piattaforme .
Per la memoria condivisa è fondamentale che non solo la testa del contenitore, ma anche i dati in essa contenuti siano archiviati nella memoria condivisa.
L'allocatore di Boost :: Interprocess è un buon esempio. Tuttavia, come puoi leggere qui questo allone non è sufficiente, per rendere compatibili tutti i contenitori STL della memoria condivisa (a causa dei diversi offset di mappatura in diversi processi, i puntatori potrebbero "rompere").
Link obbligatorio alla conferenza CppCon 2015 di Andrei Alexandrescu sugli allocatori:
https://www.youtube.com/watch?v=LIb3L4vKZ7U
La cosa bella è che il solo inventarli ti fa venire in mente idee su come le useresti :-)
Qualche tempo fa ho trovato questa soluzione molto utile per me: Allocatore C ++ 11 veloce per contenitori STL . Accelera leggermente i contenitori STL su VS2017 (~ 5x) e su GCC (~ 7x). È un allocatore per scopi speciali basato sul pool di memoria. Può essere utilizzato con i contenitori STL solo grazie al meccanismo richiesto.
Uso personalmente Loki :: Allocator / SmallObject per ottimizzare l'utilizzo della memoria per piccoli oggetti & # 8212; mostra una buona efficienza e prestazioni soddisfacenti se devi lavorare con quantità moderate di oggetti veramente piccoli (da 1 a 256 byte). Può essere fino a ~ 30 volte più efficiente dell'allocazione new / delete C ++ standard se parliamo di allocazione di quantità moderate di piccoli oggetti di dimensioni diverse. Inoltre, esiste una soluzione specifica per VC chiamata "QuickHeap", che offre le migliori prestazioni possibili (allocare e deallocare le operazioni basta leggere e scrivere l'indirizzo del blocco che viene allocato / restituito all'heap, rispettivamente fino a 99. (9)% casi & # 8212; dipende dalle impostazioni e dall'inizializzazione), ma a un costo di un notevole sovraccarico & # 8212; ha bisogno di due puntatori per estensione e uno in più per ogni nuovo blocco di memoria. È una soluzione il più veloce possibile per lavorare con enormi (10 000 ++) quantità di oggetti creati ed eliminati se non hai bisogno di una grande varietà di dimensioni degli oggetti (crea un singolo pool per ogni dimensione degli oggetti, da 1 a 1023 byte nell'attuale implementazione, quindi i costi di inizializzazione possono sminuire l'incremento complessivo delle prestazioni, ma si può andare avanti e allocare / deallocare alcuni oggetti fittizi prima che l'applicazione entri nelle sue fasi critiche per le prestazioni.
Il problema con l'implementazione new / delete standard di C ++ è che di solito è solo un wrapper per allocazione C malloc / free e funziona bene per blocchi di memoria più grandi, come 1024+ byte. Ha un notevole sovraccarico in termini di prestazioni e, a volte, memoria aggiuntiva utilizzata anche per la mappatura. Pertanto, nella maggior parte dei casi gli allocatori personalizzati sono implementati in modo da massimizzare le prestazioni e / o minimizzare la quantità di memoria aggiuntiva necessaria per allocare piccoli oggetti (& # 8804; 1024 byte).
In una simulazione grafica, ho visto allocatori personalizzati utilizzati per
- Vincoli di allineamento che
std :: allocatornon supportava direttamente. - Riduzione al minimo della frammentazione utilizzando pool separati per allocazioni di breve durata (solo questo frame) e di lunga durata.
