std :: Assegnazione di allocatori standard di mappatura contro allocatore di blocchi

Question

Ho letto su un ricettario di ottimizzazione C++ che l'allocatore standard per i contenitori STL come std :: list, std :: set, std :: multi_set, std :: map , e std :: multi_map può essere sostituito da un più performante allocatore di blocchi.

Un allocatore di blocchi ha prestazioni più elevate, bassa frammentazione e memorizzazione efficiente dei dati.

Ho trovato sul web l'FSBAllocator che afferma di essere più veloce dello standard. http://warp.povusers.org/FSBAllocator/

ho provato con std :: map e abbiamo trovato l'sembra essere più veloce in effetti, ma la mia domanda è come può essere l'implementazione STL essere così più lento di un allocatore specifico e quali sono gli svantaggi di un altro allocatore rispetto allo standard, in termini di portabilità e robustezza? Il mio codice deve essere compilato su una varietà di architetture (win32, osx, linux). Qualcuno ha esperienza con questo tipo di allocatore di blocchi di dimensione fissa?

Answer 1

Un allocatore di blocchi esegue una grande allocazione nell'archivio/heap liberi, quindi suddivide internamente questa memoria in blocchi. Uno svantaggio qui è che alloca questo chunk (che deve essere grande, e spesso specificato dall'utente a seconda dei casi) dritto, quindi anche se non lo si usa tutto, quella memoria è legata. In secondo luogo, l'allocatore di memoria standard è costruito su new/delete, che a sua volta è spesso costruito sopra malloc/free. Anche se non ricordo se malloc/free è garantito come thread safe in tutte le circostanze, di solito lo è.

Ma infine il motivo per cui i block allocator funzionano così bene è perché hanno informazioni che non sono presenti agli allocatori standard, e non hanno bisogno di coprire un insieme molto ampio di casi d'uso. Ad esempio, se hai fatto std::map< int, int >() e ha assegnato 1 MB, probabilmente saresti incazzato, ma se lo fai std::map< int, int, std::less<int>, block_alloc< 1024 * 1024 > >() ti aspetteresti. Gli allocatori standard non allocano in blocchi, richiedono nuova memoria tramite nuovi, a loro volta non hanno alcun contesto. Ottiene una richiesta di memoria di una dimensione arbitraria e deve trovare un numero contiguo di byte da restituire. Ciò che la maggior parte delle implementazioni fa è che hanno un insieme di aree di memoria che mantengono di multipli diversi (ad esempio, una regione per 4 byte è probabilmente più o meno garantita per essere presente, poiché le richieste per 4 byte sono molto comuni). Se una richiesta non è uniforme, diventa più difficile restituire una buona fetta senza sprecare spazio e causare la frammentazione. In sostanza la gestione della memoria di dimensioni arbitrarie è molto molto difficile da fare se si vuole che sia vicino alla costante di tempo, a basso frammentazione, thread-safe ecc

La documentazione Boost pool allocator ha alcune utili informazioni su come un buon blocco allocatore può funzionare.