std :: unordered_map utilizzo memoria molto elevato

Question

Ieri ho provato a utilizzare unordered_map e questo codice mi ha confuso la quantità di memoria utilizzata.

typedef list<string> entityId_list; 
struct tile_content { 
    char cost; 
    entityId_list entities; 
}; 
unordered_map<int, tile_content> hash_map; 

for (size_t i = 0; i < 19200; i++) { 
    tile_content t; 
    t.cost = 1; 
    map[i] = t; 
} 

Tutte queste parti di codice sono state compilate in MS VS2010 in modalità di debug. Quello che ho visto nel mio task manager era circa 1200 kb di processo "pulito", ma dopo aver riempito hash_map usa 8124 kb di memoria. È normale comportamento di unordered_map? Perché viene utilizzata così tanta memoria?

Answer 1

La struttura unordered_map è progettata per contenere un numero elevato di oggetti in un modo che renda efficienti, eliminazioni, ricerche e attraversamenti senza ordine. Non è pensato per essere efficiente in termini di memoria per piccole strutture di dati. Per evitare le penalità associate al ridimensionamento, alloca molte teste di catena hash quando viene creato per la prima volta.

Answer 2

Ciò non significa necessariamente che la mappa hash utilizzi tanta memoria, ma che il processo abbia richiesto molta memoria dal sistema operativo.

Questa memoria viene quindi utilizzata per soddisfare le richieste malloc/nuove del programma. Alcuni (o la maggior parte, non sono sicuro di questo) allocatori di memoria richiedono più memoria dal sistema operativo del necessario in quel momento per l'efficienza.

Per sapere quanta memoria viene utilizzata da unordered_map, utilizzerei un profiler di memoria come perftools.

Answer 3

Questo è circa 6 MB per oggetti ~ 20k, quindi 300 byte per oggetto. Dato che la tabella hash può essere dimensionata per avere più volte più bucket rispetto alle voci correnti, ogni bucket può essere esso stesso un puntatore a un elenco o vettore di oggetti in collisione, ogni allocazione dell'heap coinvolta in tutto questo è stata probabilmente arrotondata al più vicino potenza di due, e hai il debug su cui può generare qualche gonfiamento extra, tutto sembra giusto per me.

In ogni caso, non si otterrà comprensione per la memoria o l'efficienza della CPU di qualsiasi cosa nella compilazione di debug ;-P. Microsoft può iniettare qualsiasi slop a loro piace, e l'utente non ha diritto alle aspettative riguardo alle prestazioni. Se trovi che è male in una build ottimizzata, allora hai qualcosa di cui parlare.

Più in generale, il modo in cui è scalabile con size() è molto importante, ma è del tutto legittimo chiedersi come un programma andrebbe con un numero enorme di mappe non ordinate relativamente piccole. Vale la pena notare che al di sotto di un certo size() anche le ricerche di forza bruta in un vettore, le ricerche binarie in un vettore ordinato, o un albero binario possono out-performare una mappa non ordinata, oltre ad essere più efficiente in termini di memoria.